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:

Duales Simplexverfahren: Simplexschritte

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]

Die Simplexschritte für das duale Simplexverfahren werden analog zum primalen Simplexverfahren durchgeführt und sind diesem Abschnitt zu entnehmen. Es wird nun das neue Tableau aus dem vorherigen Abschnitt aufgeführt:

Duales Simplexverfahren Austausschritt

Es liegt nun das folgende neue Tableau nach Durchführung eines Simplexschrittes vor. Die Vorgehensweise sei kurz zusammengefasst:

Das Pivotelement geht mit seinem reziproken Wert ein: $\frac{1}{-1} = -1$

Die neuen Elemente der Pivotzeile werden ermittelt, indem die alten Werte durch das alte Pivotelement geteilt werden.

Die neuen Elemente der Pivotspalte werden ermittelt, indem die alten Werte durch das alte Pivotelement geteilt und mit $-1$ multipliziert werden.

Die restlichen Werte werden bestimmt indem der alte Wert abzüglich der alten Werte aus zugehöriger Pivotspalte mal Pivotzeile durch Pivotelement berechnet wird. Z.B.: Der wurde der Wert $4$ bestimmt durch:

$-8 - \frac{-1 \cdot -12}{-1}$.

Der Zielfunktionswert wurde ermittelt, indem die Basisvariablen mit den Werten der rechten Seite in die Zielfunktion eingesetzt werden (die Nichtbasisvariablen besitzen den Wert Null):

$f(x_1, x_2) = 2 \cdot 0 + 1 \cdot 12  = 12$.

Weiterer dualer Simplexschritt

Da immer noch Werte auf der rechten Seite existieren $b_i < 0$, welche kleiner Null sind, muss hier wieder der duale Simplexalgorithmus angewandt werden. Denn es ist immer noch keine zulässige Basislösung gegeben ($x_5 \le 0$). Es wird also wieder mittels des dualen Simplexverfahrens die Pivotzeile, Pivotspalte und das Pivotelement ausgewählt:

Duales Simplexverfahren Pivotspalte Pivotzeile Pivotelement

Nach dem dualen Simplexverfahren ist zunächst die Pivotzeile bestimmt worden (kleinester negativer Wert der rechten Seite). In diesem Fall existiert nur noch ein negativer Wert und dies stellt gleichzeitig die Pivotzeile dar. Danach wird die Pivotspalte (größter Quotient aus Zielfunktionswert durch Werte der Pivotzeile, wobei nur negative Werte der Pivotzeile berücksichtigt werden dürfen) ausgewählt. Auch hier existiert nur noch ein negativer Wert in der ausgewählten Pivotzeile. Dies stellt gleichzeitig die Pivotspalte dar. Das Pivotelement ergibt sich dort, wo sich Pivotspalte und Pivotzeile schneiden (hier: -2). Es wird wieder das neue Tableau (Tausch von Basisvariable und Nichtbasisvariable des Pivotelements) aufgestellt mit den neuen Elemente:

Duales Simplexverfahren Austausschritt

Es sind nun keine negativen Werte mehr auf der rechten Seite gegeben. Demnach ist eine zulässige Basislösung gegeben:

$x_1 = 1$, $x_2 = 9$, $x_3 = 2$, $x_4 = 0$ und $x_5 = 0$.

Der Zielfunktionswert ist gegeben mit $z = 11$.

Da in der unteren Zeile noch ein Zielfunktionswert mit negativem Wert gegeben ist, kann als nächstes der primale Simplexalgorithmus angewandt werden um aus der zulässigen Basislösung eine optimale Basislösung zu machen. 

Primaler Simplexalgorithmus

Primales Simplexverfahren Pivotzeile Pivotspalte Pivotelement

Bei dem primalen Simplexverfahren (nur mit zulässiger Basislösung anwendbar) kann aus einer gegebenen zulässigen Basislösung eine optimale Basislösung gewonnen werden, wenn in der Zielfunktionszeile noch negative Werte gegeben sind. Es wird als erstes die Pivotspalte bestimmt. Hier wird der kleinste negative Wert ausgewählt um die Pivotspalte zu bestimmen. In dem obigen Tableau existiert nur ein negativer Wert. Danach wird die Pivotzeile ausgewählt, indem die Werte der rechten Seite durch die Werte der ausgewählten Pivotspalte dividiert werden und der kleinste Quotient ausgewählt wird. Dabei dürfen nur positive Werte größer Null für die Division verwendet werden. In dem obigen Tableau kann nur der Wert $\frac{1}{2}$ für die Division verwendet werden, dies stellt also die Pivotzeile dar. Das Pivotelement liegt dort, wo sich Pivotzeile und Pivotspalte schneiden. Es kann nun das neue Tableau aufgestellt werden (Basis- und Nichtbasisvariable müssen vertauscht werden):

Primales Simplexverfahren Austausschritt

Es sind alle Werte der Zielfunktionszeile positiv, damit ist die optimale Lösung erreicht:

$x_1 = 10$, $x_2 = 0$, $x_3 = 2$, $x_4 = 18$ und $x_5 = 0$.

Der Zielfunktionswert beträgt dann:

$z = 20$.

Es sind noch Kapazitäten für die Restriktionen 1 und 2 vorhanden, welche durch die Schlupfvariablen $x_3$ und $x_4$ angezeigt werden. So sind für Restriktion 1 noch $x_3 = 2$ Kapazitätseinheiten verfügbar und für Restriktion 2 noch $x_4 = 18$ Kapazitätseinheiten. Die Restriktion 3 verfügt über keine Kapazitäten mehr, $x_5 = 0$.

Multiple-Choice
Wie berechnnen sich die neuen Werte der Pivotspalte bei dem Simplexverfahren?
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