Stepping-Stone-Methode
Stepping-Stone-Methode Definition
Wenn man mit dem Nord-West-Ecken-Verfahren oder der Vogelschen Approximationsmethode eine mögliche Ausgangslösung für das Transportproblem gefunden hat, kann man diese mit der Stepping-Stone-Methode optimieren (bzw. überprüfen, ob die Ausgangslösung nicht bereits optimal ist).
Der Name Stepping Stone kommt daher, dass man einen Teich trockenen Fußes überqueren kann, indem man auf die Steine (stones) im Teich tritt (step). Mit etwas Phantasie: Die Tabelle der Ausgangslösung ist der Teich und die Zellen mit Transport(vorbelegung) sind die Steine, auf denen man sich durch den Teich bewegt.
Beispiel
Beispiel: Stepping-Stone-Methode
Dies war die Ausgangslösung des Nord-West-Ecken-Verfahrens:
| Z1 | Z2 | Z3 | |
|---|---|---|---|
| Q1 | 1 (100) | 8 | 6 |
| Q2 | 5 (150) | 3 (50) | 7 |
| Q3 | 9 | 4 (150) | 2 (150) |
Die vorläufigen Transportmengen sind in Klammern eingetragen. Die Ausgangslösung enthält 5 Zellen mit Transportmengen und 4 Zellen ohne Transportmengen.
Stepping-Stone-Methode:
Für jede der 4 nicht (mit Transport) belegten Zellen wird ein Pfad bzw. eine Schleife gebildet, der ausschließlich über (mit Transport) belegte Zellen – das sind die Stepping Stones – geht und wieder zu der Ausgangszelle zurückführt.
Pfad 1
Q1Z2 (Startpunkt) - Q2Z2 - Q2Z1 - Q1Z1 - Q1Z2 (wieder am Startpunkt zurück).
Wenn man jetzt eine Einheit (ein Stück) auf diesem Pfad transportieren würde, änderten sich die Transportkosten wie folgt:
+ 8 (eins mehr transportiert in Zelle Q1Z2, d.h. von Q1 nach Z2, vorher wurde hier 0 transportiert) - 3 (eins weniger transportiert in Zelle Q2Z2; die Spaltensumme muss bei 200 bleiben, mehr braucht Z2 nicht in Summe) + 5 (eins mehr transportiert in Zelle Q2Z1) - 1 (eins weniger transportiert in Zelle Q1Z1) = 9.
Das ist > 0, die Kosten würden steigen, deshalb ist dieser Pfad uninteressant und es wird nichts geändert.
Pfad 2
Q1Z3 (Startpunkt) - Q3Z3 - Q3Z2 - Q2Z2 - Q2Z1 - Q1Z1 - Q1Z3 (wieder am Startpunkt zurück).
Änderung der Transportkosten: + 6 - 2 + 4 - 3 + 5 - 1 = 9.
Auch dieser Pfad ist uninteressant.
Pfad 3
Q2Z3 (Startpunkt) - Q3Z3 - Q3Z2 - Q2Z2 - Q2Z3 (wieder am Startpunkt zurück).
Änderung der Transportkosten: + 7 - 2 + 4 - 3 = 6.
Auch dieser Pfad ist uninteressant.
Pfad 4
Q3Z1 (Startpunkt) - Q2Z1 - Q2Z2 - Q3Z2 - Q3Z1 (wieder am Startpunkt zurück).
Änderung der Transportkosten: + 9 - 5 + 3 - 4 = 3.
Auch dieser Pfad ist uninteressant.
Da alle 4 Pfade, die von nicht mit Transport belegten Zellen ausgehen, die Transportkosten erhöhen würden, ist die Ausgangslösung optimal (sind die Transportkosten am niedrigsten) – es gibt deshalb nichts zu ändern an der Zuordnung der Ausgangstabelle für die Transportmengen.
Hätte es einen Pfad mit einem negativen Wert gegeben, würden die Transportkosten sinken, wenn man auf diesem Pfad transportiert. Dann würde man die für den Pfad maximale Menge transportieren. Für Pfad 4 wäre das z.B. eine Menge von 150 Stück: Dann würde Q3 nun 150 Stück zu Z1 transportieren, Q2 würde dafür 150 Stück weniger an Z1 transportieren (d.h. gar nichts mehr an Z1), Q2 würde nun 200 Stück statt 50 (also 150 mehr) an Z2 liefern und Q3 würde 150 Stück weniger (d.h. gar nichts mehr) an Z2 liefern. Alle Produktionsmengen wären weiterhin verteilt, alle Nachfragemengen bedient.