ZU DEN KURSEN!

Operations Research - Dualer Simplex-Algorithmus

Kursangebot | Operations Research | Dualer Simplex-Algorithmus

Operations Research

Dualer Simplex-Algorithmus

x
Juracademy JETZT WEITER LERNEN!

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


1271 Lerntexte mit den besten Erklärungen

413 weitere Lernvideos von unseren erfahrenen Dozenten

3186 Übungen zum Trainieren der Inhalte

980 informative und einprägsame Abbildungen

Merke

Hier klicken zum Ausklappen Der duale Simplex-Algorithmus und die Dualität sind unterschiedliche Methoden! 

Lösen von Minimierungsproblemen

Bisher sind wir mit Minimierungsproblemen so verfahren, dass wir es durch Dualisierung in ein Maximierungsproblem verwandelt haben und dies dann mit dem Simplex-Algorithmus lösen konnten. Der duale Simplex-Algorithmus verzichtet auf diese Umwandlung.

Für ein gegebenes Minimierungsproblem mit ≥-Restriktionen betrachten wir folgendes

Methode

Hier klicken zum Ausklappen KOCHREZEPT DUALER SIMPLEX-ALGORITHMUS:

1. Vorbereitung

- multipliziere die Zielfunktionszeile mit –1

- erhalte damit ein Maximierungsproblem

- multipliziere die Restriktionen mit –1

- die ≥-Restriktionen kehren sich dadurch um zu ≤-Restriktionen

- behalte die Nichtnegativitätsbedingungen bei

2. Bestimme das Ausgangstableau

- schreibe die Restriktionen – wie gewohnt – in ein Simplex-Tableau

- die rechte Seite ist hierbei negativ

3. Bestimme die Pivotzeile

- suche den betragsmäßig größten negativen Wert auf der rechten Seite

4. Bestimme die Pivotspalte

- bilde die Quotienten aus dem jeweiligen Wert der Zielfunktionszeile und der zugehörigen Zahl aus der Pivotzeile

- berücksichtige hiebei ausschließlich negative Koeffizienten in der Pivotzeile

- wähle den größeren negativen Quotienten aus

5. Bestimme das Pivotelement

6. Basistausch

- mache alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements – zu null.

Also:

Merke

Hier klicken zum Ausklappen Beim gewöhnlichen – primalenSimplex-Algorithmus wird zunächst die Pivotspalte, dann die Pivotzeile festgelegt.
Beim dualen Simplex-Algorithmus verhält es sich genau umgekehrt: zuerst legt man die Pivotzeile, dann die Pivotspalte fest.

Wir rechnen den dualen Simplex-Algorithmus am Beispiel 1.4 durch.

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, aber nicht zulässiges Ausgangstableau

Man sieht, dass das Ausgangstableau beim dualen Simplex-Algorithmus optimal, aber nicht zulässig ist (denn die rechte Seite hat negative Einträge). Die Zielfunktionszeile hat lediglich negative Einträge und nullen. Optimalität ist dadurch gesichert.

Da –12 die betragsmäßig größte negative Zahl ist, liegt bei y2 die Pivotzeile. Die Quotienten lauten –10/(–3) = 3,33; –12/(–3) = 4. Der erste Quotient ist minimal und unter x1 liegt demnach die Pivotspalte. Das Pivotelement ist –3. Führe einen Simplex-Schritt durch und erhalte:

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

Danach ist die dritte Zeile Pivotzeile, denn die –2 ist die einzige negative (und also betragsmäßig größte) Zahl. Die Quotienten sind –2 : (–2) = 1 sowie (–10/3) : (–1/3) = 10. Minimal ist 1, also geht x2 in die Basis. Das nächste Simplex-Tableau ist dann:

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

Es fehlt noch ein Schritt, da noch eine negative Zahl auf der rechten Seite steht. Der einzige Quotient lautet (–3) : (–5/6) = 3,6. Die Variable y2 geht in die Basis. Das nächste Simplex-Tableau ist:

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

Man erhält die gleiche Lösung wie bei der Dualitätsbetrachtung:

x1 = 18/5, x2 = 4/5, y1 = y3 = 0, y2 = 6/5

Merke

Hier klicken zum Ausklappen Beim primalen Simplex-Algorithmus ist jedes Tableau zulässig, aber erst das letzte ist optimal.
Beim dualen hingegen ist jedes Tableau optimal, aber erst das letzte ist zulässig.

Der duale Simplex lässt sich auch dazu benutzen, eine zusätzliche Nebenbedingung im Tableau einzufügen. Dies sei an folgendem Beispiel erläutert:

Beispiel

Hier klicken zum Ausklappen Das 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

Füge die neue Restriktion x1 + 2x2 ≤ 25 unmittelbar in das vorliegende Optimaltableau ein. Ist das neue Tableau zulässig? Stelle die Zulässigkeit gegebenenfalls durch einen dualen Simplex-Schritt wieder her!

Es wäre falsch, die Restriktion x1 + 2x2 ≤ 25 als x1 + 2x2 + y4 = 25 zu schreiben und dies lediglich ins Tableau einzufügen als

 

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: Ledigliches Einfügen zusätzlicher Restriktion ist falsch

Methode

Hier klicken zum Ausklappen Warum ist diese Darstellung falsch?

Die Antwort liegt darin begründet, dass unterhalb der Basisvariablen nicht mehr lediglich Einheitsvektoren stehen.

Die richtige Idee, die neue Restriktion einzubringen, ist deshalb vielmehr, die Restriktion x1 + 2x2 + y4 = 25 in Abhängigkeit der vorhandenen Nichtbasisvariablen zu schreiben. Dadurch kommen die Basisvariablen nicht ins Spiel, d.h. ihre Vorfaktoren sind null und die Einheitsvektoren bleiben erhalten. Also nutzt man die vorhandenen Gleichungen in den ersten drei Zeilen des Tableaus aus, um die Strukturvariablen x1, x2 in Abhängigkeit von den vorhandenen Nichtbasisvariablen y1, y3, y6 zu schreiben:

(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

Wir setzen dann x1 und x2 in Zeile 4 ein:

x1 + 2x2 + y4 = 25 ‹=› (20 – y1) + 2·(10 + y1 – y3) + y4 = 25

                             ‹=› y1 + 40 – 2y3 + y6 = 25

                             ‹=› y1 – 2y3 + y6 = –15.

Die letzte Gleichung kann nun unmittelbar ins Optimaltableau eingeführt werden. Man beachte, dass y1 – 2y3 + y4 = –15 nichts anderes bedeutet als 0x1 + 0x2 + y1 – 2y3 + y4 = –15. Das heißt die vorhandenen Basisvariablen gehen mit null ein, die Einheitsvektoren unterhalb derselben bleiben bestehen. Dies zeigt die Darstellung im – nun korrekten – 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: Richtiges (!)  Einfügen zusätzlicher Restriktion

Unterhalb der alten Basisvariablen x1, x2, y2 stehen weiterhin Einheitsvektoren. Das Tableau ist optimal, denn es stehen nur negative Zahlen oder Nullen in der Zielfunktionszeile. Es ist hingegen nicht zulässig, da auf der rechten Seite mit –15 eine negative Zahl steht.

Ein optimales (aber unzulässiges) Tableau kann nun mit dem dualen Simplex-Algorithmus bearbeitet werden:

Pivotzeile ist die x2-Zeile mit –15 als betragsmäßig größter (da einziger) negativer Zahl. Der einzige zu betrachtende Quotient, da –2 die einzige negative Zahl in der Pivotzeile ist, lautet –1/(–2) = 0,5. Die Pivot-Spalte steht daher unter y3. Pivot-Element ist –2. Division der Pivot-Zeile durch –2 liefert:

 

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

Nun rechnet man

  • Zeile I ... nichts, da bereits null in der Pivot-Spalte steht

  • Zeile II ... II + IV = IIneu

  • Zeile III ... III – IV = IIIneu

  • ZF-Zeile .. ZF + IV = ZFneu

Es folgt:

 

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

Dieses Tableau ist zulässig und optimal. Der maximale Deckungsbeitrag sinkt von 30 € auf nun 22,5 €, da eine zusätzliche Restriktion an die Strukturvariablen x1 und x2 gestellt wurde und nun 10 – 2,5 = 7,5 ME weniger von x2 hergestellt werden.

Video zum Dualen Simplex-Algorithmus

Schauen wir uns abschließend ein Lernvideo zum dualen Simplex-Algorithmus an:

Video: Dualer Simplex-Algorithmus