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 > Standardform: Maximierungsproblem > Simlpex-Algorithmus: Einführung:

Duales Simplexverfahren

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 soll gezeigt werden, wie das duale Simplexverfahren angewandt werden kann. Das duale Simplexverfahren wird dann angewandt, wenn das Optimierungsproblem nicht in kanonischer Form gegeben ist bzw. sich schwer in diese Form umformen lässt.

Merke

Das lineare Optimierungsmodell liegt in kanonischer Form vor, wenn die Werte der rechten Seite alle positiv sind $b_i \ge 0$ und die Standardform (Maximierungsproblem, kleiner-gleich-Nebenbedingungen, Nichtnegativitätsbedinung) vorliegt. 

Liegt das lineare Optimierungsmodell in kanonischer Form vor, so existiert bereits zu Beginn des Simplexverfahrens eine zulässige Basislösung und es kann das primale Simplexverfahren angewandt werden. In diesem Abschnitt soll nun aber das lineare Optimierungsmodell nicht in kanonischer Form vorliegen. Das bedeutet also, dass keine zulässige Basislösung vorliegt. Ist dies der Fall, so muss das duale Simplexverfahren oder die Big-M-Methode (siehe spätere Abschnitte) angewandt werden.

Methode

Voraussetzung für die Anwendung des dualen Simplex-Verfahrens:

  1. Es muss die Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung)

  2. Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.

  3. Es liegen negative Koeffizienten auf der Rechten-Seite der Nebenbedingungen vor ($b_i \le 0$).

Es wird im folgenden anhand eines Beispiels gezeigt, wie bei dem dualen Simplexverfahren vorgegangen wird.

Gegeben sei das folgende Optimierungsproblem

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

u.d.N.

$x_1 + x_2 \ge 8$

$3x_1 + x_2 \ge 12$

$x_1 + x_2 \le 10$

$x_1, x_2 \ge 0$

Das Optimierungsmodell liegt noch nicht in Standardform vor (größer-gleich-Nebenbedingungen vorhanden). Es muss also zunächst in diese transformiert werden. Eine größer-gleich-Nebenbedinung wird ein eine kleiner-gleich-Nebenbedingung transformiert, indem diese mit $-1$ multipliziert wird:

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

u.d.N.

$-x_1 - x_2 \le -8$

$-3x_1 - x_2 \le -12$

$x_1 + x_2 \le 10$

$x_1, x_2 \ge 0$

Das Optimierungsmodell liegt nun in Standardform vor (Maximierungsproblem, kleiner-gleich-Bedingungen, Nichtnegativitätsbedingung). Allerdings sind hier die Werte der rechten Seite nicht alle positiv, weshalb keine zulässige 1. Basislösung existiert. Es muss demnach das duale Simplexverfahren angewandt werden. Das Opmtimierungsproblem wird zunächst in die Normalform überführt (Einfügen von Schlupfvarbiablen um Gleichheitsbedingungen zu erhalten):

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

u.d.N.

$-x_1 - x_2 + x_3                    = -8$

$-3x_1 - x_2        + x_4           = -12$

$x_1 + x_2                           + x_5    = 10$

$x_1, x_2, x_3, x_4, x_5 \ge 0$

Danach werden die Werte in das Simplextableau eingetragen:

Duales Simplexverfahren Anfangstableau

Das obige Anfangstableau erhält die unzulässige Basislösung $x_1 = 0$, $x_2 = 0$, $x_3 = -8$, $x_4 = -12$ und $x_5 = 10$ mit dem Zielfunktionswert $f(x_1, x_2) = z = 0$. Diese Lösung ist deshalb unzulässig, da die Nichtnegativitätsbedingung für die Variablen $x_3$ und $x_4$ nicht gegeben ist. 

Merke

Nicht vergessen! Die Zielfunktionswerte gehen mit dem negativen Wert in das Tableau ein!

Multiple-Choice
Gegeben sei das folgende Optimierungsproblem:

$x_1 + 2x_2 $  max!

udN

$x_1 + x_2 \le 20$
$-x_1 - 2x_2 \ge -40$

$x_1, x_2 \ge 0$

Welche der folgenden Verfahren kann hier angewandt werden, nachdem das Problem in Normalform überführt worden ist?
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