Duality Theory 143
Since x
∗
is optimal, the corresponding reduced costs are non-negative, i.e.,
r
N
= c
N
− c
T
B
B
−1
N ≥ 0.
Now, let π
∗
= (c
T
B
B
−1
)
T
, then
c − A
T
π
∗
=
c
B
c
N
−
B
T
N
T
π
∗
=
c
B
c
N
−
B
T
N
T
(c
T
B
B
−1
)
T
=
c
B
c
N
−
c
B
(B
−1
N)
T
c
B
=
0
r
N
≥ 0.
Thus, π
∗
is a feasible solution for the dual problem. Furthermore,
b
T
π
∗
= (π
∗
)
T
b = c
T
B
B
−1
b = c
T
B
x
∗
B
= c
T
x
∗
,
so by Corollary 4.6, π
∗
is an optimal solution for the dual.
Example 4.10
Consider the linear program
maximize −2x
1
+ x
2
subject to −x
1
+ x
2
≤ 4
2x
1
+ x
2
≤ 6
x
1
≥ 0, x
2
≥ 0.
To use the simplex method on the primal, we convert to standard form
by adding slack variables x
3
and x
4
and convert the objective to a minimiza-
tion problem by multiplying the objective function by −1 (we omit the outer
negation of the minimization) to get
minimize 2x