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