previous: Unbeschränkter zulässiger Bereich up: Spezialfälle next: Kuhn-Tucker

Zulässiger Bereich leer  

BEISPIEL
Wir wollen das lineare Optimierungsproblem
(Abbildung, unten).

$$z(x_1,x_2) = x_1 + x_2 \quad\longrightarrow\quad\max$$

$$x_1 + x_2\leq 70,\quad x_1 - x_2\geq 10,\quad x_2\geq 40,\quad x_1,x_2\geq 0$$

mit dem Simplex-Algorithmus lösen.

Anfangs-Simplex-Tableau:

$$\begin{array} {c\vert ccccc\vert c} z & x_1 & x_2 & s_1 & s... ...& -1 & 40 \\ \hline 1 & -1 & -1 & 0 & 0 & 0 & 0 \end{array}$$

Die Basislösung $(x_1,x_2;s_1,s_2;s_3) = (0,0;80,0,-45)$ ist nicht zulässig. Wir müssen daher den Zwei-Phasen-Simplex-Algorithmus verwenden.

1. Phase:

Wir benötigen zwei Hilfsvariable und ersetzen die Zielfunktion $z$ durch $z^\ast = a_1 + a_2$:

$$\begin{array} {c\vert ccccccc\vert c} z^\ast & x_1 & x_2 & ... ...0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 \end{array}$$

Wir müssen die Zielfunktionszeile umformen, da $z^\ast$ nicht die Basisvariablen $a_1$ und $a_2$ enthalten darf:

$$ZFZ\leftarrow ZFZ + Z2 + Z3$$

$$\setlength {\fboxsep}{2mm} \begin{array} {c\vert ccccccc\... ...\ \hline 1 & 1 & 0 & 0 & -1 & -1 & 0 & 0 & 50 & \end{array}$$

Minimieren der Hilfsfunktion ergibt

$$\setlength {\fboxsep}{2mm} \begin{array} {c\vert ccccccc\... ... \\ \hline 1 & 0 & 1 & 0 & 0 & -1 & -1 & 0 & 40 \end{array}$$

$$\setlength {\fboxsep}{2mm} \begin{array} {c\vert ccccccc\... ...frac{1}{2}&-\frac{1}{2}& -1 &-\frac{1}{2}& 0 & 10 \end{array}$$

Wir haben das Minimum erreicht, da alle Einträge in der Zielfunktionszeile $\leq 0$ sind. Aber $z^\ast_{\min} \gt 0$.

Der zulässige Bereich ist leer. Es gibt keine Lösung des linearen Optimierungsproblem, die alle Nebenbedingungen erfüllt.