Transportproblem II
Im vorherigen Video haben wir drei Heuristiken zur Lösung eines Transportproblems kennengelernt. Deren Lösungen waren zwar zulässig, aber noch nicht optimal. Deshalb werden wir jetzt auf eine der bereits vorhandenen Basislösungen die MODI Methode anwenden und daraus die optimale Lösung ermitteln.
MODI Methode zur Lösung des Transportproblems
Das Tableau für die MODI Verfahren ist einfach nur um die Dualvariablen der Anbieter ui und Nachfrager vj erweitert. Zusätzlich benötigen wir wieder die Kostenmatrix C in unserem Tableau.
Im ersten Schritt schreibst du die Basislösung aus deinem Heuristikverfahren in das MODI Tableau und markierst sie. Die ai-Spalte und die bj-Zeile bleiben ebenso gleich.
Als zweites bestimmst du die Dualvariablen für die Basisvariablen. Diese setzen sich zusammensetzen aus cij in der Kostenmatrix gleich ui + vj im MODI Tableau. Für eine der Variablen musst du vorerst einen beliebigen Wert annehmen, um alle anderen Wert ermitteln zu können. Wir setzen deshalb zum Beispiel v4 gleich 0. Daraus ergibt sich, dass u3 gleich „4 Minus 0 gleich 4“ sein muss. Und daraus können wir wiederrum folgern, dass v3 gleich 2 sein muss, da „4 plus 2 gleich 6“ ist und so weiter.
Im dritten Schritt der MODI Methode musst du in den noch freien Felder die reduzierten Kosten für die Nicht-Basisvariablen berechnen. Diese sind ein Maß für den Kostenanstieg des Zielfunktionswertes, wenn xij um eine Mengeneinheit erhöht wird. Die reduzierten Kosten ergeben sich nach der Rechnung: 
. 
ist also gleich 4-3-2=1. Für die anderen Werte machen wir das genauso. Nachdem du alle reduzierten Kosten berechnet hast, überprüfst du, ob alle 
größer gleich Null sind. Ist das der Fall, ist unsere Basislösung optimal und wir stoppen das Verfahren.
Ist das aber nicht so – wie in unserem Beispiel – nehmen wir einen Basistausch vor.
Für den Basistausch bei der MODI Verfahren suchst du dir als erstes den negativsten Wert . Hier haben wir drei Werte, die mit „Minus 1“ den gleichen negativen Wert haben. Falls nicht anders vorgegeben, kannst du dir einen der drei aussuchen. Wir wählen . Dieser wird unsere neue Basisvariable mit dem Wert Delta.
Wir wollen ihn nun erhöhen, da er negative reduzierte Transportkosten, also erhöhte Kosten darstellt. Wir schreiben deshalb ein +Δ an die Zahl. Um diese Erhöhung in der 3. Spalte und der 1. Zeile auszugleichen, schreiben wir für die Basisvariablen darunter und daneben ein „Minus Delta“. Jetzt muss aber auch noch die 2. Zeile ausgeglichen werden. Deshalb markieren wir die Basisvariable mit dem Wert 1 mit einem „Plus Delta“. Wie du siehst, haben wir jetzt einen Ausgleichskreis.
Der Wert von Delta ist der Wert der kleinsten Basisvariable, die mit einem negativen Delta markiert ist. Demnach ist Delta gleich 4. X13 wird also anstelle von x12 unsere neue Basisvariable. Die vier Einheiten werden jetzt nicht mehr von Anbieter 1 nach Nachfrager 2, sondern von 1 nach 3 geliefert. Um die anderen Basisvariablen im Ausgleichskreis anzupassen, addierst beziehungsweise subtrahierst du sie mit Delta, also mit 4. Das ist jetzt unsere neue zulässige Basislösung. Damit haben wir die erste Iteration der MODI Methode geschafft!
Um zu sehen, ob dein Transportplan jetzt optimal ist, musst du die zweite Iteration beginnen und die Dualvariablen und die reduzierten Kosten neu bestimmen. Wie du siehst, haben wir hier immer noch negative reduzierte Kosten und damit noch keine optimale Lösung.
Wenn wir jetzt die dritte Iteration durchführen, siehst du, dass wir keine negativen reduzierten Kosten mehr haben. Wir können das MODI Verfahren damit abbrechen und haben unsere optimale Lösung bestimmt.
Wenn du nun die Zielfunktion des Transportproblems mit der MODI Methode berechnen möchtest, musst du nur die Basisvariablen, also die Transportmenge des Guts, mit ihren jeweiligen Kosten multiplizieren. Damit kommen wir auf Transportkosten von 120€. Der Zielfunktionswert der Basislösung, die wir mit der Nordwesteckenregel im vorherigen Video erhalten haben, ist 126 €.
Du siehst: Durch die MODI Methode konnten wir die Kosten des Transportproblems optimieren.