Aufstellen des Ausgangstableaus

Die Gleichungen lassen sich in ein sogenanntes Simplex-AusgangsTableau transformieren.

Wenn man lediglich die Vorfaktoren der Gleichungen einträgt und die Variablen selbst an den oberen Rand der Tabelle – wie man es beispielsweise vom Gauß-Algorithmus her kennt – erhält man folgendes Schema:

Hierzu ist einiges an Erklärung notwendig:

Am oberen Rand der Tabelle stehen

Strukturvariablen, nämlich

• x₁, x₂ und

Schlupfvariablen, nämlich

• y₁, y₂, y₃, y₄

Die Strukturvariablen sind zu optimieren, die Schlupfvariablen geben jeweils – in jedem einzelnen der gleich folgenden Simplex-Schritte – die nicht ausgenutzte Kapazität an.

Darüber hinaus stehen die Werte der rechten Seite mit in der Tabelle. Sie geben die Restriktionen an.

Weiterhin unterscheidet man

• Basisvariablen und

• Nichtbasisvariablen.

Am linken Rand stehen die Basisvariablen des jeweiligen Schrittes. Dies sind jene Terme, denen im jeweiligen Simplex-Tableau keine null zugewiesen wird.

Nichtbasisvariablen hingegen nehmen im jeweiligen Schritt eine null an. Sie stehen nicht am linken, sondern lediglich am oberen Rand. Das heißt hier konkret: x₁, x₂ sind zunächst Nichtbasisvariablen, d.h. x₁ = x₂ = 0. Am Anfang des Simplex-Algorithmus betrachtet man diese Ausgangslösung. Die Zahlen (60, 150, 70, 12.500) = (y₁, y₂, y₃, y₄) am rechten Rand lassen sich wie folgt verstehen: man produziert zunächst weder Gut 1 noch Gut 2 (x₁ = x₂ = 0). Es könnten damit noch y₁ = 60 ME beim ersten und y₂ = 150 ME beim zweiten Gut abgesetzt werden. Auf der Maschine sind y₃ = 70 Stunden frei, da nichts von den Produkten produziert wird. Auch die Arbeiter sind mit y₄ = 12.500 „Freistunden“ komplett unausgelastet.

Wenn die zu optimierenden Variablen x₁, x₂ zunächst null sind, dann resultiert auch ein Gewinn von G = 270·0 + 45·0 = 0. Dies entspricht der null im Tableau rechts unten. An dieser Stelle wird – zumindest betragsmäßig – der jeweilige Wert der Zielfunktion des jeweiligen Simplex-Schritts angegeben.

Abb. 4: Absuchen der Ecken des zulässigen Bereichs

Entscheidend beim Simplex-Algorithmus ist allerdings, dass nicht alle Ecken abgesucht werden, sondern dass man – nach gewissen Kriterien – solange sucht, wie das Ergebnis noch verbessert wird: Hier also konkret die Punkte (F), (E) und schließlich (D) der Abb. 4.

Woran sieht man, dass der gewählte Punkt – hier (F) – noch nicht optimal ist? Die Antwort lautet: weil noch positive Zahlen in der Zielfunktionszeile stehen, nämlich + 270 und + 45. Erst wenn alle Zahlen im Simplex-Tableau null oder echt kleiner als null sind, hat man die Optimallösung gefunden.