ZU DEN KURSEN!

Operations Research - Primales Simlpexverfahren

Kursangebot | Operations Research | Primales Simlpexverfahren

Operations Research

Primales Simlpexverfahren

Inhaltsverzeichnis

In den folgenden Abschnitten wird gezeigt, wie man das primale Simplexverfahren anwendet. Es muss aber zunächst festgelegt werden, wann der primale Simplex-Algorithmus angewandt werden kann.

Methode

Vorausetzung für die Anwendung des primalen Simplex-Verfahrens

  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 müssen nicht-negative Koeffizienten auf der Rechten-Seite der Nebenbedingungen vorliegen ($b_i \ge 0$, für alle $i$).

Bei Vorliegen von nur nicht-negativen Koeffizienten auf der rechten Seiten der Nebenbedingungen besitzt das lineare Maximimierungsproblem bereits eine bekannte zulässige Basislösung. Dies ist die Voraussetzung für die Anwendung des primalen Simplexverfahrens. 

Gegeben sei das folgende lineare Optimierungsproblem in Standardform:


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

u.d.N.

$x_1 + 2x_2 \le 8$

$2x_1 + x_2 \le 8$

$4x_1 + 3x_2 \le 12$

$x_1, x_2 \ge 0$

Alle Koeffizienten auf der rechten Seite der Nebenbedingungen sind positiv $B = (8,8,12)$. Das bedeutet, es kann der primale Simplex-Algorithmus angewandt werden.

Merke

Man sagt auch das lineare Optimierungsmodell liegt in kanonischer Form vor (Werte der rechten Seite sind alle positiv und es liegt die Standardform/Normalform vor). 

Zulässige Basislösung

Das eine zulässige Basislösung für das obige Problem existiert, soll gezeigt werden. Hierzu wird zunächst das LP in die Normalform überführt. Dies geschieht indem Schlupvariablen eingeführt werden. Für jede Kleiner/Gleich-Nebenbedingung wird eine neue Schlupvariable eingeführt, welche in der Zielfunktion den Wert Null annimmt:


$f(x_1, x_2) = x_1 + x_2 + 0x_3 + 0x_4 + 0x_5$  $ \rightarrow$   max!

u.d.N.

$x_1 + 2x_2 + x_3                      = 8$

$2x_1 + x_2         + x_4              = 8$

$4x_1 + 3x_2                + x_5    = 12$

$x_1, x_2, x_3, x_4, x_5 \ge 0$

Dabei sind $x_1$ und $x_2$ die Nichtbasisvariablen (NBV) und die Schlupfvariablen $x_3$, $x_4$ und $x_5$ die Basisvariablen (BV).

Die NBV nehmen dabei immer den Wert Null an und die BV den Wert der rechten Seite:

$x_3 = 8$, $x_4 = 8$ und $x_5 = 12$ für $x_1, x_2 = 0$.

Zu Beginn sind unsere Entscheidungsvariablen $x_1$ und $x_2$ also auf Null gesetzt. Da die Nichtnegativitätsbedingung $x_i \ge 0$ gegeben ist, die Variablen also auch den Wert Null annehmen dürfen, existiert bereits zu Beginn eine zulässige Basislösung:

$\vec{x} = (0,0,8,8,12)$

Diese zulässige Lösung entspricht aber nicht der optimalen Lösung $\vec{x}^*$. Um nun eine optimale Lösung zu erhalten, wird in den folgenden Abschnitten das primale Simplexverfahren angewandt. 

Da die Schlupfvariablen mit dem Wert Null in die Zielfunktion eingehen, kann das Problem auch geschrieben werden zu:


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

u.d.N.

$x_1 + 2x_2 + x_3                      = 8$

$2x_1 + x_2         + x_4              = 8$

$4x_1 + 3x_2                + x_5    = 12$

$x_1, x_2, x_3, x_4, x_5 \ge 0$