Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren

Simplex Verfahren

Auf dieser Seite wird das Simplex Verfahren behandelt.

Idee

Simplex Verfahren

Es wird in einer beliebigen Ecke des Polyeders begonnen. Dann wird verglichen, ob einer der Nachbarn eine bessere Lösung für die Optimierung bietet und anschließend wird dieser Knoten betrachtet. Am Ende erreichen wir eine Ecke, die keinen Nachbarn mit einer besseren Lösung hat. Die Lösung ist nun ein lokales Optimum. Bei der linearen Optimierung gilt, dass ein lokales Optimum automatisch ein globales Optimum ist, da der Polyeder eine konvexe Menge ist. Graphisch kann mit dieser Idee jedes lineare Optimierungsproblem gelöst werden. Dies wird aber sehr schnell unübersichtlich (und kann schlecht implementiert werden). Wir benötigen eine einfache Charakterisierung der “Ecken” des Polyeders. Diese erhalten wir durch Betrachtung der Basen der Matrix A.

Das Simplex-Verfahren löst ein lineares Programm in endlich vielen Schritten oder stellt seine Unlösbarkeit oder Unbeschränktheit fest. Im Worstcase hat es exponentielle Laufzeit unabhängig von den gewählten Pivotregeln, in der Praxis ist es sehr effizient. Das Simplex-Verfahren berechnet auch die Lösung für das duale Problem zu einem linearen Programm.

Wiederholung algebraischer Grundlagen

Seien $v_1,...,v_n\in {ℝ}^m$.

• Die Linearkombination von $v_1,...,v_n$ mit den Koeffizienten ${\alpha }_1,...,{\alpha }_n\in {ℝ}^m$ ist der Vektor ${\alpha }_1{v}_1+...+{\alpha }_n{v}_n$.
• Die Vektoren $v_1,...,v_n$ sind linear abhängig, wenn es ein $i\in \{1,...,n\}$ gibt, so dass sich $v_i$ als Linearkombination von $v_1,...,v_{i-1},v_{i+1},...,v_n$ darstellen lässt.
• Eine maximale Menge linear unabhängiger Vektoren heißt Basis des zugehörigen Raumes. Eine Basis des ${ℝ}^m$ besteht beispielsweise aus m linear unabhängigen Vektoren.
• Der Rang einer Matrix A ist die maximale Anzahl linear unabhängiger Spaltenvektoren.

Matrix lineares Optimierungsproblem

$max{x}_1+6\cdot x_2$

$x_1+s_1=200$

$x_2+s_2=300$

$x_1+x_2+s_3=400$

$A=\left(\begin{array}{ccccc}1& 0& 1& 0& 0\\ 0& 1& 0& 1& 0\\ 1& 1& 0& 0& 1\end{array}\right)$, $b=\left(\begin{array}{c}200\\ 300\\ 400\end{array}\right)$

Da wir für jede unserer ursprünglichen Ungleichungen eine Schlupfvariable eingeführt haben, gilt stets Rang(A)=m (=Anzahl der Gleichungen=Länge des Vektors b).

Basis und Basislösung

Auf dieser Seite werden die Basen und Basislösungen beim Simplex Verfahren behandelt. Gegeben ist ein lineares Gleichungssystem $ax=b,A\in {ℝ}^{mxn},b\in {ℝ}^m,Rang(A)=m$.

Dann bilden m lineare unabhängige Spaltenvektoren aus A eine Basis von A. Diese wird mit $A_B$ bezeichnet. B enthält die Indices der Basisvektoren. N enthält die Indices der Nichtbasisvektoren. Die Basislösung $x_{B}von{A}_B$ ist gegeben durch: $A_B{x}_B=b$ dies gilt genau dann wenn: $x_B=A_B^{-1}b$. $A_B$ ist eine zulässige Basis von A, wenn gilt $A_B^{-1}b\ge 0$. Wenn $(X_B{X}_N)mit{X}_N=0$ ist, dann ist es eine zulässige Basislösung von A.

Beispiel 1

$\left(\begin{array}{ccccc}1& 0& 1& 0& 0\\ 0& 1& 0& 1& 0\\ 1& 1& 0& 0& 1\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ s_1\\ s_2\\ s_3\end{array}\right)=\left(\begin{array}{c}200\\ 300\\ 400\end{array}\right)$

$B1=\{3,4,5\}N1=\{1,2\}$

$A_{B1}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$ $X_{B1}=\left(\begin{array}{c}{s}_1\\ s_2\\ s_3\end{array}\right)$

$A_{B1}{X}_{B1}=b\Rightarrow \left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}{s}_1\\ s_2\\ s_3\end{array}\right)=\left(\begin{array}{c}200\\ 300\\ 400\end{array}\right)\Rightarrow s_1=200,s_2=300;s_3=400$

Nicht-Basisvariablen werden stets auf 0 gesetzt. Die zulässige Basislösung von A mit Zielfunktionswert 0, die man durch einsetzen erhält ist dann (0,0,200,300,400).

Beispiel 2

$\left(\begin{array}{ccccc}1& 0& 1& 0& 0\\ 0& 1& 0& 1& 0\\ 1& 1& 0& 0& 1\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ s_1\\ s_2\\ s_3\end{array}\right)=\left(\begin{array}{c}200\\ 300\\ 400\end{array}\right)$

$B2=\{1,4,5\}N2=\{2,3\}$

$A_{B2}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right)$ $X_{B2}=\left(\begin{array}{c}{x}_1\\ s_2\\ s_3\end{array}\right)$

$A_{B2}{X}_{B2}=b\Rightarrow \left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right)\left(\begin{array}{c}{x}_1\\ s_2\\ s_3\end{array}\right)=\left(\begin{array}{c}200\\ 300\\ 400\end{array}\right)\Rightarrow x_1=200,s_2=300;s_3=200$

Nicht-Basisvariablen werden stets auf 0 gesetzt.

Die zulässige Basislösung von A, die man durch einsetzen erhält ist dann (200,0,0,300,200) mit dem Zielfunktionswert 200.

Basen von A

Hier gibt es eine Übersicht der Basen von A mit dessen zulässigen Lösungen.

$A_B$	$x_B$	$x_N$	x
$A_{B1}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$	$(s_1,s_2,s_3)=(200,300,400)$	$(x_1,x_2)$	$(0,0,200,300,400)$
$A_{B2}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right)$	$(x_1,s_2,s_3)=(200,300,200)$	$(x_2,s_1)$	$(200,0,0,300,200)$
$A_{B3}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 1\\ 1& 1& 0\end{array}\right)$	$(x_1,x_2,s_2)=(200,200,100)$	$(s_1,s_3)$	$(200,200,000,100,0)$
$A_{B4}=\left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 1& 1& 0\end{array}\right)$	$(x_1,x_2,s_1)=(100,300,100)$	$(s_2,s_3)$	$(100,300,100,0,0)$
$A_{B5}=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 1& 0& 1\end{array}\right)$	$(x_2,s_1,s_3)=(300,200,100)$	$(x_1,s_3)$	$(0,300,200,0,100)$

$b=\left(\begin{array}{c}200\\ 300\\ 400\end{array}\right)$

Basen von A- mit unzulässigen Lösung

Hier gibt es eine Übersicht der Basen von A mit unzulässigen Lösungen.

$A_B$	$x_B$	$x_N$	x
$A_{B6}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 1& 1\end{array}\right)$	$(x_1,x_2,s_3)=(100,300,-100)$	$(s_1,s_2)$	$(200,300,0,0,-100)$
$A_{B7}=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 1& 0& 0\end{array}\right)$	$(x_2,s_1,s_2)=(400,200,-100)$	$(x_1,s_3)$	$(0,400,200,-100,0)$
$A_{B8}=\left(\begin{array}{ccc}1& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right)$	$(x_2,s_1,s_2)=(400,-200,300)$	$(x_1,x_3)$	$(200,200,000,100,0)$
$A_{B4}=\left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 1& 1& 0\end{array}\right)$	$(x_1,x_2,s_1)=(100,300,100)$	$(s_2,s_3)$	$(100,300,100,0,0)$
$A_{B5}=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 1& 0& 1\end{array}\right)$	$(x_2,s_1,s_3)=(300,200,100)$	$(x_1,x_3)$	$(0,400,-200,300,0)$

Diese Basen haben keine zulässige Lösungen, da $x_B$ negative Werte enthält.

Die Teilmengen $\left(\begin{array}{ccc}1& 1& 0\\ 0& 0& 0\\ 1& 0& 1\end{array}\right)\left(\begin{array}{ccc}0& 0& 0\\ 1& 1& 0\\ 1& 0& 1\end{array}\right)$ von A sind keine Basen von A, da die Vektoren jeweils linear abhängig sind.

Charakterisierung von Polyederecken

Warum schauen wir uns Basen und Basislösungen an? Wir waren doch an Ecken des Polyeders interessiert...

Sei das System $Ax=b,x\ge 0$ gegeben, $Rang(A)=m<n$. Dann sind äquivalent:

1. x ist eine Ecke des zugehörigen Polyeders
2. x ist eine zulässige Basislösung von Ax=b

Wir wissen, dass die optimale Lösung in einem Eckpunkt liegen muss, falls sie existiert. D.h. wir müssen nur über die Basen von A optimieren (diese bestimmen ja die zulässigen Basislösungen von Ax=b). Dies erfolgt mit sogenannten Tableaus.

Das Simplex-Verfahren besteht aus einer Folge von Basen bzw. Tableus.

1. Zuerst wird die zulässige Basis $A_B$ gefunden und daraus das Starttableau konstruiert.
2. Anschließend wir eine neue zulässige Basis $A_{B^{\prime }}$ aus $A_B$ konstruiert, so dass die zulässige Basislösung von $A_{B^{\prime }}$ besser ist, als die von $A_B$. Das Tableau wird nun aktualisiert.
3. Wenn es keine bessere Basislösung mehr gibt, dann ist die letzte optimal.

Ein Tableau entspricht dem Gleichungssystem $\left(\begin{array}{c}{c}^T\\ A\end{array}\right)x=\left(\begin{array}{c}{c}^{T}x\\ b\end{array}\right)$ mit $max{c}^{T}x,Ax=bundx\ge 0$.

$T_B$ ist ein Simplextableau zur Basis $A_B$

$T_B=\left(\begin{array}{cc}{c}_N^T-c_B^T{A}_B^{-1}{A}_N& -c_B^T{A}_B^{-1}b\\ A_B^{-1}{A}_N& A_B^{-1}b\end{array}\right)$ mit $A=(A_B{A}_N),x=(x_B{x}_N),c^T=(c_N^T{c}_B^T)$

Beispiel Gewinnmaximierung

Nun wird der Simplex Algorithmus anhand des Beispiels der Gewinnmaximierung Schritt für Schritt durchgegangen.

Zielfunktion:

$max{x}_1+6\cdot x_2+13\cdot x_3$.

Nebenbedingungen:

$x_1\le 200$

$x_2\le 300$

$x_1+x_2+x_3\le 400$

$x_2+3\cdot x_3\le 600$

$x_1,x_2,x_3\ge 0$

Das System lässt sich umschreiben zu:

$x_1+6\cdot x_2+13\cdot x_3=z$

$x_1+s_1=200$

$x_2+s_2=300$

$x_1+x_2+x_3+s_3=400$

$x_2+3\cdot x_3+s_4=600$

$x_1,x_2,x_3,s_1,s_2,s_3,s_4\ge 0$

$A=\left(\begin{array}{ccccccc}1& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 1& 1& 1& 0& 0& 1& 0\\ 0& 1& 3& 0& 0& 0& 1\end{array}\right),b=\left(\begin{array}{c}200\\ 300\\ 400\\ 600\end{array}\right)$

Initialisierung

Gestartet wird mit der Basislösung, die durch die Schlupfvariable gegeben ist.

$A_B=(s_1{s}_2{s}_3{s}_4)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)=A_B^{-1}$

$A_N=(x_1{x}_2{x}_3)=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 1& 1\\ 0& 1& 3\end{array}\right)$ $b=\left(\begin{array}{c}200\\ 300\\ 400\\ 600\end{array}\right)$

$c^T=\left(\begin{array}{ccccccc}1& 6& 13& 0& 0& 0& 0\end{array}\right)=\left(\begin{array}{cc}{c}_N^T& c_B^T\end{array}\right)$

$A_B^{-1}{A}_N=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 1& 1\\ 0& 1& 3\end{array}\right)$ $A_B^{-1}b=\left(\begin{array}{c}200\\ 300\\ 400\\ 600\end{array}\right)$

Starttableau

	$x_1$	$x_2$	$x_3$	b
z	1	6	13	0
$s_1$	1	0	0	200
$s_2$	0	1	0	300
$s_3$	1	1	1	400
$s_4$	0	1	3	600

$x_1,x_2,x_3$ sind Nichtbasiselemente, Z ist die Zielfunktion und $s_1,s_2,s_3,s_4$ sind Basiselemente. Dabei sind die blau hinterlegten Felder das $c_N^T-c_N^T{A}_B^{-1}{A}_N$, die gelb hinterlegten Felder stellen den Teil von $A_B^{-1}{A}_N$ dar und die grünen Felder sind $A_B^{-1}b$. Das nicht markierte Feld ist dabei der negative Zielfunktionswert $-c_B^T{A}_B^{-1}b$.

Update eines Tableau

Für das Update eines Tableau wird eine neue zulässige Basis bestimmt, indem ein Basisvektor durch einen Nichtbasisvektor ausgetauscht wird. Die Menge der Nichtbasisvektoren, die getauscht werden können, ist über die positiven Koeffizienten c der Zielfunktion definiert als: $E=\{j|c_x{x}_j>0\}$. Wenn $E=\mathrm{\varnothing }$ dann breche ab und gebe x zurück. Die Menge der Basisvektoren, die getauscht werden können, ist über ihre j-te Komponente bestimmt: $L_j=\{i|x_j^i>0\}$. Wenn $L_j=\mathrm{\varnothing }$ für alle $j\in E$ dann ist das LP unbeschränkt, da die Zielfunktion $c^{T}x$ durch $x_j$ unbeschränkt wächst.

Optimierungsphase

Berechne für eine zulässige Basis, das zugehörige Tableau. Nun wird E bestimmt. Wenn $E=\mathrm{\varnothing }$ dann wird abgebrochen und x zurückgegeben. Ansonsten wird $j\in E$ durch eine geeignete Pivotregel gewählt. Als nächstes wird $L_j$ bestimmt. Wenn $L_j=\mathrm{\varnothing }$ dann wird zurückgegeben, dass LP unbeschränkt ist. Ansonsten wird $i\in L_j$ durch eine geeignete Pivotregel gewählt. Führe nun einen Basiswechsel durch und starte wieder oben.

Beispiel

	$x_1$	$x_2$	$x_3$	b
z	1	6	13	0
$s_1$	1	0	0	200
$s_2$	0	1	0	300
$s_3$	1	1	1	400
$s_4$	0	1	3	600

$E=\{j|c_x{x}_j>0\}=\{1,2,3\}\{x_1,x_2,x_3\}$

$L_1=\{i|x_1^i>0\}=\{1,3\}\{s_1,s_3\}$

$L_2=\{i|x_2^i>0\}=\{2,3,4\}\{s_2,s_3,s_4\}$

$L_3=\{i|x_3^i>0\}=\{3,4\}\{s_3,s_4\}$

Heuristik für die Auswahl der Tauschvektoren

Als erstes werden die größten Koeffizienten in der Zielfunktion gewählt (Dantzig). Eine andere Möglichkeit ist das steepest-edge pricing, welches die Kombination aus Spalten- und Zeilenvektor wählt, die den größten Zuwachs für die Zielfunktion bringt. Oder der kleinste Index wird gewählt. Die letzte Möglichkeit ist eine zufällige Auswahl.

Erste Iteration

Heuristik: Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt.

$x_1$

$0\le s_1=200-x_1$

$0\le s_3=400-x_1$

$x_1=min(200,400)=200\Rightarrow z=200$

Hier wird die Zeile von $s_{1}und{s}_3$ betrachtet und die Spalte von $x_1$. Der alte Wert ist 0. Der Koeffizient von $x_1$ in der Zielfunktion ist 1 und der Zugewinn durch $x_1$ ist 200.

$x_2$

$0\le s_2=300-x_2$

$0\le s_3=400-x_2$

$0\le s_4=600-x_2$

$x_2=min(300,400,600)=300\Rightarrow z=1800$

Hier wird die Zeile von $s_2,s_{3}und{s}_4$ betrachtet und die Spalte von $x_2$. Der alte Wert ist 0. Der Koeffizient von $x_2$ in der Zielfunktion ist 6 und der Zugewinn durch $x_2$ ist 1800.

$x_3$

$0\le s_3=400-x_3$

$0\le s_4=600-3x_3$

$x_3=min(400,200)=200\Rightarrow z=2600$

Hier wird die Zeile von $s_{3}und{s}_4$ betrachtet und die Spalte von $x_3$. Der alte Wert ist 0. Der Koeffizient von $x_3$ in der Zielfunktion ist 13 und der Zugewinn durch $x_3$ ist 2600. Nun wird $s_4$ durch $x_3$ ersetzt.

Update des Tableaus

Der neue Wert von $x_3$ wird nun berechnet.

$s_4=600-x_2-3x_3\iff x_3=200-\frac{x_2}{3}-\frac{s_4}{3}$.

Dieser Wert wird nun eingesetzt.

$z=x_1+6_{x_2}+13\cdot (200-\frac{x_2}{3}-\frac{s_4}{3})=x_1+\frac{5}{3}{x}_2-\frac{13}{3}{s}_4+2600$

$s_3=400-x_1-x_2-(200-\frac{x_2}{3}-\frac{s_4}{3})=200-x_1-\frac{2}{3}{x}_2+\frac{s_4}{3}$

$x_3=200-\frac{x_2}{3}-\frac{s_4}{3}$

Das neue Tableau sieht nun so aus:

	$x_1$	$x_2$	$s_4$	b
z	1	$\frac{5}{3}$	$-\frac{13}{3}$	-2600
$s_1$	1	0	0	200
$s_2$	0	1	0	300
$s_3$	1	$\frac{2}{3}$	$-\frac{1}{3}$	200
$x_3$	0	$\frac{1}{3}$	$\frac{1}{3}$	200

Was haben wir nun gemacht? Von der Basis $B=(s_1,s_2,s_3,s_4)$ haben wir zu der Basis $B^{\prime }=(s_1,s_2,s_3,x_3)$ gewechselt und zu der neuen Basis haben wir das entsprechende Tableau bestimmt.

${T_B}^{\prime }=\left(\begin{array}{cc}{c}_{N^{\prime }}^T-c_{B^{\prime }}^T{A}_{B^{\prime }}^{-1}{A}_{N^{\prime }}& -c_{B^{\prime }}^T{A}_{B^{\prime }}^{-1}b\\ A_{B^{\prime }}^{-1}{A}_{N^{\prime }}& A_{B^{\prime }}^{-1}b\end{array}\right)$

$A_{B^{\prime }}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 0& 3\end{array}\right)$ $A_{B^{\prime }}^{-1}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& -\frac{1}{3}\\ 0& 0& 0& \frac{1}{3}\end{array}\right)$ $A_N=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 1& 0\\ 0& 1& 1\end{array}\right)$ $A_{B^{\prime }}^{-1}{A}_N=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& \frac{2}{3}& -\frac{1}{3}\\ 0& \frac{1}{3}& \frac{1}{3}\end{array}\right)$ $A_{B^{\prime }}^{-1}b=\left(\begin{array}{c}200\\ 300\\ 200\\ 200\end{array}\right)$

$c^T=\left(\begin{array}{ccccccc}1& 6& 0& 0& 0& 0& 13\end{array}\right)=\left(\begin{array}{cc}{c}_{N^{\prime }}^T& c_{B^{\prime }}^T\end{array}\right)$

$c_{N^{\prime }}^T-c_{B^{\prime }}^T{A}_{B^{\prime }}^{-1}{A}_{N^{\prime }}=\left(\begin{array}{ccc}1& \frac{5}{3}& -\frac{13}{3}\end{array}\right)$

$-c_B^T{A}_B^{-1}b=-2600$

Zweite Iteration

$E=\{j|c_x{x}_j>0\}=\{1,2\}\{x_1,x_2\}$

$L_1=\{i|x_1^i>0\}=\{1,3\}\{s_1,s_3\}$

$L_2=\{i|x_2^i>0\}=\{2,3,4\}\{s_2,s_3,x_3\}$

Heuristik: Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt.

$x_1$

$0\le s_1=200-x_1$

$0\le s_3=200-x_1$

$x_1=200\Rightarrow z=2800$

Hier wird die Zeile von $s_{1}und{s}_3$ betrachtet und die Spalte von $x_1$. Der alte Wert ist 2600. Der Koeffizient von $x_1$ in der Zielfunktion ist 1 und der Zugewinn durch $x_1$ ist 200.

$x_2$

$0\le s_2=300-x_2$

$0\le s_2=200-\frac{2}{3}{x}_2$

$0\le x_2=200-\frac{1}{3}{x}_2$

$x_2=min(300,600)=300\Rightarrow z=4400$

Hier wird die Zeile von $s_2,s_{3}und{x}_3$ betrachtet und die Spalte von $x_2$. Der alte Wert ist 2600. Der Koeffizient von $x_2$ in der Zielfunktion ist 6 und der Zugewinn durch $x_2$ ist 1800. Nun wird $s_2$ durch $x_2$ ersetzt.

Update des Tableaus

Der neue Wert von $x_2$ wird nun berechnet.

$s_2=300-x_2\iff x_2=300-s_2$. Dieser Wert wird nun eingesetzt.

$z=x_1+\frac{5}{3}\cdot (300-s_2)-\frac{13}{3}{s}_4+2600=x_1-\frac{5}{3}{s}_2-\frac{13}{3}{s}_4+3100$

$s_3=200-x_1+\frac{2}{3}\cdot (300-s_2)+\frac{s_4}{3}=-x_1+\frac{2}{3}{s}_2+\frac{s_4}{3}$

$x_3=200-\frac{1}{3}\cdot (300-s_2)-\frac{s_4}{3}=100+\frac{1}{3}{s}_2-\frac{s_4}{3}$

Das neue Tableau sieht nun so aus:

	$x_1$	$s_2$	$s_4$	b
z	1	$-\frac{5}{3}$	$-\frac{13}{3}$	-3100
$s_1$	1	0	0	200
$x_2$	0	1	0	300
$s_3$	1	$-\frac{2}{3}$	$-\frac{1}{3}$	0
$x_3$	0	$-\frac{1}{3}$	$\frac{1}{3}$	100

Dritte Iteration

$E=\{j|c_x{x}_j>0\}=\{1\}\{x_1\}$

$L_1=\{i|x_1^i>0\}=\{1,3\}\{s_1,s_3\}$

Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt. Es müssen nur Terme aus z mit positivem Vorzeichen betrachtet werden, d.h. es bleibt nur noch $x_1$ übrig.

$x_1$

$0\le s_1=200-x_1$

$0\le s_3=0-x_1$

$x_1=min(200,0)\Rightarrow z=3100$

Update des Tableaus

Nun wird $s_3$ durch $x_1$ ersetzt.

$s_3=-x_1+\frac{2}{3}{s}_2+\frac{s_4}{3}\iff x_1=-s_3+\frac{2}{3}{s}_2+\frac{s_4}{3}$. Dieser Wert wird nun eingesetzt.

$z=-s_3+\frac{2}{3}{s}_2+\frac{s_4}{3}-\frac{5}{3}{s}_2-\frac{13}{3}{s}_4+3100=-s_3-s_2-4s_4+3100$

$s_1=200-(-s_3-\frac{2}{3}{s}_2-\frac{s_4}{3})=200+s_3+\frac{2}{3}{s}_2+\frac{s_4}{3}$

Das neue Tableau sieht nun so aus:

	$s_3$	$s_2$	$s_4$	b
z	-1	-1	-4	-3100
$s_1$	-1	$\frac{2}{3}$	$\frac{1}{3}$	200
$x_2$	0	1	0	300
$x_1$	1	$-\frac{2}{3}$	$\frac{1}{3}$	0
$x_3$	0	$-\frac{1}{3}$	$\frac{1}{3}$	100

Die Zielfunktion kann nun nicht weiter verbessert werden. Unser x ist nun (0,300,100) und unser z ist 3100.

Analyse

Das Simplex-Verfahren löst ein lineares Programm in endlich vielen Schritten oder stellt seine Unlösbarkeit oder Unbeschränktheit fest. Im Worstcare hat es eine exponentielle Laufzeit, unabhängig von den gewählten Pivotregeln. In der Praxis ist es sehr effizient.