DUALITY

Consider a MAX-Problem (called Primal Problem)

Maximize z = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
subject to
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛  𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛  𝑏2
… … … … …
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛  𝑏𝑚
𝑥1 , 𝑥2 , … , 𝑥𝑛  0
Its DUAL is
Minimize z = 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚
subject to
𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚  𝑐1
𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚  𝑐2
… … … … …
𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚  𝑐𝑛
𝑦1 , 𝑦2 , … , 𝑦𝑚  0

In Matrix form
• LPP in MAX form is (Primal Problem)
Maximize z = cx
subject to
Ax  b
x  0.
where A = (𝑎𝑖𝑗 )𝑚×𝑛 , x = (𝑥1 , 𝑥2 , … , 𝑥𝑛 )𝑡 , c = (𝑐1 , 𝑐2 , … , 𝑐𝑛 ), b = (𝑏1 , 𝑏2 , … , 𝑏𝑚 )𝑡

1
Its DUAL is
Minimize w = 𝑏 𝑡 𝑦
subject to
𝐴𝑡 𝑦  𝑐 𝑡
y0
where y = (𝑦1 , 𝑦2 , … , 𝑦𝑚 )𝑡 .
Similarly, for A MIN-Problem
• LPP in MIN form is
Minimize z = cx
subject to
Ax  b
x  0.
where A = (𝑎𝑖𝑗 )𝑚×𝑛 , x = (𝑥1 , 𝑥2 , … , 𝑥𝑛 )𝑡 , c = (𝑐1 , 𝑐2 , … , 𝑐𝑛 ), b = (𝑏1 , 𝑏2 , … , 𝑏𝑚 )𝑡

Its DUAL is
Maximize w = 𝑏 𝑡 𝑦
subject to
𝐴𝑡 𝑦  𝑐 𝑡
y0
where y = (𝑦1 , 𝑦2 , … , 𝑦𝑚 )𝑡 .
NOTE:
• Number of constraints in Minimization problem is equal to number of
variables in its Dual.
• Number of variables in Minimization problem is equal to number of
constraints in its Dual.
• In general, The Dual of the dual of a Problem is problem itself.
• The Dual of the Dual of a MIN problem is the MIN problem itself.
• The Dual of the Dual of a MAX problem is the MAX problem itself.

2
RESULT:
• If ith constraint of a Primal problem is of equality, then the ith variable of its
Dual is unrestricted in sign.
• If jth variable of a Primal problem is unrestricted in sign, then the j th
constraint of its Dual is of equality sign.
In Addition,
• If ith constraint of a MIN-problem is of less than or equal to inequality, then
the ith variable of its Dual is non-positive (i.e.  0)
• If jth variable of a MIN-problem is  0, then the jth constraint of its Dual is
of greater or equal to inequality.
• If ith constraint of a MAX-problem is of greater than or equal to inequality,
then the ith variable of its Dual is non-positive (i.e.  0)
• If jth variable of a MAX-problem is  0, then the jth constraint of its Dual is
of less than or equal to inequality.

Exercise. Write the dual of the LPP

Min z = 2𝑥1 − 3𝑥2 + 4𝑥3 + 𝑥4
subject to
𝑥1 + 𝑥2 + 3𝑥3 − 2𝑥4  −1
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 = 7
6𝑥1 − 5𝑥2 + 4𝑥3 + 2𝑥4  2
𝑥1 , 𝑥3  0, 𝑥4  0, 𝑥2 unrestricted
Solution.
Second constraint is
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 = 7
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 ≥ 7
 {
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 ≤ 7
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 ≥ 7
 {
−3𝑥1 + 𝑥2 − 2𝑥3 − 5𝑥4 ≥ − 7

3
And multiplying the third constraint by − 1, the LPP becomes
Min z = 2𝑥1 − 3𝑥2 + 4𝑥3 + 𝑥4
subject to
𝑥1 + 𝑥2 + 3𝑥3 − 2𝑥4  −1
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 ≥ 7
−3𝑥1 + 𝑥2 − 2𝑥3 − 5𝑥4 ≥ − 7
−6𝑥1 + 5𝑥2 − 4𝑥3 − 2𝑥4  − 2
𝑥1 , 𝑥3  0, 𝑥4  0, 𝑥2 unrestricted
Since 𝑥4  0
 put 𝑥4 = −𝑥4′
where 𝑥4′  0
Also since 𝑥2 unrestricted
 put 𝑥2 = 𝑥2′ − 𝑥2"
where 𝑥2′ , 𝑥2"  0.
The LPP becomes
Min z = 2𝑥1 − 3𝑥2′ + 3𝑥2" + 4𝑥3 −𝑥4′
subject to
𝑥1 + 𝑥2′ − 𝑥2" + 3𝑥3 + 2𝑥4′  −1
3𝑥1 − 𝑥2′ + 𝑥2" + 2𝑥3 − 5𝑥4′ ≥ 7
−3𝑥1 + 𝑥2′ − 𝑥2" − 2𝑥3 + 5𝑥4′ ≥ − 7
−6𝑥1 + 5𝑥2′ − 5𝑥2" − 4𝑥3 + 2𝑥4′  − 2
𝑥1 , 𝑥2′ , 𝑥2" , 𝑥3 , 𝑥4′  0.
This is a MIN-Problem.

4
Its Dual is
Max w = −𝑦1 + 7𝑦2 − 7𝑦3 − 2𝑦4
subject to
𝑦1 + 3𝑦2 − 3𝑦3 − 6𝑦4 ≤ 2
𝑦1 − 𝑦2 + 𝑦3 + 5𝑦4 ≤ −3
−𝑦1 + 𝑦2 − 𝑦3 − 5𝑦4 ≤ 3
3𝑦1 + 2𝑦2 − 2𝑦3 − 4𝑦4 ≤ 4
2𝑦1 − 5𝑦2 + 5𝑦3 + 2𝑦4 ≤ −1
𝑦1 , 𝑦2 , 𝑦3 , 𝑦4 ≥ 0
Consider the second and third constraints
𝑦1 − 𝑦2 + 𝑦3 + 5𝑦4 ≤ −3
−𝑦1 + 𝑦2 − 𝑦3 − 5𝑦4 ≤ 3
−𝑦 + 𝑦2 − 𝑦3 − 5𝑦4 ≥ 3
 { 1
−𝑦1 + 𝑦2 − 𝑦3 − 5𝑦4 ≤ 3
 −𝑦1 + 𝑦2 − 𝑦3 − 5𝑦4 = 3
Put 𝑦2 − 𝑦3 = 𝑦2′
Then 𝑦2′ is unrestricted in sign.
The Dual becomes
Max w = −𝑦1 + 7𝑦2′ − 2𝑦4
subject to
𝑦1 + 3𝑦2′ − 6𝑦4 ≤ 2
−𝑦1 + 𝑦2′ − 5𝑦4 = 3
3𝑦1 + 2𝑦2′ − 4𝑦4 ≤ 4
2𝑦1 − 5𝑦2′ + 2𝑦4 ≤ −1
𝑦1 , 𝑦4 ≥ 0 ; 𝑦2′ unrestricted.

5
 DUAL of a PROBLEM (Shortcut Method)

DUAL TABLE of A MIN problem

MINIMIZATION MAXIMIZATION
PROBLEM PROBLEM
(DUAL)
0 
VARIABLES 0  CONSTRAINTS
unrestricted =
 0
CONSTRAINTS  0 VARIABLES
= unrestricted

DUAL TABLE of A MAX problem

MAXIMIZATION MINIMIZATION
PROBLEM PROBLEM
(DUAL)
0 
VARIABLES 0  CONSTRAINTS
unrestricted =
 0
CONSTRAINTS  0 VARIABLES
= unrestricted

6
Question. Write the dual of the problem
Min z = 2𝑥1 − 3𝑥2 + 4𝑥3 + 𝑥4
subject to
𝑥1 + 𝑥2 + 3𝑥3 − 2𝑥4  −1
3𝑥1 − 𝑥2 + 2𝑥3 + 5𝑥4 = 7
6𝑥1 − 5𝑥2 + 4𝑥3 + 2𝑥4  2
𝑥1 , 𝑥3  0, 𝑥4  0, 𝑥2 unrestricted

Solution. We have the following dual table for the Minimization problems:

MINIMIZATION MAXIMIZATION
PROBLEM PROBLEM
(DUAL)
0 
VARIABLES 0  CONSTRAINTS
unrestricted =
 0
CONSTRAINTS  0 VARIABLES
= unrestricted

Since the objective function in the given problem is Minimization

 Objective function of the Dual problem will be Maximization
Since number of constraints in the given problem are 3 and number of variables
are 4
 number of variables in the Dual problem will be 3 and number of constraints
will be 4.
Since, in the given problem, first and third variables are  0
 first and third constraints of the Dual are of  signs

7
Since, in the given problem, fourth variable is  0
 fourth constraint of the Dual will be  sign
Since, in the given problem, second variable is unrestricted in sign
 second constraint of the Dual problem will be of = sign
Again, since, in the given problem, first constraint is of  sign
 first variable in the Dual problem will be  0
Since, in the given problem, second constraint is of = sign
 In the Dual, second variable be unrestricted in sign
Since, in the given problem, third constraint is of  sign
 In the Dual problem, third variable will be  0

Using these, the Dual of the given problem is

Maximize w = −𝑦1 + 7𝑦2 + 2𝑦3
subject to
𝑦1 + 3𝑦2 + 6𝑦3  2
𝑦1 − 𝑦2 − 5𝑦3 = −3
3𝑦1 + 2𝑦2 + 4𝑦3  4
−2𝑦1 + 5𝑦2 + 2𝑦3  1
𝑦1  0, 𝑦3  0, 𝑦2 unrestricted.

8
Theorem. Show that Dual of the Dual of a problem is the problem itself.
Proof. Consider the LPP in MIN form is
Minimize z = cx (P)
subject to
Ax  b
x  0.
where A = (𝑎𝑖𝑗 )𝑚×𝑛 , x = (𝑥1 , 𝑥2 , … , 𝑥𝑛 )𝑡 , c = (𝑐1 , 𝑐2 , … , 𝑐𝑛 ), b = (𝑏1 , 𝑏2 , … , 𝑏𝑚 )𝑡
Its DUAL is
Maximize w = 𝑏 𝑡 𝑦 (D)
subject to
𝐴𝑡 𝑦  𝑐 𝑡
y0
where y = (𝑦1 , 𝑦2 , … , 𝑦𝑚 )𝑡 .
Converting the above problem into minimization and multiplying the constraints by
− 1, the Dual (D) becomes
Minimize w* = − 𝑏 𝑡 𝑦
subject to
−𝐴𝑡 𝑦  −𝑐 𝑡
y0
where Min w* = − Max w

The above problem can be rewritten as

Minimize w* = (− 𝑏 𝑡 )𝑦
subject to
(−𝐴𝑡 )𝑦  (−𝑐 𝑡 )
y0
The above problem is in MIN problem,

9
So its Dual is
Maximize t = (−𝑐 𝑡 )𝑡 𝛾
subject to
(−𝐴𝑡 )𝑡 𝛾  (−𝑏 𝑡 )𝑡
0
where  = (𝛾1 , 𝛾2 , … , 𝛾𝑛 )𝑡 .
This problem can be rewritten in the form
Maximize t = −(𝑐 𝑡 )𝑡 𝛾
subject to
−(𝐴𝑡 )𝑡 𝛾  −(𝑏 𝑡 )𝑡
0
Or Maximize t = − c 𝛾
subject to
−𝐴𝛾  − b
0
Converting the problem into Minimization and multiplying the constraints by −1,
we get
Minimize t* = c 
subject to
A  b
 0
where Min t* = − Max t
This problem is equivalent to the given lpp (P).
Hence the Dual of the Dual of a problem is the problem itself.
Remark: In view of above theorem, we have
The Dual of a Min Problem is Max Problem and Dual of a Max Problem is A Min
Problem.

10
Theorem (Weak Duality Theorem)
The value of objective function corresponding to any feasible solution of a Max-
Problem (Primal) is always less than or equal to the value of the objective function
corresponding to any feasible solution of the Dual Problem.
Let 𝑥 0 be a feasible solution to the Primal problem
Maximize z = cx (P)
subject to
Ax  b
x0
and 𝑦 0 be a feasible solution to its dual problem
Minimize w = 𝑏 𝑡 𝑦 (D)
subject to
𝐴𝑡 𝑦  𝑐 𝑡
y0
Then c𝑥 0  𝑏 𝑡 𝑦 0
Proof. Since 𝑥 0 is a feasible solution of the Max Problem (P)
 A𝑥 0  b (1)
𝑥0  0 (2)
And Since 𝑦 0 be a feasible solution of the Dual (D)
𝐴𝑡 𝑦 0  𝑐 𝑡 (3)
𝑦0 0 (4)
By (1) and (4), we have
𝑡 𝑡
𝑦 0 A𝑥 0  𝑦 0 b (5)
From (2) and (3), we have
𝑡 𝑡
𝑥 0 𝐴𝑡 𝑦 0  𝑥 0 𝑐 𝑡 (6)
11
 𝑡
Now 𝑥 0 𝐴𝑡 𝑦 0 is 1  1 matrix i.e. a real number.
𝑡 𝑡 𝑡
 𝑥 0 𝐴𝑡 𝑦 0 = (𝑥 0 𝐴𝑡 𝑦 0 )
𝑡
= 𝑦 0 A𝑥 0 (7)
From (6), (7) and (5), we have
𝑡 𝑡 𝑡 𝑡
𝑥 0 𝑐 𝑡  𝑥 0 𝐴𝑡 𝑦 0 = 𝑦 0 A𝑥 0  𝑦 0 b
𝑡 𝑡
i.e. 𝑥0 𝑐𝑡  𝑦0 b
𝑡 𝑡 𝑡 𝑡
 (𝑥 0 𝑐 𝑡 )  (𝑦 0 b)
 c𝑥 0  𝑏 𝑡 𝑦 0
Hence proved.

Result: If 𝑥 0 is a feasible solution to (P) and 𝑦 0 is a feasible solution of the Dual (D)
with c𝑥 0 = 𝑏 𝑡 𝑦 0
Then 𝑥 0 is an optimal solution to (P) and 𝑦 0 is an optimal solution to (D).
Proof. Let 𝑥 ∗ be any feasible solution to (P)
Since 𝑦 0 is a feasible solution to (D)
 By Weak Duality theorem,
c𝑥 ∗  𝑏 𝑡 𝑦 0
 c𝑥 ∗  𝑏 𝑡 𝑦 0 = c𝑥 0
i.e. c𝑥 ∗  c𝑥 0
Since 𝑥 ∗ is arbitrary feasible solution to (P)
 c𝑥 ∗  c𝑥 0  feasible solution 𝑥 ∗ of (P)
 c𝑥 0 = Max { cx : x is a feasible solution of (P)}
Hence 𝑥 0 is an optimal solution of (P).

12
Again, Let 𝑦 ∗ be any feasible solution to (D)
Since 𝑥 0 is a feasible solution to (P)
 By Weak Duality theorem,
c𝑥 0  𝑏 𝑡 𝑦 ∗
 𝑏 𝑡 𝑦 0  𝑏 𝑡 𝑦 ∗ [Given c𝑥 0 = 𝑏 𝑡 𝑦 0 ]
Since 𝑦 ∗ is arbitrary feasible solution to (D)
 𝑏 𝑡 𝑦 0  𝑏 𝑡 𝑦 ∗  feasible solution 𝑦 ∗ of (D)
 𝑏 𝑡 𝑦 0 = Min { 𝑏 𝑡 𝑦 : y is a feasible solution of (D)}
Hence 𝑦 0 is an optimal solution of (D).
Theorem. If the primal problem (P) has an unbounded solution then its Dual
problem has no feasible solution.
Proof. Let a Primal problem be
Maximize z = cx (P)
subject to
Ax  b
x0
has an unbounded solution.
Its Dual is
Minimize w = 𝑏 𝑡 𝑦 (D)
subject to
𝐴𝑡 𝑦  𝑐 𝑡
y0
To prove the Dual problem (D) has no feasible solution.
Let, if possible, the Dual problem (D) has a feasible solution, say 𝑦 0 with 𝑏 𝑡 𝑦 0 as
the value of objective function.
** Since the primal problem (P) has an unbounded solution
13
 There are infinitely many feasible solutions of (P) corresponding to which the
value of the objective function can be made arbitrarily large.
Consequently, we can find a feasible solution 𝑥 ∗ of (P) satisfying
c𝑥 ∗ > 𝑏 𝑡 𝑦 0 .
This contradicts Weak Duality Theorem.
Thus our assumption is wrong.
Hence, Dual Problem (D) cannot have a feasible solution.
** So, by Weak Duality theorem,
The value of objective function corresponding to any feasible solution of a
Max-Problem (Primal) is always less than or equal to the value of the objective
function corresponding to any feasible solution of the Dual Problem.
i.e. c𝑥 0  𝑏 𝑡 𝑦 0  feasible solution 𝑥 0 of the Primal problem (P).
 Value of objective function of the Primal problem (P) is bounded by 𝑏 𝑡 𝑦 0 .
This contradicts the fact that primal problem (P) has an unbounded solution.
Thus our assumption is wrong.
Hence the Dual problem (D) has no solution.

Theorem (Basic (Strong) Duality Theorem).

If the a Max-Problem (Primal problem) (P) has an optimal solution then its Dual
problem (D) also has an optimal solution with same optimal values of objective
functions.
Proof. Let a Primal problem be
Maximize z = cx (P)
subject to
Ax  b
x0

14
has an optimal solution, say 𝑥 0 with 𝑧 0 = c𝑥 0 as optimal value of the objective
function.
Its Dual is
Minimize w = 𝑏 𝑡 𝑦 (D)
subject to
𝐴𝑡 𝑦  𝑐 𝑡
y  0.
Adding slack variables to constraints of (P), we get
Maximize z = cx (P1)
subject to
Ax + 𝐼𝑚 𝑥𝑠 = b
x, 𝑥𝑠  0
where 𝑥𝑠 is the vector of slack variables.
Since (P) has an optimal solution.
 (P1) will also have an optimal solution and one of the basic feasible solution of
(P1) will be optimal solution of (P1).
𝑥 −1
Let ( 𝐵 ) = (𝐵 𝑏) be an optimal basic feasible solution of (P1) with 𝑧𝐵 = 𝑐𝐵 𝑥𝐵 =
0 0
0
𝑧 as the optimal value of the LPP (P1)
and all 𝑧𝑗 − 𝑐𝑗  0

Now, 𝑧𝑗 − 𝑐𝑗  0  𝐴𝑗  (A : 𝐼𝑚 )

 𝑧𝑗 − 𝑐𝑗  0  𝐴𝑗  A = (𝐴1 , 𝐴2 , … , 𝐴𝑛 )

and 𝑧𝑗 − 𝑐𝑗  0  𝐴𝑗  𝐼𝑚 = (𝑒1 , 𝑒2 , … , 𝑒𝑚 )

i.e. 𝑐𝐵 𝐵−1 𝐴𝑗 − 𝑐𝑗  0  j = 1, 2, …, n

and 𝑐𝐵 𝐵−1 𝑒𝑖 − 𝑐𝑗  0  i = 1, 2, …, m

15
 (𝑐𝐵 𝐵−1 𝐴1 𝑐𝐵 𝐵−1 𝐴2 … 𝑐𝐵 𝐵−1 𝐴𝑛 )  (𝑐1 𝑐2 … 𝑐𝑛 )
and (𝑐𝐵 𝐵−1 𝑒1 𝑐𝐵 𝐵−1 𝑒2 … 𝑐𝐵 𝐵−1 𝑒𝑚 )  (0 0 … 0)
i.e. 𝑐𝐵 𝐵−1 (𝐴1 𝐴2 … 𝐴𝑛 )  c and 𝑐𝐵 𝐵−1 (𝑒1 𝑒2 … 𝑒𝑚 )  0
i.e. (𝑐𝐵 𝐵−1 )𝐴  c and (𝑐𝐵 𝐵−1 )𝐼  0
 ((𝑐𝐵 𝐵−1 )𝐴)𝑡  𝑐 𝑡 and (𝑐𝐵 𝐵−1 )𝑡  0
i.e. 𝐴𝑡 (𝑐𝐵 𝐵−1 )𝑡  𝑐 𝑡 and (𝑐𝐵 𝐵−1 )𝑡  0
Let 𝑦 0 = (𝑐𝐵 𝐵−1 )𝑡
Then, 𝐴𝑡 𝑦 0  𝑐 𝑡
and 𝑦0  0
Thus, 𝑦 0 = (𝑐𝐵 𝐵−1 )𝑡 is a feasible solution to the Dual (D)
The value of the objective function corresponding to 𝑦 0 is
𝑧 0 = 𝑏 𝑡 𝑦 0 = 𝑏 𝑡 (𝑐𝐵 𝐵−1 )𝑡
= (𝑏 𝑡 (𝑐𝐵 𝐵−1 )𝑡 )𝑡 [ as 𝑏 𝑡 (𝑐𝐵 𝐵−1 )𝑡 is 1  1 matrix ]
= (𝑐𝐵 𝐵−1 )𝑏
= 𝑐𝐵 (𝐵−1 𝑏)
= 𝑐𝐵 𝑥𝐵 [ as 𝑥𝐵 = 𝐵−1 𝑏 ]
= 𝑧𝐵 .
We know that “If 𝑥 0 is a feasible solution to (P) and 𝑦 0 is a feasible solution of the
Dual (D) with c𝑥 0 = 𝑏 𝑡 𝑦 0
Then 𝑥 0 is an optimal solution to (P) and 𝑦 0 is an optimal solution to (D)”.
Thus, 𝑦 0 is an optimal solution to (D).
Hence, the Dual problem (D) also possess an optimal solution.

16