Wie interpretiert man die End-Tabelle beim Simplexalgorithmus?

Hier ist ein End-Tabelle eines Simplexalgorithmus? Die Basisvariablen x, y, z sind die ersten drei Spalten. Wie genau lese ich die Werte jeder Variabel ab. y hätte die 1.714, aber was ist mit x und z? Sie sind in der gleichen Zeile.

Answer 1

[Mathmaninoff, UserMod Light]

Dann gibt es unendlich viele Lösungen, wie bei dem Beispiel $x + y \rightarrow \max \\ x + y \leq 1 \\ x, y \geq 0$ Das Tableau würden dann so aussehen mit der Schlupfvariable s.

$\begin{array}{ c | c c c | c} \text{BV} & x & y & s & b \\ \hline s &1 & 1 & 1 & 1 \\ \hline -z & 1 & 1 & 0 & 0 \end{array}$ Jetzt kann man die erste oder zweite Spalte als Pivotspalte nehmen, da der Zielfunktionskoeffizient bei beiden gleich ist. $\begin{array}{ c | c c c | c} \text{BV} & x & y & s & b \\ \hline x &1 & 1 & 1 & 1 \\ \hline -z & 0 & 0 & -1 & -1 \end{array}$ Mit x als Basisvariable wäre die Lösung x = 1, y = 0, s = 0. Aber man kann genau so gut y = 1 und x = 0 oder jede beliebige Konvexkombination mit x + y = 1 daraus.

Das ist allgemein so, wenn bei weiteren Spalten als der Basis in der untersten Zeile eine Null ist. Das bedeutet, wenn man mit einer solchen Spalte tauscht, ändert sich durch die Null der Zielfunktionswert nicht. Bei der Umformung muss man nichts zur untersten Zeile addieren, da schon die Null steht. Der Zielfunktionswert ändert sich nicht. Wegen der Linearität hat man dazwischen noch unendlich viele Lösungen.

Im Beispiel aus der Fragestellung und in meinem Beispiel muss auch keine andere Zeile verändert werden. Das wäre nicht so, wenn jetzt noch eine weitere Nebenbedingung wäre, wo bei der eine Variable ein Schlupf Null wäre und nach der Umformung nicht. Wenn in meinem Beispiel noch die Nebenbedingung x ≤ 1 wäre, dann wäre für x = 1 der Schlupf für diese Nebenbedingung 0 und für x = 0 der Schlupf 1. In dem Beispiel aus der Frage muss man aber gar nichts ändern, wenn man z statt x als Basisvariable nehmen will.