previous: Die Standardform up: Die Standardform next: Das Standard-Maximierungsproblem

Vorgangsweise:  

(1)

Wir bringen alle Konstanten auf die rechte Seite und auf positives Vorzeichen.

(2)

Jede ,,$\leq$``-Ungleichung bringen wir durch Addition einer Schlupfvariablen in Gleichungsform.

(3)

Jede ,,$\geq$``-Ungleichung (außer die Nichtnegativitätsbedingungen!) bringen wir durch Subtraktion einer Schlupfvariablen in Gleichungsform.

(4)

Jede Variable $x_j$, die nicht die Nichtnegativitätsbedingung erfüllt, stellen wir als Differenz zweier nicht-negativer Variablen $x_j'$ und $x_j''$ dar:

$$x_j = x_j' - x_j''\qquad\qquad x_j', x_j'' \geq 0$$

(5)

Wir fassen auch $z$ als Variable auf und fügen die zu optimierende Funktion in Form der Gleichung

$$z - b_1\,x_1 - \cdots - b_n\,x_n = 0$$

als letzte Zeile (Zielfunktionszeile) in unser lineares Gleichungssystem und bringen dieses in Matrixform (Simplex-Tableau).

Wenn eine Zeile (außer der Zielfunktionszeile) keine Schlupfvariable enthält, d.h. die entsprechende Nebenbedingung ist eine Gleichung, dann müssen wir das Tableau noch geeignet umformen:

Wir wählen die Zeile ohne Schlupfvariable als Pivotzeile, und eine Spalte, in der diese Zeile ein Element ungleich Null enthält, als Pivotspalte, und führen einen Pivotschritt aus.

Alle Zeilen (außer der Zielfunktionszeile), die dabei eine negative Konstante in der rechten Spalte erhalten, werden anschließend mit $-1$ multipliziert.

BEISPIEL
Wir bringen das lineare Optimierungsproblem auf Standardform und stellen das Anfangs-Simplex-Tableau auf:

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

(1) Wir multiplizieren die zweite Ungleichung mit $-1$:

$$\begin{array} {rcl} z = 2\,x_1-5\,x_2+x_3 &\longrightarrow&... ...1 + 4\,x_3 &=& 40\\ [0.5ex] x_1,\,x_2 &\geq& 0\\ \end{array}$$

(2) und (3).
Durch Addition und Subtraktion von Schlupfvariablen bringen wir die Ungleichungen in Gleichungsform:

$$\begin{array} {rrrrrrcr} &&&&&\makebox[0pt][r]{$z=2\,x_1-5\... ...0pt][r]{$x_1,\,x_2,\,s_1,\,s_2,\,s_3$} &\geq& 0\\ \end{array}$$

(4) $x_3$ erfüllt nicht die Nichtnegativitätsbedingung:

$$x_3=x_3'-x_3''$$

$$\setlength {\arraycolsep}{0.5em} \begin{array} {rrrrrrrcr} ... ...x_2,\,x_3',\,x_3'',\,s_1,\,s_2,\,s_3$} &\geq& 0\\ \end{array}$$

(5) Einfügen der Zielfunktion:

$$z - 2\,x_1 + 5\,x_2 - x_3' + x_3'' = 0$$

In Matrixform (Simplex-Tableau):

$$\begin{array} {c\vert ccccccc\vert c} z & x_1 & x_2 & x_3' ... ...40\\ \hline 1 & -2 & 5 & -1 & 1 & 0 & 0 & 0 & 0 \end{array}$$

(6) Die vierte Zeile enthält keine Schlupfvariable.
Wir machen einen Pivotschritt (Pivotelement in der 4. Zeile und $x_1$-Spalte).

Das Anfangs-Simplex-Tableau lautet daher:

$$\begin{array} {c\vert ccccccc\vert c} z & x_1 & x_2 & x_3' ... ...40\\ \hline 1 & 0 & 5 & 7 & -7 & 0 & 0 & 0 & 80 \end{array}$$