Beispiel: Primalproblem als Minimierungsproblem

In diesem Abschnitt soll ausführlich beschrieben werden, wie ein gegebenes Minimierungsproblem gelöst werden kann. Hierzu wird dieses zunächst dualsiert, d.h. also in ein Maximierungsproblem in kanonischer Form umgewandelt. Danach wird der primale Simplexalgorithmus angewandt um eine Optimallösung zu erhalten. Es wird gezeigt, wie man die Optimallösung des primalen Problems aus den Optimaltableau für das duale Problem ermittelt.

Beispiel: Duales Maximierungsproblem lösen

Gegeben sei das folgende Minimierungsproblem

$f(x_1, x_2, x_3) = x_1 + x_2 + 3x_3$   $\rightarrow$  min!

u.d.N.

$x_1 - x_2             \ge -12$

$x_1         - x_3     \ge 14$

$-x_1 + x_2 + x_3   \ge -10$

$2x_1 - x_2 + x_3    \ge 4$

$x_1, x_2, x_3 \ge 0$

Um das Problem mit dem primalen Simplexlagorithmus lösen zu können, muss dieses in ein duales Maximierungsproblem umgewandelt werden. Hierzu muss das Minimierungsproblem zunächst die Form "Größer/Gleich-Nebenbedingung, Nichtnegativitätsbedingung" überführt werden. Da das Problem bereits in dieser Form vorliegt, kann mit der Dualisierung begonnen werden:

Das Problem wird in eine Matrix eingetragen. Die Zielfunktionszeile geht als letztes in die Matrix ein:

$A = \left( \begin{array}{ccc|c} 1 & -1 & 0 & -12 \\ 1 & 0 & -1 & 14 \\ -1 & 1 & 1 & -10 \\ 2 & -1 & 1 & 4 \\ 1 & 1 & 3 & 0 \end{array}\right)$

Danach wird die Matrix transponiert:

$A^T = \left( \begin{array}{cccc|c} 1 & 1 & -1 & 2 & 1 \\ -1 & 0 & 1 & -1 & 1 \\ 0 & -1 & 1 & 1 & 3\\ -12 & 14 & -10 & 4 & 0 \end{array}\right)$

Das neue Problem wird aus der Matrix abgelesen, wobei die letzte Zeile die Zielfunktionszeile des dualen Problems darstellt:

$f(u_1, u_2, u_3, u_4) = -12 u_1 + 14 u_2 - 10 u_3 + 4 u_4$

$u_1 + u_2 - u_3 + 2 u_4 \le 1$

$-u_1          + u_3 - u_4    \le 1$

$      - u_2 + u_3 + u_4    \le 3$

$u_1, u_2, u_3, u_4 \ge 0$

Das duale Maximierungsproblem liegt in kanonischer Form vor, es kann hier also der primale Simplexalgorithmus angewandt werden. Hierzu muss das Problem in die Normalform überführt werden:

$f(u_1, u_2, u_3, u_4) = -12 u_1 + 14 u_2 - 10 u_3 + 4 u_4$

$u_1 + u_2 - u_3 + 2 u_4 + u_5                   = 1$

$-u_1          + u_3 - u_4           + u_6            = 1$

$      - u_2 + u_3 + u_4                     + u_7   = 3$

$u_1, u_2, u_3, u_4, u_5, u_6, u_7 \ge 0$

Nachdem die Schlupfvariablen eingefügt worden sind, kann das Problem nun in das Tableau eingetragen werden und der primale Simplexalgorithmus angewandt werden:

Nachdem alle Werte in der Zielfunktionszeile positiv sind, ist die optimale Lösung erreicht. Für das duale Maximierungsproblem beträgte diese $u^* = (0,2,1,0)$. Das bedeutet also, $u_1  = 0$, $u_2 = 2$, $u_3 = 1$ und $u_4 = 0$. Einsetzen in die Zielfunktion ergibt $f = 18$.

Die optimale Lösung für das primale Minimierungsproblem kann ebenfalls dem Tableau entnommen werden. Und zwar gilt $x_1 = u_5$, $x_2 = u_6$ und $x_3 = u_7$. Die Variablen des primalen Problems entsprechen also den Schlupfvariablen des dualen Problems. Hier wird aber wie folgt abgelesen: Die Zielfunktionswerte des dualen Problems stellen die Werte der rechten Seite für das primale Problem dar: $x_1 = 14$, $x_2 = 4$. Das bedeutet also, dass $x_1$ und $x_2$ für das primale Problem Basisvariablen darstellen. Die Werte der rechten Seite stellen die Zielfunktionswerte des primalen Problems dar, also $x_3 = 0$. Für das primale Prroblem stellt $x_3$ also eine Nichtbasisvariable dar. Insgesamt ergibt sich also für das primale Minimierungsproblem:

$f(x_1, x_2, x_3) = 14 + 4 + 3 \cdot 0 = 18$