Big-M-Methode: Simplexschritt durchführen

In diesem Abschnitt wird nun das Anfangstableau aufgestellt. Das lineare Ontimierungsproblem mittels Big-M-Methode ist gegeben durch:

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

Die Nichtbasisvariablen sind dabei $x_1$, $x_2$, $x_3$ und $x_4$ (Variablen, welche in die Zielfunktion eingehen) und die Basisvariablen sind  $x_5$, $y_1$ und $y_2$ (Variablen, welche nicht in die Zielfunktion eingehen). Dieses lineare Optimierungsproblem (Maximierungsproblem, Nichtnegativitätsbedingung, wobei die Werte der rechten Seite alle positiv sind) kann mittels primalen Simplexverfahren gelöst werden. Eintragen der Werte in das Tableau, wobei die Zielfunktionswerte immer mit entgegengesetzten Vorzeichen in das Tableau eingehen:

Bei der hier gegebenen Basislösung $y_1 = 8$, $y_2 = 12$, $x_5 = 10$ und $x_1 = x_2 = x_3 = x_4 = 0$ ergibt sich ein Zielfunktionswert von:

$f(x_1, x_2) = (2 + 4M) \cdot 0 + (1 + 2M) \cdot 0 - M \cdot 0 - M \cdot 0 - 20M = -20M$

Es wird nun wie beim primalen Simplexverfahren vorgegangen. Es erfolgt zunächst die Auswahl der Pivotspalte mittels kleinsten negativen Wert in der Zielfunktionszeile. Da $M$ hinreichend groß angenommen wird, erfolgt die Auswahl nur über die $M$-Werte. Das bedeutet also, dass hier die beiden negativen $M$-Werte $-4M$ und $-2M$ betrachtet werden müssen. Hier wird der kleinste negative Wert ausgewählt, also $-4M$. Danach wir die Pivotzeile festgelegt, indem die Werte der rechten Seite durch die Werte der Pivotspalte (nur positive Werte der Pivotspalte dürfen berücksichtigt werden) geteilt werden. Der kleinste Quotient wird ausgewählt, hier: 12: 3 = 4$. Das Pivotelement liegt dort, wo sich Pivotspalte und Pivotzeile schneiden, hier: $3$.

Es wird als nächstes das neue Tableau nach Durchführung eines Simplexschrittes aufgestellt. Dabei müssen Basisvariable und Nichtbasisvariable des Pivotelements vertauscht werden:

In der obigen Tabellen ist das neue Tableau nach dem 1. Simplexschritt zu sehen. Die Basisvariable $y_2$ und die Nichtbasisvariable $x_1$ sind vertauscht worden. Sobald eine künstliche Variable $y_i$ die Basis verlässt und zur Nichtbasisvariable wird, kann diese im weiteren Verlauf unberücksichtigt bleiben. Dies ist anhand der $x$ angedeutet. Dies stellt auch gleichzeitig die Pivotspalte dar, welche dann für das neue Tableau nicht berechnet werden muss. Auch der Wert des alten Pivotelements muss also für das neue Tableau nicht bestimmt werden. Es müssen aber die Werte der Pivotzeile und die restlichen Werte bestimmt werden.

Werte der Pivotzeile

Der alte Wert innerhalb der Pivotzeile wird durch das Pivotelement geteilt.

Restliche Werte

Die restlichen Werte werden bestimmt indem der alte Wert abzüglich der alten Werte aus zugehöriger Pivotspalte mal Pivotzeile durch Pivotelement berechnet wird. Z.B.: Der wurde der Wert $6$ bestimmt durch:

$10 - (\frac{1 \cdot 12 }{3} = 6$.

Der Wert $-\frac{1}{3} - \frac{2}{3}M$ wurde bestimmt durch:

$-1 - 2M - [\frac{(-2 - 4M) \cdot 1}{3}]$

$-1 - 2M - [ \frac{-2 - 4M}{3}]$

$-1 - 2M + \frac{2}{3} + \frac{4}{3}M$

$-\frac{1}{3} - \frac{2}{3}M$

Zielfunktionswert

Der Zielfunktionswert wurde ermittelt, indem die Basisvariablen mit den Werten der rechten Seite in die Zielfunktion eingesetzt werden (die Nichtbasisvariablen besitzen den Wert Null):

$z = (2 + 4M) \cdot 4 + (1 + 2M) \cdot 0 - M \cdot 0 - M \cdot 0 - 20M$

$z = (2 + 4M) \cdot 4 - 20 M$

$z = 8 + 16M - 20M$

$z = 8 - 4M$.

Da noch künstliche Variablen in der Basis auftauchen ($y_1$) ist die zulässige Basislösung noch nicht ermittelt worden. Es wird ein weiterer Simplexschritt durchgeführt. Zunächst müssen Pivotspalte, Pivotzeile und Pivotelement wieder nach dem primalen Simplexverfahren bestimmt werden.