ZU DEN KURSEN!

Operations Research - Aufstellung des Ausgangstableaus

Kursangebot | Operations Research | Aufstellung des Ausgangstableaus

Operations Research

Aufstellung des Ausgangstableaus

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

Hier klicken zum AusklappenHinter dem Simplex-Algorithmus steckt die Idee, dass die einzelnen Ecken geprüft und die Gewinne vergleichen werden, da die optimale Lösung meist in einer Ecke liegt (außer bei einer vorhandenen Mehrdeutigkeit). In der Abb. 4 sieht man den zulässigen Bereich mit den Ecken und den entsprechenden Gewinnen.
Absuchen der Ecken des zulässigen Bereichs
Abb. 4: Absuchen der Ecken des zulässigen Bereichs

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

Hier klicken zum Ausklappen

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.