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.

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$

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