3Solutions of linear programs
IB Optimisation
3.4 Linear programming duality
Consider the linear program in general form with slack variables,
minimize c
T
x subject to Ax − z = b, x, z ≥ 0
We have X = {(x, z) : x, z ≥ 0} ⊆ R
m+n
.
The Lagrangian is
L(x, z, λ) = c
T
x − λ
T
(Ax − z − b) = (c
T
− λ
T
A)x + λ
T
z + λ
T
b.
Since x, z can be arbitrarily positive, this has a finite minimum if and only if
c
T
− λ
T
A ≥ 0, λ
T
≥ 0.
Call the feasible set
Y
. Then for fixed
λ ∈ Y
, the minimum of
L
(
x, z, λ
) is
attained when (c
T
− λ
T
A)x and λ
T
z = 0 by complementary slackness. So
g(λ) = inf
(x,z)∈X
L(x, z, λ) = λ
T
b.
The dual is thus
maximize λ
T
b subject to A
T
λ ≤ c, λ ≥ 0
Theorem. The dual of the dual of a linear program is the primal.
Proof.
It suffices to show this for the linear program in general form. We have
shown above that the dual problem is
minimize −b
T
λ subject to −A
T
λ ≥ −c, λ ≥ 0.
This problem has the same form as the primal, with
−b
taking the role of
c
,
−c
taking the role of
b
,
−A
T
taking the role of
A
. So doing it again, we get back to
the original problem.
Example. Let the primal problem be
maximize 3x
1
+ 2x
2
subject to
2x
1
+ x
2
+ z
1
= 4
2x
1
+ 3x
2
+ z
2
= 6
x
1
, x
2
, z
1
, z
2
≥ 0.
Then the dual problem is
minimize 4λ
1
+ 6λ
2
such that
2λ
1
+ 2λ
2
− µ
1
= 3
λ
1
+ 3λ
2
− µ
2
= 2
λ
1
, λ
2
, µ
1
, µ
2
≥ 0.
We can compute all basic solutions of the primal and the dual by setting
n−m−
2
variables to be zero in turn.
Given a particular basic solutions of the primal, the corresponding solutions
of the dual can be found by using the complementary slackness solutions:
λ
1
z
1
= λ
2
z
2
= 0, µ
1
x
1
= µ
2
x
2
= 0.
x
1
x
2
z
1
z
2
f(x) λ
1
λ
2
µ
1
µ
2
g(λ)
A 0 0 4 6 0 0 0 -3 -2 0
B 2 0 0 2 6
3
2
0 0 −
1
2
6
C 3 0 -2 0 9 0
3
2
0
5
2
9
D
3
2
1 0 0
13
2
5
4
1
4
0 0
13
2
E 0 2 2 0 4 0
2
3
−
5
3
0 4
F 0 4 0 -6 8 2 0 1 0 8
A B
D
E
C
F
x
1
x
2
2x
1
+ x
2
= 4
2x
1
+ 3x
2
= 6
C
D
F
A
B
E
λ
1
λ
2
2λ
1
+ 2λ
2
= 3
λ
1
+ 3λ
2
= 2
We see that
D
is the only solution such that both the primal and dual solutions
are feasible. So we know it is optimal without even having to calculate
f
(
x
). It
turns out this is always the case.
Theorem.
Let
x
and
λ
be feasible for the primal and the dual of the linear
program in general form. Then
x
and
λ
and optimal if and only if they satisfy
complementary slackness, i.e. if
(c
T
− λ
T
A)x = 0 and λ
T
(Ax − b) = 0.
Proof. If x and λ are optimal, then
c
T
x = λ
T
b
since every linear program satisfies strong duality. So
c
T
x = λ
T
b
= inf
x
0
∈X
(c
T
x
0
− λ
T
(Ax
0
− b))
≤ c
T
x − λ
T
(Ax − b)
≤ c
T
x.
The last line is since Ax ≥ b and λ ≥ 0.
The first and last term are the same. So the inequalities hold with equality.
Therefore
λ
T
b = c
T
x − λ
T
(Ax − b) = (c
T
− λ
T
A)x + λ
T
b.
So
(c
T
− λ
T
A)x = 0.
Also,
c
T
x − λ
T
(Ax − b) = c
T
x
implies
λ
T
(Ax − b) = 0.
On the other hand, suppose we have complementary slackness, i.e.
(c
T
− λ
T
A)x = 0 and λ
T
(Ax − b) = 0,
then
c
T
x = c
T
x − λ
T
(Ax − b) = (c
T
− λ
T
A)x + λ
T
b = λ
T
b.
Hence by weak duality, x and λ are optimal.