Duales Problem
Duales Problem Definition
Mit dem Simplex-Algorithmus konnte man folgendes Optimierungsproblem lösen: eine Zielfunktion wurde unter Nebenbedingungen (Beschränkungen) maximiert.
Manchmal muss man aber eine Zielfunktion unter Nebenbedingungen minimieren (nicht maximieren; z.B. 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
Beispiel: duales Problem
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.