Lecture_11_Linear programming : Duality in LPP

11.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.

11.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.

11.4 Steps for a Standard Primal Form

Step 1 – Change the objective function to Maximization form

Step 2 – If the constraints have an inequality sign ‘?’ then multiply both sides by -1 and convert the inequality sign to ‘?’.

Step 3 – If the constraint has an ‘=’ sign then replace it by two constraints involving the inequalities going in opposite directions. For example x1+ 2x2 = 4 is written as
x1+2x2 ? 4
x1+2x2 ? 4 (using step2) ? - x1-2x2 ? - 4

Step 4 – Every unrestricted variable is replaced by the difference of two non-negative variables.

Step5 – We get the standard primal form of the given LPP in which.






11.5

o All constraints have ‘?’ sign, where the objective function is of maximization
form.
o All constraints have ‘?’ sign, where the objective function is of minimization
from.

Rules for Converting any Primal into its Dual


1. Transpose the rows and columns of the constraint co-efficient.
2. Transpose the co-efficient (c1,c2,…cn) of the objective function and the right side constants (b1,b2,…bn)
3. Change the inequalities from ‘?’ to ‘?’ sign.
4. Minimize the objective function instead of maximizing it.