ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Lineare Programmierung > Minimierungsproblem:

Dualität - Primalproblem als Minimierungsproblem

WebinarTerminankündigung aus unserem Online-Kurs Thermodynamik:
 Am 13.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Thermodynamik) Innere Energie, Wärme, Arbeit
- Innerhalb dieses 60-minütigen Webinares wird der 1. Hauptsatz der Thermodynamik für geschlossene Systeme behandelt und auf die innere Energie, Wärme und Arbeit eingegangen.
[weitere Informationen] [Terminübersicht]

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

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

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

            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

             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

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.

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

Wichtig

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.

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

Wichtig

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. 

Video: Dualität - Primalproblem als Minimierungsproblem

In diesem Abschnitt wird nun gezeigt, wie man ein gegebenes Minimierungsproblem in ein äuivalentes Maximimierungsproblem dualsiert. Dies ist hilfreich, wenn man die Simplexverfahren (primales, duales, Big-M-Methode) anwenden möchte und ein Minimierungsproblem vorliegt. Da die Simplexverfahren auf Maximierungsprobleme ausgerichtet sind, kann man mit Hilfe der Dualsisierung diese Verfahren anwenden, um eine Optimallösung zu erhalten.

Video: Dualität - Primalproblem als Minimierungsproblem

In diesem Abschnitt wird nun gezeigt, wie man ein gegebenes Minimierungsproblem in ein äuivalentes Maximimierungsproblem dualsiert. Dies ist hilfreich, wenn man die Simplexverfahren (primales, duales, Big-M-Methode) anwenden möchte und ein Minimierungsproblem vorliegt. Da die Simplexverfahren auf Maximierungsprobleme ausgerichtet sind, kann man mit Hilfe der Dualsisierung diese Verfahren anwenden, um eine Optimallösung zu erhalten.

Video: Dualität - Primalproblem als Minimierungsproblem

In diesem Abschnitt wird nun gezeigt, wie man ein gegebenes Minimierungsproblem in ein äuivalentes Maximimierungsproblem dualsiert. Dies ist hilfreich, wenn man die Simplexverfahren (primales, duales, Big-M-Methode) anwenden möchte und ein Minimierungsproblem vorliegt. Da die Simplexverfahren auf Maximierungsprobleme ausgerichtet sind, kann man mit Hilfe der Dualsisierung diese Verfahren anwenden, um eine Optimallösung zu erhalten.
Multiple-Choice
Welche der folgenden Aussagen zur Dualisierung eines primalen Minimierungsproblems sind richtig?
0/0
Lösen

Hinweis:

Bitte kreuzen Sie die richtigen Aussagen an. Es können auch mehrere Aussagen richtig oder alle falsch sein. Nur wenn alle richtigen Aussagen angekreuzt und alle falschen Aussagen nicht angekreuzt wurden, ist die Aufgabe erfolgreich gelöst.

Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen