Simplex-Verfahren

Beispielrechnung

Überführung in Gleichungen

Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt.Dazu führt man so genannte Schlupfvariablen y_A , y_B und y_C ein, welche die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Offensichtlich dürfen die Schlupfvariablen nicht negativ sein.Damit lässt sich das Problem so formulieren, dass man die Schlupfvariablen bezüglich der ursprünglichen Variablen freilegt. Ein derart genormtes Gleichungssystem heißt im Englischen dictionary (Benennung von V. Chvátal):

Maximiere die Zielfunktion z unter den Nebenbedingungen:

Die obigen Gleichungen kann man in das vorher beschriebene Simplex-Tableau übertragen:

----------------------------- | x₁ x₂ | rechte Seite --------------------------------- -z | 300 500 | 0 --------------------------------- y_A | 1 2 | 170 = b₁ y_B | 1 1 | 150 = b₂ y_C | 0 3 | 180 = b₃