previous up next contents index
previous: Spezialfälle up: Spezialfälle next: Degenerierte Basislösung

Unendlich viele Lösungen  

Lösen des lineare Optimierungsproblem (Abbildung).

\begin{displaymath}
z(x_1,x_2)=2\,x_1+x_2 \quad\longrightarrow\quad\max\end{displaymath}

\begin{displaymath}
2\,x_1 + x_2 \leq 100,\qquad
x_1 + x_2 \leq 80,\qquad
x_1 \leq 40,\end{displaymath}

\begin{displaymath}
x_1,x_2\geq 0\end{displaymath}

mit dem Simplex-Algorithmus:


\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
\begin{array}
{c\vert ccccc\ver...
 ...0 & 0&0&1 & 40&40\\  \hline
 1 & -2&-1 & 0&0&0 & 0 &\end{array}\end{displaymath}

Die Basislösung $(x_1,x_2;s_1,s_2,s_3)=(0,0;100,80,40)$ ist zulässig. Wir können daher das Standardverfahren verwenden.

Nach zwei Pivotschritten erhalten wir:

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
\begin{array}
{c\vert ccccc\ver...
 ... & 0&0&1 & 40& 40\\  \hline
 1 & 0&0 & 1&0&0 & 100 &\end{array}\end{displaymath}

Die maximale zulässige Basislösung ist

$(x_1,x_2;s_1,s_2,s_3) = (40,20;0,20,0)$.




Im Tableau ist aber nur mehr ein (statt zwei) Koeffizienten in der ZFZ ungleich Null. Wir können noch einen Pivotschritt ausführen und erhalten eine weitere maximale zulässige Basislösung:

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
\begin{array}
{c\vert ccccc\ver...
 ...&0 & 1&-1&0 & 20&\\  \hline
 1 & 0&0 & 1&0&0 & 100 &\end{array}\end{displaymath}

$(x_1,x_2;s_1,s_2,s_3) = (20,60;0,0,20)$


previous up next contents index

© 1997, Josef Leydold
Abteilung für angewandte Statistik und Datenverarbeitung