Lecture_12_Duality in LPP

12.1 Duality in LPP
Every LPP called the primal is associated with another LPP called dual. Either of the problems
is primal with the other one as dual. The optimal solution of either problem reveals the
information about the optimal solution of the other.
Let the primal problem be
Max Zx = c1x1 + c2x2 + … +cnxn
Subject to restrictions
a11x1 + a12x2 + … + a1nxn ? b1
a21x1 + a22x2 + … + a2nxn ? b2
.
.
.
am1x1 + am2x2 + … + amnxn ? bn
and
x1 ? 0, x2 ? 0,…, xn ? 0
The corresponding dual is defined as
Min Zw = b1w1 + b2w2 + … + bmwm
Subject to restrictions
a11w1 + a21w2 + … + am1wm ? c1
a12w1 + a22w2 + … + am2wm ? c2
.
.
.
a1nw1 + a2nw2 + ……….+amnwm ? cn
and
w1, w2, …, wm ? 0
Matrix Notation
Primal
Max Zx = CX
Subject to
AX ? b and X ? 0
Dual
Min Zw = bT W
Subject to
Lecture 12
Linear programming : Duality in LPP
1
AT W ? CT and W ? 0
12.2 Important characteristics of Duality
1. Dual of dual is primal
2. If either the primal or dual problem has a solution then the other also has a solution and
their optimum values are equal.
3. If any of the two problems has an infeasible solution, then the value of the objective
function of the other is unbounded.
4. The value of the objective function for any feasible solution of the primal is less than the
value of the objective function for any feasible solution of the dual.
5. If either the primal or dual has an unbounded solution, then the solution to the other
problem is infeasible.
6. If the primal has a feasible solution, but the dual does not have then the primal will not
have a finite optimum solution and vice versa.
12.3 Advantages and Applications of Duality
1. Sometimes dual problem solution may be easier than primal solution, particularly when
the number of decision variables is considerably less than slack / surplus variables.
2. In the areas like economics, it is highly helpful in obtaining future decision in the
activities being programmed.
3. In physics, it is used in parallel circuit and series circuit theory.
4. In game theory, dual is employed by column player who wishes to minimize his
maximum loss while his opponent i.e. Row player applies primal to maximize his
minimum gains. However, if one problem is solved, the solution for other also can be
obtained from the simplex tableau.
5. When a problem does not yield any solution in primal, it can be verified with dual.
6. Economic interpretations can be made and shadow prices can be determined enabling the
managers to take further decisions.