Inhaltsverzeichnis
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
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
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
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:
Weitere interessante Inhalte zum Thema
-
Zweiphasenmethode
Vielleicht ist für Sie auch das Thema Zweiphasenmethode (Minimierungsprobleme) aus unserem Online-Kurs Operations Research interessant.
