Dualität - Primalproblem als Maximierungsproblem

In diesem Abschnitt wird zunächst das primale Maximierugsproblem aufgeführt und gezeigt, wie dieses in ein äquivalentes duales Minimierungsproblem umgeformt werden kann. Diese Umformung ist notwendig für z.B. die Anwendung der Ungarischen Methode, die ein Minimierungsproblem zum Gegenstand hat (die Ungarische Methode, auch Kuhn-Tucker-Bedingung, findet sich im späteren Abschnitt Zuordnungsprobleme).

Gegeben sein das folgende in Standardform gegebene lineare Maximierungsproblem:

maximiere    $f(x_1, x_2, ... , x_n) = c x_1 + c x_2 + ... c x_n = \sum_{j = 1}^n c_j x_j$ 

u.d.N (unter den Nebenbedingungen)

$a_{ij} x_j + ... + a_{in} x_n \le b_i$        $i = 1, ..., m$  und   $j = 1, ..., n$

$x_i \ge 0$                                       $j = 1, ..., n$

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

Will man das obige in Standardform gegebene Optimierungsproblem dualisieren, so nennt man dieses Ausgangsproblem auch primales Problem.

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

Dualisierungsregeln

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

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

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

Beispiel: Maximierungsproblem dualisieren

Gegeben sei das folgende Maximierungsproblem, welches dualisiert werden soll:

$f(x_1, x_2) = 15 x_1 + 25 x_2$      $\rightarrow$ max!

u.d.N.

$x_1 + x_2 \le 150$

$5 x_1 + 8 x_2 \le 80$

              $x_2 \le 70$

$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 geht am Besten so vor, dass man das primale Problem in eine Matrix schreibt:

$A = \left( \begin{array}{cc|c} \textcolor{red}{1} & \textcolor{red}{1} & \textcolor{red}{150} \\ 5 & 8 & 80 \\ 0 & 1 & 70 \\ 15 & 25 & 0 \end{array}\right)$

Die Zielfunktion wird in der letzten Zeile der Matrix berücksichtigt. Diese Matrix wird als nächstes transponiert,  indem man aus den Zeilen Spalten macht:

$A^T = \left( \begin{array}{ccc|c} \textcolor{red}{1} & 5 & 0 & 15 \\ \textcolor{red}{1} & 8 & 1 & 25 \\ \textcolor{red}{150} & 80 & 70 & 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 Maximierungsproblem wird ein Minimierungsproblem. Die letzte Zeile der neuen Matrix stellt wieder die Zielfunktion dar, diesmal muss diese aber minimiert werden:

$f(u_1, u_2, u_3) = 150 u_1 + 80 u_2 + 70 u_3 $   $\rightarrow$ min!

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

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

$ u_1 + 5u_2        \ge 15$

$u_1 + 8u_2 + u_3 \ge 25$

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

$u_1, u_2, u_3 \ge 0$

Insgesamt ergibt sich das gesamte Problem zu:

$f(u_1, u_2, u_3) = 150 u_1 + 80 u_2 + 70 u_3 $   $\rightarrow$ min!

u.d.N.

$ u_1 + 5u_2        \ge 15$

$u_1 + 8u_2 + u_3 \ge 25$

$u_1, u_2, u_3 \ge 0$