Lecture 12 - Linear Programming: Duality in LPP PDF

Lecture 12 Linear programming : 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...

Lecture 12 Linear programming : 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 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. 12.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. 2  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. 12.5 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. 12.6 Example Problems Write the dual of the given problems Example 1 Min Zx = 2x2 + 5x3 Subject to x1+x2 ≥ 2 2x1+x2+6x3 ≤ 6 x1 - x2 +3x3 = 4 x1, x2 , x3 ≥ 0 Solution Primal Max Zx' = -2x2 – 5x3 Subject to -x1-x2 ≤ -2 2x1+x2+6x3 ≤ 6 x1 - x2 +3x3 ≤ 4 -x1 + x2 -3x3 ≤ -4 x1, x2 , x3 ≥ 0 Dual Min Zw = -2w1 + 6w2 + 4w3 – 4w4 Subject to -w1 + 2w2 +w3 –w4 ≥ 0 -w1 + w2 - w3 +w4 ≥ -2 6w2 + 3w3 –3w4 ≥ -5 w1, w2, w3, w4 ≥ 0 Example 2 3 Min Zx = 3x1- 2x2 + 4x3 Subject to 3x1+5x2 + 4x3 ≥ 7 6x1+x2+3x3 ≥ 4 7x1 - 2x2 -x3 ≥ 10 x1 - 2x2 + 5x3 ≥ 3 4x1 + 7x2 - 2x3 ≥ 2 x1, x2 , x3 ≥ 0 Solution Primal Max Zx' = -3x1 + 2x2 - 4x3 Subject to -3x1 - 5x2 - 4x3 ≤ -7 -6x1 - x2 - 3x3 ≤ -4 -7x1 + 2x2 + x3 ≤ - 10 -x1 + 2x2 - 5x3 ≤ - 3 -4x1 - 7x2 + 2x3 ≤ - 2 x1, x2 , x3 ≥ 0 Dual Min Zw = -7w1 - 4w2 - 10w3 – 3w4 -2w5 Subject to -3w1 - 6w2 - 7w3 –w4 – 4w5 ≥ -3 -5w1 - w2 + 2w3 + 2w4 – 7w5 ≥ 2 -4w1 - 3w2 + w3 - 5w4 + 2w5 ≥ -4 w1, w2, w3, w4, w5 ≥ 0 Example 3 Max Z = 2x1+ 3x2 + x3 Subject to 4x1+ 3x2 + x3 = 6 x1+ 2x2 + 5x3 = 4 x1, x2 ≥ 0 Solution Primal Max Zx = 2x1+ 3x2 + x3 Subject to 4x1+ 3x2 + x3 ≤ 6 -4x1 - 3x2 - x3 ≤ -6 x1 + 2x2 + 5x3 ≤ 4 -x1 - 2x2 - 5x3 ≤ -4 4  x1, x2 ≥ 0 Dual Min Zw = 6w1 - 6w2 + 4w3 –4w4 Subject to 4w1 - 4w2 + w3 –w4 ≥ 2 3w1 - 3w2 + 2w3 - 2w4 ≥ 3 w1 - w2 + 5w3 - 5w4 ≥ 1 w1, w2, w3, w4≥ 0 Example 4 Min Zx = x1+ x2 + x3 Subject to x1 - 3x2 + 4x3 = 5 x1 - 2x2 ≤ 3 2x2 - x3 ≥ 4 x1, x2 ≥ 0 ,x3 is unrestricted in sign Solution Primal Max Z' = - x1- x2 – x3' + x3 '' Subject to x1 - 3x2 + 4(x3 ' - x3'') ≤ 5 -x1+ 3x2 - 4(x3' - x3 '') ≤ -5 x1 - 2x2 ≤ 3 -2x2 + x3 ' - x3'' ≤ -4 x1, x2 , x3', x3 '' ≥ 0 Dual Min Zw = 5w1 - 5w2 + 3w3 – 4w4 Subject to w1 - w2 + w3 ≥ -1 -3w1 + 3w2 - 2w3 - 2w4 ≥ -1 4w1 - 4w2 + w4 ≥ -1 -4w1 + 4w2 - w4 ≥ 1 w1, w2, w3, w4, ≥ 0 5