Zu transformieren sind die Gleichungen in ein sogenanntes Simplex-AusgangsTableau.
Das folgende Schema erhält man, wenn lediglich die Vorfaktoren der Gleichungen und die Variablen selbst an den obersten Rand der Tabelle eingetragen werden (ähnlich wie beim Gauß-Algorithmus).
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
y1 | 1 | 0 | 1 | 0 | 0 | 0 | 60 |
y2 | 0 | 1 | 0 | 1 | 0 | 0 | 150 |
y3 | 1 | 0,2 | 0 | 0 | 1 | 0 | 70 |
y4 | 150 | 50 | 0 | 0 | 0 | 1 | 12.500 |
ZF | 270 | 45 | 0 | 0 | 0 | 0 | 0 |
Tab. 1: Simplex-Ausgangstableau
Dazu sind einige Erklärungen nötig:
Die Strukturvariablen stehen am oberen Rand der Tabelle
x1, x2 und
die Schlupfvariablen
y1, y2, y3, y4
Zu optimieren sind die Strukturvariablen. Durch die Schlupfvariablen werden jeweils in jedem einzelnen der folgenden Simplex-Schritte die unausgenutzten Kapazitäten angegeben.
Die Werte der rechten Seite stehen ebenfalls in der Tabelle, welche die Restriktionen angeben.
Des Weiteren wird unterschieden zwischen den
Basisvariablen und
Nichtbasisvariablen.
Die Basisvariablen stehen am linken Rand des jeweiligen Schrittes. Diesen Termen wird im jeweiligen Simplex-Tableau keine null zugewiesen.
Dagegen wird von den Nichtbasisvariablen im jeweiligen Schritt eine null angenommen. Diese befindet sich nicht am linken, sondern nur am oberen Rand. Das bedeutet genau, dass x1, x2 vorerst Nichtbasisvariablen sind, d.h. x1 = x2 = 0.
Diese Ausgangslösung wird am Anfang des Simplex-Algorithmus betrachtet. Die Zahlen (60, 150, 70, 12.500) = (y1, y2, y3, y4) am rechten Rand lassen sich folgendermaßen verstehen: hergestellt wird vorerst weder Gut a noch Gut b (x1 = x2 = 0). Abgesetzt werden könnte damit noch y1 = 60 ME beim ersten und y2 = 150 ME beim zweiten Gut. Da keiner der Produkte produziert werden, ist demnach sowohl die Maschine mit y3 = 70 Stunden als auch die Arbeiter mit y4 = 12.500 Stunden an Kapazität gänzlich unausgelastet.
Im Falle dessen, dass die zu optimierenden Variablen x1, x2 vorerst null sind, ergibt sich ein Gewinn von G = 270·0 + 45·0 = 0. Es ist gleich der null rechts unten im Tableau. Der jeweilige Wert der Zielfunktion des Simplex-Schritts wird an dieser Stelle zumindest beitragsmäßig angegeben.
Merke
Wichtig bei der Entscheidung des Simplex-Algorithmus ist jedoch, dass nicht alle Ecken abgesucht werden, sondern die Suche nach gewissen Kriterien verläuft, solange das Ergebnis nicht zu verbessern ist. Die genauen Punkte sind hier F, E und D (in Abb. 4).
Methode
Woran ist zu erkennen, dass es sich bei dem gewählten Punkt F noch nicht um einen optimalen Punkt handelt?
Lösung:
Es ist noch nicht optimal, da noch positive Zahlen in der Zielfunktionszeile stehen (+ 270 und + 45). Die Optimallösung ist erst dann erreicht, wenn alle Zahlen im Simplex-Tableau null oder echt kleiner als null sind.
Weitere interessante Inhalte zum Thema
-
Beginn der zweiten Phase
Vielleicht ist für Sie auch das Thema Beginn der zweiten Phase (Minimierungsprobleme) aus unserem Online-Kurs Operations Research interessant.
-
Schwankungen Deckungsbeitragskoeffizienten
Vielleicht ist für Sie auch das Thema Schwankungen Deckungsbeitragskoeffizienten (Sensitivitätsanalyse) aus unserem Online-Kurs Operations Research interessant.
