ZU DEN KURSEN!

Operations Research - Aufstellen des Ausgangstableaus

Kursangebot | Operations Research | Aufstellen des Ausgangstableaus

Operations Research

Aufstellen des Ausgangstableaus

x
Juracademy JETZT WEITER LERNEN!

Weitere Lernvideos sowie zahlreiche Materialien für deine Prüfungsvorbereitung erwarten dich:
wiwiweb.de Flatrate


1272 Lerntexte mit den besten Erklärungen

412 weitere Lernvideos von unseren erfahrenen Dozenten

3121 Übungen zum Trainieren der Inhalte

516 informative und einprägsame Abbildungen

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

Video: Aufstellen des Ausgangstableaus

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:

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

Hierzu ist einiges an Erklärung notwendig:

Am oberen Rand der Tabelle stehen

Strukturvariablen, nämlich

  • x1, x2 und

Schlupfvariablen, nämlich

  • y1, y2, y3, y4

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: x1, x2 sind zunächst Nichtbasisvariablen , d.h. x1 = x2 = 0. Am Anfang des Simplex-Algorithmus betrachtet man diese Ausgangslösung. Die Zahlen (60, 150, 70, 12.500) = (y1, y2, y3, y4) am rechten Rand lassen sich wie folgt verstehen: man produziert zunächst weder Gut 1 noch Gut 2 (x1 = x2 = 0). Es könnten damit noch y1 = 60 ME beim ersten und y2 = 150 ME beim zweiten Gut abgesetzt werden. Auf der Maschine sind y3 = 70 Stunden frei, da nichts von den Produkten produziert wird. Auch die Arbeiter sind mit y4 = 12.500 „Freistunden“ komplett unausgelastet.

Video: Aufstellen des Ausgangstableaus

Wenn die zu optimierenden Variablen x1, x2 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.

Merke

Die Idee des Simplex-Algorithmus ist also die folgende: da die optimale Lösung meistens in einer Ecke liegt (mit Ausnahme der manchmal vorzufindenden Mehrdeutigkeit), werden die einzelnen Ecken abgeprüft und die Gewinne verglichen. Den zulässigen Bereich mit den Ecken und den zugehörigen Gewinnen sind man in Abb. 4.
Absuchen der Ecken des zulässigen Bereichs
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.

Wie 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.