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 Maximierungsproblem

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

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.

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

Multiple-Choice
Nachfolgend sehen Sie die Regeln für die Dualisierung eines primalen Problems. Eine der Regel ist jedoch nicht richtig. Welche?
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