
90 Introduction to Linear Optimization and Extensions with MATLAB
R
FIGURE 3.3
Direction and step length for first iteration of simplex method for Example 3.6.
and
r
2
= c
2
− c
T
B
B
−1
N
2
= −1 − (−1, 0)
T
1 0
0 1
−1
0
1
= −1 < 0 .
Thus, x
(1)
is not optimal. Select x
2
as the non-basic variable to enter the
basis and go to Step 2.
Step 2: Construct d
2
=
−B
−1
N
2
e
2
=
−
1 0
0 1
−1
0
1
0
1
=
0
−1
0
1
.
Since d
2
0 the linear program cannot be determined to be unbounded
at this point. Go to Step 3.
Step 3: Compute the step length α = min
j∈B={1,4}
{−
x
current
j
d
2
j
|d
2
j
< 0}
= {−
x
current
4
d
2
4
} = {−
1
−1
} = 1.
Go to Step 4.
Step 4: Then, x
(2)
= x
(1)
+ αd
2
=
1
1
0
0
+ (1)
0
−1
0
1