Auf dieser Seite werden die Basen und Basislösungen beim Simplex Verfahren behandelt.
Gegeben ist ein lineares Gleichungssystem
a
x
=
b
,
A
∈
R
m
x
n
,
b
∈
R
m
,
R
a
n
g
(
A
)
=
m
{\displaystyle ax=b,A\in \mathbb {R} ^{mxn},b\in \mathbb {R} ^{m},Rang(A)=m}
A
B
{\displaystyle A_{B}}
x
B
v
o
n
A
B
{\displaystyle x_{B}~von~A_{B}}
a
B
x
B
=
b
{\displaystyle a_{B}x_{B}=b}
x
B
=
a
B
−
1
b
{\displaystyle x_{B}=a_{B}^{-1}b}
A
B
{\displaystyle A_{B}}
a
B
−
1
b
≥
0
{\displaystyle a_{B}^{-1}b\geq 0}
(
X
B
X
N
)
m
i
t
X
N
=
0
{\displaystyle (X_{B}X_{N})~mit~X_{N}=0}
(
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
)
(
x
1
x
2
s
1
s
2
s
3
)
=
(
200
300
400
)
{\displaystyle {\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}}}
B
1
=
{
3
,
4
,
5
}
N
1
=
{
1
,
2
}
{\displaystyle B1=\{3,4,5\}~N1=\{1,2\}}
A
B
1
=
(
1
0
0
0
1
0
0
0
1
)
{\displaystyle A_{B1}={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}}
X
B
1
=
(
s
1
s
2
s
3
)
{\displaystyle X_{B1}={\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\end{pmatrix}}}
A
B
1
X
B
1
=
b
⇒
(
1
0
0
0
1
0
0
0
1
)
(
s
1
s
2
s
3
)
=
(
200
300
400
)
⇒
s
1
=
200
,
s
2
=
300
;
s
3
=
400
{\displaystyle 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).
(
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
)
(
x
1
x
2
s
1
s
2
s
3
)
=
(
200
300
400
)
{\displaystyle {\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}}}
B
2
=
{
1
,
4
,
5
}
N
2
=
{
2
,
3
}
{\displaystyle B2=\{1,4,5\}~N2=\{2,3\}}
A
B
2
=
(
1
0
0
0
1
0
1
0
1
)
{\displaystyle A_{B2}={\begin{pmatrix}1&0&0\\0&1&0\\1&0&1\end{pmatrix}}}
X
B
2
=
(
x
1
s
2
s
3
)
{\displaystyle X_{B2}={\begin{pmatrix}x_{1}\\s_{2}\\s_{3}\end{pmatrix}}}
A
B
2
X
B
2
=
b
⇒
(
1
0
0
0
1
0
1
0
1
)
(
x
1
s
2
s
3
)
=
(
200
300
400
)
⇒
x
1
=
200
,
s
2
=
300
;
s
3
=
400
{\displaystyle 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.
Hier gibt es eine Übersicht der Basen von A mit dessen zulässigen Lösungen.
A
B
{\displaystyle A_{B}}
x
B
{\displaystyle x_{B}}
x
N
{\displaystyle x_{N}}
x
A
B
1
=
(
1
0
0
0
1
0
0
0
1
)
{\displaystyle A_{B1}={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}}
(
s
1
,
s
2
,
s
3
)
=
(
200
,
300
,
400
)
{\displaystyle (s_{1},s_{2},s_{3})=(200,300,400)}
(
x
1
,
x
2
)
{\displaystyle (x_{1},x_{2})}
(
0
,
0
,
200
,
300
,
400
)
{\displaystyle (0,0,200,300,400)}
A
B
2
=
(
1
0
0
0
1
0
1
0
1
)
{\displaystyle A_{B2}={\begin{pmatrix}1&0&0\\0&1&0\\1&0&1\end{pmatrix}}}
(
x
1
,
s
2
,
s
3
)
=
(
200
,
300
,
200
)
{\displaystyle (x_{1},s_{2},s_{3})=(200,300,200)}
(
x
2
,
s
1
)
{\displaystyle (x_{2},s_{1})}
(
200
,
0
,
0
,
300
,
200
)
{\displaystyle (200,0,0,300,200)}
A
B
3
=
(
1
0
0
0
1
1
1
1
0
)
{\displaystyle A_{B3}={\begin{pmatrix}1&0&0\\0&1&1\\1&1&0\end{pmatrix}}}
(
x
1
,
x
2
,
s
2
)
=
(
200
,
200
,
100
)
{\displaystyle (x_{1},x_{2},s_{2})=(200,200,100)}
(
s
1
,
s
3
)
{\displaystyle (s_{1},s_{3})}
(
200
,
200
,
000
,
100
,
0
)
{\displaystyle (200,200,000,100,0)}
A
B
4
=
(
1
0
1
0
1
0
1
1
0
)
{\displaystyle A_{B4}={\begin{pmatrix}1&0&1\\0&1&0\\1&1&0\end{pmatrix}}}
(
x
1
,
x
2
,
s
1
)
=
(
100
,
300
,
100
)
{\displaystyle (x_{1},x_{2},s_{1})=(100,300,100)}
(
s
2
,
s
3
)
{\displaystyle (s_{2},s_{3})}
(
100
,
300
,
100
,
0
,
0
)
{\displaystyle (100,300,100,0,0)}
A
B
5
=
(
0
1
0
1
0
0
1
0
1
)
{\displaystyle A_{B5}={\begin{pmatrix}0&1&0\\1&0&0\\1&0&1\end{pmatrix}}}
(
x
2
,
s
1
,
s
3
)
=
(
300
,
200
,
100
)
{\displaystyle (x_{2},s_{1},s_{3})=(300,200,100)}
(
x
1
,
s
3
)
{\displaystyle (x_{1},s_{3})}
(
0
,
300
,
200
,
0
,
100
)
{\displaystyle (0,300,200,0,100)}
b
=
(
200
300
400
)
{\displaystyle b={\begin{pmatrix}200\\300\\400\end{pmatrix}}}
Basen von A- mit unzulässigen Lösung
Bearbeiten
Hier gibt es eine Übersicht der Basen von A mit unzulässigen Lösungen.
A
B
{\displaystyle A_{B}}
x
B
{\displaystyle x_{B}}
x
N
{\displaystyle x_{N}}
x
A
B
6
=
(
1
0
0
0
1
0
1
1
1
)
{\displaystyle A_{B6}={\begin{pmatrix}1&0&0\\0&1&0\\1&1&1\end{pmatrix}}}
(
x
1
,
x
2
,
s
3
)
=
(
100
,
300
,
−
100
)
{\displaystyle (x_{1},x_{2},s_{3})=(100,300,-100)}
(
s
1
,
s
2
)
{\displaystyle (s_{1},s_{2})}
(
200
,
300
,
0
,
0
,
−
100
)
{\displaystyle (200,300,0,0,-100)}
A
B
7
=
(
0
1
0
1
0
1
1
0
0
)
{\displaystyle A_{B7}={\begin{pmatrix}0&1&0\\1&0&1\\1&0&0\end{pmatrix}}}
(
x
2
,
s
1
,
s
2
)
=
(
400
,
200
,
−
100
)
{\displaystyle (x_{2},s_{1},s_{2})=(400,200,-100)}
(
x
1
,
s
3
)
{\displaystyle (x_{1},s_{3})}
(
0
,
400
,
200
,
−
100
,
0
)
{\displaystyle (0,400,200,-100,0)}
A
B
8
=
(
1
1
0
0
0
1
1
0
0
)
{\displaystyle A_{B8}={\begin{pmatrix}1&1&0\\0&0&1\\1&0&0\end{pmatrix}}}
(
x
2
,
s
1
,
s
2
)
=
(
400
,
−
200
,
300
)
{\displaystyle (x_{2},s_{1},s_{2})=(400,-200,300)}
(
x
1
,
x
3
)
{\displaystyle (x_{1},x_{3})}
(
200
,
200
,
000
,
100
,
0
)
{\displaystyle (200,200,000,100,0)}
A
B
4
=
(
1
0
1
0
1
0
1
1
0
)
{\displaystyle A_{B4}={\begin{pmatrix}1&0&1\\0&1&0\\1&1&0\end{pmatrix}}}
(
x
1
,
x
2
,
s
1
)
=
(
100
,
300
,
100
)
{\displaystyle (x_{1},x_{2},s_{1})=(100,300,100)}
(
s
2
,
s
3
)
{\displaystyle (s_{2},s_{3})}
(
100
,
300
,
100
,
0
,
0
)
{\displaystyle (100,300,100,0,0)}
A
B
5
=
(
0
1
0
1
0
0
1
0
1
)
{\displaystyle A_{B5}={\begin{pmatrix}0&1&0\\1&0&0\\1&0&1\end{pmatrix}}}
(
x
2
,
s
1
,
s
3
)
=
(
300
,
200
,
100
)
{\displaystyle (x_{2},s_{1},s_{3})=(300,200,100)}
(
x
1
,
x
3
)
{\displaystyle (x_{1},x_{3})}
(
0
,
400
,
−
200
,
300
,
0
)
{\displaystyle (0,400,-200,300,0)}
Diese Basen haben keine zulässige Lösungen, da
x
B
{\displaystyle x_{B}}
Die Teilmengen
(
1
1
0
0
0
0
1
0
1
)
(
0
0
0
1
1
0
1
0
1
)
{\displaystyle {\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}}}
