Definition
Mit dem Simplex-Algorithmus konnte man folgendes Optimierungsproblem lösen: eine Zielfunktion wurde unter Nebenbedingungen (Beschränkungen) maximiert (zum Beispiel Gewinne oder Deckungsbeiträge).
Manchmal muss man aber eine Zielfunktion unter Nebenbedingungen minimieren (nicht maximieren; zum Beispiel Kosten, Zeit). Es gibt Zusammenhänge zwischen beiden, deshalb kann man aus einem Minimierungs- ein Maximierungsproblem machen (und dieses mit dem Simplex-Algorithmus lösen) – und umgekehrt.
Das lineare Ausgangsproblem nennt man primales Problem, das "ins Gegenteil überführte" dann duales Problem.
Beispiel
Wir nehmen das Maximierungsproblem aus dem Simplex-Beispiel und überführen es in ein duales Minimierungsproblem (um zu sehen, wie das geht; eigentlich haben wir ja bereits ein mit dem Simplexverfahren gut lösbares Optimierungsproblem).
Primales Problem
Das Maximierungsproblem war:
Maximiere Z(k, t) = 2k + 3t
unter den Nebenbedingungen:
k + t = 3
2k + 4t = 8
Duales Problem
Das daraus abgeleitete Minimierungsproblem ist:
Minimiere Zdual (x, y) = 3x + 8y
unter den Nebenbedingungen:
x + 2y >= 2
x + 4y >= 3
Dazu waren folgende Schritte notwendig:
Die Beschränkungen des primalen Problems (das waren 3 und 8) gehen als Koeffizienten in die "neue" Zielfunktion ein.
Die Koeffizienten des primalen Problems (die Werte, die in den Nebenbedingungen vor k und t standen) waren in Matrixschreibweise:
$$\begin{pmatrix}1 & 1 \\ 2 & 4 \end{pmatrix}$$
Transponiert man diese Matrix, ergibt sich:
$$\begin{pmatrix}1 & 2 \\ 1 & 4 \end{pmatrix}$$
Diese werden nun als Koeffizienten für die Nebenbedingungen genutzt; zugleich werden aus =-Ungleichungen nun >=-Ungleichungen (Minimierung statt Maximierung).
Die primalen Zielfunktionskoeffizienten (das waren 2 und 3) sind nun die Beschränkungen in den Nebenbedingungen des dualen Problems:
x + 2y >= 2
x + 4y >= 3
Als neue Variablennamen wurden hier x und y verwendet statt k und t, um deutlich zu machen, das das andere sind.
Würde man das so gefundene duale Problem nochmals entsprechend transformieren, ergäbe sich das Ausgangsproblem.
Fazit
- Jedes lineare Primalproblem (Maximierung) besitzt ein zugehöriges duales Problem (Minimierung) – und umgekehrt.
- Transformation: Die Koeffizienten der Nebenbedingungen werden transponiert; Zielfunktionskoeffizienten und Restriktionswerte tauschen ihre Rollen; ≤-Ungleichungen werden zu ≥-Ungleichungen.
- Der starke Dualitätssatz besagt: Im Optimum haben Primal- und Dualproblem identische Zielfunktionswerte.
- Praktischer Nutzen: Ein Minimierungsproblem lässt sich durch Überführung in das duale Maximierungsproblem mit dem Simplex-Algorithmus lösen.
Selbsttest: Duales Problem
Aufgabe: Duales Problem formulieren
Gegeben ist folgendes Primalproblem:
Maximiere Z = 4x1 + 6x2
unter den Nebenbedingungen:
x1 + x2 ≤ 5
2x1 + x2 ≤ 8
x1, x2 ≥ 0
- Formulieren Sie das zugehörige duale Minimierungsproblem.
- Erläutern Sie die Transformationsschritte.
Lösung
1. Duales Problem:
Minimiere Zdual = 5y1 + 8y2
unter den Nebenbedingungen:
y1 + 2y2 ≥ 4
y1 + y2 ≥ 6
y1, y2 ≥ 0
2. Transformationsschritte:
Schritt 1 – Zielfunktion: Die Restriktionswerte des Primalproblems (5 und 8) werden die Koeffizienten der dualen Zielfunktion.
Schritt 2 – Koeffizientenmatrix transponieren:
Primal: Zeilen [[1, 1], [2, 1]] → Dual-Spalten: [[1, 2], [1, 1]].
Schritt 3 – Beschränkungswerte: Die Zielfunktionskoeffizienten des Primalproblems (4 und 6) werden die Restriktionsgrenzen der dualen Nebenbedingungen.
Schritt 4 – ≤ wird zu ≥, Maximierung wird zu Minimierung.