imported>Wfstb: Links falsch platziert bzw. unnötig

2025-04-04T07:54:54Z

Links falsch platziert bzw. unnötig

Neue Seite

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]] optimal lösen kann.

== Verfahren ==
Es sind für ein Gut eine bestimmte Anzahl <math>n</math> Anbieter <math>A_i</math> <math>(i = 1, ..., n)</math> und eine bestimmte Anzahl <math>m</math> Empfänger <math>B_j</math> <math>(j = 1, ..., m)</math> gegeben. Im Standardfall ist die gesamte nachgefragte Menge gleich der gesamten angebotenen. Für den Transport einer Einheit <math>x_{ij}</math> zwischen <math>A_i</math> und <math>B_j</math> fallen Kosten <math>c_{ij}</math> an. Das Problem besteht darin, die von <math>A_i</math> nach <math>B_j</math> gelieferte Menge <math>x_{ij}</math> 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 [[Vogelsche Approximationsmethode|Vogelschen Approximationsmethode]]) eine zulässige Anfangsbasislösung <math>x \in \mathbb{R}^{mn}</math> 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 <math>x_{ij}</math> wird dazu analysiert, um welchen Wert <math>k_{ij}</math> sich die Gesamtkosten ändern würden, wenn eine Einheit des Gutes von <math>A_i</math> nach <math>B_j</math> transportiert werden würde. Dazu wird zu der Zelle <math>(i,j)</math> einer jeden Nichtbasisvariablen <math>x_{ij}</math> die Kostenänderung mit <math>k_{ij}= c_{ij}-u_i-v_j</math> berechnet, wobei zuvor die <math>u_1,\cdots,u_m</math> und <math>v_1,\cdots,v_n</math> iterativ mit der Gleichung <math>u_i + v_j = c_{ij}</math> berechnet wurden und dabei genau ein <math>u_{i}</math> oder <math>v_{j}</math> gleich Null gesetzt wurde und nur entsprechende Kosten <math>c_{ij}</math> von Basisvariablen <math>x_{ij}</math> zur Berechnung benutzt wurden.

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

* Gibt es mehrere negative <math>k_{ij}</math> 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 <math>A_1</math> und <math>A_2</math> die Mengen 12 bzw. 8 anbieten und von drei Nachfragern <math>B_1</math>, <math>B_2</math> und <math>B_3</math> die Mengen 4, 10 bzw. 6 nachgefragt werden. In der links stehenden Tabelle bezeichnen die <math>x_{ij}</math> die von <math>i</math> nach <math>j</math> zu liefernde Menge. Die rechts nebenstehende Tabelle enthält die Kosten <math>c_{ij}</math>, die für den Transport einer Einheit <math>x_{ij}</math> von <math>i</math> nach <math>j</math> entstehen.

<math>
\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}
</math>

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

Zur Bestimmung der <math>v_j</math> und <math>u_i</math> werden die Kosten der Basisvariablen benötigt: 
<math>
\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}
</math>

Setze dazu <math>v_3=0</math>. Mit <math>v_3</math> und den Kosten <math>c_{23}</math> der Basisvariable <math>x_{23}</math> lässt sich jetzt mit der Formel <math>c_{ij}=u_i+v_j</math> der Wert von <math>u_2</math> berechnen: <math>u_2=c_{23}-v_3=6-0=6</math>.
Mit <math>u_2</math> und <math>c_{22}</math> lässt sich nun <math>v_2</math> berechnen: <math>v_2=c_{22}-u_2=5-6=-1</math>. Ebenso lassen sich jetzt noch <math>u_1=4-(-1)=5</math> und <math>v_1=7-5=2</math> berechnen. Mit den <math>v_j</math> und <math>u_i</math> und <math>c_{ij}</math> aus obiger Kostentabelle lassen sich jetzt mit der Formel <math>k_{ij}=c_{ij}-u_i-v_j</math> die Kostenänderung berechnen, die sich bei Transport von einer Einheit über die Nichtbasisvariablen <math>x_{ij}</math> ergeben: 
<math>
\begin{array}{c|ccc|c}
& & & & u_i \\ \hline
& & & k_{13} & 5 \\
& k_{21} & & & 6 \\ \hline
v_j & 2 & -1 & 0 & \\
\end{array}
</math>

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

Jetzt müssen wieder wie oben mit den Kosten <math>c_{ij}</math> aus der obigen Tabelle der Basisvariablen und durch Setzen von <math>v_3=0</math> die übrigen <math>v_j</math> und <math>u_i</math> mit der Formel <math>c_{ij}=u_i+v_j</math> berechnet werden: 
<math>
\begin{array}{c|ccc|c}
c_{ij} & & & & u_i \\ \hline
& 7 & 4 & & 8 \\
& 5 & & 6 & 6 \\ \hline
v_j & -1 & -4 & 0 & \\
\end{array}
</math>

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

Jetzt müssen wieder zur Bestimmung von <math>k_{11}</math> und <math>k_{22}</math> die <math>v_j</math> und <math>u_i</math> bestimmt werden. Dieses wird solange wiederholt, bis in einer Iteration die <math>k_{ij}</math> alle nicht negativ sind und damit ''eine'' Optimallösung, bzw. wenn alle <math>k_{ij}</math> größer als Null sind, ''die'' Optimallösung gefunden wurde. Es ergibt sich die gleiche Lösung wie im Beispiel zur [[Stepping-Stone-Methode]].

{{DEFAULTSORT:Modi-Methode}}
[[Kategorie:Optimierungsalgorithmus]]
[[Kategorie:Transportproblem]]

MODI-Methode - Versionsgeschichte

imported>Wfstb: Links falsch platziert bzw. unnötig