Definition der Stepping-Stone-Methode
Die Stepping-Stone-Methode ist ein Optimierungsverfahren für Transportprobleme und dient der Bestimmung einer optimalen Lösung bei welcher die Transportkosten minimal sind. Ausgehend von der Ausgangslösung nach dem Matrixminiumverfahren, erfolgt in diesem Abschnitt die iterative Verbesserung der Ausgangslösung hin zu einer optimalen Lösung durch die Stepping-Stone-Methode.
Methode
Hier klicken zum AusklappenStepping-Stone-Methode
1. Es wird ein nicht belegtes Feld ausgewählt. In dieses Feld setzt man die fiktive Menge . Ausgehend von diesem Feld schreitet man waagerecht (nach rechts oder links) voran zu einem belegten Feld, welches aber ein unter oder über sich (senkrecht) belegtes Feld aufweist. Die Menge des belegten Feldes wird fiktiv um reduziert.
2. Man schreitet dann von diesem Feld zu dem senkrecht belegten Feld, welches aber wiederum ein rechts oder links liegendes (waagrechtes) belegtes Feld oder das Ausgangsfeld aufweisen muss. Die Menge des belegten Feldes wird fiktiv um erhöht.
Die Schritte 1-2 werden solange wiederholt, bis man wieder am Ausgangsfeld angekommen ist.
3. Danach werden die Kosten der abgegangenen Felder miteinander verrechnet und damit der Zykluswert bestimmt. Die Kosten der Felder mit +1 werden addiert, die Kosten der Felder mit -1 subtrahiert. Am Ende wird der Zykluswert auf das Statfeld in die rechte unteren Ecke notiert.
4. Ist , so kann eine Verbesserung der Ausganglösung erfolgen. Es wird dann eine Mengenverschiebung vorgenommen. Es wird dafür die minimale Menge auf dem Pfad mit den Felder die um 1 reduziert wurden gewählt und diese Menge an das Startfeld verschoben. Alle anderen Mengen auf dem Pfad müssen dann so angepasst werden, dass die Mengen der Felder mit +1 mit dieser Menge addiert werden und die Mengen der Felder mit -1 mit dieser Menge subtrahiert. Es werden dann wieder für alle unbelegten Felder (auch die bereits eine Zykluszahl erhalten) neue Zyklen bestimmt.
Ist so kann keine Verbesserung der Ausgangslösung erfolgen. Es wird dann das nächste nicht belegte Feld betrachtet und die Schritte 1-4 wiederholt.
Die Schritte werden solange wiederholt bis alle .
Vorgehensweise bei der Stepping-Stone-Methode
Die Vorgehensweise soll anhand der Ausgangslösung nach dem Matrixminimumverfahren durchgeführt werden:
Auswahl eines nicht belegten Feldes. (Hinweis: Das Feld besitzt zwar Null Mengen, ist aber trotzdem belegt, da Basisvariablen gegeben sein müssen). Es wird beliebig das unbelegte Feld gewählt.
Die Vorgehensweise ist nun wie folgt. Es muss zunächst waagerecht vorgegangen werden zu einem belegten Feld. Danach wird abwechseld senkrecht und waagerecht von belegtem Feld zu belegtem Feld vorgegangen, bis wieder das Startfeld erreicht wird.
Es wird zunächst vom Feld waagerecht vorgegangen. Dabei wird ein belegtes Feld angesteuert. Dieses belegte Feld muss aber ein belegtes Feld senkrecht von sich aufweisen und das senkrechte Feld wieder ein belegtes Feld waagerecht etc. So dass ein Zyklus entsteht. Das Feld besitzt zwei senkrecht unter sich liegende Felder oder . Da man aber nur vom Feld wieder waagerecht weiter zu einem belegten Feld schreiten kann, wird dieses Feld für den Zyklus gewählt. Von diesem Feld kann man dann entweder das belegte Feld oder ansteuern. Das Feld besitzt aber kein senkrechtes belegtes Feld über oder unter sich. Deswegen wird das Feld angeseteuert und dann wieder zum Startfeld zurück.
In der obigen Grafik ist der Zyklus aufgeführt. Beginnend bei dem unbelegten Feld werden danach nur noch belegte Felder angesteuert. Dabei muss immer ein Richtungswechsel von waagrecht zu senkrecht und umgekehrt stattfinden. Der Zyklus wird wieder beim Startfeld beendet. Das Startfeld erhält die fiktive Menge +1. Danach werden immer abwechselnd die belegten Felder mit -1 und +1 belegt. Es wird dann bestimmt, indem die Kosten für die Felder mit +1 addiert werden und die Kosten mit Felder -1 subtrahiert:
.
Da kann hier keine Verbesserung der Ausgangslösung vorgenommen werden. Der Zykluswert wird an die untere rechte Ecke des Startfeldes geschrieben und das nächste nicht belegte Feld betrachtet.
Es wurde als Startfeld das unbelegte Feld gewählt. Der Zykluswert beträgt:
.
Auch hier ist keine Verbesserung der Ausgangslösung zu erreichen.
Es wurde als Startfeld das unbelegte Feld gewählt. Der Zykluswert beträgt:
.
Da , kann hier eine Verbesserung der Ausgangslösung stattfinden. Es wird nun die minimale Menge mit -1 auf dem Zyklus gewählt. Diese beträgt . Diese wird nun auf das Startfeld gesetzt. Alle anderen Mengen müssen nun so angepasst werden, dass die Angebots-und Nachfragemengen eingehalten werden. Das bedeutet also, dass überall dort wo eine -1 steht die 100 Mengen abgezogen werden und überall dort wo eine +1 steht die 100 Mengen addiert werden:
Nachdem nun die Mengenverschiebung von (jetzt ein unbelegtes Feld) zu (jetzt ein belegtes Feld) stattgefunden hat, müssen wieder alle unbelegten Felder betrachtet werden, d.h. die bereits berechneten Zykluswerte muss erneut berechnet werden, da sich neue Zyklen ergeben. In der folgenden Grafik sind die Zykluswerte der einzelnen Felder aufgeführt:
Alle weiteren Zykluswerte sind größer als Null, das bedeutet also, dass hier die optimale Lösung gefunden ist. Es ist zulässig, dass sich bei der Ermittlung der Zyklen die Pfeile für einen Zyklus überschneiden. Bei den Zykluswerte für die Felder und ergeben sich solche Überschneidungen der Pfeile.
Die gesamten Transportkosten können nun bestimmt werden, indem die Ausgangskostenmatrix herangezogen wird:
Lösung der Stepping-Stone-Methode
Die gesamten minimalen Transportkosten ergeben sich zu:
.
