Video

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.

direkt ins Video springen
MODI-Methode

Als zweites bestimmst du die Dualvariablen für die Basisvariablen. Diese setzen sich zusammensetzen aus cij  in der Kostenmatrix gleich u­i + 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.

Zweiter Schritt
direkt ins Video springen
Zweiter Schritt

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: \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.

Dritter Schritt
direkt ins Video springen
Dritter Schritt

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.

Basistausch
direkt ins Video springen
Basistausch

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.

Ausgleichskreis
direkt ins Video springen
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!

Neue Basislösung
direkt ins Video springen
Neue Basislösung

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.

Zweite Iteration
direkt ins Video springen
Zweite Iteration

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.

Dritte Iteration
direkt ins Video springen
Dritte Iteration

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 €.

Basislösung MODI-Methode
direkt ins Video springen
Basislösung MODI-Methode

Du siehst: Durch die MODI Methode konnten wir die Kosten des Transportproblems optimieren.

Beliebte Inhalte aus dem Bereich Operations Research

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte .