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:

Dualität

WebinarTerminankündigung aus unserem Online-Kurs Volks- und Betriebswirtschaft:
 Am 12.01.2017 (ab 18:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar Grundbegriffe der Bilanzierung
- In diesem 60-minütigen Gratis-Webinar gibt Daniel Lambert einen Überblick über die zentralen Begriffe der Bilanzierung - hier im Besonderen dem Bilanzausweis.
[weitere Informationen] [Terminübersicht]

Bisher haben wir Maximierungsprobleme mit „≤“-Restriktionen kennengelernt. Dies führt auf folgende Definition:

Ein Primalproblem in Normalform liegt vor, wenn die Aufgabe folgende Gestalt hat:

x1 ... xn

a11 ... a1n ≤ b1

⋮ ⋮ ⋮

am1 ... amn ≤ bm

c1 ... cn → max!

X1, ..., xn ≥ 0.

Merke

Die Normalform zeichnet sich also aus durch

• Restriktionen,
• ein Maximierungsproblem
• Nichtnegativitätsbedingungen

Streng abzugrenzen ist dies vom sogenannten Dualproblem:

u1 ... un

a11 ... a1n ≥ c1

⋮ ⋮ ⋮

am1 ... amn ≥ cn

b1 ... bm →  min!

b1, ..., bm ≥ 0.

Die Koeffizientenmatrix wird also transponiert. Zeilen des Primalproblems werden zu Spalten des Dualproblems.

Es sind einige Punkte erwähnenswert:

statt der Primalvariablen xi werden nun die Dualvariablen uj optimiert
aus dem Maximierungs- wird ein Minimierungsproblem, d.h.
  • die Optimierungsrichtung kehrt sich um
     
  • die Zielfunktionskoeffizienten cj des Primalproblems werden zur rechten Seite des Dualproblems
     
  • die rechte Seite bides Primalproblems werden zu den Zielfunktionskoeffizienten des Dualproblems
     
  • die Strukturvariablen des Primalproblems sind die Schlupfvariablen des Dualproblems
     
  • die Basisvariablen des Primalproblems sind die Nichtbasisvariablen des Dualproblems
     
  • aus≤-Restriktionen im Primalproblem werden ≥-Bedingungen im Dualproblem
     
  • die Anordnung der Koeffizienten im Primalproblem ist umgekehrt zu jener im Dualproblem, d.h. aus Zeilen werden Spalten und aus Spalten werden Zeilen
     
  • sowohl Primalvariablen xi als auch Dualvariablen uj unterliegen den Nichtnegativitätsbedingungen.
     
    Die Dualität sei exemplarisch an folgendem Beispiel erläutert, das wir schon als 1.3 kennen.

Beispiel

Wir betrachten das Problem

2x1 + x2 ≥ 8
3x1 + 3x2 ≥ 12
x1 + 3x2 ≥ 6
x1, x2 ≥ 0.

Die Zielfunktion ist K: 10x1 + 12x2 → min!

Bestimme die Lösung mit
- der Dualität
- dem dualen Simplex-Algorithmus.

Gehen wir zunächst auf die Dualität ein. Das Primalproblem lautet in Matrixschreibweise

2x1 + x2 ≥ 8

3x1 + 3x2 ≥ 12

x1 + 3x2 ≥ 6

10x1, 12x2 → min!

mit x1, x2 ≥ 0.

Matrixschreibweise:

218
3312
136
1012

Das Dualproblem hingegen ist

2y1 + 3y2 + y3 ≤ 10

y1 + 3y2 + 3y3 ≤ 12

8y1 + 12y2 + 6y3 → max!

23110
13312
8126

mit y1, y2, y3 ≥ 0

Wir lösen das Dualproblem und können auf das Primalproblem zurückschließen.

2y1 + 3y2 + y3 + x1 = 10

y1 + 3y2 + 3y3 + x2 = 12

8y1 + 12y2 + 6y3 → max!

x1 und x2 sind hier Schlupfvariablen. Strukturvariablen hingegen sind im Dualproblem y1, y2 und y3. Man erhält folgendes Ausgangstableau:

BV

y1

y2

y3

x1

x2

RHS

x1

2

3

1

1

0

10

x2

1

3

3

0

1

12

-Z

8

12

6

0

0

0

Tab. 22: Ausgangstableau des Dualproblems

Mit dem gewöhnlichen Simplex-Algorithmus wird nun das Dualproblem gelöst. Zweites, drittes und viertes Tableau lauten folgendermaßen:

BV

y1

y2

y3

x1

x2

RHS

y2

2/3

1

1/3

1/3

0

10/3

x2

-1

0

2

-1

1

2

-Z

0

0

2

-4

0

-40

Tab. 23: Zweites Tableau der Dualität

und dann

BV

y1

y2

y3

x1

x2

RHS

y2

5/6

1

0

1/2

-1/6

3

y3

-1/2

0

1

-1/2

1/2

1

-Z

1

0

0

-3

-1

-42

Tab. 24: Drittes Tableau der Dualität

und schließlich

BV

y1

y2

y3

x1

x2

RHS

y2

1

6/5

0

3/5

-1/5

18/5

y3

0

3/5

1

-1/5

2/5

14/5

-Z

0

-6/5

0

-18/5

-4/5

-45 - 3/5

Tab. 25: Optimaltableau der Dualität

Schließlich können somit Optimalwerte abgelesen werden. Man erhält

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

Man beachte nochmals die vertauschten Rollen von Basis- und Nichtbasisvariablen. Die xi– im Dualproblem Schlupf- und schließlich (im Endtableau) Nichtbasisvariablen, werden im Primalproblem Struktur- und schließlich Basisvariablen. Daher sind ihre Werte ablesbar in der Zielfunktionszeile. Die Variablen y1 und y3 hingegen – im Dual Struktur- und schließlich Basisvariablen, sind im Primalproblem Schlupf- und Nichtbasisvariablen, daher vom Wert her null.

Video zur Dualität

Schauen wir uns nun ein Lernvideo zur Dualität an:

Video: Dualität

Lösung eines Dualproblems durch Transportation der Koeffizientenmatrix des Primalproblems anhand eines ausführlichen Beispiels.
Lückentext
Bitte die Lücken im Text sinnvoll ausfüllen.

Um vom Primalproblem zum Dualproblem zu gelangen, wird die  transponiert.

0/0
Lösen

Hinweis:

Bitte füllen Sie alle Lücken im Text aus. Möglicherweise sind mehrere Lösungen für eine Lücke möglich. In diesem Fall tragen Sie bitte nur eine Lösung ein.

Bild von Autor Daniel Lambert

Autor: Daniel Lambert

Dieses Dokument Dualität 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