Linear Programming -

Duality

RK Jana

1
Lecture Outline

 Concept of duality
 Formulation of dual
 Duality theorems
 Economic interpretation of dual
 Concept of shadow price
 Duality and simplex method
 Dual Simplex algorithm

2
Concept of Duality

One of the most important discoveries in the

early development of linear programming was
the concept of duality. The discovery disclosed
the fact that every LPP has associated with it
another LPP. The original problem is called
the “primal” and the other is called its “dual”.
The optimal solution of either problem reveals
information concerning the optimal solution of
the other.

3
 Case 1

In the summer, the City of Sunset Beach staffs lifeguard

stations seven days a week. Regulations require that city
employees (including lifeguards) work five days a week
and be given two consecutive days off. Insurance
requirements mandate that Sunset Beach provide at
least one lifeguard per 8000 average daily attendance on
any given day. The average daily attendance figures by
day are as follows: Sunday – 58,000, Monday – 42,000,
Tuesday – 35,000, Wednesday – 25,000, Thursday –
44,000, Friday – 51,000 and Saturday – 68,000. Given a
tight budget constraint, the city would like to determine a
schedule that will employ as few lifeguards as possible.

4
 Solution

Min: X1 + X2 + X3 + X4 + X5 + X6 + X7
subject to
X1 + 0.X2 + 0.X3 + X4 + X5 + X6 +X7 ≥ 8 (Sun)
X1 + X2 + 0.X3 + 0.X4 + X5 + X6 +X7 ≥ 6 (Mon)
X1 + X2 + X3 + 0.X4 + 0.X5 + X6 +X7 ≥ 5 (Tue)
X1 + X2 + X3 + X4 + 0.X5 + 0.X6 +X7 ≥ 4 (Wed)
X1 + X2 + X3 + X4 + X5 + 0.X6 + 0.X7 ≥ 6 (Thurs)
0.X1 + X2 + X3 + X4 + X5 +X6 +0.X7 ≥ 7 (Fri)
0.X1 + 0.X2 + X3 + X4 + X5 + X6 +X7 ≥ 9 (Sat)
All variables ≥ 0 and integer
5
 Primal Dual Relationship

Primal Problem Dual Problem

Max Z = c1x1 + c2x2 Min w = b1v1 + b2v2 + b3v3 + b4v4

s. t. s. t.
a11x1 + a12x2  b1 a11v1 + a21v2 + a31v3+ a41v4  c1
a21x1 + a22x2  b2 a12v1 + a22v2 + a32v3+ a42v4  c2
a31x1 + a32x2  b3 v1 , v2 , v3 , v4 0
a41x1 + a42x2  b4
x1 , x2 0

6
 Formulation of Dual

 Number of variables in the dual problem is equal to the

number of constraints in the primal & vice-versa
 The elements of the requirement vector in one problem
are the respective prices in the objective function of
the other problem
 If the primal is maximization type then the dual is
minimization type & vice-versa
 The “less than equal” sign in primal constraints
become “greater than equal” in the dual & vice-versa

7
Dual in Vector Notations

The Primal
Max Z = cx

s. t. Ax  b, x 0

The Dual
Min w = bT v

s. t. AT v  cT, v 0

8
 Example 1

Write the dual of the LPP:

Max Z = x1 + 2x2 + 3x3

s. t.
3x1 + x2 + x3  12
x1 + 2x2 + 4x3  20
2x1 + 5x2 - x3  18
x1 , x2 , x3 0

9
 Continued…

The dual of the LPP:

Min W = 12y1 + 20y2 + 18y3

s. t.
3y1 + y2 + 2y3  1
y1 + 2y2 + 5y3  2
y1 + 4y2 - y3  3
y1 , y2 , y3 0

10
 Example 2

Write the dual of the following primal problem:

11
 Continued…

 The second inequality can be changed to the less-than-or-equal-

to type by multiplying both sides of the inequality by -1 and
reversing the direction of the inequality; that is,

 The equality constraint can be replaced by the following two

inequality constraints:

 If both of these inequality constraints are satisfied, the original

equality constraint is also satisfied.

12
 Continued…

 Multiplying both sides of the inequality by –1 and reversing the

direction of the inequality yields:

 The primal problem can now take the following standard form:

13
 Continued…

The dual of this problem can now be obtained as follows:

Min w = 56v1 - 20v2 + 40v3 - 40v4

s. t.
4v1 - 2v2 + 5v3 - 5v4  12
7v1 - 5v2 + 4v3 - 4v4  4
v1 , v2 , v3 , v4 0

14
 Example 3

Formulate the dual of the LPP:

Max Z = 2x1 + 3x2 + 4x3

s. t.
x1 - 5x2 + 3x3 =7
2x1 - 5x2 + 3x3  3
3x2 - x3  5
x1 , x2 0
and x3 is unrestricted in sign.

15
 Continued…

Rewrite the problem by introducing new positive

variables: x3 = x’3 – x’’3

Max Z = 2x1 + 3x2 + 4(x’3 – x’’3)

s. t.
x1 - 5x2 + 3(x’3 – x’’3)  7
x1 - 5x2 + 3(x’3 – x’’3)  7
2x1 - 5x2 + 3(x’3 – x’’3)  3
3x2 – (x’3 – x’’3) 5
x1 , x2 , x’3 , x’’3 0
16
 Continued…

Writing equivalently:

Max Z = 2x1 + 3x2 + 4(x’3 – x’’3)

s. t.
x1 - 5x2 + 3(x’3 – x’’3)  7
-x1 + 5x2 - 3(x’3 – x’’3)  -7
2x1 - 5x2 + 3(x’3 – x’’3)  3
- 3x2 + (x’3 – x’’3)  -5
x1 , x2 , x’3 , x’’3 0

17
 Continued…

Min w = 7v1 – 7v2 + 3v3 - 5v4

s. t.
v1 - v2 + 2v3 2
- 5v1 + 5v2 - 5v3 - 3v4 3
3v1 – 3v2 + 3v3 + v4 4
-3v1 + 3v2 - 3v3 - v4  -4
v1 , v2 , v3 , v4 0

18
 Continued…

Final form:
Min w = 7v5 + 3v3 - 5v4
s. t.
v5 + 2v3 2
- 5v5 - 5v3 - 3v4  3
3v5 + 3v3 + v4 =4
v3 , v4 0,
v5 (= v1 - v2 ) is unrestricted in sign

19
 Additional Problems

Find the dual of the following primal problems:

Max z = x1 - x2 + 3x3 + 2x4 Min z = x3 + x4 + x5

s. t. s. t.
x1 + (Birth Year)x2  -1 x1 - x3 + x4 - x5 =-2
x1 - 3x2 – x3  7 x2 - x3 - x4 + x5 =1
x1 + x2 – 3x4 = - Roll No xj 0 for all j
x1 , x4 0
x2 , x3 are unrestricted in sign

20
 Continued…

Find the dual of the following primal problems:

Max z = 4x1 + 5x2 - 3x3 Min z = 3x1 - 2x2 + 4x3

s. t. s. t.
x1 + x2 + x3 =1 3x1 + 5x2 + 4x3  7
3x1 + 5x2 – 2x3  65 6x1 + x2 + 3x3  4
x1 + 7x2 + 4x4  120 7x1 - 2x2 - x3  10
x1 , x2 0 x1 - 2x2 + 5x3  3
x3 is unrestricted in sign 4x1 + 7x2 - 2x3  2
xj 0 for all j

21
 Important Theorems in Duality

 Theorem 1: The dual of the dual is primal.

 Theorem 2: If there exists a feasible solution to both
the primal and dual problems such that the objective
values are equal then the solutions are optimum to the
respective problems.
 Theorem 3: An LPP admits of a finite number of
optimum solutions if and only if there exist feasible
solutions to both primal & dual problems.

22
 Continued…

 Theorem 4: If the primal problem has an unbounded

objective function then the dual has no feasible
solution & vice-versa.
 Theorem 5: If any of the constraints in the primal is a
perfect equality, then the corresponding dual variable
is unrestricted in sign.
 Theorem 6: If any of the variables in the primal is
unrestricted in sign, then the corresponding dual
constraint is a perfect equality.

23
 Fundamental Duality Theorem

 (a) If either the primal or the dial has a finite optimal

solution, then the other problems also has a finite
optimal solution.
 (b) If either problem has an unbounded optimum
solution, then the other problem has no feasible
solution.
 (c) Both problems may be infeasible, i.e. may not have
any solution.

24
 Useful Summary
Primal Problem Dual Problem Conclusion

Feasible solution Feasible solution Finite optimum for both

No feasible solution Feasible solution Unbounded dual objective

Feasible solution No feasible solution Unbounded primal objective

No feasible solution No feasible solution No solution exists

Equality constraint … Corresponding dual variable

unrestricted in sign
Primal variable … Corresponding dual constraint
unrestricted in sign is equality type

25
 Duality & Simplex Method

Rule 1

If the primal (dual) variable be related to a slack and/or

surplus variable in the dual (primal) problem, its
optimum solution is directly read off from the net
evaluation row of the optimum dual (primal) simplex
table, as the net evaluation corresponding to this slack
and/or surplus variable.

26
 Continued…

Rule 2

If the primal (dual) variable be related to an artificial

starting variable in the dual (primal) problem, its
optimum value is directly read off from the net
evaluation row of the optimum dual (primal) simplex
table as the net evaluation relating to this artificial
variable after deleting the penalty cost M and changing
sign of the net evaluations.

27
 Continued…

Rule 3

If either problem (primal or dual) has unbounded

solution then the other will have no feasible solution.

28
 Example 4
An animal feed manufacturing company manufactures two types of
feed, Feed Activex and Feed Solutex. Each of the feed must contain
some of the four ingredients prescribed by a veterinary doctor. These
ingredients are a, b, c and d. The daily per head requirement (in kgs)
of the feed and the ingredients in each of the product is given as
follows:
Ingredient Feed Feed Requirement
Activex Solutex
a 1 0 4
b 0 1 6
c 1 2 2
d 2 1 18
Cost 7 5
Determine the quantity of the feeds in the mixture so that the total
cost is minimum.
29
 Continued…

The primal problem:

Min Z = 7x1 + 5x2

s. t. x1 4
x2 6
x1 + 2x2 2
2x1 + x2 18
x1 , x2 0

where x1 and x2 represent the kgs of Feed Activex and Feed

Solutex manufactured.
30
 Continued…

The dual problem:

Max W = 4v1 + 6v2 + 2v3 + 18v4

s. t. v1 + 0.v2 + v3 + 2v4 7
0.v1 + v2 + 2v3 + v4 5
v1, v2, v3, v4 0

31
 Continued…

Table 1
cj 4 6 2 18 0 0

cB vB b v1 v2 v3 v4 s1 s2
0 s1 7 1 0 1 2 1 0
0 s2 5 0 1 2 1 0 1

zj – c j -4 -6 -2 -18 0 0

32
 Continued…

Table 3
cj 4 6 2 18 0 0

cB vB b v1 v2 v3 v4 s1 s2
18 v4 7/2 1/2 0 1/2 1 1/2 0
6 v2 3/2 -1/2 1 3/2 0 -1/2 1

zj – c j 2 0 16 0 6 6

Dual solution: v1 = 0, v2 =3/2, v3 = 0, v4 = 7/2, max w = 72;

Primal solution: x1 = 6, x2 = 6, min z = 72.
33
 Example 5

Use duality to solve the following LPP:

Max Z = 2x1 + x2
s. t. x1 + 2x2 10
x1 + x2 6
x1 - x2 2
x1 - 2x2 1
x1 , x2 0

34
 Continued…

The dual problem:

Min W = 10v1 + 6v2 + 2v3 + v4

s. t. v1 + v2 + v3 + v4 2
2v1 + v2 - v3 - 2v4 1
v1, v2, v3, v4 0

35
 Continued…

Optimal Table
cj -10 -6 -2 -1 0 0 -M -M

cB vB b v1 v2 v3 v4 s1 s2 s3 s4
-2 v3 1/2 -1/2 0 1 3/2 -1/2 1/2 1/2 -1/2
-6 v2 3/2 3/2 1 0 -1/2 -1/2 -1/2 1/2 1/2

zj – cj 2 0 0 1 4 2 M-4 M-2

Dual solution: v1 = 0, v2 =3/2, v3 = 1/2, v4 = 0, min w = 10;

Primal solution: x1 = 4, x2 = 2, max z = 10.
37
 Example 6

Write the dual of the following LPP & hence solve it:

Max Z = 3x1 - 2x2

s. t. x1 4
x2 6
x1 + x2 5
- x2 -1
x1 , x2 0
38
 Continued…

The dual

Min w = 4v1 + 6v2 + 5v3 - v4

s. t.
v1 + v3  3
v2 + v3 - v4  -2
v1 , v2 , v3 , v4 0

39
 Continued…

The standard form

Max w’ = - 4v1 - 6v2 - 5v3 + v4 + 0.s1 + 0.s2

s. t.
v1 + v3 - s1 =3
- v2 - v3 + v4 + s2 =2
vj 0, for j=1,2,3,4; s1 ,s2 0

40
Continued…

Table 1

cj -4 -6 -5 1 0 0

cB vB b v1 v2 v3 v4 s1 s2

-4 v1 3 1 0 1 0 -1 0

0 s2 2 0 -1 -1 1 0 1

zj – c j 0 6 1 -1 4 0

41
 Continued…

Table 2

cj -4 -6 -5 1 0 0

cB vB b v1 v2 v3 v4 s1 s2

-4 v1 3 1 0 1 0 -1 0

1 v4 2 0 -1 -1 1 0 1

zj – c j 0 5 0 0 4 1

v1 = 3, v2 = v3 = 0, v4 = 2, min w = 10; x1 = 4, x2 = 1, max z = 10 42

 Example 7

Use duality to solve the LPP:

Max Z = 2x1 + 3x2
s. t. - x1 + 2x2 4
x1 + x2 6
x1 + 3x2 9
x1 , x2 0

43
 Continued…

The standard form

Max w = - 4v1 - 6v2 - 9v3 + 0.s1 + 0.s2 - M.s3 - M.s4

s. t.
-v1 + v2 + v3 - s1 + s3 =2
2v2 + v2 + 3v3 - s2 + s4 =3
v1 ,v2,v3 , s1,s2,s3,s4 0

44
 Continued…

Table 1
cj -4 -6 -9 0 0 -M -M

cB vB b v1 v2 v3 s1 s2 s3 s4

-M s3 2 -1 1 1 -1 0 1 0

-M s4 3 2 1 3 0 -1 0 1

zj – c j -M+4 -2M+6 -4M+9 M M 0 0

45
 Continued…

Table 2
cj -4 -6 -9 0 0 -M -M

cB vB b v1 v2 v3 s1 s2 s3 s4

-M s3 1 -5/3 2/3 0 -1 1/3 1 -1/3

-9 v3 1 2/3 1/3 1 0 -1/3 0 1/3

zj – c j 5M/3-2 -2M/3+3 0 M -M/3+3 0 4M/3–3

46
 Continued…

Table 3
cj -4 -6 -9 0 0 -M -M

cB vB b v1 v2 v3 s1 s2 s3 s4

-6 v2 3/2 -5/2 1 0 -3/2 1/2 3/2 -1/2

-9 v3 1/2 3/2 0 1 1/2 -1/2 -1/2 1/2

zj – cj 11/2 0 0 9/2 3/2 M–9/2 M–3/2

v1 = 0, v2 = 3/2, v3 = 1/2, min w = 27/2; x1 = 9/2, x2 = 3/2, max z = 27/2

47
 Economic Interpretation of Dual

 The interpretation of the dual variables from the cost of economic

point of view helps us in making decisions on business
processes.
 The primal objective function represents the profit to be
maximized while the constraints give the limits of the resources.
 The dual objective is to minimize the cost of the resources by
considering many alternatives. The value of the alternative uses is
called the shadow prices of the resources.
 The management of the business will be interested in finding the
shadow prices so as to minimize the expenditure associated with
existing capacities of the various resources.
 Example 8
A firm makes two products A and B. Product A and B contribute
Rs 3 and Rs 4 per unit, respectively. Product A requires 6 hrs
processing time in machine M1 and 1 hr in machine M2. Product
B requires 4 hrs processing time in machine M1 and 1 hr in
machine M2. Machine M1 and M2 are available for 60 hrs and 22
hrs, respectively in a week.

Determine the optimum product mix. Write the dual of this

problem and give its economic interpretation.
 Continued…
Primal problem:
Max Z = 3x1 + 4x2
s. t. 6x1 + 4x2 60
x1 + 2x2 22
x1 , x2 0
where x1 is the # units of product A and x2 is the # units of product B.

Dual problem:
Min W = 60v1 + 22v2
s. t. 6v1 + v2 3
4v1 + 2v2 4
v1 , v2 0
where v1 is the cost per hr on machine M1 and v2 is the cost per hr on
50
machine M2.
 Continued…
Final Table using Simplex Method
cj 3 4 0 0

cB xB b x1 x2 s1 s2

3 x1 4 1 0 1/4 -1/2

4 x2 9 0 1 -1/8 -3/4

zj – cj 0 0 1/4 3/2

Primal solution: x1 = 4, x2 = 9, max profit = Rs 48.

Dual solution: v1 = Rs 0.25 /hr, v2 = Rs 1.5 /hr, min machine cost =
Rs 48. 51
 Economic Interpretation

Shadow prices are the opportunity costs that indicate

the potential profit that is lost by not having an
additional unit of the respective right hand side
(resource) assuming that all right hand side values are
used optimally.
Thus, v1 = Rs 0.25 /hr, v2 = Rs 1.5 /hr, means that
additional processing hours on M1 and M2 will
increase the profit by Rs 0.25 and Rs 1.5, respectively.
 Continued…

Similarly, in the primal problem, if we increase the total

available hrs on machine M1 from 60 hrs to 61 hrs, the
new set of constraints will be:
6x1 + 4x2 61
x1 + 2x2 22
Solving the primal with the new set of constraints, the
optimum solution becomes:
x1 = 4.25, x2 = 8.875, max profit = Rs 48.25.
This is exactly Rs 0.25 more than the earlier value of z
when only 60 hrs of machine M1 were available.
 Assignment - I
A dairy has two bottling plants one located in Kolkata (K) and New Delhi
(N). Each plant bottles up three different kinds of milk, i.e., Cow’s, Toned
and Double Toned. The capacity of the two plants in number of bottles
per shift in a day are as follows:
Milk Plant in Kolkata Plant in New Delhi
Cow’s 2000 1000
Toned 2000 3000
Double Toned 1000 1000

Market survey shows that the demand of Cow’s, Toned and Double
Toned milk are at least 14000, 22000 and 1000 bottles per day. The
operating costs per shift of running plants K and N are Rs 900 and Rs
600, respectively. How many shift should the firm run each plant per day
so that the production cost is minimum while still meeting the market
demand. Also, write the dual and give and economic interpretation of
dual variables.