MODI

Die Modifizierte Distributionsmethode (MODI-Methode), auch als Potentialmethode, u-v-Methode oder Transportalgorithmus bezeichnet, ist ein numerisches Verfahren, mit dem man (bei gegebener Anfangs-Basislösung) ein Standard-Transportproblem lösen kann.

Es sind für ein Gut eine bestimmte Anzahl n Anbieter A_i (i = 1,...,n) und eine bestimmte Anzahl m Empfänger B_j (j = 1,...,m) gegeben. Im Standardfall ist die gesamte nachgefragte Menge gleich der gesamten angebotenen. Für den Transport einer Einheit x_ij zwischen A_i und B_j fallen Kosten c_ij an. Das Problem besteht darin, die von A_i nach B_j gelieferte Menge x_ij so festzulegen, dass die Gesamtransportkosten 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, dem Zeilen- oder Spaltenfolge-Verfahren, der Zeilen-Spalten-Sukzession, der Vogelschen Approximationsmethode oder der Russell´schen Approximationsmethode) eine zulässige Anfangsbasislösung $x \in \mathbb{R}^{mn}$ bestimmt. Variablen der Basislösung, die im Eröffnungsverfahren a priori gleich Null gesetzt wurden sind die Nichtbasisvariablen, die restlichen die Basisvariablen des zu Grunde liegenden Gleichungssystems. Die MODI-Methode verringert dann iterativ durch Austausch einer Nichtbasisvariablen mit einer Basisvariablen die Gesamtkosten. Kann keine Verbesserung mehr erzielt werden ist eine Optimallösung gefunden.

Verfahren

Das Optimierungsverfahren wird iterativ durchgeführt. In jedem Schritt werden alle Nichtbasisvariablen im Hinblick auf das Kostensenkungspotential überprüft. Für jede Nichtbasisvariable x_ij wird dazu analysiert, um welchen Wert k_ij sich die Gesamtkosten ändern würden, wenn eine Einheit des Gutes von A_i nach B_j transportiert werden würde. Dazu wird zu der Zelle (i,j) einer jeden Nichtbasisvariablen x_ij die Kostenänderung mit k_ij = c_ij − u_i − v_j berechnet, wobei zuvor die $u_1,\cdots,u_m$ und $v_1,\cdots,v_n$ iterativ mit der Gleichung u_i + v_j = c_ij berechnet wurden und dabei genau ein u_i oder v_j a priori gleich Null gesetzt wurde und nur entsprechende Kosten c_ij von Basisvariablen x_ij zur Berechnung benutzt wurden.

Ist k_ij positiv, würde dies zu einer Erhöhung der Gesamtkosten führen, ist k_ij gleich Null, würden sich die Gesamtkosten nicht ändern. Um mit möglichst wenig Iterationen zur Optimallösung zu kommen wird deswegen die Nichtbasisvariable x_ij mit dem negativsten k_ij als neue Basisvariable aufgenommen. Zu der zugehörigen Zelle (i,j) des Transporttableaus wird dazu zusammen mit den Zellen der Basisvariablen ein elementarer Kreis bestimmt. Die Zellen z₁ bis z_k $(k \geq 5)$ bilden dabei einen elementaren Kreis, wenn z₁ = z_k, zwei aufeinanderfolgende Zellen z_i und 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 $(i,o),(p,o),(p,q),\cdots , (v,j)$ der Basisvariablen, die zusammen mit der Zelle (i,j) x_ij einen elementaren Kreis beschreiben, bestimmt. Jetzt wird wie bei der Stepping-Stone-Methode entlang des elementaren Kreises alternierend von der ersten Basisvariablen x_io der Wert h subtrahiert und auf die nächste Basisvariable x_po addiert, bis die Zelle (i,j) erreicht wird. Dabei ist h der kleinste Wert der Basisvariablen, von denen h subtrahiert werden soll. Diese Basisvariable wird zu einer neuen Nichtbasisvariablen und durch x_ij mit Wert h in der neuen Basislösung ersetzt. Das Verfahren wird solange wiederholt, bis alle (in jeder Iteration neu zu bestimmenden) 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 B_{m + 1}, der das überschüssige Angebot nachfragt und Transportkosten c_{i,m + 1} = 0 für alle Anbieter 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 k_ij bei Aufnahme der Variable 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.

• Ein ähnliche Methode zur Verbesserung einer Anfangsbasislösung und finden der Optimallösung ist die Stepping-Stone-Methode. Dabei werden die Kostenveränderungen k_ij mit höherem Rechenaufwand (aber identischen Werten) als bei der MODI-Methode bestimmt.

• Gibt es mehrere negative k_ij kann statt dem betragsmäß größtem 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 A₁ und A₂ die Mengen 12 bzw. 8 anbieten und von drei Nachfragern B₁, B₂ und B₃ die Mengen 4, 10 bzw. 6 nachgefragt werden. In folgender Tabelle bezeichnen die x_ij die von i nach j zu liefernde Menge.

20 |  4  10   6 
----------------
12 | x11 x12 x13
8  | x21 x22 x23

Die Kosten c_ij, die für den Transport einer Einheit x_ij von i nach j entstehen, sind in der folgenden Tabelle aufgeführt.

cij| B1 B2  B3 
---------------
A1 |  7  4  3 
A2 |  5  5  6 

Für die Anfangslösung wird das Nord-West-Ecken-Verfahren verwendet. Es ergibt sich also:

xij|  4  10   6 
-----------------
12 |  4   8     
8  |      2   6

Zur Bestimmung der v_j und u_i werden die Kosten der Basisvariablen benötigt:

cij| B1 B2  B3
---------------------
A1 |  7  4    |  u1 
A2 |     5  6 |  u2 
---------------------
   | v1 v2  v3|

Setze dazu v₃ = 0. Mit v₃ und den Kosten c₂₃ der Basisvariable x₂₃ lässt sich jetzt mit der Formel c_ij = u_i + v_j der Wert von u₂ berechnen: u₂ = c₂₃ − v₃ = 6 − 0 = 6. Mit u₂ und c₂₂ lässt sich nun v₂ berechnen: v₂ = c₂₂ − u₂ = 5 − 6 = − 1. Ebenso lassen sich jetzt noch u₁ = 4 − ( − 1) = 5 und v₁ = 7 − 5 = 2 berechnen. Mit den v_j und u_i und c_ij aus obiger Kostentabelle lassen sich jetzt mit der Formel k_ij = c_ij − u_i − v_j die Kostenänderung berechnen, die sich bei Transport von einer Einheit über die Nichtbasisvariablen x_ij ergeben:

   |          |  ui
---------------------
   |       k13|  5
   | k21      |  6
---------------------
vj |  2 -1  0 |

Also ist k₁₃ = c₁₃ − u₁ − v₃ = 3 − 5 − 0 = − 2 und k₂₁ = c₂₁ − u₂ − v₁ = 5 − 6 − 2 = − 3. Mit beiden x_ij würde sich also eine Kostenverringerung ergeben. Da bei x₂₁ die Ersparnisse größer sind wählen wir diese Nichtbasisvariable und ermitteln den elementaren Kreis zur Zelle (2,1). Dieser ist (2,1),(2,2),(1,2) und (1,1). Maximal können jetzt zwei Einheiten über x₂₁ transportiert werden, da sonst x₂₂ negativ werden würde: Entlang des elementaren Kreises werden jetzt die zwei Einheiten abwechselnd hinzuaddiert bzw. subtrahiert. Dabei wird x₂₁ zur Basisvariablen und x₂₂ zur Nichtbasisvariablen:

xij|  4  10   6 
-----------------
12 |  2  10     
8  |  2       6

Jetzt müssen wieder wie oben mit den Kosten c_ij aus der obigen Tabelle der Basisvariablen und durch setzen von v₃ = 0 die übrigen v_j und u_i mit der Formel c_ij = u_i + v_j berechnet werden:

cij|          | ui 
---------------------
   |  7  4    | 8
   |  5     6 | 6
---------------------
vj | -1 -4  0 |

Mit den v_j, u_i und c_ij lassen sich jetzt wieder die Kostenänderungen k₁₃ und k₂₂ berechnen: k₁₃ = c₁₃ − u₁ − v₃ = 3 − 8 − 0 = − 5 und analog k₂₂ = 5 + 4 − 6 = 3. Mit Transport einer Einheit über x₁₃ lässt sich also wieder eine Kostensenkung erreichen. Der elementare Kreis zur Zelle (1,3) ist: (1,3),(1,1),(2,1) und (3,1). Es lassen sich also wieder maximal zwei Einheiten (wegen x₁₃ = 2) entlang des elementaren Kreises verschieben und es entsteht die neue Basislösung:

xij|  4  10   6 |
-----------------
12 |     10   2 
8  |  4       4

Jetzt müssen wieder zur Bestimmung von k₁₁ und k₂₂ die v_j und u_i bestimmt werden. Dieses wird solange wiederholt, bis in einer Iteration die k_ij alle nicht negativ sind und damit eine Optimallösung, bzw. wenn alle k_ij größer als Null sind, die Opimallösung gefunden wurde. Es ergibt sich die gleiche Lösung wie im Beispiel zur Stepping-Stone-Methode.

Weblinks

• MODI-Anleitung Schritt-für-Schritt Anleitung zur manuellen Anwendung der MODI-Methode