Auf dieser Seite wird der Simplex Algorithmus anhand des Beispiels der Gewinnmaximierung Schritt für Schritt durchgegangen.
Zielfunktion:
m
a
x
x
1
+
6
⋅
x
2
+
13
⋅
x
3
{\displaystyle max~x_{1}+6\cdot x_{2}+13\cdot x_{3}}
Nebenbedingungen:
x
1
≤
200
{\displaystyle x_{1}\leq 200}
x
2
≤
300
{\displaystyle x_{2}\leq 300}
x
1
+
x
2
+
x
3
≤
400
{\displaystyle x_{1}+x_{2}+x_{3}\leq 400}
x
2
+
3
⋅
x
3
≤
600
{\displaystyle x_{2}+3\cdot x_{3}\leq 600}
x
1
,
x
2
,
x
3
≥
0
{\displaystyle x_{1},x_{2},x_{3}\geq 0}
Das System lässt sich umschreiben zu:
x
1
+
6
⋅
x
2
+
13
⋅
x
3
=
z
{\displaystyle x_{1}+6\cdot x_{2}+13\cdot x_{3}=z}
x
1
+
s
1
=
200
{\displaystyle x_{1}+s_{1}=200}
x
2
+
s
2
=
300
{\displaystyle x_{2}+s_{2}=300}
x
1
+
x
2
+
x
3
+
s
3
=
400
{\displaystyle x_{1}+x_{2}+x_{3}+s_{3}=400}
x
2
+
3
⋅
x
3
+
s
4
=
600
{\displaystyle x_{2}+3\cdot x_{3}+s_{4}=600}
x
1
,
x
2
,
x
3
,
s
−
1
,
s
2
,
s
3
,
s
4
≥
0
{\displaystyle x_{1},x_{2},x_{3},s-1,s_{2},s_{3},s_{4}\geq 0}
A
=
(
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
)
,
b
=
(
200
300
400
600
)
{\displaystyle 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}}}
Gestartet wird mit der Basislösung, die durch die Schlupfvariable gegeben ist.
A
B
=
(
s
1
,
s
2
,
s
3
,
s
4
)
=
(
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
)
=
a
B
−
1
{\displaystyle 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
)
=
(
1
0
0
0
1
0
1
1
1
0
1
3
)
{\displaystyle 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
=
(
200
300
400
600
)
{\displaystyle b={\begin{pmatrix}200\\300\\400\\600\end{pmatrix}}}
c
T
=
(
1
6
13
0
0
0
0
)
=
(
c
N
T
c
B
T
)
{\displaystyle 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
=
(
1
0
0
0
1
0
1
1
1
0
1
3
)
{\displaystyle 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
=
(
200
300
400
600
)
{\displaystyle A_{B}^{-1}b={\begin{pmatrix}200\\300\\400\\600\end{pmatrix}}}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
b
z
1
6
13
0
s
1
{\displaystyle s_{1}}
1
0
0
200
s
2
{\displaystyle s_{2}}
0
1
0
300
s
3
{\displaystyle s_{3}}
1
1
1
400
s
4
{\displaystyle s_{4}}
0
1
3
600
x
1
,
x
2
,
x
3
{\displaystyle x_{1},x_{2},x_{3}}
s
1
,
s
2
,
s
3
,
s
4
{\displaystyle s_{1},s_{2},s_{3},s_{4}}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
b
z
1
6
13
0
s
1
{\displaystyle s_{1}}
1
0
0
200
s
2
{\displaystyle s_{2}}
0
1
0
300
s
3
{\displaystyle s_{3}}
1
1
1
400
s
4
{\displaystyle s_{4}}
0
1
3
600
E
=
{
j
|
c
x
x
j
>
0
}
=
{
1
,
2
,
3
}
{
x
1
,
x
2
,
x
3
}
{\displaystyle 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
}
{\displaystyle 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
}
{\displaystyle 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
}
{\displaystyle L_{3}=\{i|x_{3}^{i}>0\}=\{3,4\}~\{s_{3},s_{4}\}}
Heuristik: Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt.
x
1
{\displaystyle x_{1}}
0
≤
s
1
=
200
−
x
1
{\displaystyle 0\leq s_{1}=200-x_{1}}
0
≤
s
3
=
400
−
x
1
{\displaystyle 0\leq s_{3}=400-x_{1}}
x
1
=
m
i
n
(
200
,
400
)
=
200
⇒
z
=
200
{\displaystyle x_{1}=min(200,400)=200\Rightarrow z=200}
Hier wird die Zeile von
s
1
u
n
d
s
3
{\displaystyle s_{1}~und~s_{3}}
x
1
{\displaystyle x_{1}}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
0
≤
s
2
=
300
−
x
2
{\displaystyle 0\leq s_{2}=300-x_{2}}
0
≤
s
3
=
400
−
x
2
{\displaystyle 0\leq s_{3}=400-x_{2}}
0
≤
s
4
=
600
−
x
2
{\displaystyle 0\leq s_{4}=600-x_{2}}
x
2
=
m
i
n
(
300
,
400
,
600
)
=
300
⇒
z
=
18000
{\displaystyle x_{2}=min(300,400,600)=300\Rightarrow z=18000}
Hier wird die Zeile von
s
2
,
s
3
u
n
d
s
4
{\displaystyle s_{2},s_{3}~und~s_{4}}
x
2
{\displaystyle x_{2}}
x
2
{\displaystyle x_{2}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
0
≤
s
3
=
400
−
x
3
{\displaystyle 0\leq s_{3}=400-x_{3}}
0
≤
s
4
=
600
−
3
x
3
{\displaystyle 0\leq s_{4}=600-3x_{3}}
x
3
=
m
i
n
(
400
,
200
)
=
200
⇒
z
=
26000
{\displaystyle x_{3}=min(400,200)=200\Rightarrow z=26000}
Hier wird die Zeile von
s
3
u
n
d
s
4
{\displaystyle s_{3}~und~s_{4}}
x
3
{\displaystyle x_{3}}
x
3
{\displaystyle x_{3}}
x
3
{\displaystyle x_{3}}
s
4
{\displaystyle s_{4}}
x
3
{\displaystyle x_{3}}
Der neue Wert von
x
3
{\displaystyle x_{3}}
s
4
=
600
−
x
2
−
3
x
3
⇔
x
3
=
200
−
x
2
3
−
s
4
3
{\displaystyle 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
⋅
200
−
x
2
3
−
s
4
3
=
x
1
+
5
3
x
2
+
13
3
s
4
+
2600
{\displaystyle 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
−
x
2
3
−
s
4
3
=
200
−
x
−
1
−
2
3
x
2
+
s
4
3
{\displaystyle 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
−
x
2
3
−
s
4
3
{\displaystyle s_{4}=200-{\frac {x_{2}}{3}}-{\frac {s_{4}}{3}}}
Das neue Tableau sieht nun so aus:
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
s
4
{\displaystyle s_{4}}
b
z
1
5
3
{\displaystyle {\frac {5}{3}}}
−
13
3
{\displaystyle -{\frac {13}{3}}}
-2600
s
1
{\displaystyle s_{1}}
1
0
0
200
s
2
{\displaystyle s_{2}}
0
1
0
300
s
3
{\displaystyle s_{3}}
1
2
3
{\displaystyle {\frac {2}{3}}}
−
1
3
{\displaystyle -{\frac {1}{3}}}
200
x
3
{\displaystyle x_{3}}
0
1
3
{\displaystyle {\frac {1}{3}}}
1
3
{\displaystyle {\frac {1}{3}}}
200
Was haben wir nun gemacht?
Von der Basis
B
=
(
s
1
,
s
2
,
s
3
,
s
4
)
{\displaystyle B=(s_{1},s_{2},s_{3},s_{4})}
B
′
=
(
s
1
,
s
2
,
s
3
,
x
3
)
{\displaystyle B'=(s_{1},s_{2},s_{3},x_{3})}
T
B
′
=
(
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
)
{\displaystyle 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
′
=
(
1
0
0
0
0
1
0
0
0
0
1
1
0
0
0
3
)
{\displaystyle {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
=
(
1
0
0
0
0
1
0
0
0
0
1
−
1
3
0
0
0
1
3
)
{\displaystyle 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
=
(
1
0
0
0
1
0
1
1
0
0
1
1
)
{\displaystyle {A_{N}}={\begin{pmatrix}1&0&0\\0&1&0\\1&1&0\\0&1&1\end{pmatrix}}}
A
B
′
−
1
A
N
=
(
1
0
0
0
1
0
1
2
3
−
1
3
0
1
3
1
3
)
{\displaystyle 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
=
(
200
300
200
200
)
{\displaystyle {A_{B'}^{-1}}={\begin{pmatrix}200\\300\\200\\200\end{pmatrix}}}
c
T
=
(
1
6
0
0
0
0
13
)
=
(
c
N
′
T
c
B
′
T
)
{\displaystyle 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
′
=
(
1
5
3
−
13
3
)
{\displaystyle 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
{\displaystyle -c_{B}^{T}A_{B}^{-1}b=-2600}
E
=
{
j
|
c
x
x
j
>
0
}
=
{
1
,
2
}
{
x
1
,
x
2
}
{\displaystyle 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
}
{\displaystyle 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
}
{\displaystyle 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
{\displaystyle x_{1}}
0
≤
s
1
=
200
−
x
1
{\displaystyle 0\leq s_{1}=200-x_{1}}
0
≤
s
3
=
200
−
x
1
{\displaystyle 0\leq s_{3}=200-x_{1}}
x
1
=
200
⇒
z
=
2800
{\displaystyle x_{1}=200\Rightarrow z=2800}
Hier wird die Zeile von
s
1
u
n
d
s
3
{\displaystyle s_{1}~und~s_{3}}
x
1
{\displaystyle x_{1}}
x
1
{\displaystyle x_{1}}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
0
≤
s
2
=
300
−
x
2
{\displaystyle 0\leq s_{2}=300-x_{2}}
0
≤
s
2
=
200
−
2
3
x
2
{\displaystyle 0\leq s_{2}=200-{\frac {2}{3}}x_{2}}
0
≤
x
2
=
200
−
1
3
x
2
{\displaystyle 0\leq x_{2}=200-{\frac {1}{3}}x_{2}}
x
2
=
m
i
n
(
300
,
600
)
=
300
⇒
z
=
4400
{\displaystyle x_{2}=min(300,600)=300\Rightarrow z=4400}
Hier wird die Zeile von
s
2
;
s
3
u
n
d
x
3
{\displaystyle s_{2};s_{3}~und~x_{3}}
x
2
{\displaystyle x_{2}}
x
2
{\displaystyle x_{2}}
x
2
{\displaystyle x_{2}}
s
2
{\displaystyle s_{2}}
x
2
{\displaystyle x_{2}}
Der neue Wert von
x
2
{\displaystyle x_{2}}
s
2
=
300
−
x
2
⇔
x
2
=
300
−
s
2
{\displaystyle s_{2}=300-x_{2}\Leftrightarrow x_{2}=300-s_{2}}
z
=
x
1
+
5
3
⋅
(
300
−
s
2
)
−
13
3
s
4
+
2600
=
x
1
+
5
3
s
2
−
13
3
s
4
+
3100
{\displaystyle 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
2
3
⋅
(
300
−
s
2
)
+
s
4
3
=
−
x
1
+
2
3
s
2
+
s
4
3
{\displaystyle 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
−
1
3
⋅
(
300
−
s
2
)
−
s
4
3
=
100
+
1
3
s
2
−
s
4
3
{\displaystyle 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
{\displaystyle x_{1}}
s
2
{\displaystyle s_{2}}
s
4
{\displaystyle s_{4}}
b
z
1
−
5
3
{\displaystyle -{\frac {5}{3}}}
−
13
3
{\displaystyle -{\frac {13}{3}}}
-3100
s
1
{\displaystyle s_{1}}
1
0
0
200
x
2
{\displaystyle x_{2}}
0
1
0
300
s
3
{\displaystyle s_{3}}
1
2
3
{\displaystyle {\frac {2}{3}}}
−
1
3
{\displaystyle -{\frac {1}{3}}}
0
x
3
{\displaystyle x_{3}}
0
−
1
3
{\displaystyle -{\frac {1}{3}}}
1
3
{\displaystyle {\frac {1}{3}}}
100
E
=
{
j
|
c
x
x
j
>
0
}
=
{
1
}
{
x
1
}
{\displaystyle E=\{j|c_{x}x_{j}>0\}=\{1\}~\{x_{1}\}}
L
1
=
{
i
|
x
1
i
>
0
}
=
{
1
,
3
}
{
s
1
,
s
3
}
{\displaystyle 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
{\displaystyle x_{1}}
x
1
{\displaystyle x_{1}}
0
≤
s
1
=
200
−
x
1
{\displaystyle 0\leq s_{1}=200-x_{1}}
0
≤
s
3
=
0
−
x
1
{\displaystyle 0\leq s_{3}=0-x_{1}}
x
1
=
m
i
n
(
200
,
0
)
⇒
z
=
3100
{\displaystyle x_{1}=min(200,0)\Rightarrow z=3100}
Nun wird
s
3
{\displaystyle s_{3}}
x
1
{\displaystyle x_{1}}
s
3
=
x
1
+
2
3
s
2
+
s
4
3
⇔
x
1
=
−
s
3
+
2
3
s
2
+
s
4
3
{\displaystyle 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}}}
z
=
s
3
+
2
3
s
2
+
s
4
3
−
5
3
s
2
−
13
3
s
4
+
3100
=
−
s
3
−
s
2
−
4
s
4
+
3100
{\displaystyle 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
−
2
3
s
2
−
s
4
3
=
200
+
s
3
+
2
3
s
2
+
s
4
3
{\displaystyle 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
{\displaystyle s_{3}}
s
2
{\displaystyle s_{2}}
s
4
{\displaystyle s_{4}}
b
z
-1
-1
-4
-3100
s
1
{\displaystyle s_{1}}
-1
2
3
{\displaystyle {\frac {2}{3}}}
1
3
{\displaystyle {\frac {1}{3}}}
200
x
2
{\displaystyle x_{2}}
0
1
0
300
x
1
{\displaystyle x_{1}}
1
−
2
3
{\displaystyle -{\frac {2}{3}}}
1
3
{\displaystyle {\frac {1}{3}}}
0
x
3
{\displaystyle x_{3}}
0
−
1
3
{\displaystyle -{\frac {1}{3}}}
1
3
{\displaystyle {\frac {1}{3}}}
100
Die Zielfunktion kann nun nicht weiter verbessert werden. Unser x ist nun (0,300,100) und unser z ist 3100.
