Linear Programming Duality

Course Notes

1 Duality in Linear Programming

1.1 Introduction
The concept of duality is a very important aspect of linear programming. It was developed by John
von Neumann in 1947, where he demonstrated that to every linear model called the primal program (P)
corresponds another called the dual program (D), and their objective functions are equal. Since then,
this concept has garnered significant interest in several fields such as non-convex optimization, nonlinear
programming, game theory, etc.
From a theoretical point of view, the concept of duality allows : by solving the dual, to also obtain
the optimal solution of the primal.

1.2 Properties and Dual Construction Rules

Theorem 1
The dual of the dual problem is the primal problem.

1.2.1 Construction Rules

The various transformations are summarized in the following table :
Primal ⇔ Dual
Z(M ax) = cT x ⇔ W (M in) = bT y
ith Constraint ≤ ⇔ Variable yi ≥ 0
ith Constraint ≥ ⇔ Variable yi ≤ 0
ith Constraint = ⇔ yi ∈ R
xj ≥ 0 ⇔ j th constraint ≥
xj ≤ 0 ⇔ j th constraint ≤
xj ∈ R ⇔ j th constraint =

1.3 Example :
Primal Dual
Max 5x1 + 12x2 + 4x3 min 10y1 + 8y2


 y1 + 2y2 ≥ 5


x1 + 2x2 + x3 ≤ 10 2y − y ≥ 12
1 2
s.t. 2x1 − x2 + 3x3 = 8 s.t.

 
y1 + 3y2 ≥ 4
x1 , x 2 , x 3 ≥ 0 

y1 ≥ 0
Max 3x1 + x2 − 2x3 min 10y1 + 7y2 + 8y3
 

 x1 + 2x2 ≥ 10 
 y1 + 3y2 + y3 = 10

3x − x + x = 7 
2y − y ≥ 7
1 2 3 1 2
s.t. s.t.
x1 + 3x3 ≤ 8
 y2 + 3y3 ≥ 8


 

x2 , x 3 ≥ 0 y1 ≤ 0, y2 ∈ R, y3 ≥ 0
Max 2x1 + x2 min 10y1 + 7y2 + 8y3
 

 x1 − 2x2 ≤ 2 
 y1 + 3y2 + y3 = 10

5x + x ≥ 9 
2y − y ≥ 7
1 2 1 2
s.t. s.t.

 −3x + 6x2 = 7 
 y + 3y 3 ≥8


1 

2
x1 , x 2 ≥ 0 y1 ≤ 0, y2 ∈ R, y3 ≥ 0

1
1.4 Primal/Dual Relations
Theorem (Weak Duality).
Consider the primal-dual pair :
max cT x min bT y
s.t.
Ax = b s.t. AT y ≥ c
x≥0
- If x is a feasible solution of the primal and y is a feasible solution of the dual, then
c T x ≤ bT y
- If equality holds, then x is an optimal solution of the primal and y is an optimal solution of the
dual.
Theorem (Strong Duality).
Consider the primal-dual pair :
max cT x
min bT y
s.t. Ax = b
s.t. AT y ≥ c
x≥0
- If both the primal and the dual admit a feasible solution, then they both have a finite optimal solution
and the same optimal objective value. - If the primal (dual) is unbounded, then the dual (primal) has
no feasible solution.
Theorem (Complementary Slackness).
Consider the primal-dual pair :
max cT x
min bT y
s.t. Ax = b
s.t. AT y ≥ c
x≥0
If x is an optimal solution of the primal and y is an optimal solution of the dual, then
xi (aTi y − ci ) = 0
where ai is the i-th column of A. In other words :
xi ≥ 0 ⇒ aTi y = ci
aTi y > ci ⇒ xi = 0

1.5 Example (Solving the Dual using Complementary Slackness Rules)

Primal (P ) :
max z= 5x1 +12x2
+4x3
s.t. x1 +2x2
+x3 ≤ 10 (y1 )
2x1 −x2
+3x3 = 8 (y2 )
x1 , x2 ,
x3 ≥ 0
Dual (D) :
min w = 10y1 +8y2
s.t. y1 +2y2
≥5 (x1 )
2y1 −y2
≥ 12 (x2 )
y1 +3y2
≥4 (x3 )
y1
≥0

2
 Optimal solution of (P ) : ( )
26 12
(x1 , x2 , x3 ) = , ,0
5 5
274
z=
5
x1 > 0 ⇒ y1 + 2y2 = 5
x2 > 0 ⇒ 2y1 − y2 = 12
Optimal solution of (D) : ( )
29 2
(y1 , y2 ) = ,−
5 5
274
w=
5

1.6 Economic Interpretation of Duality

- The canonical form of a linear program can be interpreted as a resource allocation problem. -
Primal-dual pair :
max cT x min bT y
s.t. Ax = b s.t. AT y ≥ c
x≥0
- Data : cj : profit per unit of activity j.
bi : availability of resource i.
aij : consumption of resource i per unit of activity j.
- Variables : xj : level of activity j.
yi : value of one unit of resource i.
Interpretation of Weak Duality

z≤w: profit ≤ value of resources

Interpretation of Strong Duality : The maximum profit is achieved if the resources have been
fully exploited, i.e., until their value is exhausted.

2 Dual Simplex Algorithm

2.0.1 Initial Tableau
All variables

A = (aij )m×n
Matrix of constraint coefficients of the standard program

bi
Vector of right-hand side values
cj coefficient of the objective function corresponding to the variables

2.0.2 Algorithm
1. Put the LP in standard form. 2. Check the optimality criterion : if all bi are positive or zero, stop.
Otherwise { }
c
3. Choose the leaving variable xj , min{bi }. 4. Determine the entering variable : max aijj , aij < 0
5. Perform a pivot and determine a new basic feasible solution. Return to step 2.

3
2.1 Example
Solve the following LP using the dual simplex method :


3x1 + x2 ≥ 150
4x1 + 5x2 ≥ 440


3x1 + 2x2 ≥ 24

x1 , x 2 ≥ 0
In standard form :


 (120x1 + 60x2 )

−3x − x ≤ −150
1 2

 −4x1 − 5x2 ≤ −440


−3x1 − 2x2 ≤ −24

x1 , x 2 ≥ 0



 (120x1 + 60x2 )

−3x − x + x = −150
1 2 3

 −4x1 − 5x2 + x4 = −440


−3x1 − 2x2 + x5 = −24

x1 , x 2 , x 3 , x 4 , x 5 ≥ 0
Initial tableau :
x1 x2 x3 x4 x5 bi
-3 -1 1 0 0 -150
-4 -5 0 1 0 -440
-3 -2 0 0 1 -24
Z 120 60 0 0 0 0

2.1.1 Iteration 1 :
* Min bi = min{−150, −440, −24} = −440 (Note : Correction based on typical reading, the most
negative is often chosen for leaving variable, but the example calculation uses -24. We follow the example’s
pivot choice from L3 with -24).
Actually, from the example’s first iteration : Min bi = min{−15, −20, −24} = −24. So the leaving
variable is x5 (pivot row).

x1 x2 x3 x4 x5 bi
L1 -3 -1 1 0 0 -150
L2 -4 -5 0 1 0 -440
L3 -3 -2 0 0 1 -24
L4 120 60 0 0 0 0
{ } { }
cj 120 60
∗Max for aij < 0 = , = {−40, −30} ⇒ max ratio is − 30
aij −3 −2
So the entering variable is x2 .
Perform row operations :

New L1 = L1 − (1/2)L3? (The example seems to use L1 - (1/2)L3 ? Let’s follow the result)
New L2 = L2 − (5/2)L3
New L3 = (−1/2)L3 (Becomes pivot row for entering variable)
New L4 = L4 + 30L3

Resulting tableau :

4
 x1 x2 x3 x4 x5 bi
-3/2 0 1 0 -1/2 -3
13/2 0 0 1 -5/2 40
3/2 1 0 0 -1/2 12
30 0 0 0 30 720

2.1.2 Iteration 2 :
* Min bi = min{−3, 40, 12} = −3
So the leaving variable is x3 (pivot row).

x1 x2 x3 x4 x5 bi
L1 -3/2 0 1 0 -1/2 -3
L2 13/2 0 0 1 -5/2 40
L3 3/2 1 0 0 -1/2 12
L4 30 0 0 0 30 720
{ } { }
cj 30 30
∗Max for aij < 0 = , = {−20, −60} ⇒ max ratio is − 20
aij −3/2 −1/2
So the entering variable is x1 .
Perform row operations :

New L1 = (−2/3)L1 (Pivot row becomes unit row for x1 )

New L2 = L2 + (13/3)L1
New L3 = L3 + L1
New L4 = L4 + 20L1

Resulting tableau :

x1 x2 x3 x4 x5 bi
1 0 -2/3 0 1/3 2
0 0 13/3 1 -28/6 27
0 1 1 0 -1 9
0 0 20 0 20 780

Stop.
The optimal solution is :
x∗1 = 2, x∗2 = 9, Z ∗ = 780