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 :gruebel: ). 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.

Delphi-Quellcode:

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

[Gruber_Hans_12345]

ja danke, habe das system von simplex schon verstanden (zumindest, was ich als ausgangsbasis habe, und was ich dann bekomme)

und da ist nun mein problem, ich brauche ja für das simplex verfahren eine reihe von gleichungen, die ich dann als matrizen verwenden kann.
nur wüsste ich nicht, wie ich aus meiner ausgangsbasis gleichungen erstellen soll?

mit dem pascal code kann ich das simplex verfahren auf jeden fall schon mal verwenden ...

wenn mir da jemand tipps geben kann, wie man da ne gleichung drausmacht - ich bin mir da extrem unsicher, ob man mein problem so wie es ist in gleichungen formen kann ... ? :spin2:

[ConstantGardener]

@mschaefer : wenn auch noch begrenzte Lagerkapazitäten eine Rolle spielen (bzw. Kosten für zusätzliche Lagerkapazitäten, Mindestbestände usw.) wird's mit der Simplex Methode aber eng oder ?

[grenzgaenger]

hallo gardener,

mal so dahergefragt, die Andler'sche Formel ist dir schon bekannt??? andler formel

ausserdem würd ich mir mal die ABC und XYZ analyse näher angucken... denke, die sind die voraussetzung, um überhaupt die obige formel anwenden zu können...

die optimierungsmethoden, scheinen mir auch zu weit hergeholt, wobei einige sogar recht fraglich sind... wie z.b. die lineare programmierung oder der symplex.. (spezialfall der linearen progr.). da ist die andlerformel auch nicht schlechter ... :???:

[ConstantGardener]

@grenzgänger : ich bin noch ziemlich am Anfang der Recherche für dieses Problem. Die von Dir genannten Formeln kannte ich noch nicht. Nach kurzen überfliegen in Wikipedia halte ich die Andler Formel usw. für mein Problem aber zu unflexibel. :( Übrigens ist das hier nicht mein Thread. :???:

[Mackhack]

Wird da normalerweise nicht das Bestellpunktverfahren oder das Bestellrhythmusverfahren angewandt? Zumindest hab ich das als Kaufmann mal gelernt!

[QuickAndDirty]

Ich dachte auch das Problem wäre einfach das Kaufmänische Problem
"Optimale Bestellmenge"
Also Brute Force alle Möglichkeiten miteinander Vergleichen....neeeee

Simplex funktioniert ja auch für Optimierungsprobleme wenn die Zahl der
Variablen groß ist. In so fern ist IMHO Simplex schon der richtige weg.

[Gruber_Hans_12345]

@grenzgaenger
also hab mir mal die Andler Formel angeschaut, die passt bei meinem problem gar nicht, die geht ja von einem fixen stetigen lagerabgang aus, und das ist bei mir ja nicht der fall, bzw. ich kenne ja den genauen (bzw. fast genauen) lagerabgang.

aber so weit ich mich jetzt eingelesen haben in simplex und co. kann ich mein problem nicht lösen damit, da es nicht möglich ist das problem in formeln zu fassen.
da muß ich mir irgend was anderes einfallen lassen ... :(

[mschaefer]

Moin, moin,

Zitat:

Zitat von ConstantGardener

@mschaefer : wenn auch noch begrenzte Lagerkapazitäten eine Rolle spielen (bzw. Kosten für zusätzliche Lagerkapazitäten, Mindestbestände usw.) wird's mit der Simplex Methode aber eng oder ?

Gerade um so was einzubauen ist der Simplex-Algorithmus gut geeignet. Es gibt da etliche Erweiterungen im Matrizenaufbau um sowas zu konsturieren. Allerdings befürchte ich, dass ich hier kein halbes Jahr Vorlesungen zusammenfassen kann.

Die Grenzen von Simplex liegen überall da wo die Linearität von Verfahren nicht mehr besteht. Bei Lager sind oft die Einmodellierung von Klimaeinflüssen so eine Sache, also wenn Produkthaltbarkeit betroffen ist.

Grüße // Martin

[Gruber_Hans_12345]

hmmm, werde mir das simplex verfahren noch mal durchlesen, und hoffentlich geht mir dann ein licht auf, wie ich mein problem formularen kann ;)

ich habe auf jeden fall mal die kosten in matizenform zusammen geschrieben

Code:

Lagerkosten                 Bestellkosten               Gesamtkosten                    
    1   2   3   4   5           1   2   3   4   5           1   2   3   4   5
1   0   1   4   7   9       1   9   13  21  28  29      1   9   14  25  35  38
2   0   0   2   5   7       2   0   5   13  21  23      2   0   5   15  26  30
3   0   0   0   1   3       3   0   0   9   18  20      3   0   0   9   19  23
4   0   0   0   0   2       4   0   0   0   10  13      4   0   0   0   10  15
5   0   0   0   0   0       5   0   0   0   0   3       5   0   0   0   0   3

wobei ich nur die letzte (Gesamtkosten) brauche ...

jetzt müsste ich nur wissen, wie ich von der matrix zu meiner lösung komme :)

[ConstantGardener]

Hallo zusammen,

@mschaefer : Danke für die Info, ich werde mir den SIMPLEX nochmal näher ansehen. Vom Gefühl her komm ich da aber nicht so wirklich weit da unser Problem recht komplex und nicht kontinuierlich ist. Wir haben keine kontinuierlichen Materialflüsse, der Absatz ist stark saisonal geprägt, sehr begrenzte Haltbarkeit usw. Aber schaun wir mal....

[grenzgaenger]

wenn ihr euch schon ohne grundlagen der materie (hier: beschaffungslogistik und OR) mit OR beschäftigen wollt, dann aber mit dem richtigen teilgebiet. an euerer stelle würd ich mir mal die dynamische programmierung ansehen... die könnt ggf. weiterhelfen...

PS: meine meinung zu LP und dem spzialfall symplex, für euere anforderungen, ist das ganze nicht mächtig genug ... --> vergebene liebesmüh...

dennoch, noch viel glück und erfolg

PPS: der andler gibt die optimale losgrösse, unter ggf. bedingungen an, in welcher auch variablen wie lagerzinssatz, etc. einbezogen werden. er wird in der beschaffungs- wie auch in der produktionslogistik angewand, also logistik allgemein. er gehört zum grundlagenwerk eines jeden logistikers... ist also so viel wie der hammer für den mauerer .. :-) ebenso, zu den absoluten grundlagenwerk gehören die ABC und die XYZ analyse... aber die kennt ihr sicher in- und auswendig... :-)

[Gruber_Hans_12345]

Also irgendwie habe ich das gefühl, das ihr alle hier von was anderem redet aber nicht über dieses thema hier?

habe mir die ABC/XYZ Analyse mal angedchaut, die hat ja mal absolut nix mit der Frage dieses Threads zu tun

[ibp]

ich werf mal einen anderen lösungsansatz in die runde...
Rucksack-Problem

Zitat:

Zitat von Wikipedia

Das Rucksackproblem (oft mit RUCKSACK, KNAPSACK bezeichnet) ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzenwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzenwert der ausgewählten Objekte maximiert werden

[Mackhack]

Zitat:

Zitat von Gruber_Hans_12345

Also irgendwie habe ich das gefühl, das ihr alle hier von was anderem redet aber nicht über dieses thema hier?

habe mir die ABC/XYZ Analyse mal angedchaut, die hat ja mal absolut nix mit der Frage dieses Threads zu tun

Hast du dir auch mal angesehen was ich dir vorgeschlagen habe nachzulesen? Denn das ist im Prinzip genau das was du brauchst um die Optimale (Menge wie Kosten) Bestellmenge herauszufinden.

[Gruber_Hans_12345]

Zitat:

Zitat von Mackhack

Zitat:

Zitat von Gruber_Hans_12345

Also irgendwie habe ich das gefühl, das ihr alle hier von was anderem redet aber nicht über dieses thema hier?

habe mir die ABC/XYZ Analyse mal angedchaut, die hat ja mal absolut nix mit der Frage dieses Threads zu tun

Hast du dir auch mal angesehen was ich dir vorgeschlagen habe nachzulesen? Denn das ist im Prinzip genau das was du brauchst um die Optimale (Menge wie Kosten) Bestellmenge herauszufinden.

ja habe ich mir angeschaut, sind zwar interessante themen aber haben leider nix mit meiner frage zu tun.
in diesen themen wird behandelt, wie man die optimalen Lagerkonstatnten ausrechnet, aber ich habe schon für zb 50 wochen die fixen lagerabrufe, die sich nicht mehr (oder nur ganz minimal ändern) und nun muß ich ausrechnen, oder schätzen, wie ich am besten bestelle. Also, die Lagerabrufe sind schon alle im Vorfeld bekannt, und ich muß NUR noch die ideale Bestellmenge finden, um die Lagerkosten zu minimieren.

das rucksack problem, geht schon am ehesten in diese richtung, allerdings leider auch nicht praktikabel ... bin derzeit am inforamtionen zusammentragen in richtung Tiefensuche/Breitensuche ... das sieht auch sehr vielversprechend aus ...

[grenzgaenger]

das kannste doch mit dem andler prima berechnen... wo liegt das problem?

[Gruber_Hans_12345]

Zitat:

Zitat von grenzgaenger

das kannste doch mit dem andler prima berechnen... wo liegt das problem?

und wie?

Zitat:

Zitat von wikipedia

Das klassische Losgrößenmodell hat eine grundlegende Prämisse (wie z.B. konstante Abgangsrate vom Lager), die in der Realität nicht oder nur sehr selten anzutreffen sind. Die Andler-Formel hat eher Lehrbuchcharakter als einen praktischen Nutzen

also da steht konstante Abgangsraten vom Lager - ich habe hier zwar vordefinierte aber ganz und gar nicht konstante abgangsraten vom lager - also wüsste ich nicht, wie mir da die andler formel helfen sollte

[mschaefer]

Moin, moin,

Auf das vorliegende Problem passt die Andlerformel nun nicht, dass sollte inzwischen geklärt sein. Mit den gegebenen Informationen handelt es sich bisher auch nur um lineare Beziehungen, von daher kann man mit LP-Matrizen arbeiten. Allerdings fehlen für die Aufstellung einer zu rechnenden Matrix weitere Informationen.



Bisher würde ein Algorithmus mit den obigen Tabellen einfach folgendes machen:
Minimiere die Kosten -> Bestelle nichts und Lager nichts.

1. Es fehlen die Beiträge / Gewinnspanne der Verfahren / Produkte
___ oft bezeichnet als c1, ..., cx

2. Es fehlen die Grenzen der anzufordernden Ressourcen. Hier ist insbesondere die Lagerkapazität zu nennen
___ oft bezeichnet als b1, ..., bx

3. Vorhanden sind Restiktionskoeffizienten (Ansprüche der Verfahren in Form von Kosten).
___ oft bezeichnet als a1, ..., ax

Letzlich geht es ja darum die Mischung aus Bestellmenge und Lagermenge zu ermitteln:
Also bei einer Mischung aus Bestellung und Lager wird erst das Lager über die zur Verfügung stehenden Zeit ausgelastet.
Dabei kann das Lager in verschiedenen Wochen unterschiedliche Kosten haben. Eventuell hat man auch verschiednen Lagertypen,
Aussenlager usw. zur Verfügung. Oder Produkte mit höheren Gewinnspannen knapsen sich etwas vom Lager ab...



Was die Fragestellung des Thread´s angeht, Suche nach einem Algorithmus, würde ich mit dem Simplex anfangen, er ist sicherlich nicht der Weisheit letzter Schluss, aber einfach zu implementieren.

Da das Problem aber im wesentlichen bisher die Matrizen sind neige ich zur Empfehlung ein fertiges Programm zu verwenden oder ein Blick auf den Online-Simples-Instructor zu werden.

Grüße // Martin