Jetzt neu: Steuerrecht online lernen auf steuerkurse.de!
ZU DEN KURSEN!

Operations Research - Dualer Simplex-Algorithmus

Kursangebot | Operations Research | Dualer Simplex-Algorithmus

Operations Research

Dualer Simplex-Algorithmus

wiwiweb JETZT WEITER LERNEN!

Weitere Lernvideos sowie zahlreiche Materialien erwarten dich:
Komplettpaket für wiwi-Studenten


1363 Lerntexte mit den besten Erklärungen

434 weitere Lernvideos von unseren erfahrenen Dozenten

3440 Übungen zum Trainieren der Inhalte

1282 informative und einprägsame Abbildungen

Merke

Hier klicken zum AusklappenDie Methoden des dualen Simplex-Algorithmus und der Dualität unterscheiden sind zueinander. 

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

Hier klicken zum AusklappenSCHEMA DUALER SIMPLEX-ALGORITHMUS:

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

Hier klicken zum AusklappenPrimaler Simplex-Algorithmus: Festlegung der Pivotspalte und danach Pivotzeile.
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

Hier klicken zum AusklappenPrimaler Simplex-Algorithmus: Jedes Tableau ist zulässig, jedoch ist nur das letzte optimal.
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

Hier klicken zum AusklappenDas Optimaltableau einer linearen Maximierungsaufgabe lautet:

 

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

Die neue Restriktion x1 + 2x2 ≤ 25 ist unmittelbar in das gegebene Optimaltableau einzufügen.

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

Hier klicken zum AusklappenWeshalb handelt es sich um eine falsche Darstellung?

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:

Video: Dualer Simplex-Algorithmus