Inhaltsverzeichnis
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
- 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
multipliziert. - Dort wo sich negative Schlupfvariablen befinden, werden künstliche Variablen
mit positiven Vorzeichen eingefügt. - In der zu maximierenden Zielfunktion werden diese künstlichen Variablen
mit bewertet ( 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
keine Basisvariablen mehr darstellen. - Hat eine künstliche Variable
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:
u.d.N.
Es werden nun zunächst die Nebenbedingungen mit negativen Werten auf der rechten Seite mit
u.d.N.
Dadurch nehmen die Schlupfvariablen
u.d.N.
Grundgedanke der Big-M-Methode
Bevor als nächstes das Otimierungsproblem 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
Weitere interessante Inhalte zum Thema
-
Minimierungsproblem- Big-M/dualer Simplex
Vielleicht ist für Sie auch das Thema Minimierungsproblem- Big-M/dualer Simplex (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.
-
Die Big-M-Methode des primalen Simplexverfahrens
Vielleicht ist für Sie auch das Thema Die Big-M-Methode des primalen Simplexverfahrens (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.