ZU DEN KURSEN!

Operations Research - Dualität - Primalproblem als Maximierungsproblem

Kursangebot | Operations Research | Dualität - Primalproblem als Maximierungsproblem

Operations Research

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:

Methode

            maximiere $f(x) = c^Tx$

u.d.N.


$Ax \le b$

$x \ge 0$

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:

Methode

             minimiere $f(x) = b^Tu$

u.d.N.


$A^Tu \ge c$

$u \ge 0$

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.
Dualisierung - primales Maximierungsproblem in duales Minimierungsproblem

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

Merke

Wichtig: Zur Dualsierung muss das primale Maximierungsproblem in Standardform gegegeben sein! Ist ein lineares Optimierungsproblem nicht in Standardform gegeben, so muss dieses vorher in diese umgeformt werden, um dann die Dualisierung anzuwenden. Eine Standardform liegt vor, wenn es sich um ein Maximierungsproblem handelt, mit Kleiner/Gleich-Nebenbedingungen und Nichtnegativitätsbedingung für alle Variablen. Die Werte der rechten Seite dürfen dabei auch negative Werte annehmen. Von einem kanonischen Problem ist die Rede, wenn das LP in Standardform gegeben ist und die Werte der rechten Seite alle positive Werte aufweisen.

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$