Report

B Linear Programming PowerPoint presentation to accompany Heizer and Render Operations Management, 10e Principles of Operations Management, 8e PowerPoint slides by Jeff Heyl © 2011 Pearson Education, Inc. publishing as Prentice Hall B-1 Outline Requirements of a Linear Programming Problem Formulating Linear Programming Problems Shader Electronics Example Graphical Solution to a Linear Programming Problem Graphical Representation of Constraints Iso-Profit Line Solution Method Corner-Point Solution Method Solving Minimization Problems Linear Programming Applications Production-Mix Example Diet Problem Example 2 Learning Objectives 1. Formulate linear programming models, including an objective function and constraints 2. Graphically solve an LP problem with the iso-profit line method 3. Graphically solve an LP problem with the corner-point method 4. Construct and solve a minimization problem 3 Why Use Linear Programming? A mathematical technique to help plan and make decisions relative to the trade-offs necessary to allocate resources Will find the minimum or maximum value of the objective Guarantees the optimal solution to the model formulated 4 LP Applications 1. Scheduling school buses to minimize total distance traveled 2. Allocating police patrol units to high crime areas in order to minimize response time to 911 calls 3. Scheduling tellers at banks so that needs are met during each hour of the day while minimizing the total cost of labor 5 LP Applications 4. Selecting the product mix in a factory to make best use of machine- and labor-hours available while maximizing the firm’s profit 5. Picking blends of raw materials in feed mills to produce finished feed combinations at minimum costs 6. Determining the distribution system that will minimize total shipping cost 6 Requirements of an LP Problem 1. LP problems seek to maximize or minimize some quantity 2. The presence of restrictions, or constraints 3. There must be alternative courses of action to choose from 4. The objective and constraints in linear programming problems must be expressed in terms of linear equations or inequalities 7 Formulating LP Problems The product-mix problem at Shader Electronics Two products 1. Shader x-pod, a portable music player 2. Shader BlueBerry, an internetconnected color telephone Determine the mix of products that will produce the maximum profit 8 Formulating LP Problems Hours Required to Produce 1 Unit Department Electronic Assembly Profit per unit x-pods (X1) BlueBerrys (X2) 4 2 3 1 $7 $5 Available Hours This Week 240 100 Table B.1 Decision Variables: X1 = number of x-pods to be produced X2 = number of BlueBerrys to be produced 9 Formulating LP Problems Objective Function: Maximize Profit = $7X1 + $5X2 There are three types of constraints Upper limits where the amount used is ≤ the amount of a resource Lower limits where the amount used is ≥ the amount of the resource Equalities where the amount used is = the amount of the resource 10 Formulating LP Problems First Constraint: Electronic time used is ≤ Electronic time available 4X1 + 3X2 ≤ 240 (hours of electronic time) Second Constraint: Assembly time used is ≤ Assembly time available 2X1 + 1X2 ≤ 100 (hours of assembly time) 11 Graphical Solution Can be used when there are two decision variables 1. Plot the constraint equations at their limits by converting each equation to an equality 2. Identify the feasible solution space 3. Create an iso-profit line based on the objective function 4. Move this line outwards until the optimal point is identified 12 Graphical Solution X2 100 – Number of BlueBerrys – 80 – – 60 – – 40 – Electronics (Constraint A) – 20 – Feasible – |– 0 Figure B.3 Assembly (Constraint B) region | | 20 | | 40 | | 60 | | 80 | | 100 X1 Number of x-pods 13 Graphical Solution X2 Iso-Profit Line Solution Method 100 – Number of BlueBerrys Choose a–possible value for the objective 80 –function Assembly (Constraint B) – $210 = 7X1 + 5X2 60 – – Solve for 40 –the axis intercepts of the function Electronics (Constraint A) and plot the line – 20 – Feasible – |– 0 Figure B.3 region X2 = | | 20 | 42 | 40 X1 = 30 | | 60 | | 80 | | 100 X1 Number of x-pods 14 Graphical Solution X2 100 – Number of BlueBerrys – 80 – – 60 – – 40 – $210 = $7X1 + $5X2 (0, 42) – 20 – (30, 0) – |– 0 Figure B.4 | | 20 | | 40 | | 60 | | 80 | | 100 X1 Number of x-pods 15 Graphical Solution X2 100 – Number of BlueBerrys – $350 = $7X1 + $5X2 80 – $280 = $7X1 + $5X2 – 60 – $210 = $7X1 + $5X2 – 40 – – $420 = $7X1 + $5X2 20 – – |– 0 Figure B.5 | | 20 | | 40 | | 60 | | 80 | | 100 X1 Number of x-pods 16 Graphical Solution X2 100 – Number of BlueBerrys – Maximum profit line 80 – – 60 – Optimal solution point (X1 = 30, X2 = 40) – 40 – – $410 = $7X1 + $5X2 20 – – |– 0 Figure B.6 | | 20 | | 40 | | 60 | | 80 | | 100 X1 Number of x-pods 17 Corner-Point Method X2 Number of BlueBerrys 100 – 2 – 80 – – 60 – – 3 40 – – 20 – – 1 Figure B.7 |– 0 | | 20 | | 40 | 4 | 60 | | 80 | | 100 X1 Number of x-pods 18 Corner-Point Method The optimal value will always be at a corner point Find the objective function value at each corner point and choose the one with the highest profit Point 1 : (X1 = 0, X2 = 0) Profit $7(0) + $5(0) = $0 Point 2 : (X1 = 0, X2 = 80) Profit $7(0) + $5(80) = $400 Point 4 : (X1 = 50, X2 = 0) Profit $7(50) + $5(0) = $350 19 Corner-Point Method The optimal value will always be at a Solvepoint for the intersection of two constraints corner (electronics time) 1 + 3X2 ≤ 240 Find the4Xobjective function value at each (assembly time)with the corner 2X point and choose the one 1 + 1X 2 ≤ 100 highest profit Point 1 : 4X1 + 3X2 = 240 - 4X1 - 2X2 = -200 (X1 = 0, X2 = 0) + 1X2 = 40 4X1 + 3(40) = 240 4X1 + 120 = 240 Profit $7(0) + $5(0) = $0 X1 = 30 Point 2 : (X1 = 0, X2 = 80) Profit $7(0) + $5(80) = $400 Point 4 : (X1 = 50, X2 = 0) Profit $7(50) + $5(0) = $350 20 Corner-Point Method The optimal value will always be at a corner point Find the objective function value at each corner point and choose the one with the highest profit Point 1 : (X1 = 0, X2 = 0) Profit $7(0) + $5(0) = $0 Point 2 : (X1 = 0, X2 = 80) Profit $7(0) + $5(80) = $400 Point 4 : (X1 = 50, X2 = 0) Profit $7(50) + $5(0) = $350 Point 3 : (X1 = 30, X2 = 40) Profit $7(30) + $5(40) = $410 21 Solving Minimization Problems Formulated and solved in much the same way as maximization problems In the graphical approach an iso-cost line is used The objective is to move the iso-cost line inwards until it reaches the lowest cost corner point 22 Minimization Example X1 = number of tons of black-and-white picture chemical produced X2 = number of tons of color picture chemical produced Minimize total cost = 2,500X1 + 3,000X2 Subject to: X1 X2 X1 + X2 X1, X2 ≥ 30 tons of black-and-white chemical ≥ 20 tons of color chemical ≥ 60 tons total ≥ $0 nonnegativity requirements 23 Minimization Example Table B.9 X2 60 – X1 + X2 = 60 50 – Feasible region 40 – 30 – b 20 – a 10 – |– 0 X1 = 30 | 10 | 20 X2 = 20 | 30 | 40 | 50 | 60 X1 24 Minimization Example Total cost at a = 2,500X1 + 3,000X2 = 2,500 (40) + 3,000(20) = $160,000 Total cost at b = 2,500X1 + 3,000X2 = 2,500 (30) + 3,000(30) = $165,000 Lowest total cost is at point a 25 LP Applications Production-Mix Example Department Product XJ201 XM897 TR29 BR788 Wiring Drilling .5 1.5 1.5 1.0 3 1 2 3 Assembly 2 4 1 2 Inspection .5 1.0 .5 .5 Unit Profit $ 9 $12 $15 $11 Department Capacity (in hours) Product Minimum Production Level Wiring Drilling Assembly Inspection 1,500 2,350 2,600 1,200 XJ201 XM897 TR29 BR788 150 100 300 400 26 LP Applications X1 = number of units of XJ201 produced X2 = number of units of XM897 produced X3 = number of units of TR29 produced X4 = number of units of BR788 produced Maximize profit = 9X1 + 12X2 + 15X3 + 11X4 subject to .5X1 + 1.5X2 + 1.5X3 + 1X4 3X1 + 1X2 + 2X3 + 3X4 2X1 + 4X2 + 1X3 + 2X4 .5X1 + 1X2 + .5X3 + .5X4 X1 X2 X3 X4 ≤ 1,500 hours of wiring ≤ 2,350 hours of drilling ≤ 2,600 hours of assembly ≤ 1,200 hours of inspection ≥ 150 units of XJ201 ≥ 100 units of XM897 ≥ 300 units of TR29 ≥ 400 units of BR788 27 LP Applications Diet Problem Example Feed Product A B C D Stock X Stock Y Stock Z 3 oz 2 oz 1 oz 6 oz 2 oz 3 oz 0 oz 8 oz 4 oz 1 oz 2 oz 4 oz 28 LP Applications X1 = number of pounds of stock X purchased per cow each month X2 = number of pounds of stock Y purchased per cow each month X3 = number of pounds of stock Z purchased per cow each month Minimize cost = .02X1 + .04X2 + .025X3 Ingredient A requirement: Ingredient B requirement: Ingredient C requirement: Ingredient D requirement: Stock Z limitation: 3X1 + 2X1 + 1X1 + 6X1 + 2X2 + 3X2 + 0X2 + 8X2 + 4X3 1X3 2X3 4X3 X3 X1, X2, X3 ≥ 64 ≥ 80 ≥ 16 ≥ 128 ≤ 80 ≥0 Cheapest solution is to purchase 40 pounds of grain X at a cost of $0.80 per cow 29 In-Class Problems from the Lecture Guide Practice Problems Problem 1: Chad’s Pottery Barn has enough clay to make 24 small vases or 6 large vases. He has only enough of a special glazing compound to glaze 16 of the small vases or 8 of the large vases. Let X1 = the number of small vases and X2 = the number of large vases. The smaller vases sell for $3 each, and the larger vases would bring $9 each. (a) Formulate the problem (b) Solve the problem graphically 30 In-Class Problems from the Lecture Guide Practice Problems Problem 2: A fabric firm has received an order for cloth specified to contain at least 45 pounds of cotton and 25 pounds of silk. The cloth can be woven out of any suitable mix of two yarns A and B. They contain the proportions of cotton and silk (by weight) as shown in the following table: A B Cotton 30% 60% Silk 50% 10% Material A costs $3 per pound, and B costs $2 per pound. What quantities (pounds) of A and B yarns should be used to minimize the cost of this order? 31 32