Dualität - Primalproblem als Minimierungsproblem

In diesem Abschnitt wird nun gezeigt, wie man ein gegebenes Minimierungsproblem in ein äquivalentes Maximimierungsproblem dualisiert. Dies ist hilfreich, wenn man das primale Simplexverfahren anwenden möchte, aber ein Minimierungsproblem vorliegt. Das primale Simplexverfahren kann angewendet werden, wenn die kanonische Form vorliegt, d.h. ein Maximierungsproblem, kleiner/gleich-Nebenbedingungen, Nichtnegativitätsbedingung und positive Werte der rechten Seite. Das bedeutet also, dass das resultierende duale Maximierungsproblem in kanonischer Form vorliegen muss, um den primalen Simplexalgorithmus anwenden zu können.

Resultiert hingegen ein Maximierungsproblem, welches nicht in kanonischer Form vorliegt, aber in Standardform (Maximierungsproblem, Kleiner/Gleich-Bedingungen, Nichtnegativitätsbedingung) mit negativen Werten auf der rechten Seite, dann gibt es zwei Möglichkeiten:

1. Auf das duale Maximierungsproblem die Big-M-Methode oder das duale Simplexverfahren anwenden bis eine zulässige Lösung ermittelt wurde. Danach den primalen Simplexalgorithmus anwenden, um einen optimale Lösung zu erhalten.
   
   
2. Keine Dualisierung vornehmen und das Minimierungsproblem mittels Umformungsregeln in ein Maximierungsproblem umwandeln. Danach die Big-M-Methode oder den dualen Simplexalgorithmus anwenden bis eine zulässige Lösung vorliegt und danach den primalen Simplexalgorithmus, bis eine optimale Lösung vorliegt.

Gegeben sei das folgende Minimierungsproblem:

Mittels Matrixschreibweise lässt sich die Standardform kompakter schreiben zu:

Will man das obige Minimierungsproblem (Größer/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung) dualisieren, so nennt man dieses Ausgangsproblem auch primales Problem.

Zu diesem primalen Minimierungsproblem, existiert ein duales Maximierungsproblem mit der Form:

Dualisierungsregeln

Es sollen im Folgenden die Regeln für die Dualisierung eines primalen Minimierungsproblems aufgezeigt werden:

1. Ein primales Minimierungsproblem entspricht einem dualen Maximierungsproblem.
   
   
2. Eine $\ge$-Nebenbedingung im primalen Minimierungsproblem entspricht einer Nichtnegativitätsbedingung im dualen Maximierungsproblem.
   
   
3. Eine Nichtnegativitätsbedingung im primalen Minimierungsproblem entspricht einer $\le$-Nebenbedingung im dualen Maximierungsproblem.

Im Weiteren wird ein Beispiel aufgeführt, wie man ein primales Minimierungsproblem in ein duales Maximierungsproblem umformt.

Beispiel: Minimierungsproblem dualisieren

Gegeben sei das folgende Minimierungsproblem, welches dualisiert werden soll:

$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$

Die Dualisierung wird wie folgt vorgenommen:

Die Werte aus der Zielfunktion werden zu den Werten der rechten Seite. Die Werte der rechten Seite werden zu den Werten der Zielfunktion. Man sieht gleich, dass die Werte der Zielfunktion alle positiv sind und damit die Werte der rechten Seite des dualen Problems. Damit kann das Verfahren nach der Dualsierung mittels primalen Simplex gelöst werden.

Man geht am Besten so vor, dass man das primale Problem in eine Matrix schreibt:

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

Dabei werden die Zielfunktionskoeffizienten immer zuletzt in die Matrix geschrieben. Diese Matrix wird als nächstes transponiert, indem man aus den Zeilen Spalten macht:

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

Anhand der roten Markierung ist deutlich zu erkennen, dass aus der 1. Zeile die 1. Spalte des dualen Problems wird. Ebenso verfährt man mit allen weiteren Zeilen. 

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

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

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

Es ist deutlich zu erkennen, dass nun drei Variablen auftreten.

2. Aus einer Nichtnegativitätsbedingung $x_i \ge 0$ eines primalen Minimierungsproblems werden Kleiner/Gleich-Nebenbedingungen eines duales Maximierungsproblems:

$2 u_1 + u_2            \le 5$

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

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

$u_1, u_2, u_3 \ge 0$

Insgesamt ergibt sich das gesamte Problem 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$

Beispiel2: Minimierungsproblem dualisieren

Gegeben sei das folgende Minimierungsproblem, welches dualisiert werden soll:

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

u.d.N.

$4x_1 + 2x_2 + x_3 \ge 30$

$ 6x_1 + 4 x_2 + x_3 \ge 40$

              $x_2 \ge 12$

$x_1, x_2 \ge 0$

Die Dualisierung wird wie folgt vorgenommen:

Die Werte aus der Zielfunktion werden zu den Werten der rechten Seite. Die Werte der rechten Seite werden zu den Werten der Zielfunktion. Man sieht gleich, dass die Werte der Zielfunktion alle positiv sind und damit die Werte der rechten Seite des dualen Problems. Damit kann das Verfahren nach der Dualsierung mittels primalen Simplex gelöst werden.

Man geht am Besten so vor, dass man das primale Problem in eine Matrix schreibt:

$A = \left( \begin{array}{ccc|c} 4 & 2 & 1 & 30 \\ 6 & 4 & 1 & 40 \\ 0 & 1 & 0 & 12 \\ 5 & 8 & -1 & 0 \end{array}\right)$

Dabei werden die Zielfunktionskoeffizienten immer zuletzt in die Matrix geschrieben. Diese Matrix wird als nächstes transponiert, indem man aus den Zeilen Spalten macht:

$A^T = \left( \begin{array}{ccc|c} 4 & 6 & 0 & 5 \\ 2 & 4 & 1 & 8 \\ 1 & 1 & 0 & -1 \\ 30 & 40 & 12 & 0 \end{array}\right)$  

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

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

$f(u_1, u_2, u_3) = 30 u_1 + 40 u_2 + 12 u_3 $   $\rightarrow$ max!

Es ist deutlich zu erkennen, dass nun drei Variablen auftreten.

2. Aus einer Nichtnegativitätsbedingung $x_i \ge 0$ eines primalen Minimierungsproblems werden Kleiner/Gleich-Nebenbedingungen eines duales Maximierungsproblems:

$4 u_1 + 6u_2            \le 5$

$2u_1 + 4 u_2 +  u_3  \le 8$

$u_1 + u_2                \le -1$

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

$u_1, u_2, u_3 \ge 0$

Insgesamt ergibt sich das gesamte Problem zu:

$f(u_1, u_2, u_3) = 30 u_1 + 40 u_2 + 12 u_3 $   $\rightarrow$ max!

u.d.N.

$4 u_1 + 6u_2            \le 5$

$2u_1 + 4 u_2 +  u_3  \le 8$

$u_1 + u_2                \le -1$

$u_1, u_2, u_3 \ge 0$