Lösung des Transportproblems mit der Potentialmethode

Bei der Aufstellung des gewöhnlichen Simplextableaus für dieses Problem erhält man ein riesiges Schema vom Typ mit einer großen Anzahl von Nullen: Jede Spalte enthält nur zwei 1-Elemente. Deshalb arbeitet man besser mit einem reduzierten Schema. Das Verfahren besteht aus Simplexschritten, die nur mit Nicht-Null-Elementen des theoretischen Simplextableaus durchgeführt werden. Die Matrix des Simplextableaus enthält die Koeffizienten der Zielfunktion. Die Basisvariablen werden iterativ gegen die Nichtbasisvariablen ausgetauscht, um so jeweils eine zugehörige modifizierte Kostenmatrix zu berechnen. Der Rechengang wird am Beispiel erläutert.

1. Ermittlung der modifizierten Kostenmatrix aus mittels

   unter den Bedingungen

   Dazu werden in die zu Basisvariablen gehörenden Kosten markiert und p₁=0 gesetzt. Die weiteren Größen p_i und , auch Potentiale bzw. Simplexmultiplikatoren genannt, werden so errechnet, daß zu markierten Kosten gehörende p_i und q_j zusammen mit den Kosten c_ij die Summe 0 ergeben:

   Beispiel

   
   

2. Berechnung von:

   Ist , dann ist der gegebene Verteilungsplan optimal; anderenfalls wird x_pq als neue Basisvariable gewählt. Im Beispiel ist .

3. In werden und die zu Basisvariablen gehörenden Kosten markiert. Enthält eine Zeile oder Spalte mit maximal einem markierten Element, dann wird diese Spalte oder Zeile gestrichen. Mit der verbleibenden Restmatrix wird dieser Vorgang wiederholt, bis keine Streichungen mehr möglich sind.
4. Die zu verbleibenden markierten Elementen gehörenden x_ij bilden einen Zyklus. Man setzt zunächst . Alle weiteren zu markierten gehörenden werden so bestimmt, daß die Nebenbedingungen erfüllt bleiben. Die Größe errechnet sich aus

   wobei x_rs Nichtbasisvariable wird. Im Beispiel ist .

   
   

   Danach wird das Verfahren ab Schritt 1 und wiederholt.
   

   

   
   

   Die nächste zu bestimmende Matrix enthält keine negativen Elemente. Deshalb ist ein optimaler Verteilungsplan.