previous: Schlupfvariable up: Der Simplex-Algorithmus next: Naive Methode

Der zulässige Bereich  

Der zulässige Bereich des linearen Optimierungsproblems läßt sich daher beschreiben als die Menge aller Lösungen $(x_1,x_2;s_1,s_2,s_3)$ dieses linearen Gleichungssystems mit $x_j\geq 0$ und $s_i\geq 0$( Nichtnegativitätsbedingung).

Der zulässige Bereich ist eine konvexe Menge. Daher liegt das Optimum immer in einem Eckpunkt des zulässigen Bereichs.

Diese Eckpunkte sind die Schnittpunkte der Begrenzungsgeraden. In diesen Schnittpunkten sind immer zwei der fünf Variablen $x_1$, $x_2$, $s_1$, $s_2$ und $s_3$ gleich Null. Derartige Lösungen dieses linearen Gleichungssystems heißen  Basislösungen.

(Im Falle von $n$ Variablen $x_1,\ldots,x_n$ werden $n$ der Variablen $x_1,\ldots,x_n;s_1,\ldots,s_m$ gleich 0 gesetzt.)

Eine Basislösung, die die Nichtnegativitätsbedingung erfüllt, heißt  zulässige Basislösung.

Wir müssen aus der Menge aller zulässigen Basislösungen jene ermitteln, in der die Zielfunktion den größten Wert annimmt.