ZU DEN KURSEN!

Operations Research 1 - Dualität - Primalproblem als Minimierungsproblem

Kursangebot | Operations Research 1 | Dualität - Primalproblem als Minimierungsproblem

Operations Research 1

Dualität - Primalproblem als Minimierungsproblem

ingenieurkurse JETZT WEITER LERNEN!

Weitere Lernvideos sowie zahlreiche Materialien erwarten dich:
Komplettpaket für Ingenieurstudenten


3108 Lerntexte mit den besten Erklärungen

501 weitere Lernvideos von unseren erfahrenen Dozenten

5120 Übungen zum Trainieren der Inhalte

3108 informative und einprägsame Abbildungen

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.

Merke

Hier klicken zum Ausklappen

Man sieht deutlich, dass die Dualsierung eines Minimierungsproblems nur dann vorgenommen werden sollte, wenn danach ein Maximinierungsproblem in kanonischer Form resultiert, damit man sofort den primalen Simplexalgorithmus anwenden kann, weil die Dualisierung in jedem Fall länger dauert, als die Umformung. 


Gegeben sei das folgende Minimierungsproblem:

Methode

Hier klicken zum Ausklappen

minimiere    $f(x_1, x_2, ... , x_n) = c_1 x_1 + c_2 x_2 + ... c_n x_n = \sum_{j = 1}^n c_j x_j$  mit $c_j \ge 0$


u.d.N (unter den Nebenbedingungen)

$a_{ij} x_j + ... + a_{in} x_n \ge 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

Hier klicken zum Ausklappen

            minimiere $f(x) = c^Tx$

u.d.N.


$Ax \ge b$

$x \ge 0$

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:

Methode

Hier klicken zum Ausklappen

             maximiere $f(x) = b^Tu$

u.d.N.


$A^Tu \le c$

$u \ge 0$

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.
Dualität primales Minimierungsproblem in duales Maximierungsproblem

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

Merke

Hier klicken zum Ausklappen

Wichtig: Zur Dualsierung muss das primale Minimierungsproblem in der oben angegebenen Form vorliegen. Ist ein lineares Minimierungsprroblem nicht in dieser Form gegeben, so muss dieses vorher umgeformt werden, um dann die Dualisierung anzuwenden. Es muss sich also um ein primales Minimierungsproblem mit Größer/Gleich-Nebenbedingungen und Nichtnegativitätsbedingung für alle Variablen handeln.

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$

Hinweis

Hier klicken zum Ausklappen

Das Problem liegt in kanonischer Form vor (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung und die Werte der rechten Seite sind alle positiv), das bedeutet es kann als nächstes der primale Simplexalgorithmus angewandt werden um eine Optimallösung zu erhalten.

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$

Hinweis

Hier klicken zum Ausklappen

Es liegt hier die Standardform vor. Da negative Werte auf der rechten Seite vorhanden sind, ist die Nichtnegativitätsbedingung nicht erfüllt. Demnach wird zunächst der duale Simplexalgorithmus angewandt, bis eine zulässige Lösung vorliegt (Werte der rechten Seite sind alle positiv) und dann wird der primale Simplexalgorithmus angewandt, bis eine optimale Lösung vorliegt (Werte der Zielfunktionszeile sind alle positiv). Danach wird das Problem wieder in ein Minimierungsproblem dualisiert (folgender Abschnitt). Bei diesem Problem wäre es also sinnvoller gewesen gar nicht erst zu dualisieren, sondern eine Umformung vorzunehmen und dann den dualen Simplex anzuwenden, bis eine zulässige Lösung vorliegt und danach den primalen Simplex bis eine optimale Lösung vorliegt.