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

Bearbeiten

Es sind für ein Gut eine bestimmte Anzahl   Anbieter     und eine bestimmte Anzahl   Empfänger     gegeben. Im Standardfall ist die gesamte nachgefragte Menge gleich der gesamten angebotenen. Für den Transport einer Einheit   zwischen   und   fallen Kosten   an. Das Problem besteht darin, die von   nach   gelieferte Menge   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   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   wird dazu analysiert, um welchen Wert   sich die Gesamtkosten ändern würden, wenn eine Einheit des Gutes von   nach   transportiert werden würde. Dazu wird zu der Zelle   einer jeden Nichtbasisvariablen   die Kostenänderung mit   berechnet, wobei zuvor die   und   iterativ mit der Gleichung   berechnet wurden und dabei genau ein   oder   gleich Null gesetzt wurde und nur entsprechende Kosten   von Basisvariablen   zur Berechnung benutzt wurden.

Ist   positiv, würde dies zu einer Erhöhung der Gesamtkosten führen, ist   gleich Null, würden sich die Gesamtkosten nicht ändern. Um mit möglichst wenig Iterationen zur Optimallösung zu kommen, wird deshalb die Nichtbasisvariable   mit dem negativsten   als neue Basisvariable aufgenommen. Zu der zugehörigen Zelle   des Transporttableaus wird dazu zusammen mit den Zellen der Basisvariablen ein elementarer Kreis bestimmt. Die Zellen   bis     bilden dabei einen elementaren Kreis, wenn  , zwei aufeinanderfolgende Zellen   und   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   der Basisvariablen, die zusammen mit der Zelle     einen elementaren Kreis beschreiben, bestimmt. Jetzt wird wie bei der Stepping-Stone-Methode entlang des elementaren Kreises alternierend von der ersten Basisvariablen   der Wert   subtrahiert und auf die nächste Basisvariable   addiert, bis die Zelle   erreicht wird. Dabei ist   der kleinste Wert der Basisvariablen, von denen   subtrahiert werden soll. Diese Basisvariable wird zu einer neuen Nichtbasisvariablen und durch   mit Wert   in der neuen Basislösung ersetzt. Das Verfahren wird solange wiederholt, bis alle (in jeder Iteration neu zu bestimmenden)   größer oder gleich Null sind, die Gesamtkosten also nicht mehr verringert werden können und die Lösung damit optimal ist.

Bemerkungen

Bearbeiten
  • Ist die gesamte nachgefragte Menge kleiner als die gesamte angebotene Menge, kann durch Einführen eines fiktiven Nachfragers  , der das überschüssige Angebot nachfragt und Transportkosten   für alle Anbieter   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   bei Aufnahme der Variable   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   mit höherem Rechenaufwand (aber identischen Werten) als bei der MODI-Methode bestimmt.
  • Gibt es mehrere negative   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

Bearbeiten

Es liege folgendes, tabellarisch zusammengefasstes Transportproblem vor, bei dem die Anbieter   und   die Mengen 12 bzw. 8 anbieten und von drei Nachfragern  ,   und   die Mengen 4, 10 bzw. 6 nachgefragt werden. In der links stehenden Tabelle bezeichnen die   die von   nach   zu liefernde Menge. Die rechts nebenstehende Tabelle enthält die Kosten  , die für den Transport einer Einheit   von   nach   entstehen.

 

Als Eröffnungsverfahren wird das Nord-West-Ecken-Verfahren verwendet. Damit ergibt sich folgende, noch nicht optimale, Ausgangslösung:
 

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

Setze dazu  . Mit   und den Kosten   der Basisvariable   lässt sich jetzt mit der Formel   der Wert von   berechnen:  . Mit   und   lässt sich nun   berechnen:  . Ebenso lassen sich jetzt noch   und   berechnen. Mit den   und   und   aus obiger Kostentabelle lassen sich jetzt mit der Formel   die Kostenänderung berechnen, die sich bei Transport von einer Einheit über die Nichtbasisvariablen   ergeben:
 

Also ist   und  . Mit beiden   würde sich also eine Kostenverringerung ergeben. Da bei   die Ersparnisse größer sind wählen wir diese Nichtbasisvariable und ermitteln den elementaren Kreis zur Zelle  . Dieser ist   und  . Maximal können jetzt zwei Einheiten über   transportiert werden, da sonst   negativ werden würde: Entlang des elementaren Kreises werden jetzt die zwei Einheiten abwechselnd hinzuaddiert bzw. subtrahiert. Dabei wird   zur Basisvariablen und   zur Nichtbasisvariablen:
 

Jetzt müssen wieder wie oben mit den Kosten   aus der obigen Tabelle der Basisvariablen und durch setzen von   die übrigen   und   mit der Formel   berechnet werden:
 

Mit den  ,   und   lassen sich jetzt wieder die Kostenänderungen   und   berechnen:   und analog  . Mit Transport einer Einheit über   lässt sich also wieder eine Kostensenkung erreichen. Der elementare Kreis zur Zelle   ist:   und  . Es lassen sich also wieder maximal zwei Einheiten (wegen  ) entlang des elementaren Kreises verschieben und es entsteht die neue Basislösung:
 

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