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

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