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:

Die Big-M-Methode: Einfügen von künstlichen Variablen

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 soll die Vorgehensweise bei der Big-M-Methode des primalen Simplexverfahrens (auch: 2-Phasen-Methode, Groß-M-Methode) aufgezeigt werden. Hierfür wird das im vorherigen Abschnitt aufgeführte Optimierungsproblem verwendet.

Methode

Vorgehensweise bei der Big-M-Methode des primalen Simplexverfahrens:

  • Das Maximierungsproblem muss zunächst in Normalform vorliegen, dann werden die folgenden Schritte angewandt:

  • Überall dort, wo sich negative Werte auf der rechten Seite befinden, wird die gesamte Gleichung mit $-1$ multipliziert.

  • Dort wo sich negative Schlupfvariablen befinden, werden künstliche Variablen $y_i$ mit positiven Vorzeichen eingefügt.

  • In der zu maximierenden Zielfunktion werden diese künstlichen Variablen $y_i$ mit $-M$ bewertet ($M$ ist hinreichend groß zu wählen). 

  • Die künstlichen Variablen müssen aus der Zielfunktion entfernt werden, so dass diese in das Tableau als Basisvariablen eingehen.

  • Der primale Simplexalgorithmus ist auf dieses Problem solange anzuwenden, bis die künstlichen Variablen $y_i$ keine Basisvariablen mehr darstellen.

  • Hat eine künstliche Variable $y_i$ die Basis verlassen, kann diese aus der gesamten Betrachtung ausgeschlossen werden.

Zum besseren Verständnis der Vorgehensweise, wird nun das Beispiel aus dem vorherigen Abschnitt herangezogen und ausführlich gezeigt, wie diese Schritte durchgeführt werden:

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


Es werden nun zunächst die Nebenbedingungen mit negativen Werten auf der rechten Seite mit $-1$ multipliziert:

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

Dadurch nehmen die Schlupfvariablen $x_3$ und $x_4$ negative Werte an. Als nächstes werden künstliche Variablen $y_i$ für alle Nebenbedingungen eingefügt, für welche negative Schnlupfvariablen gegeben sind. Diese werden in der Zielfunktion mit $-M$ bewertet, wobei $M$ hinreichend groß zu wählen ist:

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

u.d.N.

$x_1 + x_2 - x_3                             + y_1                     = 8$

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

$x_1 + x_2                           + x_5                              = 10$

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

Bevor als nächstes das Omtimierungsproblem mittels primalen Simplex gelöst werden kann, muss noch eine Umformung stattfinden. Zunächst soll aber das Ziel der Big-M-Methode erläutert werden. Die beiden künstlichen Variablen $y_1$ und $y_2$ sind mit dem Big-M versehen worden. Dieses soll hinreichend groß angenommen werden. Das bedeutet, dass die optimale Basislösung die künstlichen Variablen nicht beinhaltet. Denn die Zielfunktion soll maximiert werden. Bei Berücksichtigung von $y_1$ und $y_2$ würde sich aber (aufgrund des Minuszeichens und aufgrund des großen M's) der Zielfunktionswert ziemlich stark verringern. Es ist also sinnvoll, wenn am Ende die beiden künstlichen Variablen den Wert Null annehmen, denn nur so kann der Zielfunktionswert seinen maximalen Wert annehmen. Den Wert null nehmen Variablen an, wenn diese zu Nichtbasisvariablen werden. Um das zu erreichen müssen die beiden künstlichen Variablen aber zunächst als Basisvariablen in das Tableau eingehen. Der Simplexalgorithmus, welcher das Ziel hat den Zielfunktionswert zu maximieren, wird diese künstlichen Variablen dann nach und nach aus der Basis entfernen. Am Ende werden die beiden künstlichen Variablen dann zu Nichtbasisvariablen und nehmen damit den Wert Null an. Im Optimierungsmodell müssen die künstlichen Variablen also zunächst aus der Zielfunktion entfernt werden, damit diese als Basisvariablen in das Tableau eingehen. Dieses Vorgehen wird im nachfolgenden Abschnitt aufgezeigt.

Multiple-Choice
Es ist folgendes Optimierungsproblem bekannt, das mit Hilfe der Big-M-Methode des primalen Simplexverfahrens gelöst werden soll.

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

u.d.N.

$x_1 + x_2= 10$
$-2x_1 - 2x_2= -5$

Stellen Sie das Problem nach der Big-M-Methode auf. Welches Aussagen 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