ZU DEN KURSEN!

Operations Research - Dualität

Kursangebot | Operations Research | Dualität

Operations Research

Dualität

x
Juracademy JETZT WEITER LERNEN!

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


1272 Lerntexte mit den besten Erklärungen

412 weitere Lernvideos von unseren erfahrenen Dozenten

3121 Übungen zum Trainieren der Inhalte

516 informative und einprägsame Abbildungen

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

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

Expertentipp

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

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