ZU DEN KURSEN!

Operations Research - Dualität - Dualproblem in Primalproblem

Kursangebot | Operations Research | Dualität - Dualproblem in Primalproblem

Operations Research

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. 

Merke

Die Dualisierung eines dualen Problems führt wieder auf das primale System.

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$

Merke

Es soll darauf hingewiesen werden, dass es sich hierbei zwar um eine zulässige Lösung handelt, da die Werte der rechten Seite alle positiv sind, jedoch nicht um die Optimallösung. Erst nach Anwendung des primalen Simplexalgorithmus ergibt sich die Optimallösung. Die Durchführung des Simplexalgorithmus soll hier nicht durchgeführt werden. Stattdessen wird dieses duale Problem wieder in das primale Problem umgewandelt.

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.