More Related Content
More from sailavanyar1 (14)
Recently uploaded (20)
INIDNVNCVNKFDNVKNNVIFNVNFINIFDNIFNINIFDICNVIFDIVNX
- 1. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Beni Asllani Beni Asllani University of Tennessee at Chattanooga University of Tennessee at Chattanooga Operations Management - 5th Edition Chapter 13 Supplement Chapter 13 Supplement Roberta Russell & Bernard W. Taylor, III Linear Programming Linear Programming
- 2. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-2 2 Lecture Outline Lecture Outline Model Formulation Graphical Solution Method Linear Programming Model Solution Solving Linear Programming Problems with Excel Sensitivity Analysis
- 3. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-3 3 A model consisting of linear relationships representing a firms objective and resource constraints Linear Programming (LP) LP is a mathematical modeling technique used to determine a level of operational activity in order to achieve an objective, subject to restrictions called constraints
- 4. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-4 4 Types of LP Types of LP
- 5. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-5 5 Types of LP (cont.) Types of LP (cont.)
- 6. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-6 6 Types of LP (cont.) Types of LP (cont.)
- 7. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-7 7 LP Model Formulation LP Model Formulation Decision variables mathematical symbols representing levels of activity of an operation Objective function a linear relationship reflecting the objective of an operation most frequent objective of business firms is to maximize profit most frequent objective of individual operational units (such as a production or packaging department) is to minimize cost Constraint a linear relationship representing a restriction on decision making
- 8. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-8 8 LP Model Formulation (cont.) LP Model Formulation (cont.) Max/min z = c Max/min z = c1 1x x1 1 + c + c2 2x x2 2 + ... + c + ... + cn nx xn n subject to: subject to: a a11 11x x1 1 + a + a12 12x x2 2 + ... + a + ... + a1n 1nx xn n (, =, ) b (, =, ) b1 1 a a21 21x x1 1 + a + a22 22x x2 2 + ... + a + ... + a2n 2nx xn n (, =, ) b (, =, ) b2 2 : : a am1 m1x1 + a x1 + am2 m2x x2 2 + ... + a + ... + amn mnx xn n (, =, ) b (, =, ) bm m x xj j = decision variables = decision variables b bi i = constraint levels = constraint levels c cj j = objective function coefficients = objective function coefficients a aij ij = constraint coefficients = constraint coefficients
- 9. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-9 9 LP Model: Example LP Model: Example Labor Labor Clay Clay Revenue Revenue PRODUCT PRODUCT (hr/unit) (hr/unit) (lb/unit) (lb/unit) ($/unit) ($/unit) Bowl Bowl 1 1 4 4 40 40 Mug Mug 2 2 3 3 50 50 There are 40 hours of labor and 120 pounds of clay There are 40 hours of labor and 120 pounds of clay available each day available each day Decision variables Decision variables x x1 1 = number of bowls to produce = number of bowls to produce x x2 2 = number of mugs to produce = number of mugs to produce RESOURCE REQUIREMENTS RESOURCE REQUIREMENTS
- 10. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-10 10 LP Formulation: Example LP Formulation: Example Maximize Maximize Z Z = $40 = $40 x x1 1 + 50 + 50 x x2 2 Subject to Subject to x x1 1 + + 2 2x x2 2 ｏ ｏ40 hr 40 hr (labor constraint) (labor constraint) 4 4x x1 1 + + 3 3x x2 2 ｏ ｏ120 lb 120 lb (clay constraint) (clay constraint) x x1 1 , , x x2 2 鰹 鰹0 0 Solution is Solution is x x1 1 = 24 bowls = 24 bowls x x2 2 = 8 mugs = 8 mugs Revenue = $1,360 Revenue = $1,360
- 11. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-11 11 Graphical Solution Method Graphical Solution Method 1. 1. Plot model constraint on a set of coordinates Plot model constraint on a set of coordinates in a plane in a plane 2. 2. Identify the feasible solution space on the Identify the feasible solution space on the graph where all constraints are satisfied graph where all constraints are satisfied simultaneously simultaneously 3. 3. Plot objective function to find the point on Plot objective function to find the point on boundary of this space that maximizes (or boundary of this space that maximizes (or minimizes) value of objective function minimizes) value of objective function
- 12. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-12 12 Graphical Solution: Example Graphical Solution: Example 4 4 x x1 1 + 3 + 3 x x2 2 ｏ ｏ120 lb 120 lb x x1 1 + 2 + 2 x x2 2 ｏ ｏ40 hr 40 hr Area common to Area common to both constraints both constraints 50 50 40 40 30 30 20 20 10 10 0 0 | 10 10 | 60 60 | 50 50 | 20 20 | 30 30 | 40 40 x x1 1 x x2 2
- 13. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-13 13 Computing Optimal Values Computing Optimal Values x x1 1 + + 2 2x x2 2 = = 40 40 4 4x x1 1 + + 3 3x x2 2 = = 120 120 4 4x x1 1 + + 8 8x x2 2 = = 160 160 -4 -4x x1 1 - - 3 3x x2 2 = = -120 -120 5 5x x2 2 = = 40 40 x x2 2 = = 8 8 x x1 1 + + 2(8) 2(8) = = 40 40 x x1 1 = = 24 24 4 4 x x1 1 + 3 + 3 x x2 2 ｏ ｏ120 lb 120 lb x x1 1 + 2 + 2 x x2 2 ｏ ｏ40 hr 40 hr 40 40 30 30 20 20 10 10 0 0 | 10 10 | 20 20 | 30 30 | 40 40 x x1 1 x x2 2 Z Z = $50(24) + $50(8) = $1,360 = $50(24) + $50(8) = $1,360 24 8
- 14. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-14 14 Extreme Corner Points Extreme Corner Points x x1 1 = 224 bowls = 224 bowls x x2 2 = = 8 mugs 8 mugs Z Z = $1,360 = $1,360 x x1 1 = 30 bowls = 30 bowls x x2 2 = = 0 mugs 0 mugs Z Z = $1,200 = $1,200 x x1 1 = 0 bowls = 0 bowls x x2 2 = = 20 mugs 20 mugs Z Z = $1,000 = $1,000 A A B B C C | 20 20 | 30 30 | 40 40 | 10 10 x x1 1 x x2 2 40 40 30 30 20 20 10 10 0 0
- 15. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-15 15 4 4x x1 1 + 3 + 3x x2 2 ｏ ｏ120 lb 120 lb x x1 1 + 2 + 2x x2 2 ｏ ｏ40 hr 40 hr 40 40 30 30 20 20 10 10 0 0 B B | 10 10 | 20 20 | 30 30 | 40 40 x x1 1 x x2 2 C C A A Z Z = 70 = 70x x1 1 + 20 + 20x x2 2 Optimal point: Optimal point: x x1 1 = 30 bowls = 30 bowls x x2 2 = = 0 mugs 0 mugs Z Z = $2,100 = $2,100 Objective Function Objective Function
- 16. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-16 16 Minimization Problem Minimization Problem CHEMICAL CONTRIBUTION CHEMICAL CONTRIBUTION Brand Brand Nitrogen (lb/bag) Nitrogen (lb/bag) Phosphate (lb/bag) Phosphate (lb/bag) Gro-plus Gro-plus 2 2 4 4 Crop-fast Crop-fast 4 4 3 3 Minimize Minimize Z Z = $6x = $6x1 1 + $3x + $3x2 2 subject to subject to 2 2x x1 1 + + 4 4x x2 2 16 lb of nitrogen 16 lb of nitrogen 4 4x x1 1 + + 3 3x x2 2 24 lb of phosphate 24 lb of phosphate x x1 1, , x x2 2 0 0
- 17. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-17 17 14 14 12 12 10 10 8 8 6 6 4 4 2 2 0 0 | 2 2 | 4 4 | 6 6 | 8 8 | 10 10 | 12 12 | 14 14 x x1 1 x x2 2 A B C Graphical Solution Graphical Solution x1 = 0 bags of Gro-plus x2 = 8 bags of Crop-fast Z = $24 Z = 6x1 + 3x2
- 18. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-18 18 Simplex Method Simplex Method A mathematical procedure for solving linear programming A mathematical procedure for solving linear programming problems according to a set of steps problems according to a set of steps Slack variables added to constraints to represent unused Slack variables added to constraints to represent unused resources resources x x1 1 + 2x + 2x2 2 + s + s1 1 =40 hours of labor =40 hours of labor 4x 4x1 1 + 3x + 3x2 2 + s + s2 2 =120 lb of clay =120 lb of clay Surplus variables subtracted from constraints to represent variables subtracted from constraints to represent excess above resource requirement. For example excess above resource requirement. For example 2 2x x1 1 + 4 + 4x x2 2 16 is transformed into 16 is transformed into 2 2x x1 1 + 4 + 4x x2 2 - s - s1 1 = 16 = 16 Slack/surplus variables have a 0 coefficient in the objective Slack/surplus variables have a 0 coefficient in the objective function function Z = $40x Z = $40x1 1 + $50x + $50x2 2 + 0s + 0s1 1 + 0s + 0s2 2
- 19. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-19 19 Solution Points with Slack Variables
- 20. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-20 20 Solution Points with Surplus Variables
- 21. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-21 21 Solving LP Problems with Excel Solving LP Problems with Excel Click on Tools to invoke Solver. Objective function Decision variables bowls (x1)=B10; mugs (x2)=B11 =C6*B10+D6*B11 =C7*B10+D7*B11 =E6-F6 =E7-F7
- 22. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-22 22 Solving LP Problems with Excel Solving LP Problems with Excel (cont.) (cont.) After all parameters and constraints have been input, click on Solve. Objective function Decision variables C6*B10+D6*B1140 C7*B10+D7*B11120 Click on Add to insert constraints
- 23. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-23 23 Solving LP Problems with Excel Solving LP Problems with Excel (cont.) (cont.)
- 24. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-24 24 Sensitivity Analysis Sensitivity Analysis
- 25. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-25 25 Sensitivity Range for Labor Hours
- 26. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-26 26 Sensitivity Range for Bowls
- 27. Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- Supplement 13-27 27 Copyright 2006 John Wiley & Sons, Inc. Copyright 2006 John Wiley & Sons, Inc. All rights reserved. Reproduction or translation of this work beyond that All rights reserved. Reproduction or translation of this work beyond that permitted in section 117 of the 1976 United States Copyright Act without express permitted in section 117 of the 1976 United States Copyright Act without express permission of the copyright owner is unlawful. Request for further information permission of the copyright owner is unlawful. Request for further information should be addressed to the Permission Department, John Wiley & Sons, Inc. The should be addressed to the Permission Department, John Wiley & Sons, Inc. The purchaser may make back-up copies for his/her own use only and not for purchaser may make back-up copies for his/her own use only and not for distribution or resale. The Publisher assumes no responsibility for errors, distribution or resale. The Publisher assumes no responsibility for errors, omissions, or damages caused by the use of these programs or from the use of omissions, or damages caused by the use of these programs or from the use of the information herein. the information herein.