Primales Simplexverfahren: 1. Simplexschritt

Im vorangegangenen Abschnitt wurde gezeigt, wie die Pivotspalte, die Pivotzeile und das Pivotelemet ausgewählt werden. In diesem Abschnitt sollen jetzt die Werte des neuen Tableaus bestimmt werden, nachdem die Basisvariable der Pivotzeile mit der Nichtbasisvariablen der Pivotspalte vertauscht worden ist. Das neue Tableau sieht nun zunächst wie folgt aus:

Ein Austauschschritt entspricht exakt einem Schritt beim Lösen eines linearen Gleichungssystems, bei dem man die Pivotzeile  nach der Variablen (hier: ) auflöst und dann  in die restlichen Gleichungen einsetzt.

Simplexschritt

Bei einem Austauschschritt berechnet sich das neue Simplextableau folgendermaßen:

Dort wo das Pivotelement stand wird der neue Wert bestimmt, indem der Kehrwert gebildet wird: .

Die neuen Werte in der Pivotzeile werden bestimmt, indem die alten Werte durch das Pivotelement dividiert werden. Dies gilt auch für den Wert der rechten Seite der Pivotzeile.

Die neuen Werte der Pivotspalte werden bestimmt, indem die alten Werte durch das Pivotelement dividiert und mit einem Minuszeichen versehen werden. Dies gilt auch für den neuen Wert der Zielfunktionszeile der Pivotspalte.

Die restlichen Werte werden bestimmt, indem von dem alten Wert das Produkt aus zugehörigem Element der Pivospalte und Pivotzeile dividiert mit dem Pivotelemet abgezogen wird.

Diese Rechenschritte müssen durchgeführt werden, damit das neue Tableau mit verbessertem Zielfunktionswert ermittelt werden kann.

Beispiel: Simplexschritt

Das ganze Vorgehen wird im Nachfolgenden anhand des Beispiels aus dem vorherigen Abschnitt aufgezeigt.

• Dort wo im alten Tableau das Pivotelement () stand, wird nun das neue Element ermittelt durch: 1/Pivotelement, d.h. also .
  
  
  
• Die neuen Elemente der Pivotzeile werden bestimmt indem die alten Elemente durch das Pivotelement dividiert werden: Neue Elemente = Alte Elemente/Pivotelement, z.B. .
  
  
  
• Die neuen Elemente der Pivotspalte werden bestimmt, indem die alten Elemente durch das Pivotelement dividiert werden und mit multipliziert werden: Neue Elemente = Alte Elemente/Pivotelement, z.B.

Es sind nun alle alten Element der Pivotzeile und Pivotspalte ausgetauscht worden. Es fehlen nun noch die restlichen Werte, diese werden wie folgt bestimmt:

Die Vorgehensweise ist wie folgt: 

.

Für diese restlichen Werte wird die Berechnung nochmals separat aufgeführt:

Basislösung

Aufgrund der Durchführung eines Simplexschrittes resultiert eine neue Basislösung. Dabei besitzen die Nichtbasisvariablen immer den Wert Null und und die Basisvariablen immer den Wert der rechten Seite: , und . 

Der Zielfunktionswert ist bei dieser zweiten Basislösung:

Der Zielfunktionswert hat sich demnach verbessert. Bei der ersten Basislösung besaß dieser noch den Wert null und ist nun nach einem Simplexschritt auf den Wert 3 angestiegen. Es handelt sich hierbei wieder um eine zulässige Basislösung, allerdings noch nicht um die optimale Basislösung, da noch ein negativer Wert in der Zielfunktionszeile steht (-1/4).