Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Gewinnmaximierung

Beispiel Gewinnmaximierung

Auf dieser Seite 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.

Optimierungsphase

	$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\}$

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 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=18000$

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=26000$

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}$

$s_4=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 Bais $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^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)$

${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}=\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+n\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.