previous: Das Standard-Maximierungsproblem up: Lineare Optimierung next: 2-Phasen-Simplex-Algorithmus

Das Standard-Minimierungsproblem  

Das Standard-Minimierungsproblem ist vollkommen analog zum Maximierungsproblem. Wir müssen nun aber entgegen der Richtung des Gradienten wandern. Daraus ergibt sich folgende Änderung der Vorgangsweise in den Punkten (3) und (4).

(Alle anderen Punkte sind identisch!)

 

$$\leq 0\quad\Rightarrow\quad$$ (3')

(4') Pivotspalte: größter Eintrag in ZFZ.

BEISPIEL

$$\begin{array} {rcl} z(x_1,x_2,x_3) = 3\,x_1 + 2\,x_2 +4\,x_... ...1 + 2\,x_3 &\geq& -1 \\ [1ex] x_1,\,x_3 &\geq& 0 \end{array}$$

Anfangs-Simplex-Tableau aufstellen:

$$\setlength {\fboxsep}{2mm} \begin{array} {c\vert cccccc\v... ...- \\ \hline 1 & -3 & -2 & 2 & -4 & 0 & 0 & 10 & \end{array}$$

Die Basislösung dieses Tableaus ist zulässig: $(0,0,0,0;3,1)$.

$$\begin{array} {c\vert cccccc\vert cc} z & x_1 & x_2' & x_2'... ...- \\ \hline 1 & -5 & 0 & 0 & -6 & -2 & 0 & 4 & \end{array}$$

Alle Einträge in der Zielfunktionszeile sind $\leq 0$. Wir haben daher das Minimum erreicht.

Die minimale zulässige Basislösung lautet

$(x_1,x_2',x_2'',x_3;s_1,s_2) = (0,0,3,0;0,1)$

Das Minimum liegt somit im Punkt $(0,-3,0)$.

$z_{\min} = 4$.