
120 Introduction to Linear Optimization and Extensions with MATLAB
R
Step 1: Check the optimality of x
(0)
by computing the reduced costs of the
non-basic variables r
1
and r
2
.
First solve the linear system B
T
π = c
B
, i.e.,
1 0
0 1
T
π
1
π
2
=
0
0
and so π =
π
1
π
2
=
0
0
.
Now
r
1
= c
1
− π
T
N
1
= 2 − (0, 0)
−1
2
= 2 ≥ 0
and
r
2
= c
2
− π
T
N
2
= −1 − (0, 0)
1
1
= −1 < 0 .
Thus, x
(0)
is not optimal and x
2
must be selected as the non-basic variable
to enter the basis. Go to Step 2.
Step 2: Solve the system Bd = −N
q
, i.e.,
1 0
0 1
d
1
d
2
= −
1
1
so d =
−1
−1
.
Construct d
2
=
d
e
2
=
−
1 0
0 1
−1
1
1
0
1
=
−1
−1
0
1
.
Since d
2
0, the linear program cannot be determined to be unbounded
at ...