ZU DEN KURSEN!

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

Kursangebot | Operations Research | Die Big-M-Methode: Einfügen von künstlichen Variablen

Operations Research

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

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

Hier klicken zum Ausklappen 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.