Duales Simplexverfahren: Pivotzeile/-spalte/-element

Nachdem das Tableau für das lineare Optimierungsproblem im vorherigen Abschnitt aufgestellt worden ist, soll nun die erste Iteration für das duale Simplexverfahren durchgeführt werden. Für jede Iteration müssen die folgenden Schritte durchgeführt werden. Im Gegensatz zum primalen Simplexverfahren beginnt das duale Simplexverfahren mit Wahl der PivotZeile:

1. Wahl der Pivotzeile s: Existiert kein $b_i < 0$, so liegt bereits eine zulässige Basislösung vor. Es wird dann das duale Simplexverfahren abbgebrochen und mit dem primale Simplexverfahren fortgesetzt.
   
   Ansonsten wird diejenige Zeile $s$ mit dem kleinsten negativen Wert der rechten Seite als Pivotzeile gewählt. Sind mehrere Zeilen mit kleinstem negativen Wert gegeben, so kann unter diesen eine beliebige Zeile ausgewählt werden. 
   
   
2. Wahl der Pivotspalte t: Sind in der Pivotszeile aus 1. alle $a_{sj} > 0$, so exsitiert für das Problem keine zulässige Basislösung. Das gesamte Verfahren wird dann abgebrochen. 
   
   Ansonsten wird die untere Zeile (Zielfunktionszeile) für alle Elemente $a_{sj} < 0$ der Pivotzeile betrachtet und diejenige Pivotspalte ausgewählt, für die gilt $max\frac{c_j}{a_{sj}}$. Dort wo sich die Pivotspalte und die Pivotzeile schneiden, liegt das Pivotelement $a_{st}$.
   
   
3. Nachdem die Pivotzeile $s$ und die Pivotspalte $t$ sowie das Pivotelement $a_{st}$ bestimmt worden sind, wird nun in einem nächsten Schritt die Basisvariable der Pivotzeile mit der Nichtbasisvarbiablen der Pivotspalte getauscht und ein neues Tableau aufgestellt.

Zum besseren Verständnis der ersten drei Schritte, wird nun das Beispiel aus dem vorherigen Abschnitt herangezogen und ausführlich gezeigt, wie diese Schritte durchgeführt werden:

1. Schritt: Wahl der Pivotzeile

Für den kleinsten Wert der rechten Seite wird die Pivotzeile festgelegt. In dem obigen Beispiel ist dies der Wert $-12$.

2. Schritt: Wahl der Pivotspalte

Als nächstes werden dann alle Werte innerhalb der Pivotzeile betrachtet (hier: -3, -1). Es werden dann diejenigen Werte kleiner Null ausgewählt (die größer Null bleiben unberücksichtigt) und mit den Werten der Zielfunktionszeile verrechnet (Division der Zielfunktionswerte durch die Werte der Pivotzeile). Dort wird der größte Wert ausgewählt und die Pivotspalte festgelegt. Das Pivotelement liegt dann dort, wo sich Pivotzeile und Pivotspalte schneiden:

Die weitere Vorgehensweise ist wie beim primalen Simplexalgorithmus. Es muss also zunächst das neue Tableau aufgestellt werden, indem die Nichtbasisvariable und die Basisvariable des Pivotelements miteinander vertauscht werden. Danach werden die Rechenschritte zur Bestimmung der neuen Elemente analog wie beim primalen Simplexalgorithmus durchgeführt. Im folgenden Abschnitt wird das neue Tableau mit den neuen Elementen aufgeführt.