Video

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 u_i und Nachfrager v_j 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 a_i-Spalte und die b_j-Zeile bleiben ebenso gleich.

Als zweites bestimmst du die Dualvariablen für die Basisvariablen. Diese setzen sich zusammensetzen aus c_ij in der Kostenmatrix gleich u_i + v_j 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 v₄ gleich 0. Daraus ergibt sich, dass u₃ gleich „4 Minus 0 gleich 4“ sein muss. Und daraus können wir wiederrum folgern, dass v₃ 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 x_ij um eine Mengeneinheit erhöht wird. Die reduzierten Kosten ergeben sich nach der Rechnung: $\bar{c_{ij}}=c_{ij}-u_i-v_j$ . $\bar{c_{13}}$ 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 $\bar{c_{ij}}$ 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 $\bar{c_{ij}}$ . 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 $\bar{c_{13}}$ . 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. X₁₃wird also anstelle von x₁₂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 €.