Dualität - Dualproblem in Primalproblem

Nachdem in den vorherigen Abschnitten gezeigt worden ist, wie man ein primales Problem in ein duales Problem umformt, muss noch gezeigt werden, wie das Dualproblem wieder in ein Primalproblem zurückgeführt wird. 

Das bedeutet ganz einfach, dass wenn ein duales Problem wieder dualisiert wird, so erhält man das primale System. Dies soll im Folgenden gezeigt werden. Gegeben sei das folgende primale Minimierungsproblem:

$f(x_1, x_2) = 5 x_1 + 8 x_2$      $\rightarrow$ min!

u.d.N.

$2x_1 + x_2 \ge 30$

$ x_1 + 3 x_2 \ge 10$

              $x_2 \ge 5$

$x_1, x_2 \ge 0$

Es handelt sich um das primale Minimierungsproblem aus dem vorherigen Abschnitt. Dort resultierte das dazu duale Maximierungsproblem zu:

$f(u_1, u_2, u_3) = 30 u_1 + 10u_2 + 5u_3 $   $\rightarrow$ max!

u.d.N.

$2 u_1 + u_2 +         \le 5$

$u_1 + 3 u_2 + 1 u_3 \le 8$

$u_1, u_2, u_3 \ge 0$

Dualisiert man das duale Maximierungsproblem, so erhält man wieder das primale Minimierungsproblem.

Es wird nun folgendermaßen vorgegangen:

Das duale System wird wieder als primales Problem behandelt. In diesem Fall als primales Maximierungsproblem. Da das primale Maximierungsproblem in Standardform vorliegt, kann direkt mit der Dualisierung begonnen werden. Die Dualsierung wird wie im Abschnitt Dualität - Primalproblem als Maximierungsproblem durchgeführt :

$A = \left( \begin{array}{ccc|c} 2 & 1 & 0 & 5 \\ 1 & 3 & 1 & 8 \\ 30 & 10 & 5 & 0 \end{array}\right)$  

Diese Matrix wird als nächstes transponiert, indem man aus den Zeilen Spalten macht:

$A^T = \left( \begin{array}{cc|c} 2 & 1 & 30 \\ 1 & 3 & 10 \\ 0 & 1 & 5 \\ 5 & 8 & 0 \end{array}\right)$

Es wird nun aus der neuen Matrix $A^T$ das duale Problem des Primalproblems abgelesen. Dabei werden nun die Variablen $x_i$ wieder eingeführt. Es werden hier außerdem die Dualisierungsregeln beachtet. 

1. Aus einem primalen Maximierungsproblem wird ein duales Minimierungsproblem. Die erste Zeile der neuen Matrix stellt wieder die Zielfunktion dar, diesmal muss diese aber wieder minimiert werden:

$f(x_1, x_2) = 5 x_1 + 8x_2 = 0$   $\rightarrow$ min!

Es ist deutlich zu erkennen, dass nun wieder zwei Variablen auftreten.

2. Aus einer Nichtnegativitätsbedingung $u_i \ge 0$ eines primalen Maximierungsproblems werden Größer/Gleich-Nebenbedingungen eines dualen Minimierungsproblems:

$2 x_1 + x_2 \ge  30$

$x_1 + 3 x_2 \ge 10$

           $x_2 \ge 5$

3. Aus einer Kleiner/Gleich-Nebenbedingung eines primalen Maximierungsproblems wird eine Nichtnegativitätsbedingung des dualen Minimierungsproblems:

$x_1, x_2 \ge 0$

Insgesamt ergibt sich das gesamte Problem zu:

$f(x_1, x_2) = 5 x_1 + 8x_2 = 0$   $\rightarrow$ min!

u.d.N.

$2 x_1 + x_2 \ge  30$

$x_1 + 3 x_2 \ge 10$

           $x_2 \ge 5$

$x_1, x_2 \ge 0$

Es ist deutlich zu erkennen, dass es sich hierbei wieder um das primale Minimierungsproblem handelt.