ZU DEN KURSEN!

Operations Research 1 - Die Big-M-Methode des primalen Simplexverfahrens

Kursangebot | Operations Research 1 | Die Big-M-Methode des primalen Simplexverfahrens

Operations Research 1

Die Big-M-Methode des primalen Simplexverfahrens

In den vorherigen Abschnitten ist der duale Simplexalgorithmus angewandt worden. Dabei ist ein lineares Optimierungsproblem so umgeformt worden, dass es in Standardform (Maximierungsproblem, Kleiner-Gleich-Nebenbedingung, Nichtnegativitätsbedingung) vorlag, jedoch negative Werte auf der rechten Seite vorhanden waren.

Bei der Big-M-Methode des primalen Simplexverfahrens (auch: Groß-M-Methode) wird das lineare Optimierungsproblem ebenfalls zunächst in die Standardform überführt.

Methode

Hier klicken zum Ausklappen

Voraussetzung für die Anwendung der Big-M-Methode des primalen Simplexverfahrens:

  1. Es muss die Standardform vorliegen (Maximierungsproblem, kleiner-gleich-Nebenbedingung, Nichtnegativitätsbedingung)

  2. Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.

  3. Es liegen negative Koeffizienten auf der Rechten-Seite der Nebenbedingungen vor ($b_i \le 0$).

Es wird im folgenden anhand eines Beispiels gezeigt, wie bei der Big-M-Methode des primalen Simplexverfahrens vorgegangen wird.

Gegeben sei das folgende Optimierungsproblem

$f(x_1, x_2) = 2x_1 + x_2$  $ \rightarrow$   max!

u.d.N.

$x_1 + x_2 \ge 8$

$3x_1 + x_2 \ge 12$

$x_1 + x_2 \le 10$

$x_1, x_2 \ge 0$

Das Optimierungsmodell liegt noch nicht in Standardform vor (größer-gleich-Nebenbedingungen vorhanden). Es muss also zunächst in diese transformiert werden. Eine größer-gleich-Nebenbedingung wird ein eine kleiner-gleich-Nebenbedingung transformiert, indem diese mit $-1$ multipliziert wird:

$f(x_1, x_2) = 2x_1 + x_2$  $ \rightarrow$   max!

u.d.N.

$-x_1 - x_2 \le -8$

$-3x_1 - x_2 \le -12$

$x_1 + x_2 \le 10$

$x_1, x_2 \ge 0$

Das Optimierungsmodell liegt nun in Standardform vor (Maximierungsproblem, kleiner-gleich-Bedingungen, Nichtnegativitätsbedingung). Allerdings sind hier die Werte der rechten Seite nicht alle positiv, weshalb keine zulässige 1. Basislösung existiert. Es muss demnach das duale Simplexverfahren angewandt werden. Das Optimierungsproblem wird zunächst in die Normalform überführt (Einfügen von Schlupfvarbiablen um Gleichheitsbedingungen zu erhalten):

$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 sind hier für die Schlupfvariablen $x_3, x_4, x_5$ eingefügt worden, anstelle von $y_1, y_2,y_3$. Grund dafür ist, dass bei der Big-M-Methode die künstlichen Variablen $y_i$ eingefügt werden. Der Übersicht halber ist demnach für die Schlupfvariablen $x_i$ gewählt worden.

Nachdem nun die Normalform vorliegt, kann als nächstes die Big-M-Methode angewandt werden.