Introduction to Algorithms, Third Edition

Lemma 29.8 (Weak linear-programming duality)
Let
N
x
be any feasible solution to the primal linear program in (29.16)–(29.18) and
let
N
y
be any feasible solution to the dual linear program in (29.83)–(29.85). Then,
we have
n
X
j
D
1
c
j
N
x
j
m
X
i
D
1
b
i
N
y
i
:

---

29.4
Duality
881
Proof
We have
n
X
j
D
1
c
j
N
x
j
n
X
j
D
1
m
X
i
D
1
a
ij
N
y
i
!
N
x
j
(by inequalities (29.84))
D
m
X
i
D
1
n
X
j
D
1
a
ij
N
x
j
!
N
y
i
m
X
i
D
1
b
i
N
y
i
(by inequalities (29.17)) .
Corollary 29.9
Let
N
x
be a feasible solution to a primal linear program
.A; b; c/
, and let
N
y
be a
feasible solution to the corresponding dual linear program. If
n
X
j
D
1
c
j
N
x
j
D
m
X
i
D
1
b
i
N
y
i
;
then
N
x
and
N
y
are optimal solutions to the primal and dual linear programs, respec-
tively.
Proof
By Lemma 29.8, the objective value of a feasible solution to the primal
cannot exceed that of a feasible solution to the dual. The primal linear program is
a maximization problem and the dual is a minimization problem. Thus, if feasible
solutions
N
x
and
N
y
have the same objective value, neither can be improved.
Before proving that there always is a dual solution whose value is equal to that
of an optimal primal solution, we describe how to find such a solution. When
we ran the simplex algorithm on the linear program in (29.53)–(29.57), the final
iteration yielded the slack form (29.72)–(29.75) with objective
´
D
28
x
3
=6
x
5
=6
2x
6
=3
,
B
D f
1; 2; 4
g
, and
N
D f
3; 5; 6
g
. As we shall show below, the basic
solution associated with the final slack form is indeed an optimal solution to the
linear program; an optimal solution to linear program (29.53)–(29.57) is therefore
.
N
x
1
;
N
x
2
;
N
x
3
/
D
.8; 4; 0/
, with objective value
.3
8/
C
.1
4/
C
.2
0/
D
28
. As
we also show below, we can read off an optimal dual solution: the negatives of the
coefficients of the primal objective function are the values of the dual variables.
More precisely, suppose that the last slack form of the primal is
´
D
0
C
X
j
2
N
c
0
j
x
j
x
i
D
b
0
i
X
j
2
N
a
0
ij
x
j
for
i
2
B :

---

882
Chapter 29
Linear Programming
Then, to produce an optimal dual solution, we set
N
y
i
D
(
c
0
n
C
i
if
.n
C
i /
2
N ;
0
otherwise
:
(29.91)
Thus, an optimal solution to the dual linear program defined in (29.86)–(29.90)
is
N
y
1
D
0
(since
n
C
1
D
4
2
B
),
N
y
2
D 
c
0
5
D
1=6
, and
N
y
3
D 
c
0
6
D
2=3
.
Evaluating the dual objective function (29.86), we obtain an objective value of
.30
0/
C
.24
.1=6//
C
.36
.2=3//
D
28
, which confirms that the objective value
of the primal is indeed equal to the objective value of the dual. Combining these
calculations with Lemma 29.8 yields a proof that the optimal objective value of the
primal linear program is
28
. We now show that this approach applies in general:
we can find an optimal solution to the dual and simultaneously prove that a solution
to the primal is optimal.