80 Introduction to Linear Optimization and Extensions with MATLAB
R
Now the idea is to first solve for x
B
using the first constraint and then
substitute into the objective function equation z. After the substitution, some
terms will be re-arranged from which a necessary and sufficient condition for
optimality will be obtained.
From the first constraint we have Bx
B
= b − Nx
N
and so x
B
= B
−1
(b −
Nx
N
) and then substituting into
z = c
T
B
x
B
+ c
T
N
x
N
we get
z = c
T
B
B
−1
(b − Nx
N
) + c
T
N
x
N
= c
T
B
B
−1
b − c
T
B
B
−1
Nx
N
+ c
T
N
x
N
= c
T
B
B
−1
b + (c
T
N
− c
T
B
B
−1
N)x
N
= c
T
B
x
∗
B
+ (c
T
N
− c
T
B
B
−1
N)x
N
since x
∗
B
= B
−1
b. Now z is the objective function value associated with x ∈ P
and so z = c
T
x. Also, c
T
x
∗
= c
T
B
x
∗
B
+ c
T
N
x
∗
N
= c
T
B
x
∗
B
since x
∗
N
= 0, so
c
T
x = c
T
B
x
∗
B
+ (c
T
N
− c
T
B
B
−1
N)x
N
or
c
T
x − c
T
x
∗
= (c
T
N
− c
T
B
B
−1
N)x
N
.