Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Gewinnmaximierung

Beispiel Gewinnmaximierung[Bearbeiten]

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

$x_{2}\leq 300$

$x_{1}+x_{2}+x_{3}\leq 400$

$x_{2}+3\cdot x_{3}\leq 600$

$x_{1},x_{2},x_{3}\geq 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}\geq 0$

$A={\begin{pmatrix}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{pmatrix}},b={\begin{pmatrix}200\\300\\400\\600\end{pmatrix}}$

Initialisierung[Bearbeiten]

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

$A_{B}=(s_{1},s_{2},s_{3},s_{4})={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}=a_{B}^{-1}$

$A_{N}=(x_{1},x_{2},x_{3})={\begin{pmatrix}1&0&0\\0&1&0\\1&1&1\\0&1&3\end{pmatrix}}$ $b={\begin{pmatrix}200\\300\\400\\600\end{pmatrix}}$

$c^{T}={\begin{pmatrix}1&6&13&0&0&0&0\end{pmatrix}}={\begin{pmatrix}c_{N}^{T}&c_{B}^{T}\end{pmatrix}}$

$A_{B}^{-1}A_{N}={\begin{pmatrix}1&0&0\\0&1&0\\1&1&1\\0&1&3\end{pmatrix}}$ $A_{B}^{-1}b={\begin{pmatrix}200\\300\\400\\600\end{pmatrix}}$

Starttableau[Bearbeiten]

	$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[Bearbeiten]

	$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[Bearbeiten]

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

$x_{1}$

$0\leq s_{1}=200-x_{1}$

$0\leq 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\leq s_{2}=300-x_{2}$

$0\leq s_{3}=400-x_{2}$

$0\leq 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\leq s_{3}=400-x_{3}$

$0\leq 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[Bearbeiten]

Der neue Wert von $x_{3}$ wird nun berechnet.

$s_{4}=600-x_{2}-3x_{3}\Leftrightarrow 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'=(s_{1},s_{2},s_{3},x_{3})$ gewechselt und zu der neuen Basis haben wir das entsprechende Tableau bestimmt.

$T_{B}'={\begin{pmatrix}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{pmatrix}}$

${A_{B}'}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&1\\0&0&0&3\end{pmatrix}}$ $A_{B'}^{-1}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&-{\frac {1}{3}}\\0&0&0&{\frac {1}{3}}\end{pmatrix}}$ ${A_{N}}={\begin{pmatrix}1&0&0\\0&1&0\\1&1&0\\0&1&1\end{pmatrix}}$ $A_{B'}^{-1}A_{N}={\begin{pmatrix}1&0&0\\0&1&0\\1&{\frac {2}{3}}&-{\frac {1}{3}}\\0&{\frac {1}{3}}&{\frac {1}{3}}\end{pmatrix}}$ ${A_{B'}^{-1}}={\begin{pmatrix}200\\300\\200\\200\end{pmatrix}}$

$c^{T}={\begin{pmatrix}1&6&0&0&0&0&13\end{pmatrix}}={\begin{pmatrix}c_{N'}^{T}&c_{B'}^{T}\end{pmatrix}}$

$c_{N'}^{T}-c_{B'}^{T}A_{B'}^{-1}A_{N'}={\begin{pmatrix}1&{\frac {5}{3}}&-{\frac {13}{3}}\end{pmatrix}}$

$-c_{B}^{T}A_{B}^{-1}b=-2600$

Zweite Iteration[Bearbeiten]

$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\leq s_{1}=200-x_{1}$

$0\leq 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\leq s_{2}=300-x_{2}$

$0\leq s_{2}=200-{\frac {2}{3}}x_{2}$

$0\leq 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[Bearbeiten]

Der neue Wert von $x_{2}$ wird nun berechnet.

$s_{2}=300-x_{2}\Leftrightarrow 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[Bearbeiten]

$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\leq s_{1}=200-x_{1}$

$0\leq s_{3}=0-x_{1}$

$x_{1}=min(200,0)\Rightarrow z=3100$

Update des Tableaus[Bearbeiten]

Nun wird $s_{3}$ durch $x_{1}$ ersetzt.

$s_{3}=x_{1}+{\frac {2}{3}}s_{2}+{\frac {s_{4}}{3}}\Leftrightarrow 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.