
The Simplex Method 115
The basic variables are then
x
B
= B
−1
b =
x
3
x
4
x
1
=
ε
1
− 2ε
3
5 + ε
2
− ε
3
15 + ε
3
where
B =
1 0 2
0 1 1
0 0 1
, so the reduced costs are
r
2
= −1 − (0, 0, −1)
1 0 2
0 1 1
0 0 1
−1
1
1
0
= −1
and r
5
= 1 (in general, if a variable left the basis in the previous iteration,
then it will not enter the basis in the next iteration), so x
2
is selected to enter
the basis. Then,
d
2
=
−B
−1
N
2
e
2
=
−
1 0 2
0 1 1
0 0 1
−1
1
1
0
0
1
=
−1
−1
0
0
1
.
The minimum ratio test gives
α = min{
ε
1
−2ε
3
1
,
5+ε
2
−ε
3
1
} = ε
1
− 2ε
3
(why?),
so x
3
leaves the basis. Then,
x
2
=
ε
1
− 2ε
3
5 + ε
2
− ε
3
15 + ε
3
0
0
+ (ε
1
− 2ε
3
)
−1
−1
0
0
1
=
0
5 − ε
1
+ ε
2
+ ε