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


1277 Lerntexte mit den besten Erklärungen

417 weitere Lernvideos von unseren erfahrenen Dozenten

3269 Übungen zum Trainieren der Inhalte

1080 informative und einprägsame Abbildungen

Bisher haben wir Maximierungsprobleme mit „≤“-Restriktionen kennengelernt. Dies führt zu folgender 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 AusklappenDie 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 AusklappenEs sind einige Punkte erwähnenswert:

statt der Primalvariablen xi werden nun die Dualvariablen uj optimiert.
Aus dem Maximierungs- wird ein Minimierungsproblem. Das heißt:

  • die Optimierungsrichtung kehrt sich um
     
  • die Zielfunktionskoeffizienten cj des Primalproblems werden zur rechten Seite des Dualproblems
     
  • die Werte der rechten Seite bi des 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 aus 1.3 kennen.

Beispiel

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

2x1 + x2 ≥ 8

3x1 + 3x2 ≥ 12

x1 + 3x2 ≥ 6

10x1, 12x2 → min!

mit x1, x2 ≥ 0.

In Matrixschreibweise:

218
3312
136
1012

Das Dualproblem hingegen ist

2y1 + 3y2 + y3 ≤ 10

y1 + 3y2 + 3y3 ≤ 12

8y1 + 12y2 + 6y3 → max!

In Matrixschreibweise:

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

dann folgt

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 in der Zielfunktionszeile ablesbar. 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