Der Simplexalgorithmus besteht aus zwei Phasen. Da alle bisherigen Ausführungen auf einem vereinfachten Modell fußen, bei dem immer schon nach Aufstellen des Tableaus eine zulässige Basislösung vorliegt, kann mit der 2. Phase begonnen werden.

Um gleich zu Beginn das Geheimnis zu lüften, die Optimierung erfolgt beim Simplexalgorithmus über eine Folge von Basistäuschen. Da der maximale Zielwert gesucht wird, ist es zielführend, wenn sich der Zielwert bei jedem Basistausch vergrößert. Weiterhin muss sichergestellt werden, dass die Nichtnegativitätsbedingungen eingehalten werden.

Bei einem Basistausch ist zu entscheiden, welche Variable die Basis verlassen soll und welche aufgenommen werden soll. Die aufzunehmende Variable wird über die Auswahl der Pivotspalte festgelegt, die verlassende über die Pivotzeile. Anders ausgedrückt, es wird festgelegt, welche Variable einen höheren Wert annehmen soll und welche auf null gesetzt wird.

Auswahl der Pivotspalte (=Aufzunehmenden Basisvariablen)

In Worten: Suche den kleinsten Koeffizienten in der Zielzeile, die Spalte in der er steht ist die Pivotspalte. Ist der kleinste Koeffizient größer als 0, ist bereits das Optimum erreicht und es braucht nicht weiter gerechnet zu werden.

Erhöht man den Wert einer Variablen x_j um eine Einheit, so ändert sich der Zielwert um c_j. Aufgrund der Umformungen beim Aufstellen des Tableaus steigt der Zielwert, wenn man den Wert einer Variable mit negativen Zielzeilenkoeffizienten erhöht und sinkt bei einer mit positiven.

Deswegen wird der kleinste Zielzeilenkoeffizient gesucht, er verspricht die größte Erhöhung des Zielwertes. Existiert kein negativer Zielzeilenkoeffizient, gibt es keine Möglichkeit den Zielfunktionswert zu erhöhen. Es ist von daher nicht sinnvoll, einen Basistausch vorzunehmen, das Optimum ist erreicht.

Im Tableau wird gemäß vorstehender Regel die x₂ Spalte als Pivotspalte gewählt.

Auswahl der Pivotzeile (=die Basis verlassende Variable)

Die Auswahl der Pivotzeile r erfolgt nach dem Quotientenkriterium.

Um die Pivotzeile zu bestimmen, wird für jede Zeile, in der sich ein positiver Koeffizient in der Pivotspalte befindet, der Qutient aus dem Wert auf der rechten Seite und dem Koeffizienten der Pivotspalte gebildet.

Es wird die Zeile gewählt, in der der Quotient am kleinsten ist. In diesem Beispiel ist es die Zeile der zweiten Nebenbedingung, die Variable x₄ verlässt die Basis, d.h. sie nimmt den Wert null an.

Über diese Auswahlregel wird die Nichtnegativität der Variablen sichergestellt.

Eine ausführliche Betrachtung

Ausgeschrieben lautet die erste Nebenbedingung:

0,8·x₁+ 0,8·x₂ + x₃ =80

Ursprünglich sind x₁ und x₂ null, da es Nichtbasisvariablen sind. Nun soll x₂ erhöht werden, x₁ bleibt in dieser Iteration null und ist für die Betrachtung unerheblich.

0,8·x₂ + x₃ =80

Wie verhält sich der Wert von x₃ in Abhängigkeit von x₂? Durch Auflösen nach x₃ lässt sich das gut erkennen:

x₃ =80 - 0,8·x₂

Je größer x₂ ist, desto kleiner wird x₃. Um die Nichtnegativitätsbedingung zu erfüllen, darf x₃ aber nicht kleiner als null werden. Wie groß darf x₂ werden? 0 =80 - 0,8·x₂

x₂=80/0,8

x₂=100.

Vorstehendes ist nichts anderes als der oben gebildete Quotient. Da keine Variable negative Werte annehmen darf, wird das für jede Zeile geprüft. Die Zeile, die die kleinste Erhöhung zulässt, ist einschränkend. Die Schlupfvariable in dieser Zeile wird null und verlässt die Basis.

Für Zeilen in denen der Koeffizient in der Pivotspalte negativ bzw. null ist, braucht der Quotient nicht gebildet werden. Wird in einer Zeile mit negativem Koeffizient die Variable erhöht, steigt der Wert der Basisvariablen ebenfalls, ist der Koeffizient null besteht kein Einfluss.