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 \mathbb {R} ^{mxn},b\in \mathbb {R} ^{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\geq 0$ . Wenn $(X_{B}X_{N})~mit~X_{N}=0$ ist, dann ist es eine zulässige Basislösung von A.

Beispiel 1

${\begin{pmatrix}1&0&1&0&0\\0&1&0&1&0\\1&1&0&0&1\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\s_{1}\\s_{2}\\s_{3}\end{pmatrix}}={\begin{pmatrix}200\\300\\400\end{pmatrix}}$

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

$A_{B1}={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}$ $X_{B1}={\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\end{pmatrix}}$

$A_{B1}X_{B1}=b\Rightarrow {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\end{pmatrix}}={\begin{pmatrix}200\\300\\400\end{pmatrix}}\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

${\begin{pmatrix}1&0&1&0&0\\0&1&0&1&0\\1&1&0&0&1\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\s_{1}\\s_{2}\\s_{3}\end{pmatrix}}={\begin{pmatrix}200\\300\\400\end{pmatrix}}$

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

$A_{B2}={\begin{pmatrix}1&0&0\\0&1&0\\1&0&1\end{pmatrix}}$ $X_{B2}={\begin{pmatrix}x_{1}\\s_{2}\\s_{3}\end{pmatrix}}$

$A_{B2}X_{B2}=b\Rightarrow {\begin{pmatrix}1&0&0\\0&1&0\\1&0&1\end{pmatrix}}{\begin{pmatrix}x_{1}\\s_{2}\\s_{3}\end{pmatrix}}={\begin{pmatrix}200\\300\\400\end{pmatrix}}\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}={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}$	$(s_{1},s_{2},s_{3})=(200,300,400)$	$(x_{1},x_{2})$	$(0,0,200,300,400)$
$A_{B2}={\begin{pmatrix}1&0&0\\0&1&0\\1&0&1\end{pmatrix}}$	$(x_{1},s_{2},s_{3})=(200,300,200)$	$(x_{2},s_{1})$	$(200,0,0,300,200)$
$A_{B3}={\begin{pmatrix}1&0&0\\0&1&1\\1&1&0\end{pmatrix}}$	$(x_{1},x_{2},s_{2})=(200,200,100)$	$(s_{1},s_{3})$	$(200,200,000,100,0)$
$A_{B4}={\begin{pmatrix}1&0&1\\0&1&0\\1&1&0\end{pmatrix}}$	$(x_{1},x_{2},s_{1})=(100,300,100)$	$(s_{2},s_{3})$	$(100,300,100,0,0)$
$A_{B5}={\begin{pmatrix}0&1&0\\1&0&0\\1&0&1\end{pmatrix}}$	$(x_{2},s_{1},s_{3})=(300,200,100)$	$(x_{1},s_{3})$	$(0,300,200,0,100)$

$b={\begin{pmatrix}200\\300\\400\end{pmatrix}}$

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}={\begin{pmatrix}1&0&0\\0&1&0\\1&1&1\end{pmatrix}}$	$(x_{1},x_{2},s_{3})=(100,300,-100)$	$(s_{1},s_{2})$	$(200,300,0,0,-100)$
$A_{B7}={\begin{pmatrix}0&1&0\\1&0&1\\1&0&0\end{pmatrix}}$	$(x_{2},s_{1},s_{2})=(400,200,-100)$	$(x_{1},s_{3})$	$(0,400,200,-100,0)$
$A_{B8}={\begin{pmatrix}1&1&0\\0&0&1\\1&0&0\end{pmatrix}}$	$(x_{2},s_{1},s_{2})=(400,-200,300)$	$(x_{1},x_{3})$	$(200,200,000,100,0)$
$A_{B4}={\begin{pmatrix}1&0&1\\0&1&0\\1&1&0\end{pmatrix}}$	$(x_{1},x_{2},s_{1})=(100,300,100)$	$(s_{2},s_{3})$	$(100,300,100,0,0)$
$A_{B5}={\begin{pmatrix}0&1&0\\1&0&0\\1&0&1\end{pmatrix}}$	$(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 ${\begin{pmatrix}1&1&0\\0&0&0\\1&0&1\end{pmatrix}}{\begin{pmatrix}0&0&0\\1&1&0\\1&0&1\end{pmatrix}}$ von A sind keine Basen von A, da die Vektoren jeweils linear abhängig sind.