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 > Die Big-M-Methode des primalen Simplexverfahrens:

Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)

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]

Es wird nun ein weiterer Simplexschritt durchgeführt. Ziel ist es, die künstliche Variable $y_1$ aus der Basis zu eliminieren. Es müssen zunächst wieder Pivotspalte, Pivotzeile und Pivotelement nach dem primalen Simplexverfahren bestimmt werden:

Big-M-Methode Pivotspalte Pivotzeile Pivotelement

Es wird zunächst wieder die Pivotspalte bestimmt, indem der kleinste negative Wert ausgewählt wird. Da hier $M$ als hinreichend groß angenommen wird, bestimmt man den kleinsten negativen Wert anhand der $M$-Werte:

$-\frac{2}{3}M$ und $-\frac{1}{3}M$

Der kleinste negative Wert ist demnach $-\frac{2}{3}M$.

Die Pivotzeile wird dann bestimmt, indem die rechte Seite durch die positiven Werte der Pivotspalte geteilt werden und der kleinste Quotient ausgewählt wird. In diesem Fall ist $4:\frac{2}{3} = 6$ der kleinste Quotient. 

Das Pivotelement liegt dort, wo sich Pivotspalte und Pivotzeile schneiden. 

Es wird als nächstes das neue Tableau nach Durchführung eines weiteren Simplexschrittes aufgestellt. Dabei müssen Basisvariable und Nichtbasisvariable des Pivotelements vertauscht werden:

Big-M-Methode Simplexschritt

In der obigen Tabellen ist das neue Tableau nach einem weiteren Simplexschritt zu sehen. Die Basisvariable $y_1$ und die Nichtbasisvariable $x_2$ sind vertauscht worden. Sobald eine künstliche Variable $y_i$ die Basis verlässt und zur Nichtbasisvariable wird, kann diese im weiteren Verlauf unberücksichtigt bleiben. Dies ist anhand der $x$ angedeutet. Dies stellt auch gleichzeitig die Pivotspalte dar, welche dann für das neue Tableau nicht berechnet werden muss. Auch der Wert des alten Pivotelements muss also für das neue Tableau nicht bestimmt werden. Es müssen aber die Werte der alten Pivotzeile und die restlichen Werte bestimmt werden.

Werte der alten Pivotzeile:

Der alte Wert innerhalb der Pivotzeile wird durch das Pivotelement geteilt.


Restliche Werte:

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 Wert $-\frac{1}{2}$ in der Zielfunktionszeile unter $x_3$:

$M - [\frac{(- \frac{1}{3} - \frac{2}{3}M \cdot -1)}{\frac{2}{3}}]$

$M - [\frac{ \frac{1}{3} + \frac{2}{3}M}{\frac{2}{3}}]$

$M - \frac{1}{2} - 1M$

$-\frac{1}{2}$

Zielfunktionswert:

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

$z = (2 + 4M) \cdot 2 + (1 + 2M) \cdot 6 - M \cdot 0 - M \cdot 0 - 20M$

$z = (2 + 4M) \cdot 2 + (1 + 2M) \cdot 6 - 20M $

$z = 4 + 8M + 6 + 12 M - 20M = 10$.

Zulässige Lösung

Es sind alle künstlichen Variablen $y_i$ aus der Basis entfernt worden. Auch die $M$-Werte sind alle eliminiert. Es liegt demnach eine zulässige Lösung vor:

$x_1 = 2$, $x_2 = 6$, $x_5 = 2$ und $y_1 = y_2 = x_3 = x_4 = 0$ mit dem Zielfunktionswert $z = 10$.

Merke

Da noch negative Werte in der Zielfunktionsleiste vorliegen, liegt zwar eine zulässige, aber keine optimale Lösung vor. Es werden nun noch weitere Simplexschritte nach dem primalen Simplexverfahren durchgeführt, solange, bis eine optimale Lösung vorliegt (keine negativen Werte mehr in der Zielfunktionszeile). 

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