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.