
The Simplex Method 95
We start (Step 0) the simplex method with the basic feasible solution
x
(0)
=
x
B
x
N
=
x
3
x
4
x
1
x
2
=
1
1
0
0
with B =
1 0
0 1
and N =
−2 1
1 −1
and
c
B
=
c
3
c
4
=
0
0
, c
N
=
c
1
c
2
=
−1
−1
, B = {3, 4}, and N =
{1, 2}.
First Iteration
Step 1: Check the optimality of x
(0)
by computing the reduced costs of the
non-basic variables r
1
and r
2
. Now
r
1
= c
1
− c
T
B
B
−1
N
1
= −1 − (0, 0)
T
1 0
0 1
−1
−2
1
= −1 < 0
and
r
2
= c
2
− c
T
B
B
−1
N
2
= −1 − (0, 0)
T
1 0
0 1
−1
1
−1
= −1 < 0 .
Thus, x
(0)
is not optimal. Choose x
1
as the non-basic variable to enter the
basis. Go to Step 2.
Step 2: Construct
d
1
=
−B
−1
N
1
e
1
=
−
1 0
0 1
−1
−2
1
1
0
=
2
−1
1
0
.
Since d
1
0, the linear