Jetzt neu: Steuerrecht online lernen auf steuerkurse.de!
ZU DEN KURSEN!

Operations Research - Dualität

Kursangebot | Operations Research | Dualität

Operations Research

Dualität

wiwiweb JETZT WEITER LERNEN!

Weitere Lernvideos sowie zahlreiche Materialien erwarten dich:
Komplettpaket für wiwi-Studenten


1362 Lerntexte mit den besten Erklärungen

430 weitere Lernvideos von unseren erfahrenen Dozenten

3440 Übungen zum Trainieren der Inhalte

1334 informative und einprägsame Abbildungen

Wir haben bislang das Maximierungsprobleme mit „≤“-Restriktionen thematisiert, wodurch sich diese Definition ergab: 
Man kann von einem Primalproblem in Normalform sprechen, wenn die Aufgabe wie folgt aussieht:

x1 ... xn

a11 ... a1n ≤ b1

⋮ ⋮ ⋮

am1 ... amn ≤ bm

c1 ... cn → max!

X1, ..., xn ≥ 0.

Merke

Hier klicken zum AusklappenCharakteristisch für die Normalform sind: Restriktionen, Nichtnegativitätsbedingungen und ein Maximierungsproblem. 

Es grenzt sich präzise vom sog. Dualproblem ab:

u1 ... un

a11 ... a1n ≥ c1

⋮ ⋮ ⋮

am1 ... amn ≥ cn

b1 ... bm →  min!

b1, ..., bm ≥ 0.

Demnach wird die Koeffizientenmatrix transportiert. Aus den Zeilen des Primalproblems werden Spalten des Dualproblems.

Expertentipp

Hier klicken zum AusklappenFolgende Punkte sind zentral:

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

Dualvariablen uj werden optimiert, im Gegensatz zu den Primalvariablen xi 

  • die Optimierungsrichtung ändert sich (kehrt um)
     
  • zur rechten Seite des Dualproblems werden die Zielfunktionskoeffizienten cj des Primalproblems 
     
  • zu den Zielfunktionskoeffizienten des Dualproblems werden die Werte der rechten Seite bi des Primalproblems
     
  • die Schlupfvariablen des Dualproblems sind die Strukturvariablen des Primalproblems
     
  • die Nichtbasisvariablen des Dualproblems sind die Basisvariablen des Primalproblems
     
  • es kommt zur Veränderung der Restriktionen: von ≤-Restriktionen im Primalproblem werden ≥-Bedingungen im Dualproblem
     
  • die Anorndung der Koeffizienten im Primalproblem ändert sich hinsichtlich jener im Dualproblem. Somit werden Zeilen zu Spalten und umgekehrt.
     
  • den Nichtnegativitätsbedingungen unterliegen sowohl Primalvariablen xi als auch Dualvariablen uj

    An dem folgenden Beispiel (aus 1.3) lässt sich die Dualität veranschaulichen:

Beispiel

Hier klicken zum AusklappenSchauen wir uns das Problem an:

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

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

Die Lösung ist mit der Dualität und dem dualen Simplex-Algorithmus zu bestimmen.

Beschäftigen wir uns vorerst mit der Dualität. Das folgende Primalproblem liegt vor:

2x1 + x2 ≥ 8

3x1 + 3x2 ≥ 12

x1 + 3x2 ≥ 6

10x1, 12x2 → min!

mit x1, x2 ≥ 0.

Ausgedrückt in der Matrixschreibweise:

218
3312
136
1012

Dagegen ist das Dualproblem:

2y1 + 3y2 + y3 ≤ 10

y1 + 3y2 + 3y3 ≤ 12

8y1 + 12y2 + 6y3 → max!

Ausgedrückt in der Matrixschreibweise:

23110
13312
8126

mit y1, y2, y3 ≥ 0

Durch das Lösen des Dualproblems kann auf das Primalproblem geschlossen werden:

2y1 + 3y2 + y3 + x1 = 10

y1 + 3y2 + 3y3 + x2 = 12

8y1 + 12y2 + 6y3 → max!

x1 und x2 bilden hierbei die Schlupfvariablen. Strukturvariablen hingegen sind im Dualproblem y1, y2 und y3. Es ergibt sich das folgende 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

Das Dualproblem kann durch den Simplex-Algorithmus gelöst werden. 
Das zweite, dritte und vierte Tableau lautet:

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

Es folgt 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 letzendlich...

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

Schlussendlich können die Optimalwerte abgelesen werden, wodurch sich x1 = 18/5, x2 = 4/5, y1 = y3 = 0, y2 = 6/5 ergibt.

Zu berücksichtigen sind nochmals die umgekehrten Rollen von Basis- und Nichtbasisvariablen. Die xi – im Dualproblem Schlupf- und dann (im Endtableau) Nichtbasisvariablen – werden im Primalproblem Struktur- und dann Basisvariablen. Aus dem Grund können die Werte in der Zielfunktionszeile abgelesen werden. Dagegen sind die Variablen y1 und y3 – im Dual Struktur- und schließlich Basisvariablen, im Primalproblem Schlupf- und Nichtbasisvariablen, vom Wert null.

Video zur Dualität

Dieses Lernvideo beschreibt nochmals die Dualität:

Video: Dualität