wiwiweb
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research
Den Kurs kaufen für:
einmalig 29,00 €
Zur Kasse
Minimierungsprobleme > Zweiphasenmethode:

Dualer Simplex-Algorithmus

WebinarTerminankündigung aus unserem Online-Kurs Abgabenordnung:
 Am 08.12.2016 (ab 18:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar Diskrete und stetige Verteilungen in der Wahrscheinlichkeitsrechnung
- In diesem 60-minütigen Gratis-Webinar gehen wir darauf ein, welche diskreten und stetigen Verteilungen Sie in der Prüfung beherrschen müssen.
[weitere Informationen] [Terminübersicht]

Methode

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

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

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 ist minimal. Unter x1 liegt also 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 die 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

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

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 wird falsch

Methode

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 sodann x1 und x2 in die 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, d.h. 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 mit –15 als betragsmäßig größte (da einzige) negative Zahl die x2 -Zeile. 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 maximal 30 € auf nun 22,5 €, da eine Restriktion zusätzlich 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

Lösung eines Minimierungsproblems mit dem dualen Simplex-Algorithmus ohne Umwandlung in ein Maximierungsproblem.
Multiple-Choice
Bitte die richtigen Aussagen auswählen.
0/0
Lösen

Hinweis:

Bitte kreuzen Sie die richtigen Aussagen an. Es können auch mehrere Aussagen richtig oder alle falsch sein. Nur wenn alle richtigen Aussagen angekreuzt und alle falschen Aussagen nicht angekreuzt wurden, ist die Aufgabe erfolgreich gelöst.

Bild von Autor Daniel Lambert

Autor: Daniel Lambert

Dieses Dokument Dualer Simplex-Algorithmus ist Teil eines interaktiven Online-Kurses zum Thema Operations Research.

Dipl.-Math. Dipl.-Kfm. Daniel Lambert gibt seit vielen Jahren Kurse zur Prüfungsvorbereitung. Er unterrichtet stets orientiert an alten Prüfungen und weiß aus langjähriger Erfahrung, wie sich komplexe Sachverhalte am besten aufbereiten und vermitteln lassen. Daniel Lambert ist Repetitor aus Leidenschaft seit nunmehr 20 Jahren.
Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research

wiwiweb - Interaktive Online-Kurse (wiwiweb.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
  • Maximierungsprobleme
    • Einleitung zu Maximierungsprobleme
  • Beste Lösung, Graphische Lösung
    • Aufstellen des Problems
    • Graphische Darstellung des Maximierungsproblems
  • Analytische Lösung
    • Vorbereitung
    • Schlupfvariablen
    • Aufstellen des Ausgangstableaus
    • Der Simplex-Algorithmus
    • Simplex-Austausch-Schritt
    • Weiterer Simplex-Schritt und Interpretation des Optimaltableaus
  • Entartung
    • Mehrdeutigkeit
    • Degeneration
  • Sensitivitätsanalyse
    • Schwankungen Deckungsbeitragskoeffizienten
    • Änderungen der Restriktionen
  • Zweitbeste Lösung
    • Zweitbeste Lösung
  • Minimierungsprobleme
    • Einleitung zu Minimierungsprobleme
    • Zweiphasenmethode
      • Zweiphasenmethode
      • Beginn erste Phase
      • Beginn zweite Phase
      • Dualität
      • Dualer Simplex-Algorithmus
  • Transportproblem
    • Nordwest-Ecken-Methode
    • Matrix-Minimum-Methode
    • Stepping-Stone-Methode
  • 24
  • 18
  • 56
  • 6
einmalig 29,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research

    Ein Kursnutzer am 16.03.2015:
    "alles top"

  • Gute Bewertung für Operations Research

    Ein Kursnutzer am 02.12.2014:
    "Super Erklärungen in den Videos!"

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen