Duality

2. Duality Theory
Every LP problem (called the ‘Primal’) has
associated with another problem called the ‘Dual’.
The ‘Dual’ problem is an LP defined directly and
systematically from the original (or Primal) LP
model.
The optimal solution of one problem yields the
optimal solution to the other.
Duality ease the calculations for the problems,
whose number of variables is large.

3. Rules for converting Primal to
Dual
If the Primal is to maximize, the dual is to minimize.
If the Primal is to minimize, the dual is to maximize.
For every constraint in the primal, there is a dual
variable.
For every variable in the primal, there is a constraint
in the dual.

4. Dual Problem
Primal LP Primal LP ::
Max Max z = cz = c
11xx
11 + c + c
22xx
22 + ... + c + ... + c
nnxx
nn
subject to:subject to:
aa
1111xx
11 + a + a
1212xx
22 + ... + a + ... + a
1n1nxx
nn ≤ b ≤ b
11
aa
2121xx
11 + a + a
2222xx
22 + ... + a + ... + a
2n2nxx
nn ≤ b ≤ b
22
::
aa
m1m1xx
11 + a + a
m2m2xx
22 + ... + a + ... + a
mnmnxx
nn ≤ b ≤ b
m m
xx
1 1 ≥ 0, x≥ 0, x
22 ≥ 0,…….x ≥ 0,…….x
jj ≥ 0,……., x ≥ 0,……., x
nn ≥ 0. ≥ 0.
Associated Dual LP Associated Dual LP ::
Min. z = bMin. z = b
11yy
11 + b + b
22yy
22 + ... + b + ... + b
mmyy
mm
subject to:subject to:
aa
1111yy
11 + a + a
2121yy
22 + ... + a + ... + a
m1m1yy
mm ≥ c ≥ c
11
aa
1212yy
11 + a + a
2222yy
22 + ... + a + ... + a
m2m2yy
mm ≥ c ≥ c
22
::
aa
1n1nyy
11 + a + a
2n2nyy
22 + ... + a + ... + a
mnmnyy
mm ≥ c ≥ c
nn
yy
1 1 ≥ 0, y≥ 0, y
22 ≥ 0,…….y ≥ 0,…….y
jj ≥ 0,……., y ≥ 0,……., y
mm ≥ 0. ≥ 0.

5. Example
Primal
Max. Z = 3x
1
+5x
2
Subject to constraints:
x
1 << 4 y 4 y
11
2x2x
2 2 << 12 y 12 y
22
3x3x
11+2x+2x
2 2 << 18 y 18 y
33
xx
11, x, x
2 2
> 0
The Primal has:
2 variables and 3 constraints.
So the Dual has:
3 variables and 2 constraints
Dual
Min. Z’ = 4y
1
+12y
2
+18y
3
Subject to constraints:
y
1
+ 3y
3
> 3 3
2y2y
2 2 +2y+2y
3 3
> 5 5
yy
11, y, y
22, y, y
3 3
> 0
We define one dual
variable for each primal
constraint.

6. Example
Primal
Min.. Z = 10x
1
+15x
2
Subject to constraints:
5x
1
+ 7x
2
> 80 80
6x6x
1 1 + 11x+ 11x
2 2
> 100 100

xx
11, x, x
2 2
> 0

7. Solution
Dual
Max.. Z’ = 80y
1
+100y
2
Subject to constraints:
5y
1
+ 6y
2 << 10 10
7y7y
1 1 + 11y+ 11y
2 2 << 15 15

yy
11, y, y
2 2
> 0

8. Example
Primal
Max. Z = 12x
1
+ 4x
2
Subject to constraints:
4x
1
+ 7x
2 << 56 56
2x2x
11 + 5x + 5x
2 2
> 20 20
5x5x
1 1 + 4x+ 4x
2 2 = 40 = 40
xx
11, x, x
2 2 > 0

9. Solution
The equality constraint 5x5x
1 1 + 4x+ 4x
2 2 = 40= 40 can be replaced by
the following two inequality constraints:
5x5x
1 1 + 4x+ 4x
2 2 << 40 40
5x5x
1 1 + 4x+ 4x
2 2
> 40 -5x 40 -5x
1 1 - 4x- 4x
2 2 << -40 -40
The second inequality 2x2x
11 + 5x + 5x
2 2
> 20 20 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,
-2x-2x
11 - 5x - 5x
2 2 << -20 -20

10. Cont…
The primal problem can now take the following standard form:
Max. Z = 12x
1
+ 4x
2
Subject to constraints:
4x
1
+ 7x
2 << 56 56
-2x-2x
11 - 5x - 5x
2 2 << -20 -20
5x5x
1 1 + 4x+ 4x
2 2 << 40 40
-5x-5x
1 1 - 4x- 4x
2 2 << -40 -40
xx
11, x, x
2 2
> 0

11. Cont…
Min. Z’ = 56y
1
-20y
2
+ 40y
3
– 40y
4
Subject to constraints:
4y
1
– 2y
2
+ 5y
3
– 5y
4


> 12 12
7y7y
11 - 5y - 5y
2 2 + 4y+ 4y
3 3 – 4y– 4y
4 4
> 4 4

yy
11, y, y
22, y, y
33, y, y
4 4
> 0
The dual of this problem can now be obtained as follows:

12. Example
Primal
Min.. Z = 2x
2
+ 5x
3
Subject to constraints:
x
1
+ x
2
> 2 2
2x2x
11 + x + x
2 2 +6x+6x
3 3 << 6 6
xx
1 1 - x- x
2 2 +3x+3x
3 3 = 4 = 4
xx
11, x, x
22, x, x
3 3 > 0

13. Solution
Primal in standard form :
Max.. Z = -2x
2
- 5x
3
Subject to constraints:
-x
1
- x
2 << -2 -2
2x2x
11 + x + x
2 2 +6x+6x
3 3 << 6 6
xx
1 1 - x- x
2 2 +3x+3x
3 3 << 4 4
- x- x
1 1 + x+ x
2 2 - 3x - 3x
3 3 << -4 -4
xx
11, x, x
22, x, x
3 3 > 0

14. Cont…
Dual
Min. Z’ = -2y
1
+ 6y
2
+ 4y
3
– 4y
4
Subject to constraints:
-y
1
+ 2y
2
+ y
3
– y
4


> 0 0
-y-y
11 + y + y
2 2 - y- y
3 3 + y+ y
4 4
> -2 -2
6y6y
2 2 + 3y+ 3y
3 3 - 3y- 3y
4 4
> -5 -5
yy
11, y, y
22, y, y
33, y, y
4 4
> 0

16. Introduction
Suppose a “basic solution” satisfies the optimality
condition but not feasible, then we apply dual simplex
method. In regular Simplex method, we start with a
Basic Feasible solution (which is not optimal) and
move towards optimality always retaining feasibility. In
the dual simplex method, the exact opposite occurs. We
start with a “optimal” solution (which is not feasible)
and move towards feasibility always retaining
optimality condition.The algorithm ends once we
obtain feasibility.

17. Dual Simplex Method
To start the dual Simplex method, the following
two conditions are to be met:
•The objective function must satisfy the
optimality conditions of the regular Simplex
method.
•All the constraints must be of the type £.

18. Example
Min. Z = 3x
1
+ 2x
2
Subject to constraints:
3x
1
+ x
2
> 3 3
4x4x
1 1 + 3x+ 3x
2 2
> 6 6
xx
1 1 + x+ x
2 2 << 3 3
xx
11, x, x
2 2
> 0

19. Cont…
Step I: The first two inequalities are multiplied by –1
to convert them to << constraints and convert the constraints and convert the
objective function into maximization function.objective function into maximization function.
Max. Z’ = -3x
1
- 2x
2
where Z’= -Z
Subject to constraints:
-3x
1
- x
2 << -3 -3
-4x-4x
1 1 - 3x- 3x
2 2 << -6 -6
xx
1 1 + x+ x
2 2 << 3 3
xx
11, x, x
2 2
> 0

20. Cont…
Let S
1
, S
2
, S
3
be three slack variables
Model can rewritten as:
Z’ + 3x
1
+ 2x
2
= 0
-3x
1
- x
2
+S
1
= -3 -3
-4x-4x
1 1 - 3x- 3x
2 2 +S+S
22 = -6 = -6
xx
1 1 + x+ x
2 2 +S+S
33 = 3 = 3
Initial BS is : x
1
= 0, x
2
= 0, S
1
= -3,
S
2
= -6, S
3
= 3 and Z=0.

21. Cont…
---2/33/4- Ratio
3100110S
3
-6010-3-40S
2
-3001-1-30S
1
0000231Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
•Initial Basic Solution is Optimal (as the optimality condition is satisfied) but
infeasible.
•Choose the most negative basic variable. Therefore, S
2
is the departing
variable.
•Calculate Ratio = |Z row / S
2
row| (S
2
< 0)
•Choose minimum ratio. Therefore, x
2
is the entering variable.

22. Cont…
-2--1/5- Ratio
111/300-1/30S
3
20-1/3014/30x
2
-10-1/310-5/30S
1
402/3001/31Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, S
1
is the departing variable and x
1
is the
entering variable.

23. Cont…
6/512/5-1/5000S
3
6/50-3/54/5100x
2
3/501/5-3/5010x
1
21/503/51/5001Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 3/5, x
2
= 6/5, Z= 21/5

24. Example
Max. Z = -x
1
- x
2
Subject to constraints:
x
1
+ x
2 << 8 8
xx
2 2
> 3 3
-x-x
1 1 + x+ x
2 2 << 2 2
xx
11, x, x
2 2
> 0

25. Cont…
Let S
1
, S
2
, S
3
be three slack variables
Model can rewritten as:
Z + x
1
+ x
2
= 0
x
1
+ x
2
+ S
1
= 8 8
-x-x
2 2 + S+ S
2 2 = -3= -3
-x-x
1 1 + x+ x
2 2 + S+ S
33 = 2 = 2
xx
11, x, x
2 2
> 0
Initial BS is : x
1
= 0, x
2
= 0, S
1
= 8,
S
2
= -3, S
3
= 2 and Z=0.

26. Cont…
---1-- Ratio
21001-10S
3
-3010-100S
2
8001110S
1
0000111Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, S
2
is the departing variable and x
2
is the
entering variable.

27. Cont…
----1- Ratio
-11100-10S
3
30-10100x
2
5011010S
1
-3010011Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, S
3
is the departing variable and x
1
is the
entering variable.

28. Cont…
1-1-10010x
1
30-10100x
2
4021000S
1
-4120001Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 1, x
2
= 3, Z= -4