
158 Introduction to Linear Optimization and Extensions with MATLAB
R
minimize 2x
1
+ 3x
2
subject to −4x
1
+ 3x
2
+x
3
= −5
−x
1
− 2x
2
+x
4
= −4
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0.
Step 0: Recall that the initial basic solution has as basic variables x
(0)
B
=
"
x
(0)
3
x
(0)
4
#
and so x
(0)
N
=
"
x
(0)
1
x
(0)
2
#
, B =
1 0
0 1
and N =
−4 3
−1 −2
with
B = {3, 4} and N = {1, 2}.
Now
x
(0)
B
= B
−1
b =
−5
−4
and so the initial solution is primal infeasible, but
π
(0)
= B
−1
c
B
=
"
π
(0)
1
π
(0)
2
#
=
0
0
and so the reduced costs are r
1
= 2 and
r
2
= 3, and the primal solution satisfies primal optimality conditions (but not
primal feasibility). Let k = 0 and go to Step 1.
Iteration 1
Step 1: Both basic variables x
(0)
B
=
"
x
(0)
3