Inhaltsverzeichnis
Merke
Minimierungsprobleme Lösen
Bei Minimierungproblemen sind wir bislang so vorgegangen, dass diese mit Hilfe der Dualisierung in ein Maximierungsproblem umgewandelt wurde und folglich als Simplex-Algorithmus gelöst werden konnte. Bei dem dualen Simplex-Algorithmus wird auf diese Form der Umwandlung verzichtet.
Wir schauen uns für ein Minimierungsproblem mit ≥-Restriktionen folgendes an:
Methode
1. Vorbereitung
- die Zielfunktionszeile ist mit –1 zu multiplizieren
- daraus ergibt sich ein Maximierungsproblem
- die Restriktionen sind mit –1 zu multiplizieren
- die ≥-Restriktionen werden zu ≤-Restriktionen umgeformt
- die Nichtnegativitätsbedingungen werden dabei belassen
2. Bestimmung des Ausgangstableaus
- die Restriktionen sind, wie üblich, in ein Simplex-Tableau zu schreiben
- dabei ist die rechte Seite negativ
3. Bestimmung der Pivotzeile
- die betragsmäßig größten negativen Wert auf der rechten Seite sind dafür zu suchen
4. Bestimmung der Pivotspalte
- die Quotienten aus dem entsprechenden Wert der Zielfunktionszeile und der jeweiligen Zahl aus der Pivotzeile sind zu bilden.
- es sind nur die negativen Koeffizienten in der Pivotzeile zu berücksichtigen
- der größere negative Quotient ist auszuwählen
5. Bestimmung des Pivotelements
6. Basistausch
- mache alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements – zu null.
Demnach:
Merke
Dualer Simplex-Algorithmus: Festlegung der Pivotzeile und danach Pivotspalte
-> umgekehrt zum primalen Simplex-Algorithmus.
Der duale Simplex-Algorithmus wird am Beispiel 1.4 durchgerechnet:
BV | x1 | x2 | y1 | y2 | y3 | RHS |
y1 | -2 | -1 | 1 | 0 | 0 | -8 |
y2 | -3 | -3 | 0 | 1 | 0 | -12 |
y3 | -1 | -3 | 0 | 0 | 1 | -6 |
-Z | -10 | -12 | 0 | 0 | 0 | 0 |
Tab. 26: Optimales, jedoch nicht zulässiges Ausgangstableau
Es wird ersichtlich, dass das Ausgangstableau beim dualen Simplex-Algorithmus zwar optimal, jedoch nicht zuverlässig ist, aufgrund der negativen Einträge auf der rechten Seite. Die Zielfunktionszeile weist lediglich negative Einträge und nullen auf, wodurch eine Optimalität vorliegt.
Bei y2 liegt die Pivotzeile vor, denn –12 die betragsmäßig größte negative Zahl. Die Quotienten sind –10/(–3) = 3,33; –12/(–3) = 4. Der erste Quotient ist minimal. Die Pivotspalte liegt unter x1. Das Pivotelement ist –3.
Ein Simples-Schritt ist durchzuführen, woraus sich jenes ergibt:
BV | x1 | x2 | y1 | y2 | y3 | RHS |
y1 | 0 | 1 | 1 | -2/3 | 0 | 0 |
x1 | 1 | 1 | 0 | -1/3 | 0 | 4 |
ys | 0 | -2 | 0 | -1/3 | 1 | -2 |
-Z | 0 | -2 | 0 | -10/3 | 0 | 40 |
Tab. 27: Tableau nach erstem Simplex-Schritt
Da -2 die einzig negative Zahl und beitragsmäßig größte Zahl ist, ergibt sich als Pivotzeile die dritte Zeile. Die Quotienten betragen –2 : (–2) = 1 und (–10/3) : (–1/3) = 10. In die Basis geht x2, da 1 minimal ist.
Das neue Simplex-Tableau ist damit:
BV | x1 | x2 | y1 | y2 | y3 | RHS |
y2 | 0 | 0 | 1 | -5/6 | 1/2 | -1 |
x1 | 1 | 0 | 0 | -1/2 | 1/2 | 3 |
x2 | 0 | 1 | 0 | 1/6 | -1/2 | 1 |
-Z | 0 | 0 | 0 | -3 | -1 | 42 |
Tab. 28: Tableau nach zweitem Simplex-Schritt
Wegen der negativen Zahl auf der rechten Seite, ist noch ein weiterer Schritt vorzunehmen. Der einzige Quotient ist (–3) : (–5/6) = 3,6. In die Basis geht die Variable y2 ein. Ein weiteres Simplex-Tableau lautet:
BV | x1 | x2 | y1 | y2 | y3 | RHS |
y2 | 0 | 0 | -6/5 | 1 | -3/5 | 6/5 |
x1 | 1 | 0 | -3/5 | 0 | 1/5 | 18/5 |
x | 0 | 1 | 1/5 | 0 | -2/5 | 4/5 |
-Z | 0 | 0 | -18/5 | 0 | -14/5 | 45 |
Tab. 29: Endtableau dualer Simplex-Algorithmus
Die gleiche Lösung wie bei der Dualitätsbetrachtung kommt dabei heraus:
x1 = 18/5, x2 = 4/5, y1 = y3 = 0, y2 = 6/5
Merke
Dualer Simplex-Algorithmus: Jedes Tablau ist optimal, doch nur das letzte ist zulässig.
Eine zusätzliche Nebenbedingung im Tableau kann auch durch den dualen Simplex erfolgen.
Das kann am folgenden Beispiel verdeutlicht werden:
Beispiel
x1 | x2 | y1 | y2 | y3 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 20 |
y2 | 0 | 0 | 1 | 1 | -1 | 15 |
x2 | 0 | 1 | -1 | 0 | 1 | 10 |
-D | 0 | 0 | -3 | 0 | -1 | -30 |
Frage: Ist das neue Tableau zulässig?
Falls nicht, so ist die Zuverlässigkeit ggf. durch einen dualen Simplex-Schritt herzustellen!
Nicht richtig wäre es, die Restriktion x1 + 2x2 ≤ 25 als x1 + 2x2 + y4 = 25 einfach ins Tableau zu schreiben.
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 20 |
y2 | 0 | 0 | 1 | 1 | -1 | 0 | 15 |
x2 | 0 | 1 | -1 | 0 | 1 | 0 | 10 |
y4 | 1 | 2 | 0 | 0 | 0 | 1 | 25 |
-D | 0 | 0 | -3 | 0 | -1 | 0 | -30 |
Tab. 30: stumpfes Einfügen zusätzlicher Restriktionen ist nicht richtig
Methode
Die Antwort begründet sich in dem, dass unterhalb der Basisvariablen nicht mehr nur Einheitsvektoren enthalten sind.
Aus dem Grund wäre der richtige Weg, die Restriktion x1 + 2x2 + y4 = 25 in Abhängigkeit der vorhandenen Nichtbasisvariablen zu notieren. Die Basisvariablen bleiben dadurch außenvor. Somit sind ihre Vorfaktoren null und die Einheitsvektoren bleiben bestehen. Die gegebenen Gleichungen werden in den ersten drei Zeilen des Tableaus ausgenutzt, damit die Strukturvariablen x1, x2 in Abhängigkeit von den vorhandenen Nichtbasisvariablen y1, y3, y6 geschrieben werden können.
Zeile 1 aus Tab. 30: x1 + y1 = 20 ‹=› x1 = 20 – y1,
Zeile 3 aus Tab. 30: x2 – y1 + y3 = 10 ‹=› x2 = 10 + y1 – y3
Zeile 4 aus Tab. 30: x1 + 2x2 + y4 = 25
Es werden x1 und x2 in Zeile 4 eingesetzt:
x1 + 2x2 + y4 = 25 ‹=› (20 – y1) + 2·(10 + y1 – y3) + y4 = 25
‹=› y1 + 40 – 2y3 + y6 = 25
‹=› y1 – 2y3 + y6 = –15.
Dabei kann die letzte Gleichung direkt ins Optimaltableau eingesetzt werden. Zu beachten sei, dass y1 – 2y3 + y4 = –15 das selbe bedeutet wie: 0∙x1 + 0∙x2 + y1 – 2y3 + y4 = –15. Es heißt so viel wie, dass die vorhandenen Basisvariablen mit null eingehen und die Einheitsvektoren unterhalb bestehen bleiben.
Ersichtlich wird dies im Tableau:
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 20 |
y2 | 0 | 0 | 1 | 1 | -1 | 0 | 15 |
x2 | 0 | 1 | -1 | 0 | 1 | 0 | 10 |
y4 | 0 | 0 | 1 | 0 | -2 | 1 | -15 |
-D | 0 | 0 | -3 | 0 | -1 | 0 | -30 |
Tab. 31: Das richtige (!) Einfügen zusätzlicher Restriktion
Einheitsvektoren befinden sich weiterhin unterhalb der alten Basisvariablen x1, x2, y4. Da nur negative Zahlen oder Nullen in der Zielfunktionszeile stehen, ist das Tableau optimal. Aufgrund der -15 (negative Zahl) auf der rechten Seite, ist dieses jedoch nicht zulässig.
Das unzulässige Tableau kann des Weiteren mit dem dualen Simplex-Algorithmus überarbeitet werden:
Die x2-Zeile als Pivotzeile ist die betragsmäßig größte und einzige negative Zahl. Weil -2 die einzig negative Zahl in der Pivotzeile ist, lautete der zu betrachtende Quotient: –1/(–2) = 0,5. Deshalb steht die Pivot-Spalte unter y3. Das Pivot-Element ist –2. Bei der Division der Pivot-Zeile durch -2 kommt heraus:
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 20 |
y2 | 0 | 0 | 1 | 1 | -1 | 0 | 15 |
x2 | 0 | 1 | -1 | 0 | 1 | 0 | 10 |
y4 | 0 | 0 | -1/2 | 0 | 1 | -1/2 | 7,5 |
-D | 0 | 0 | -3 | 0 | -1 | 0 | -30 |
Tab. 32: Tableau nach erstem Pivotschritt
Gerechnet wird
Zeile I ... nichts, da schon null in der Pivot-Spalte steht
Zeile II ... II + IV = IIneu
Zeile III ... III – IV = IIIneu
ZF-Zeile .. ZF + IV = ZFneu
Es ergibt sich:
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 20 |
y2 | 0 | 0 | 1/2 | 1 | 0 | -1/2 | 22,5 |
x2 | 0 | 1 | -1/2 | 0 | 0 | 1/2 | 2,5 |
y3 | 0 | 0 | -1/2 | 0 | 1 | -1/2 | 7,5 |
-D | 0 | 0 | -3,5 | 0 | 0 | -1/2 | -22,5 |
Tab.: Zulässiges und optimales Tableau
Das vorliegende Tableau ist sowohl zulässig als auch optimal. Weil nun eine zusätzliche Restriktion an die Strukturvariablen x1 und x2 gestellt wurde und jetzt 10 – 2,5 = 7,5 ME weniger von x2 produziert werden, kommt es zu einer Senkung des Deckungsbeitrags von 30 € auf 22,5 €.
Video zum Dualen Simplex-Algorithmus
Zu guter Letzt ein Lernvideo zum dualen Simplex-Algorithmus:
Weitere interessante Inhalte zum Thema
-
Definition der Grenzrate der Substitution
Vielleicht ist für Sie auch das Thema Definition der Grenzrate der Substitution (Theorie der Haushaltsnachfrage) aus unserem Online-Kurs Mikroökonomie interessant.
-
Gleichungsverfahren - Mathematisches Verfahren
Vielleicht ist für Sie auch das Thema Gleichungsverfahren - Mathematisches Verfahren (Verrechnung der Kosten) aus unserem Online-Kurs Kosten- und Leistungsrechnung interessant.
