Die Big-M-Methode: Künstliche Variablen als Basisvariablen

Es wird im Weiteren gezeigt wie man das lineare Optimierungsmodell so umformt, dass die künstlichen Variablen $y_i$ nicht mehr in der Zielfunktion auftauchen und somit als Basisvariablen in das Simplex-Tableau eingehen. Ziel ist es dann mittels primalen Simplexverfahren, dass diese künstlichen Basisvariablen zu Nichtbasisvariablen werden und mit dem Wert Null in die Zielfunktion eingehen. Dies wird in jedem Fall erreicht, da das $M$ als hinreichend groß angenommen wird und durch das Minuszeichen den Zielfunktionswert sehr stark reduziert. Der primale Simplexalgorithmus hat das Ziel den größtmöglichen Zielfunktionswert zu erreichen. Dies kann bei hinreichend großem $M$ also nur dann geschehen, wenn die künstlichen Variablen $y_i$ den Wert Null annehmen, da sich sonst der Zielfunktionswert stark reduziert. Die künstlichen Variablen nehmen dann den Wert Null an, wenn diese zu Nichtbasisvariablen werden. Im Anfangstableau gehen diese aber zunächst als Basisvariablen ein. Dazu muss das Optimierungsproblem aber umgeformt werden, d.h. also die künstlichen Variablen müssen aus der Zielfunktion eliminiert werden. Das Optimierungsproblem ist wie folgt gegeben:

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

Es werden die Variablen $y_1$ und $y_2$ aus der Zielfunktion eliminiert. Hierzu werden die Nebenbedingungen betrachtet, welche $y_1$ und $y_2$ beinhalten und nach diesen aufgelöst:

$y_1 = 8 - x_1 - x_2 + x_3$

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

Diese werden dann in die Zielfunktion eingesetzt:

$f(x_1, x_2) = 2x_1 + x_2 - M \cdot (8 - x_1 - x_2 + x_3)  - M \cdot (12 - 3x_1 - x_2 + x_4)$

Die Klammern werden aufgelöst:

$f(x_1, x_2) = 2x_1 + x_2 - 8 M + M x_1 + Mx_2 - Mx_3 - 12 M + 3Mx_1 + Mx_2 - Mx_4$

Die Variablen werden zusammengefasst:

$f(x_1, x_2) = (2 + M + 3M)x_1 + (1 + M + M)x_2 - Mx_3 - Mx_4 - 20 M$

$f(x_1, x_2) = (2 + 4M)x_1 + (1 + 2M)x_2 - Mx_3 - Mx_4 - 20 M$.

Es ergibt sich also das folgende Optimierungsmodell:

$f(x_1, x_2) = (2 + 4M)x_1 + (1 + 2M)x_2 - Mx_3 - Mx_4 - 20M   $ \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$

Es kann als nächstes begonnen werden das Optimierungsproblem in das Tableau einzutragen.