Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Basis&Basislösung

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, die man durch einsetzen erhällt 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=400$

Die zulässige Basislösung von A, die man durch einsetzen erhällt ist dann (0,0,200,300,400) 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.