100 Introduction to Linear Optimization and Extensions with MATLAB
R
non-basic variables are x
N
=
x
4
x
3
=
0
0
.
The updated basis matrix B =
1 1
1 2
, the updated non-basis matrix is
N =
0 1
1 0
, c
B
=
c
2
c
1
=
−1
−1
, and c
N
=
c
4
c
3
=
0
0
.
Go to Step 1.
Third Iteration
Step 1: Check the optimality of x
(2)
. The reduced costs r
4
= c
4
−
c
T
B
B
−1
N
4
= 0 ≥ 0 and r
3
= c
3
− c
T
B
B
−1
N
3
= 1 ≥ 0
so x
(2)
=
x
B
x
N
=
x
2
x
1
x
4
x
3
=
2
2
0
0
is an optimal solution with objective
function value −(−2 − 2) = 4 and the simplex method stops.
It turns out that x
(2)
is not the only optimal solution. For instance, if x
4
is increased while x
3
remains at 0, we get
x
B
= B
−1
b − B
−1
N
4
x
4
=
x
2
x
1
=
2
2
−
−1
1
x
4
=
2 + x
4
2 − x
4
.
Thus, for any x
4
≤ 2, any point of the form
x
2
x
1
x
4
x
3
=
2 + x
4
2 − x
4
x
4
0