MODI-Methode

Die Modifizierte Distributionsmethode (MODI-Methode), a​uch als Potentialmethode, u-v-Methode o​der Transportalgorithmus bezeichnet, i​st ein numerisches Verfahren, m​it dem m​an (bei gegebener Anfangs-Basislösung) e​in Standard-Transportproblem optimal lösen kann.

Verfahren

Es sind für ein Gut eine bestimmte Anzahl ${\displaystyle n}$ Anbieter ${\displaystyle A_{i}}$ ${\displaystyle (i=1,...,n)}$ und eine bestimmte Anzahl ${\displaystyle m}$ Empfänger ${\displaystyle B_{j}}$ ${\displaystyle (j=1,...,m)}$ gegeben. Im Standardfall ist die gesamte nachgefragte Menge gleich der gesamten angebotenen. Für den Transport einer Einheit ${\displaystyle x_{ij}}$ zwischen ${\displaystyle A_{i}}$ und ${\displaystyle B_{j}}$ fallen Kosten ${\displaystyle c_{ij}}$ an. Das Problem besteht darin, die von ${\displaystyle A_{i}}$ nach ${\displaystyle B_{j}}$ gelieferte Menge ${\displaystyle x_{ij}}$ so festzulegen, dass die Gesamttransportkosten minimiert werden.

Da es sich um ein Verbesserungsverfahren handelt, wird zunächst mit einem Eröffnungsverfahren (z. B. dem Matrixminimumverfahren, dem Nord-West-Ecken-Verfahren oder der Vogelschen Approximationsmethode) eine zulässige Anfangsbasislösung ${\displaystyle x\in \mathbb {R} ^{mn}}$ bestimmt. Variablen der Basislösung, die im Eröffnungsverfahren zunächst gleich Null gesetzt wurden, sind die Nichtbasisvariablen, die restlichen die Basisvariablen des zu Grunde liegenden Gleichungssystems. Die MODI-Methode verringert anschließend iterativ durch Austausch einer Nichtbasisvariablen mit einer Basisvariablen die Gesamtkosten. Kann keine Verbesserung mehr erzielt werden, ist eine Optimallösung gefunden.

Das Optimierungsverfahren wird iterativ durchgeführt. In jedem Schritt werden alle Nichtbasisvariablen im Hinblick auf das Kostensenkungspotential überprüft. Für jede Nichtbasisvariable ${\displaystyle x_{ij}}$ wird dazu analysiert, um welchen Wert ${\displaystyle k_{ij}}$ sich die Gesamtkosten ändern würden, wenn eine Einheit des Gutes von ${\displaystyle A_{i}}$ nach ${\displaystyle B_{j}}$ transportiert werden würde. Dazu wird zu der Zelle ${\displaystyle (i,j)}$ einer jeden Nichtbasisvariablen ${\displaystyle x_{ij}}$ die Kostenänderung mit ${\displaystyle k_{ij}=c_{ij}-u_{i}-v_{j}}$ berechnet, wobei zuvor die ${\displaystyle u_{1},\cdots ,u_{m}}$ und ${\displaystyle v_{1},\cdots ,v_{n}}$ iterativ mit der Gleichung ${\displaystyle u_{i}+v_{j}=c_{ij}}$ berechnet wurden und dabei genau ein ${\displaystyle u_{i}}$ oder ${\displaystyle v_{j}}$ gleich Null gesetzt wurde und nur entsprechende Kosten ${\displaystyle c_{ij}}$ von Basisvariablen ${\displaystyle x_{ij}}$ zur Berechnung benutzt wurden.

Ist ${\displaystyle k_{ij}}$ positiv, würde dies zu einer Erhöhung der Gesamtkosten führen, ist ${\displaystyle k_{ij}}$ gleich Null, würden sich die Gesamtkosten nicht ändern. Um mit möglichst wenig Iterationen zur Optimallösung zu kommen, wird deshalb die Nichtbasisvariable ${\displaystyle x_{ij}}$ mit dem negativsten ${\displaystyle k_{ij}}$ als neue Basisvariable aufgenommen. Zu der zugehörigen Zelle ${\displaystyle (i,j)}$ des Transporttableaus wird dazu zusammen mit den Zellen der Basisvariablen ein elementarer Kreis bestimmt. Die Zellen ${\displaystyle z_{1}}$ bis ${\displaystyle z_{k}}$ ${\displaystyle (k\geq 5)}$ bilden dabei einen elementaren Kreis, wenn ${\displaystyle z_{1}=z_{k}}$, zwei aufeinanderfolgende Zellen ${\displaystyle z_{i}}$ und ${\displaystyle z_{i+1}}$ in der gleichen Zeile oder Spalte des Tableau liegen und in jeder Spalte und Zeile höchstens zwei Zellen des elementaren Kreises sind. Seien jetzt die Zellen ${\displaystyle (i,o),(p,o),(p,q),\cdots ,(v,j)}$ der Basisvariablen, die zusammen mit der Zelle ${\displaystyle (i,j)}$ ${\displaystyle x_{ij}}$ einen elementaren Kreis beschreiben, bestimmt. Jetzt wird wie bei der Stepping-Stone-Methode entlang des elementaren Kreises alternierend von der ersten Basisvariablen ${\displaystyle x_{io}}$ der Wert ${\displaystyle h}$ subtrahiert und auf die nächste Basisvariable ${\displaystyle x_{po}}$ addiert, bis die Zelle ${\displaystyle (i,j)}$ erreicht wird. Dabei ist ${\displaystyle h}$ der kleinste Wert der Basisvariablen, von denen ${\displaystyle h}$ subtrahiert werden soll. Diese Basisvariable wird zu einer neuen Nichtbasisvariablen und durch ${\displaystyle x_{ij}}$ mit Wert ${\displaystyle h}$ in der neuen Basislösung ersetzt. Das Verfahren wird solange wiederholt, bis alle (in jeder Iteration neu zu bestimmenden) ${\displaystyle k_{ij}}$ größer oder gleich Null sind, die Gesamtkosten also nicht mehr verringert werden können und die Lösung damit optimal ist.

Bemerkungen

• Ist die gesamte nachgefragte Menge kleiner als die gesamte angebotene Menge, kann durch Einführen eines fiktiven Nachfragers ${\displaystyle B_{m+1}}$, der das überschüssige Angebot nachfragt und Transportkosten ${\displaystyle c_{i,m+1}=0}$ für alle Anbieter ${\displaystyle A_{i}}$ hat, das Transportproblem in ein Standardtransportmodell transformiert werden und damit ebenfalls mit der MODI-Methode gelöst werden.

• Ist bei der Optimallösung eine mögliche Kostenveränderung ${\displaystyle k_{ij}}$ bei Aufnahme der Variable ${\displaystyle x_{ij}}$ gleich Null, bedeutet dieses, dass der Wert der zugehörige Nichtbasisvariable mit dem einer Basisvariablen ausgetauscht werden kann, ohne dass sich die Gesamtkosten ändern und die Optimallösung damit nicht eindeutig ist.

• Eine ähnliche Methode zur Verbesserung einer Anfangsbasislösung und finden der Optimallösung ist die Stepping-Stone-Methode. Dabei werden die Kostenveränderungen ${\displaystyle k_{ij}}$ mit höherem Rechenaufwand (aber identischen Werten) als bei der MODI-Methode bestimmt.

• Gibt es mehrere negative ${\displaystyle k_{ij}}$ kann statt des betragsmäßig größten auch jene zugehörige Nichtbasisvariable ausgewählt werden, die zu einer maximalen Verbesserung der Kostensumme führt oder eine zufällig davon ausgewählt werden.

Beispiel

Es liege folgendes, tabellarisch zusammengefasstes Transportproblem vor, bei dem die Anbieter ${\displaystyle A_{1}}$ und ${\displaystyle A_{2}}$ die Mengen 12 bzw. 8 anbieten und von drei Nachfragern ${\displaystyle B_{1}}$, ${\displaystyle B_{2}}$ und ${\displaystyle B_{3}}$ die Mengen 4, 10 bzw. 6 nachgefragt werden. In der links stehenden Tabelle bezeichnen die ${\displaystyle x_{ij}}$ die von ${\displaystyle i}$ nach ${\displaystyle j}$ zu liefernde Menge. Die rechts nebenstehende Tabelle enthält die Kosten ${\displaystyle c_{ij}}$, die für den Transport einer Einheit ${\displaystyle x_{ij}}$ von ${\displaystyle i}$ nach ${\displaystyle j}$ entstehen.

${\displaystyle {\begin{array}{c|ccc}20&4&10&6\\\hline 12&x_{11}&x_{12}&x_{13}\\8&x_{21}&x_{22}&x_{23}\\\end{array}}\qquad {\begin{array}{c|ccc}c_{ij}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7&4&3\\A_{2}&5&5&6\\\end{array}}}$

Als Eröffnungsverfahren wird das Nord-West-Ecken-Verfahren verwendet. Damit ergibt sich folgende, noch nicht optimale, Ausgangslösung:
${\displaystyle {\begin{array}{c|ccc}x_{ij}&4&10&6\\\hline 12&4&8&\\8&&2&6\\\end{array}}}$

Zur Bestimmung der ${\displaystyle v_{j}}$ und ${\displaystyle u_{i}}$ werden die Kosten der Basisvariablen benötigt:
${\displaystyle {\begin{array}{c|ccc|c}c_{ij}&B_{1}&B_{2}&B_{3}&\\\hline A_{1}&7&4&&u_{1}\\A_{2}&&5&6&u_{2}\\\hline &v_{1}&v_{2}&v_{3}&\\\end{array}}}$

Setze dazu ${\displaystyle v_{3}=0}$. Mit ${\displaystyle v_{3}}$ und den Kosten ${\displaystyle c_{23}}$ der Basisvariable ${\displaystyle x_{23}}$ lässt sich jetzt mit der Formel ${\displaystyle c_{ij}=u_{i}+v_{j}}$ der Wert von ${\displaystyle u_{2}}$ berechnen: ${\displaystyle u_{2}=c_{23}-v_{3}=6-0=6}$. Mit ${\displaystyle u_{2}}$ und ${\displaystyle c_{22}}$ lässt sich nun ${\displaystyle v_{2}}$ berechnen: ${\displaystyle v_{2}=c_{22}-u_{2}=5-6=-1}$. Ebenso lassen sich jetzt noch ${\displaystyle u_{1}=4-(-1)=5}$ und ${\displaystyle v_{1}=7-5=2}$ berechnen. Mit den ${\displaystyle v_{j}}$ und ${\displaystyle u_{i}}$ und ${\displaystyle c_{ij}}$ aus obiger Kostentabelle lassen sich jetzt mit der Formel ${\displaystyle k_{ij}=c_{ij}-u_{i}-v_{j}}$ die Kostenänderung berechnen, die sich bei Transport von einer Einheit über die Nichtbasisvariablen ${\displaystyle x_{ij}}$ ergeben:
${\displaystyle {\begin{array}{c|ccc|c}&&&&u_{i}\\\hline &&&k_{13}&5\\&k_{21}&&&6\\\hline v_{j}&2&-1&0&\\\end{array}}}$

Also ist ${\displaystyle k_{13}=c_{13}-u_{1}-v_{3}=3-5-0=-2}$ und ${\displaystyle k_{21}=c_{21}-u_{2}-v_{1}=5-6-2=-3}$. Mit beiden ${\displaystyle x_{ij}}$ würde sich also eine Kostenverringerung ergeben. Da bei ${\displaystyle x_{21}}$ die Ersparnisse größer sind wählen wir diese Nichtbasisvariable und ermitteln den elementaren Kreis zur Zelle ${\displaystyle (2,1)}$. Dieser ist ${\displaystyle (2,1),(2,2),(1,2)}$ und ${\displaystyle (1,1)}$. Maximal können jetzt zwei Einheiten über ${\displaystyle x_{21}}$ transportiert werden, da sonst ${\displaystyle x_{22}}$ negativ werden würde: Entlang des elementaren Kreises werden jetzt die zwei Einheiten abwechselnd hinzuaddiert bzw. subtrahiert. Dabei wird ${\displaystyle x_{21}}$ zur Basisvariablen und ${\displaystyle x_{22}}$ zur Nichtbasisvariablen:
${\displaystyle {\begin{array}{c|ccc}x_{ij}&4&10&6\\\hline 12&2&10&\\8&2&&6\\\end{array}}}$

Jetzt müssen wieder wie oben mit den Kosten ${\displaystyle c_{ij}}$ aus der obigen Tabelle der Basisvariablen und durch setzen von ${\displaystyle v_{3}=0}$ die übrigen ${\displaystyle v_{j}}$ und ${\displaystyle u_{i}}$ mit der Formel ${\displaystyle c_{ij}=u_{i}+v_{j}}$ berechnet werden:
${\displaystyle {\begin{array}{c|ccc|c}c_{ij}&&&&u_{i}\\\hline &7&4&&8\\&5&&6&6\\\hline v_{j}&-1&-4&0&\\\end{array}}}$

Mit den ${\displaystyle v_{j}}$, ${\displaystyle u_{i}}$ und ${\displaystyle c_{ij}}$ lassen sich jetzt wieder die Kostenänderungen ${\displaystyle k_{13}}$ und ${\displaystyle k_{22}}$ berechnen: ${\displaystyle k_{13}=c_{13}-u_{1}-v_{3}=3-8-0=-5}$ und analog ${\displaystyle k_{22}=5+4-6=3}$. Mit Transport einer Einheit über ${\displaystyle x_{13}}$ lässt sich also wieder eine Kostensenkung erreichen. Der elementare Kreis zur Zelle ${\displaystyle (1,3)}$ ist: ${\displaystyle (1,3),(1,1),(2,1)}$ und ${\displaystyle (2,3)}$. Es lassen sich also wieder maximal zwei Einheiten (wegen ${\displaystyle x_{11}=2}$) entlang des elementaren Kreises verschieben und es entsteht die neue Basislösung:
${\displaystyle {\begin{array}{c|ccc}x_{ij}&4&10&6\\\hline 12&&10&2\\8&4&&4\\\end{array}}}$

Jetzt müssen wieder zur Bestimmung von ${\displaystyle k_{11}}$ und ${\displaystyle k_{22}}$ die ${\displaystyle v_{j}}$ und ${\displaystyle u_{i}}$ bestimmt werden. Dieses wird solange wiederholt, bis in einer Iteration die ${\displaystyle k_{ij}}$ alle nicht negativ sind und damit eine Optimallösung, bzw. wenn alle ${\displaystyle k_{ij}}$ größer als Null sind, die Optimallösung gefunden wurde. Es ergibt sich die gleiche Lösung wie im Beispiel zur Stepping-Stone-Methode.