ZU DEN KURSEN!

Operations Research - Primales Simplexverfahren: Anfangstableau aufstellen

Kursangebot | Operations Research | Primales Simplexverfahren: Anfangstableau aufstellen

Operations Research

Primales Simplexverfahren: Anfangstableau aufstellen

Der primale Simplexalgorithmus geht wie folgt vor:

  • Ausgehend von einer Startecke mit einer Ausgangsbasis schreitet dieser durch Basisaustausch zu einer Ecke mit besserem Zielfunktionswert fort.
  • Da es nur endlich viele Ecken gibt, wird nach endlich vielen Schritten die optimale Lösung erreicht.
  • Der Basistausch geschieht dabei so sparsam wie möglich: Es wird stets genau eine Basisvariable gegen eine Nichtbasisvariable ausgetauscht

Das Simplexverfahren findet in einem sogenannten Simplex-Tableau statt. Dieses ist wie folgt aufgebaut:

Primales Simplexverfahren - Tableau

Erläuterung des Tableaus zu Beginn des Verfahrens

Auf der linken Seite stehen die Basisvariablen. Dies sind die Schlupfvariablen, welche mit dem Wert Null in die Zielfunktion eingehen und demnach in dieser nicht berücksichtigt werden. Auf der rechten Seite stehen die Werte rechts von den Nebenbedingungen. Beim primalen Simplex müssen diese Werte alle positiv sein. Ganz oben stehen die Nichtbasisvariablen, dies sind die Entscheidungsvariablen, welche nicht mit dem Wert Null in die Zielfunktion eingehen. Ganz unten stehen die Werte, welche die Nichtbasisvariablen in der Zielfunktion besitzen. Diese müssen mit entgegengesetzten Vorzeichen versehen werden (positive Werte werden negativ und umgekehrt). Unten rechts steht der momentane Zielfunktionswert (zu Beginn ist dieser Null). In die Mitte des Tableaus kommen alle Werte der Nichtbasisvariablen der Nebenbedingungen.

Merke

Die sich in der Zielfunktion befindlichen Variablen (Variablen die nicht mit den Wert Null in die Zielfunktion eingehen) gehen in das Anfangstableau als Nichtbasisvariablen ein. Die sich nicht in der Zielfunktion befindlichen Variablen (=Schlupfvariablen) gehen als Basisvariablen in das Anfangstableau ein.

Es soll im Folgenden ausführlich beschrieben werden, wie die optimale Lösung mit Hilfe des primalen Simplexverfahrens ermittelt werden kann.  Hierzu wird das Beispiel aus dem vorangegangenen Abschnitt verwendet:

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

Die Nichtbasisvariablen sind dabei $x_1$ und $x_2$ und die Schlupfvariablen $x_3$, $x_4$ und $x_5$ die mit Null in die Zielfunktion eingehen stellen die Basisvariablen (BV) dar. 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:

Primales Simplexverfahren - Beispiel 1

Wie bereits im vorherigen Kapitel gezeigt, zeigt dieses Tableau die erste Basislösung an. Dabei besitzen die Nichtbasisvariablen immer den Wert Null $x_1 = 0$ und $x_2 = 0$ und die Basisvariablen immer den Wert der rechten Seite: $x_3 = 8$, $x_4 = 8$ und $x_5 = 12$. Betrachtet man das Optimierungsproblem so erhält man diese Werte indem $x_1 = 0$ und $x_2 = 0$ in die Nebenbedingungen eingesetzt werden:

$0 + 2 \cdot 0 + x_3                      = 8$

$2 \cdot 0 + 0         + x_4              = 8$

$4 \cdot 0 + 3 \cdot 0      + x_5       = 12$

Daraus resultieren die Werte für die Basisvariablen.

Der Zielfunktionswert ist bei dieser ersten Basislösung Null:

$f(0,0) = 1 \cdot 0 + 1 \cdot 0 = 0$

Diese erste Lösung stellt zwar eine zulässige Basislösung, jedoch keine optimale Basislösung dar. Es wird im nächsten Abschnitt ausführlich gezeigt, wie die optimale Basislösung mittels primalen Simplexverfahren ermittelt werden kann. Ziel ist dabei den Zielfunktionswert (welcher im Moment noch Null ist) zu maximierem (da Maximierungsproblem).