Duel simplex method_operations research .pptx

advanced LPP

1. ADVANCE TOPICS IN LINEAR PROGRAMMING  Duality in Linear Programming  The Dual Simplex Method  Important & Efficient Computational Technique:  The Revised Simplex Method / Simplex Method with Multipliers  Bounded Variables LP Problem  Parametric Analysis 2

2. DUALITY IN LINEAR PROGRAMMING  It is interesting that every linear programming model has two forms: The Primal and The Dual .  The original form of a linear programming model is called the Primal.  The dual is an alternative model form derived completely from the primal. The dual is useful because it provides the decision maker with an alternative way of looking at a problem. 3

3. / // / // / // / // DUALITY (Cont …) STEPS FOR PRIMAL PROBLEM TO DUAL PROBLEM IN CASE OF NON – NORMAL LP PROBLEM: Step –1: If the given LP problem is in non – normal form then we first convert it into normal form, for converting the non – normal LP problem into normal LP problem adopt the following procedure: IN CASE OF MAXIMIZATION PROBLEM Constraints / Variable Type 1. If Less than or equal to ( ≤) type 2. If greater than or equal to ( ≥) type 3. If equal to (=) type 4. Unrestricted – in –sign Decision Variable (X i ) Procedure No Change is required Convert the ‘≥’ type inequality into ‘≤’ type by multiplying it by ‘–1’ . a. Convert the equality into two inequalities in which one having ‘≥’ sign while other having ‘≤’ sign. b. Convert the ‘ ≥’ type inequality into ‘ ≤’ type by multiplying it by ‘– 1’. Any unrestricted in sign decision variable can be rewritten ‘X i ’ as the difference X i = X i – X i of two non – negative decision variables X i , X i . IN CASE OF MINIMIZATION PROBLEM Constraints / Variable Type Procedure 1. If Less than or equal to ( ≤) type 2. If greater than or equal to ( ≥) type 3. If equal to (=) type 4. Unrestricted – in – sign Decision Variable (X i ) Convert the ‘≤’ type inequality into ‘≥’ type by multiplying it by ‘–1’ . No Change is required a. Convert the equality into two inequalities in which one having ‘≥’ sign while other having ‘≤’ sign. b. Convert the ‘≤’ type inequality into ‘≥’ type by multiplying it by ‘–1’ . Any unrestricted in sign decision variable can be rewritten ‘X i ’ as the difference X i = X i – X i of two non – negative decision variables X i , X i .

4. th th th th th Finding Dual of a LP problem Primal Dual Maximization Minimization Minimization Maximization i variable i constraint j constraint j variable x i > Inequality sign of i Constraint: ≥ if dual is maximization ≤ if dual is minimization …contd. to next slide

5. th th th th th th th Finding Dual of a LP problem …contd. Primal Dual i variable unrestricted i constraint with = sign j constraint with = sign j variable unrestricted RHS of j constraint Cost coefficient associated with j th variable in the objective function Cost coefficient associated with i variable in the objective function RHS of i constraint constraints Refer class notes for pictorial representation of all the operations

6. As the given LP problem is in the form of maximum non – normal form so we need to convert it into maximum normal LP problem in which we need all the constraints in the form of less than or equal to ‘≤’ . So, Now restating the primal as below: Maximize: Z = 6X 1 + 8X 2 Subject to: 2X 1 + 3X 2 ≤ 16 –4X 1 – 2X 2 ≤ –16 2X 1 + X 2 ≤ 16 –2X 1 – X 2 ≤ –16 X 1 , X 2 ≥ / / / / Minimize: Z = 16Y 1 –16Y 2 + 16Y Subject to: 2Y 1 – 4Y 2 + 2Y ≥ 6 3Y 1 – 2Y 2 + Y ≥ 8 Where, Y 1 , Y 2 ≥ 0; Y unrestricted in sign Find the dual of the following problem: Maximize: Z = 6X 1 + 8X 2 Subject to: 2X 1 + 3X 2 ≤ 16 4X 1 + 2X 2 ≥ 16 2X 1 + X 2 = 16 X 1 , X 2 ≥ DUALITY (Cont …) DUAL: Minimize: Z = 16Y 1 –16Y 2 + 16Y 3 –16Y 4 Subject to: 2Y 1 – 4Y 2 + 2 Y 3 – 2Y 4 ≥ 6 3Y 1 – 2Y 2 + Y 3 – Y 4 ≥ 8 Y 1 , Y 2 , Y 3 , Y 4 ≥ 11

7. 1 2 3 1 2 3 1 2 3 1 2 3 Find the dual of the following problem: Maximize: Z = 12X + 15X + 9X Subject to: 8X + 16X + 12X ≤ 25 4X + 8X + 10X ≥ 80 7X + 9X + 8X = 105 X , X , X ≥ 1 2 3 1 2 Minimize: Z = 25Y – 80Y + 105Y Subject to: 8Y – 4Y + 7Y ≥ 12 16Y – 8Y + 9Y ≥ 15 12Y – 10Y + 8Y ≥ 9 Where, Y , Y ≥ 0; Y unrestricted in sign 1 2 / 1 2 / / 1 2 / 1 2 / Find the dual of the following problem: Maximize: Z = 3X 1 + X 2 + X 3 – X 4 Subject to: X 1 + X 2 + 2X 3 + 3X 4 ≤ 5 X 3 – X 4 ≥ –1 X 1 – X 2 = –1 X 1 , X 2 , X 3 , X 4 ≥ / / / / Minimize: Z = 5Y 1 + Y 2 – Y Subject to: Y 1 + Y ≥ 3 Y 1 – Y ≥ 1 2Y 1 – Y 2 ≥ 1 3Y 1 + Y 2 ≥ –1 Where, Y 1 , Y 2 ≥ 0; Y (unrestricted in sign) DUALITY (Cont …) 12

8. 1 2 1 2 3 1 2 3 1 2 1 1 1 2 2 2 1 2 3 3 1 2 3 1 2 3 1 2 3 Maximize: Z = –40X – 200X + 0S + 0S + 0S – MA – MA – MA Subject to: 4X + 40X – S + A = 160 3X + 10X – S + A = 60 8X + 10X – S + A = 80 Where: X , X , X , S , S , S , A , A , A ≥ Variables (B) (Qty) DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: PRIMAL PROBLEM: Solve the given LP problem. Minimize: Z = 40X 1 + 200X 2 Subject to: 4X 1 + 40X 2 ≥ 160 3X 1 + 10X 2 ≥ 60 8X 1 + 10X 2 ≥ 80 X 1 , X 2 ≥ Contribution Per Unit C j – 40 – 200 –M –M –M Ratio C Bi Basic Quantity X 1 X 2 S 1 S 2 S 3 A 1 A 2 A 3 –M A 1 160 4 40 * –1 1 4 ← –M A 2 60 3 10 –1 1 6 –M A 3 80 8 10 –1 1 8 Total Profit (Z j ) – 300M – 15M – 60M M M M –M –M –M Net Contribution (C j – Z j ) – 40+15M – 200+60M ↑ –M –M –M 13

9. C Bi C Bi –M DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: Contribution Per Unit C j – 40 – 200 – M – M – M Ratio Basic Variables (B) Quantity (Qty) X 1 X 2 S 1 S 2 S 3 A 1 A 2 A 3 – 200 X 2 4 1/10 1 – 1/40 1/40 40 – M A 2 20 2 1/4 – 1 – 1/4 1 10 – M A 3 40 7 * 1/4 – 1 – 1/4 1 40/7 ← Total Profit (Z j ) – 800 –60M – 20 – 9M – 200 5 – M/2 M M –5+M/2 – M – M Net Contribution (C – Z j ) – 20+9M ↑ –5+M/2 – M – M 5 – 3M/2 Contribution Per Unit C j – 40 – 200 –M –M –M Ratio B.V. (B) Quantity (Qty) X 1 X 2 S 1 S 2 S 3 A 1 A 2 A 3 – 200 X 2 24/7 1 – 1/35 1/70 1/35 – 1/70 240 –M A 2 60/7 5/28 –1 (2/7) * – 5/28 1 –2/7 30 ← – 40 X 1 40/7 1 1/28 – 1/7 –1/28 1/7 --- Total Profit: (Z j ) ( – 6400 – 60M)/7 – 40 – 200 (120 – 5M)/28 M (20 – 2M)/7 ( – 120+ 5M)/28 –M ( – 20+ 2M)/7 Net Contribution (C j – Z j ) ( – 120+ 5M)/28 [(– 20+ 2M)/7] ↑ (120 – 5M)/28 (20 – 2M)/7 14

10. 1 2 DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: Contribution Per Unit C j – 40 – 200 –M –M –M C Bi B.V. (B) Quantity (Qty) X 1 X 2 S 1 S 2 S 3 A 1 A 2 A 3 – 200 X 2 3 1 – 21/560 1/20 21/560 – 1/20 S 3 30 5/8 –7/2 1 –5/8 7/2 –1 – 40 X 1 10 1 1/8 –1/2 –1/8 1/2 Total Profit: (Z j ) – 1000 – 40 – 200 5/2 10 – M+1/8 – M+1/2 –M Net Contribution (C j – Z j ) – 5/2 – 10 – 1/8 – 1/2 Value of ‘Z’ = ( – 40)(10) + ( – 200)(3) = – 1000 Optimal solution is –1000 for Max. ‘Z ’; at X = 10, X = 3. Because Min (Z) = – Max ( – Z) = 1000; at X 1 = 10, X 2 = 3. 15

11. 1 2 3 DUAL PROBLEM: The Dual of the above primal is written as follows: Maximize: Z = 160Y 1 + 60Y 2 + 80Y 3 Subject to: 4Y 1 + 3Y 2 + 8Y 3 ≤ 40 40Y 1 + 10Y 2 + 10Y 3 ≤ 200 Y , Y , Y ≥ PRIMAL PROBLEM: Solve the given LP problem. Minimize: Z = 40X 1 + 200X 2 Subject to: 4X 1 + 40X 2 ≥ 160 3X 1 + 10X 2 ≥ 60 8X 1 + 10X 2 ≥ 80 X 1 , X 2 ≥ DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: 16

12. 1 2 3 1 2 1 2 3 1 1 2 3 2 1 2 3 1 2 C Bi C Bi 17 DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: Maximize: Z = 160Y + 60Y + 80Y + 0S + 0S Subject to: 4Y + 3Y + 8Y + S = 40 40Y + 10Y + 10Y + S = 200 Y , Y , Y , S , S ≥ Contribution Per Unit C j 160 60 80 Ratio Basic Variables (B) Quantity (Qty) Y 1 Y 2 Y 3 S 1 S 2 S 1 40 4 3 8 1 10 S 2 200 40 * 10 10 1 5 ← Total Profit (Z j ) Net Contribution (C j – Z j ) 160 ↑ 60 80 Contribution Per Unit C j 160 60 80 Ratio Basic Variables (B) Quantity (Qty) Y 1 Y 2 Y 3 S 1 S 2 S 1 20 2 7 * 1 – 1/10 20/7 ← 160 Y 1 5 1 1/4 1/4 1/40 20 Total Profit (Z j ) 800 160 40 40 4 Net Contribution (C j – Z j ) 20 40 ↑ –4

13. (B) C Bi (Qty) DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: Contribution Per Unit C j 160 60 80 Ratio Basic Variables Quantity (Qty) Y 1 Y 2 Y 3 S 1 S 2 80 Y 3 20/7 (2/7) * 1 1/7 – 1/70 10 ← 160 Y 1 30/7 1 5/28 – 1/28 1/35 24 Total Profit (Z j ) 6400/7 160 360/7 80 40/7 24/7 Net Contribution (C j – Z j ) 60/7 ↑ – 40/7 – 24/7 Contribution Per Unit C j 160 60 80 C Bi Basic Variables (B) Quantity Y 1 Y 2 Y 3 S 1 S 2 60 Y 2 10 1 7/2 1/2 – 1/20 160 Y 1 5/2 1 –5/8 –1/8 3/80 Total Profit (Z j ) 1000 160 60 110 10 3 Net Contribution (C j – Z j ) – 30 – 10 –3 Value of ‘Z ’ = (60)(10) + (160)(5/2) = 1000; at Y 1 = 5/2, Y 2 = 10. 18

14. (B) C Bi (Qty) DUALITY (Cont …) INTERPRETATION OF THE PRIMAL –DUAL SOLUTION RELATIONSHIP: COMPARISON OF THE PRIMAL AND DUAL OPTIMAL TABLE PRIMAL OPTIMAL SOLUTION (After deleting artificial variable columns) Contribution Per Unit C j – 40 – 200 B.V. Quantity (Qty) X 1 X 2 S 1 S 2 S 3 – 200 X 2 3 1 – 21/560 1/20 S 3 30 5/8 –7/2 1 – 40 X 1 10 1 1/8 –1/2 Total Profit: (Z j ) – 1000 – 40 – 200 5/2 10 Net Contribution (C j – Z j ) –5/2 – 10 DUAL OPTIMAL SOLUTION Contribution Per Unit C j 160 60 80 C Bi Basic Variables (B) Quantity Y 1 Y 2 Y 3 S 1 S 2 60 Y 2 10 1 7/2 1/2 – 1/20 160 Y 1 5/2 1 –5/8 –1/8 3/80 Total Profit (Z j ) 1000 160 60 110 10 3 Net Contribution (C j – Z j ) – 30 – 10 –3 19

15. 1 2 3 j j DUALITY (Cont …) INTERPRETATION OF THE PRIMAL – DUAL SOLUTION RELATIONSHIP: COMPARISON OF THE PRIMAL AND DUAL OPTIMAL TABLE Note: The respective coefficients of S , S & Y in the (C – Z ) row (ignoring the sign) from the Dual optimal solution table are 10, 3 & 30.    Now, it is clear that the primal and dual lead to the same solution, even though they are formulated differently. It is also clear that in the final simplex table of primal problem, the absolute value of the numbers in (C j – Z j ) row under the slack variable represents the solutions to the dual problem. In another words it also happens that the absolute value of the (C j – Z j ) values of the slack variable in the optimal dual solution represent the optimal values of the primal ‘X 1 ’ and ‘X 2 ’ variables. The minimum opportunity cost derived in the dual must always be equal the maximum profit derived in the primal.

16. / / T / T / T / T / T / T / * T T DUALITY (Cont …) PRIMAL – DUAL RELATIONSHIPS: WEAK DUALITY THEOREM:  If ‘X ’ is a feasible solution for primal problem and ‘Y ’ is a feasible solution for dual problem, then:  (Primal Objective function value) C X ≤ b Y (Dual Objective function value) if the primal is in a maximization case &  (Primal Objective function value) C X ≥ b Y (Dual Objective function value) if the primal is in a minimization case  This is called the weak duality.  The non – negative quantity β = │ b Y – C X │ is called the duality gap. So, when β = 0, we can say that there is no duality gap. STRONG DUALITY:  If ‘X ’ is an optimal solution for primal problem and ‘Y*’ is an optimal solution for dual problem, then the optimal objective value of the primal is the same as the optimal objective value of the dual: C X* = b Y*; in this case, the duality gap is zero so this is called the strong duality.  DUAL OF THE DUAL IS PRIMAL 21

17. DUAL SIMPLEX METHOD  Dual simplex method, developed by C.E. Lemte, is very similar to the regular simplex method.  The only differences lies in the criterion used for selecting a variable to enter the basis (Basic Variables) and the leave the basis (Basic Variables). In dual simplex method, we first select the variable to leave the basis (Basic Variables) and then the variable to enter the basis (Basic Variables).  In this method the solution starts from optimum but infeasible and remains infeasible until the true optimum is reached at which the solution becomes feasible.  The advantage of this method is avoiding the artificial and surplus variables introducing in the constraints, as the constraint is in the form of greater than or equal to ‘≥’ converted into less than or equal to ‘ ≤ ’ . 22

18. Compute “C j – Z j ” values Mark the key element, perform row operations as in regular simplex method Convert the minimization problem, if any, into the maximization Convert “≥” type constraints, if any, into “ ≤ ” type Convert “≤” type constraints into equations and setup the initial dual simplex table Optimal Solution Obtained 23 a) Select Key row with the most negative “b i ” b) Find ratios of “ C j – Z j ” elements to the negative elements of key row. Select key column with minimum ratio DUAL SIMPLEX ALGORITHM Are All “C j – Z j ” ≤ And b i ≥ NO YES

19. 24 DUAL SIMPLEX METHOD EXAMPLE : Use Dual Simplex method to solve the LP problem. Maximize: Z = –3X 1 – X 2 Subject to: X 1 + X 2 ≥ 1 2X 1 + 3X 2 ≥ 2 X 1 , X 2 ≥ Step – 1: Given problem is already in the form of maximization. So go to the next step. Step – 2: Convert the Given constraints into ( ≤) form by multiplying with ‘– 1 ’ both sides. Maximize: Z = – 3X 1 – X 2 Subject to: – X 1 – X 2 ≤ –1 –2X 1 –3X 2 ≤ –2 X 1 , X 2 ≥ Step – 3: After introducing slack variables (S 1 , S 2 ) standard form of the given problem is: Maximize: Z = – 3X 1 – X 2 + 0S 1 + 0S 2 Subject to: – X 1 – X 2 + S 1 = –1 –2X 1 –3X 2 + S 2 = –2 X 1 , X 2 , S 1 , S 2 ≥

20. C X X S S VarIables (B) (Qty) C X X S S Variables (B) (Qty) DUAL SIMPLEX METHOD (Cont …) Now, we display the initial simplex table: COntribuTion Per Unit C j –3 –1 Bi Bas)c Quantity 1 2 1 2 S 1 –1 –1 –1 1 S 2 –2 –2 –3 1 Total Profit (Z j ) Net Contribution (C j – Z j ) –3 –1 Step– 4: Since all (C j – Z j ) ≤ and all the values in the quantity (Qty) column less than (<) zero. So, the current solution is not optimum basic feasible solution. Step – 5: Contribution Per Unit C j –3 –1 Bi Basic Quantity 1 2 1 2 S 1 –1 –1 –1 1 S 2 ← –2 –2 –3 * 1 Total Profit (Z j ) Net Contribution (C j – Z j ) –3 –1 Replacement Ratio 3/2 (1/3) ↑ --- --- Step – 6: Pivot row indicates that outgoing (leaving) variable is ‘S 2 ’ While Pivot column indicates that incoming (entering) variable is ‘X 2 ’ . So, we replace the outgoing (leaving) variable ‘S 2 ’ by the incoming (entering) variable ‘X 2 ’ together with its contribution per unit. 25

21. Contribution Per Unit C j –3 –1 Bi Basic Variables Quantity 1 2 1 2 S 1 ← –1/3 –1/3 1 (–1/3) * –1 X 2 2/3 2/3 1 –1/3 Total Profit (Z j ) –2/3 –2/3 –1 1/3 Net Contribution (C j – Z j ) –7/3 –1/3 Replacement Ratio 7 --- --- 1 ↑ C X X S S (B) (Qty) C X X S S (B) (Qty) DUAL SIMPLEX METHOD (Cont …) Now, preparing the next duaL simplex table Contribution Per Unit C j –3 –1 Bi Basic Variables Quantity 1 2 1 2 S 2 1 1 –3 1 –1 X 2 1 1 1 –1 Total Profit (Z j ) –1 –1 –1 1 Net Contribution (C j – Z j ) –2 –1 Since all (C j – Z j ) ≤ and all the values in the quantity (Qty) column greater than or equal to zero (≥ 0); so, the current solution is optimum feasible solution. Thus, the optimal feasible solution to the given LP problem is: Maximum Z = – 1; at X 1 = 0, X 2 = 1. 26

22. DUAL SIMPLEX METHOD (Cont …) PRACTICE QUESTION: Use Dual Simplex method to solve the LP problem. Minimize: Z = X 1 + 2X 2 + 3X 3 Subject to: X 1 – X 2 + X 3 ≥ 4 X 1 + X 2 + 2X 3 ≤ 8 X 2 – X 3 ≥ 2 X 1 , X 2 , X 3 ≥ 27