Obere Schranken: Primales Simplexverfahren

Das im vorherigen Abschnitt betrachtete lineare Optimierungsproblem mit den oberen Schranken, kann auch ganz einfach mittels primalen Simplexalgorithmus gelöst werden. Dabei werden die oberen Schranken als Nebenbedingungen (so wie auch in den vorherigen Abschnitten geschehen) in das Tableau aufgenommen.

Gegeben sei das folgende Optimierungsproblem:

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

u.d.N.

$x_1 + 2x_2 \le 100$

$x_1 + x_2 \le 75$

$x_1          \le 45$

          $x_2 \le 30$

$x_1, x_2 \ge 0$

Das Problem liegt in Standardform vor und die Werte der rechten Seite sind alle positiv (kanonische Form). Demnach kann hier der primale Simplexalgorithmus angewandt werden. Das Problem wird in Normalform überführt (Einfügen von Schlupfvariablen):

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

u.d.N.

$x_1 + 2x_2 + x_3                             \le 100$

$x_1 + x_2           + x_4                     \le 75$

$x_1                             + x_5            \le 45$

          $x_2                             + x_6  \le 30$

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

Einfügen in das Simplextableau:

Es wird nun der primale Simplexalgorithmus angewandt. Die Vorgehensweise sollte aus den vorherigen Abschnitten bekannt sein. Es wird das Tableau nach dem 1. Simplexschritt aufgestellt:

Es wird ein weiterer Simplexschritt mittels primalen Simplexalgorithmus durchgeführt. Das Tableau ergibt sich zu:

Es existiert noch ein negativer Wert in der Zielfunktionszeile. Es muss noch eine Iteration durchgeführt werden:

Das Optimaltableau ist gegeben. Der Zielfunktionswert beträgt 172,5 mit $x_1 = 45$ und $x_2 = 27,5$. Die Werte entsprechen also genau den im vorherigen Abschnitt ermittelten Werte.