Algorithmus zum Optimieren

[Gruber_Hans_12345]

Hi

ich bin gerade auf der suche nach einem Algorithmus, um zb einen einkaufsprozess zu automatisieren ...

es geht darum, das ich ausrechnen (bzw. probieren) möchte, wie es am besten ist zu bestellen
wenn ich zu oft bestelle, dann muß ich jedes mal porto zahlen, und auch die artikel sind teuerer
wenn ich die bestellungen zusammenfasse, dann sind die artikel billiger (größere stückzahl) und ich zahle nur einmal porto, aber ich fülle mir mein lager an, und habe auch ein paar Euros im lager liegen.

habe mal soweit das ganze definiert, das ich es in kosten verfassen kann

Delphi-Quellcode:

function GetLagerKosten(Menge, Dauer) : currency;  // Berechnet wieviel es kostet, wenn ich Menge Artikel für Dauer auf dem Lager liegen haben
function GetBestellKosten(Menge) : currency; // Berechnet wieviel die Menge Teile Kosten (inklusiv aller Nebenkosten)

nun habe ich zb.: 20 Bedarfsmeldungen, mit verschiedenen Mengen zu einem jeweils verschiedenen Datum

ich kann mir jetzt die gesamten Kosten ausrechnen, aber wie kann ich jetzt das ganze optimieren, muß man bei sowas immer alle Kombinationen ausrechnen?

Kann mir jemand Tipps geben - bzw. auch mal Tipps nach was ich da suchen kann?

[ConstantGardener]

Hallo Hans,

ein möglicher Ansatzpunkt für dich wären evtl. GENETISCHE ALGORITHMEN, MONTE CARLO METHODEN usw. Es sollten sich Beispielimplementierungen (nicht unbedingt in Pascal) im Netz finden lassen.

Gruß Andreas

[marabu]

Hallo Hans,

deine Fragestellung fällt in das Gebiet Operations Research. Für eine Suche eignen sich die Schlagwörter "Optimierung Beschaffung Lager Fehlmengen". Ein für dich vielleicht interessantes Skript vom diesjährigen Sommersemester der Uni Postdam findest du neben anderen hier: klick

Grüße vom marabu

[Gruber_Hans_12345]

hi

danke mal für die antworten, also der link von dem skriptum klingt ja sehr interessant, ich hoffe nur, das ich wenigstens etwas von dem skriptum verstehe ... in der theorie sieht das immer so unübersichtlich aus

@ConstantGardener
wie meinst das mit der Monte Carlo Methode? Ich weiss zwar ungefähr was die tut, und zu was man die braucht, aber hätte die jetzt nicht unbedingt für meinen Lösungsansatz verwendet.

Meine große Frage ist ja eigentlich noch diese, ich kann es ja 100% berechnen, welcher Weg am besten ist (da ich eigetnlich keinerlei wahrscheinlichgkeiten drinnen habe) - aber muß ich da dann wirklich immer alle möglichkeiten berechnen, oder kann ich da dann bestimmte wege bzw. bestimmte zweige ausschließen?

[ConstantGardener]

Hallo Hans,

die MONTE CARLO Methode ist vielleicht nicht der optimale Ansatz für dein Problem (Marabu hatte mit Operation Research usw. die richtigen/besseren Vokabeln parat).

Vom Grundprinzip her hast Du aber natürlich durch die Verwendung eines Genetischen Algorithmus eine Möglichkeit die Suche zu beschleunigen da Du nicht alle Lösungen betrachtest. Der Nachteil den man sich hier erkauft ist aber, daß man nur eine Lösung nahe am globalen Optimum findet und nicht unbedingt die wirklich beste Lösung. Ich bin gerade auch am planen solch eines Algorithmus für Liefermengen/Lagerhaltung/Liquidität usw. Je mehr beeinflussende Faktoren Du be(tr)achten mußt je interessanter werden die Evolutionsalgos denke ich (in meinem begrenztem Gärtnerhirn ). Hagen (aka negaH) kann da bestimmt Bücher drüber schreiben !!?

Gruß Andreas

[mschaefer]

Die Einzelfälle müssen jeweils in ihren Verfahren zusammengestellt werden, dabei muss die Verdienstmöglichkeit
pro einer Einheit Produkt angegeben. Die Mengen an verbrauchten Kapaziäten müssen jeweisl auch mit Kosten pro Kapazität angegeben sein. Die Kombination der Verfahren würde ich mit "linearer Optimierung" Link angehen.

Grüße // Martin

PS; Die Internetseite ist wirklich gut gemacht.

[Gruber_Hans_12345]

danke für den link, das progi sieht ja schon mal gut aus (gibt leider keinen source )

aber ganz habe ich das noch nicht geschallt, wie mir das helfen soll, - muß ich dafür nicht sowieso alle möglichkeiten ausprobieren und in variablen bzw. matrizen schreiben damit ich sowas verwenden kann? (und sobald ich alle möglichkeiten ausrechen, habe ich dann ja schon das ergebnis)

so würde zb ein kleines Beispiel aussehen (wobei das in echtdaten dann bis zu 100 einträge sein werden)

Code:

KW   Menge   Durchlauf1 Durchlauf2 Durhclauf3 Durchlauf4
             BE  LA     BE  LA     BE  LA     BE  LA
2    100     100 0      180 0      270 0      100 0
4    100     100 0      0   10     0   10     180 0
26   100     100 0      100 0      0   200    0   170
Summe        300        290        480        450

BE sind die Bestellkosten
LA sind die Lagerkosten
In diesem Fall würde der Durchlauf 2 die besten Werte zurückliefern

[negaH]

Also der Vorschlag mal mein DWAG Tree auszuprobieren ist schon richtig.

Besonderst die Suche nach allen möglichen Kombination von Wörtern die man aus einem Set aus Buchstaben zusammenbauen kann, also das Scrable Problem, ist damit sehr effizient zu machen. Besser als genetische Algorithmen usw. Das hat auch einen einfachen Grund. Während man bei solchen Verfahren quasi sinnlose Wörter zusammenbaut und erst dann überprüft ob dieses Wort einen Sinn ergibt, per Datenbank, werden bei der kombinatorischen Suche in meinem DWAG von vornherein nur Wörter gesucht die auch wirklich korrekt sind. Dh. das DWAG als Wörterbuch mit korrekten Wörtern ist auch die Basis bei der Kombinatorischen Suche nach sinnvollen Wörtern aus einem Set von Buchstaben. Die kombinatorische Suche probiert also niemals Wörter aus die garnicht mit dem Set an Buchstaben nicht erzeugbar sind. Dies reduziert den Suchraum der kombinatorik auf das absolute Minimum, bzw. auf exakt den Suchraum der exakt so groß ist wie die Anzahl alle gültigen Wörter die man erzeugen kann und im DWAG gespeichert wurden. Das DWAG ist damit 1000'ende male schneller und effizienter als vergleichbare Algorithmen. Das hat aber auch seinen Preis: ein DWAG ist exakt nur dafür konstruiert als Algorithmus, als eine Wörterbuch-Engine. Genetische Algorithmen, Eveolutions Strategien und Neuronale Netzwerke können für ganz andere Probleme adaptiert werden.

Gruß Hagen

http://www.michael-puff.de/Developer...agen_Reddmann/ hier kannst du den Source meines DWAGs samt deutscher Wortdatenbank downloaden.

function SearchCombinatoric(const Pattern: String; Found: TDawg; MinLength: Integer = 2): Boolean; ist die Methode die du benutzen müsstest.

[edit]
Shit jetzt habe ich doch tatsächlich im falschen Thread geantwortet, sorry
[/edit]

[Gruber_Hans_12345]

na, vielleicht funkt das auch bei meinem problem, werde mal den gärtner aufsuchen, und einen baum besorgen

[mschaefer]

Etwa Einlesen muß man sich da schon Simplex bei Wikipedia
und das braucht sicherlich seine Zeit. Lineare Optimierung ist zwar nicht der Weisheit letzter Schluss, aber es läßt sich schon einges damit machen. Für kleinere Matrizen geht auch der Excel-Solver, eigentlich ein kombinatorisches Newton-Verfahren, aber erspart halt das Programmieren, Optimieren mit Excel. Eine Delphi - Komponente ist mir derzeit nicht bekannt. Hatte sowas zwar mal angefangen, aber der Code braucht noch deutlich Räumung bis zur Offenlegung. Viele Quellcodes gibt ea aber in Pascal, wie zum Beispiel

Simplex-Verfahren in Pascal

Grüße // Martin