Transportproblem, aber anders |
| 10.06.2011, 17:11 | gabriel56 | Auf diesen Beitrag antworten » | ||
| Transportproblem, aber anders Ich habe ein Lager, welches von der Filialen mehrere Artikel mit bestimmten Mengen zurückholen soll. Es ist nicht garantiert, dass jeder Artikel auf einmal geholt werden kann (keine der Filialen hat gewünschte Menge) oder dass er überhaupt komplett geholt werden kann (dann muss die höchstmögliche Menge geholt werden). Ein Beispiel: Lager braucht vom Artikel A 5 Stück, B 10 Stück, C 8 Stück. Filialen haben: 1: A 3 Stück, B 5 Stück, C 0 Stück, 2: A 3 Stück, B 10 Stück, C 12 Stück, 3: A 5 Stück, B 8 Stück, C 9 Stück. Gegeben sind auch Transportkosten für jede Filiale. Aufgabe: Mengen von jedem Artikel und jeder Filiale berechnen, die transportiert werden müssen, damit die Kosten minimal sind. Meine Ideen: Meine erste Idee war, die Filialen absteigend nach maximalen Abgabemengen zu sortieren. Dann von oben gehen und die Mengen zuteilen, bis nichts mehr zu holen ist, oder Lager genug hat. Diese Lösung berücksichtgt keine Kosten, versucht aber möglichst viele Artikel aus einer Filiale zu holen. Zweite Idee: Transportproblem, ich habe aber nur einen Empfänger, dafür aber mehrere Artikel. Ich kann die Randbedingungen dafür nicht schreiben. |
||||
| 11.06.2011, 13:41 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Transportproblem, aber anders
Hallo, starte zB mit 9 Variablen (Skizze machen), mit denen beschrieben wird, wieviel von welchem Lager wohin transportiert wird. Die Zielfunktion beschreibt dann eine Kostenminimierung. Abakus 
|
||||
| 14.06.2011, 16:45 | gabriel | Auf diesen Beitrag antworten » | ||
Ich habe mit brute force versucht - ab 4 Artikeln wird zu langsam. Heute habe ich neue Methode ausprobiert. Die Filialen sortiere ich absteigend nach Kosten, anschließen gehe ich von oben und teile die Mengen zu. Wenn ich alle zugeteilt habe, versuche ich für jede Filiale, ob es möglich ist, Abgabemengen an andere zu leiten, die sowieso schon was abgeben müssen. Das funktioniert schon relativ gut. Beispiel. Diese Mengen brauche ich: Artikel, Bedarf a4711, 8 a4712, 9 a4713, 4 a4714, 3 a4715, 8 Die Filialen haben: Filiale, Kosten, a4711, a4712, a4713, a4714, a4715 f004, 8, 2, 2, 3, 4, 2 f002, 17, 6, 2, 4, 6, 4 f005, 25, 7, 0, 7, 6, 6 f003, 27, 5, 3, 3, 4, 3 f006, 27, 5, 7, 5, 1, 4 f008, 28, 3, 7, 2, 2, 0 f007, 55, 6, 5, 4, 0, 6 f001, 89, 4, 6, 7, 1, 2 Nach der anfänglichen Verteilung hole ich: Filiale, Kosten, a4711, a4712, a4713, a4714, a4715 f004, 8, 2, 2, 3, 3, 2 f002, 17, 6, 2, 1, 0, 4 f005, 25, 0, 0, 0, 0, 2 f003, 27, 0, 3, 0, 0, 0 f006, 27, 0, 2, 0, 0, 0, f008, 28, f007, 55, f001, 89, Sum, 104, 8, 9, 4, 3, 8 Das wird optimiert zu: Filiale, Kosten, a4711, a4712, a4713, a4714, a4715 f004, 8, f002, 17, f005, 25, 7, 0, 4, 3, 6 f003, 27, 1, 3, 0, 0, 2 f006, 27, 0, 6, 0, 0, 0, f008, 28, f007, 55, f001, 89, Sum, 79, 8, 9, 4, 3, 8 Wenn ich aber per Hand optimiere, würde ich Filialen f004,f003 und f006 wählen, mit Gesamtkosten von 62. Kann man das irgendwie in Algorithmus fassen? |
||||
| 14.06.2011, 18:22 | gabriel | Auf diesen Beitrag antworten » | ||
RE: Transportproblem, aber anders
Wohin transportiert wird, ist klar - ich habe nur ein Ziel. Das Problem sind unterschiedliche Artikel - und das passt zu keinem der fertigen Algorithmen, die ich gefunden habe (Knapsack,Transportproblem,Arbeitszuteilung usw.) Gabriel |
||||
| 15.06.2011, 19:06 | Abakus | Auf diesen Beitrag antworten » | ||
| RE: Transportproblem, aber anders Du machst es dir recht schwierig. Nimm - für dein nun verändertes Problem - für jede Filiale eine binäre Variable: 1, wenn sie angesteuert wird; 0, wenn nicht. Damit solltest du die Kosten-Zielfunktion und alle Restriktionen (Summe der Lagerinhalte größer benötigte Menge) hinschreiben können. Abakus
|
||||
| 18.06.2011, 19:11 | gabriel | Auf diesen Beitrag antworten » | ||
| RE: Transportproblem, aber anders Es ist mir gelungen, dir Formel aufzuschreiben. Dann habe ich festgestellt, dass das Problem im Bereich "binary linear programming" liegt und dafür habe ich einige fertige Algorithmen. Nach einer Normalisierung der Gleichungen und Abtippen des Programmquellcodes aus meinem 35 alten Programmierhandbuch konnte ich additive Methode von E.Balas verwenden. Die funktioniert noch gut bis 25-30 Variablen und 15-20 Randbedingungen. Leider erwarte ich bis zu 100 Variablen. Gibt es Möglichkeiten, den Algorithmus zu verbessern oder einen schnelleren zu verwenden? Es gibt Benchmarks, die zeigen, dass es bei 1000x1000 noch unter einer Minute läuft. Ich musste bei 50x16 nach einen Stunde abbrechen. Gruß, Gabriel |
||||
| Anzeige | ||||
|
|
||||
| 19.06.2011, 13:18 | Abakus | Auf diesen Beitrag antworten » | ||
| RE: Transportproblem, aber anders Du suchst also einen Algorithmus für einen bestimmten Aufgabentyp und möchtest nicht unbedingt eine spezielle Aufgabe lösen? Ich denke, letztendlich wird man da Branch & Bound reinstecken müssen, ggf. mit einer mehr oder weniger schlauen Heuristik. Du kannst ja mal ausprobieren, wie schnell es LP-Programme lösen erstmal, wenn du soetwas zur Verfügung hast. Abakus
|
||||
| 19.06.2011, 15:41 | gabriel | Auf diesen Beitrag antworten » | ||
| RE: Transportproblem, aber anders Wir stellen Software für Einzelhandel her. In diesem Fall geht es um ein Modul, mit dem der Händler sein Webshop bedienen kann. In regelmässigen Abständen prüft er, was bestellt wurde und holt die Ware aus seinen Geschäften. Unsere grössten Kunden haben um 80-100 Verkaufstellen. Das wäre die Anzahl der freien Variablen. Wenn man die Prüfungen oft genug durchführt, denke ich, dass man die Anzahl Artikel auf 10 bis 20 reduzieren kann. Und wenn die Mengen jedes Artikels auch noch relativ klein sind (im Vergleich zu den Beständen in Filialen), läuft sogar Balas ziemlich schnell. Trotzdem würde ich gerne ein existierendes Programm ausprobieren. Zur Zeit habe ich keins zu Verfügung. Gabriel |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
