Report

Linear Programming: Modeling Examples Chapter 4 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-1 Chapter Topics A Product Mix Example A Diet Example An Investment Example A Marketing Example A Transportation Example A Blend Example A Multiperiod Scheduling Example A Data Envelopment Analysis Example Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-2 A Product Mix Example Problem Definition (1 of 8) Four-product T-shirt/sweatshirt manufacturing company. ■ Must complete production within 72 hours ■ Truck capacity = 1,200 standard sized boxes. ■ Standard size box holds12 T-shirts. ■ One-dozen sweatshirts box is three times size of standard box. ■ $25,000 available for a production run. ■ 500 dozen blank T-shirts and sweatshirts in stock. ■ How many dozens (boxes) of each type of shirt to produce? Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-3 A Product Mix Example (2 of 8) Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-4 A Product Mix Example Data (3 of 8) Resource requirements for the product mix example. Processing Cost Profit Time (hr) ($) ($) Per dozen per dozen per dozen Sweatshirt - F 0.10 $36 $90 Sweatshirt – B/F 0.25 48 125 T-shirt - F 0.08 25 45 T-shirt - B/F 0.21 35 65 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-5 A Product Mix Example Model Construction (4 of 8) Decision Variables: x1 = sweatshirts, front printing x2 = sweatshirts, back and front printing x3 = T-shirts, front printing x4 = T-shirts, back and front printing Objective Function: Maximize Z = $90x1 + $125x2 + $45x3 + $65x4 Model Constraints: 0.10x1 + 0.25x2+ 0.08x3 + 0.21x4 72 hr 3x1 + 3x2 + x3 + x4 1,200 boxes $36x1 + $48x2 + $25x3 + $35x4 $25,000 x1 + x2 500 dozen sweatshirts x3 + x4 500 dozen T-shirts Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-6 A Product Mix Example Computer Solution with Excel (5 of 8) Objective function Click on “Data” tab to access Solver =D7*B14+E7*B15+F7*B16+G7*B17 =J7-H7 These cells have no effect; added for “cosmetic” purposes. =F11*B16+G11*B17 Exhibit 4.1 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Model formulation included on all Excel files on Companion Web site 4-7 A Product Mix Example Solution with Excel Solver Window (6 of 8) Includes all five constraints. Exhibit 4.2 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-8 A Product Mix Example Solution with QM for Windows (7 of 8) Model solution is: x1=175.56 boxes of front-only sweatshirts x2=57.78 boxes of front and back sweatshirts x3 = 500 boxes of front-only t-shirts Z=$45,522.22 profit Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 4.3 4-9 A Product Mix Example Solution with QM for Windows (8 of 8) Exhibit 4.4 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-10 A Diet Example Data and Problem Definition (1 of 5) Breakfast Food Cal 1. Bran cereal (cup) 90 2. Dry cereal (cup) 110 3. Oatmeal (cup) 100 4. Oat bran (cup) 90 5. Egg 75 6. Bacon (slice) 35 7. Orange 65 8. Milk-2% (cup) 100 9. Orange juice (cup) 120 10. Wheat toast (slice) 65 Fat Cholesterol Iron Calcium Protein Fiber Cost (g) (mg) (mg) (mg) (g) (g) ($) 0 0 6 20 3 5 0.18 2 0 4 48 4 2 0.22 2 0 2 12 5 3 0.10 2 0 3 8 6 4 0.12 5 270 1 30 7 0 0.10 3 8 0 0 2 0 0.09 0 0 1 52 1 1 0.40 4 12 0 250 9 0 0.16 0 0 0 3 1 0 0.50 1 0 1 26 3 3 0.07 Breakfast to include at least 420 calories, 5 milligrams of iron, 400 milligrams of calcium, 20 grams of protein, 12 grams of fiber, and must have no more than 20 grams of fat and 30 milligrams of cholesterol. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-11 A Diet Example Model Construction – Decision Variables (2 of 5) x1 = cups of bran cereal x2 = cups of dry cereal x3 = cups of oatmeal x4 = cups of oat bran x5 = eggs x6 = slices of bacon x7 = oranges x8 = cups of milk x9 = cups of orange juice x10 = slices of wheat toast Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-12 A Diet Example Model Summary (3 of 5) Minimize Z = 0.18x1 + 0.22x2 + 0.10x3 + 0.12x4 + 0.10x5 + 0.09x6 + 0.40x7 + 0.16x8 + 0.50x9 + 0.07x10 subject to: 90x1 + 110x2 + 100x3 + 90x4 + 75x5 + 35x6 + 65x7 + 100x8 + 120x9 + 65x10 420 calories 2x2 + 2x3 + 2x4 + 5x5 + 3x6 + 4x8 + x10 20 g fat 270x5 + 8x6 + 12x8 30 mg cholesterol 6x1 + 4x2 + 2x3 + 3x4+ x5 + x7 + x10 5 mg iron 20x1 + 48x2 + 12x3 + 8x4+ 30x5 + 52x7 + 250x8 + 3x9 + 26x10 400 mg of calcium 3x1 + 4x2 + 5x3 + 6x4 + 7x5 + 2x6 + x7 + 9x8+ x9 + 3x10 20 g protein 5x1 + 2x2 + 3x3 + 4x4+ x7 + 3x10 12 xi 0, for all j Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-13 A Diet Example Computer Solution with Excel (4 of 5) =SUMPRODUCT(C5:C14,F5:F14) or =C5*F5+C6*F6+C7*F7+C8*F8+ C9*F9+C10*F10+C11*F11+C12* F12+C13*F13+C14*F14 Constraint value, 420, typed in cell F17 Decision variable, C5:C14 =SUMPRODUCT(C5:C14,E5:E14) or =C5*E5+C6*E6+C7*E7+C8*E8+ C9*E9+C10*E10+C11*E11+C12* E12+C13*E13+C14*E14 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 4.5 4-14 A Diet Example Solution with Excel Solver Window (5 of 5) Decision variables; “servings” in column C Constraint for “calories” in column F; SUMPRODUCT (C5:C14,F5:F14)<420 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 4.6 4-15 An Investment Example Model Summary (1 of 5) An investor has $70,000 to divide among several instruments. Municipal bonds have an 8.5% return, CD’s a 5% return, t-bills a 6.5% return, and growth stock 13%. The following guidelines have been established: 1. No more than 20% in municipal bonds 2. Investment in CDs should not exceed the other three alternatives 3. At least 30% invested in t-bills and CDs 4. More should be invested in CDs and t-bills than in municipal bonds and growth stocks by a ratio of 1.2 to 1 5. All $70,000 should be invested. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-16 An Investment Example Model Summary (2 of 5) Maximize Z = $0.085x1 + 0.05x2 + 0.065 x3+ 0.130x4 subject to: x1 $14,000 x2 - x1 - x3- x4 0 x2 + x3 $21,000 -1.2x1 + x2 + x3 - 1.2 x4 0 x1 + x2 + x3 + x4 = $70,000 x1, x2, x3, x4 0 where x1 = amount ($) invested in municipal bonds x2 = amount ($) invested in certificates of deposit x3 = amount ($) invested in treasury bills x4 = amount ($) invested in growth stock fund Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-17 An Investment Example Computer Solution with Excel (3 of 5) Objective function, Z, for total return First guideline, =D6*B13 Total investment requirement, =D10*B13+E10*B14+F10*B15+G10*B16 Exhibit 4.7 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-18 An Investment Example Solution with Excel Solver Window (3 of 4) Guideline constraints Exhibit 4.8 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-19 An Investment Example Sensitivity Report (4 of 4) Shadow price for the amount available to invest Exhibit 4.9 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-20 A Marketing Example Data and Problem Definition (1 of 7) Television Commercial Exposure (people/ad or commercial) 20,000 Cost $15,000 Radio Commercial 2,000 6,000 Newspaper Ad 9,000 4,000 Budget limit $100,000 Television time for four commercials Radio time for 10 commercials Newspaper space for 7 ads Resources for no more than 15 commercials and/or ads Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-21 A Marketing Example Model Summary (2 of 7) Maximize Z = 20,000x1 + 12,000x2 + 9,000x3 subject to: 15,000x1 + 6,000x 2+ 4,000x3 100,000 x1 4 x2 10 x3 7 x1 + x2 + x3 15 x1, x2, x3 0 where x1 = number of television commercials x2 = number of radio commercials x3 = number of newspaper ads Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-22 A Marketing Example Solution with Excel (3 of 7) Exhibit 4.10 Objective function =F6*D6+F7*D7+F8*D8 or =SUMPRODUCT(D6:D8,F6:F8) Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-23 A Marketing Example Solution with Excel Solver Window (4 of 7) Includes all five constraints Exhibit 4.11 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-24 A Marketing Example Integer Solution with Excel (5 of 7) Decision variables Click on “int” for integer. Exhibit 4.12 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-25 A Marketing Example Integer Solution with Excel (6 of 7) Integer restriction Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 4.13 4-26 A Marketing Example Integer Solution with Excel (7 of 7) Integer solution Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Better solution—17,000 more total exposures—than rounded-down solution Exhibit 4.14 4-27 A Transportation Example Problem Definition and Data (1 of 3) Warehouse supply of Television Sets: Retail store demand for television sets: 1 - Cincinnati 300 A - New York 150 2 - Atlanta 200 B - Dallas 250 3 - Pittsburgh 200 C - Detroit 200 Total 700 Total 600 Unit Shipping Costs: From Warehouse 1 2 3 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall A $16 14 13 To Store B $18 12 15 C $11 13 17 4-28 A Transportation Example Model Summary (2 of 4) Minimize Z = $16x1A + 18x1B + 11x1C + 14x2A + 12x2B + 13x2C + 13x3A + 15x3B + 17x3C subject to: x1A + x1B+ x1C 300 x2A+ x2B + x2C 200 x3A+ x3B + x3C 200 x1A + x2A + x3A = 150 x1B + x2B + x3B = 250 x1C + x2C + x3C = 200 All xij 0 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-29 A Transportation Example Solution with Excel (3 of 4) =C5+D5+E5 =C5+C6+C7 Exhibit 4.15 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-30 A Transportation Example Solution with Solver Window (4 of 4) Decision variables Demand constraints Supply constraints Exhibit 4.16 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-31 A Blend Example Problem Definition and Data (1 of 6) Component Maximum Barrels Available/day Cost/barrel 1 4,500 $12 2 2,700 10 3 3,500 14 Grade Component Specifications Selling Price ($/bbl) Super At least 50% of 1 Not more than 30% of 2 $23 Premium At least 40% of 1 Not more than 25% of 3 Extra At least 60% of 1 At least 10% of 2 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 20 18 4-32 A Blend Example Problem Statement and Variables (2 of 6) ■ Determine the optimal mix of the three components in each grade of motor oil that will maximize profit. Company wants to produce at least 3,000 barrels of each grade of motor oil. ■ Decision variables: The quantity of each of the three components used in each grade of gasoline (9 decision variables); xij = barrels of component i used in motor oil grade j per day, where i = 1, 2, 3 and j = s (super), p (premium), and e (extra). Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-33 A Blend Example Model Summary (3 of 6) Maximize Z = 11x1s + 13x2s + 9x3s + 8x1p + 10x2p + 6x3p + 6x1e + 8x2e + 4x3e subject to: x1s + x1p + x1e 4,500 bbl. x2s + x2p + x2e 2,700 bbl. x3s + x3p + x3e 3,500 bbl. 0.50x1s - 0.50x2s - 0.50x3s 0 0.70x2s - 0.30x1s - 0.30x3s 0 0.60x1p - 0.40x2p - 0.40x3p 0 0.75x3p - 0.25x1p - 0.25x2p 0 0.40x1e- 0.60x2e- - 0.60x3e 0 0.90x2e - 0.10x1e - 0.10x3e 0 x1s + x2s + x3s 3,000 bbl. x1p+ x2p + x3p 3,000 bbl. all xij 0 x1e+ x2e + x3e 3,000 bbl. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-34 A Blend Example Solution with Excel (4 of 6) =B7+B10+B13 Decision variables—B7:B15 =B7+B8+B9 =0.5*B7-0.5*B8-0.5*B9 Exhibit 4.17 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-35 A Blend Example Solution with Solver Window (5 of 6) Exhibit 4.18 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-36 A Blend Example Sensitivity Report (6 of 6) Exhibit 4.19 The shadow price for component 1 is $20. The upper limit for the sensitivity range for component 1 is 4500+1700=6200. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-37 A Multiperiod Scheduling Example Problem Definition and Data (1 of 5) Production Capacity: 160 computers per week 50 more computers with overtime Assembly Costs: $190 per computer regular time; $260 per computer overtime Inventory Holding Cost: $10/computer per week Order schedule: Week Computer Orders 1 105 2 170 3 230 4 180 5 150 6 250 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-38 A Multi-Period Scheduling Example Decision Variables (2 of 5) Decision Variables: rj = regular production of computers in week j (j = 1, 2, …, 6) oj = overtime production of computers in week j (j = 1, 2, …, 6) ij = extra computers carried over as inventory in week j (j = 1, 2, …, 5) Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-39 A Multi-Period Scheduling Example Model Summary (3 of 5) Model summary: Minimize Z = $190(r1 + r2 + r3 + r4 + r5 + r6) + $260(o1+o2 +o3 +o4+o5+o6) + 10(i1 + i2 + i3 + i4 + i5) subject to: rj 160 computers in week j (j = 1, 2, 3, 4, 5, 6) oj 150 computers in week j (j = 1, 2, 3, 4, 5, 6) r1 + o1 - i1 = 105 week 1 r2 + o2 + i1 - i2 = 170 week 2 r3 + o3 + i2 - i3 = 230 week 3 r4 + o4 + i3 - i4 = 180 week 4 r5 + o5 + i4 - i5 = 150 week 5 r6 + o6 + i5 = 250 week 6 rj, oj, ij 0 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-40 A Multi-Period Scheduling Example Solution with Excel (4 of 5) G7-H7 Decision variables for regular production – B6:B11 Decision variables for overtime production – D6:D11 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall B7+D7+I6; regular production + overtime production + inventory from previous week Exhibit 4.20 4-41 A Multi-Period Scheduling Example Solution with Solver Window (5 of 5) Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 4.21 4-42 A Data Envelopment Analysis (DEA) Example Problem Definition (1 of 5) DEA compares a number of service units of the same type based on their inputs (resources) and outputs. The result indicates if a particular unit is less productive, or efficient, than other units. Elementary school comparison: Input 1 = teacher to student ratio Input 2 = supplementary funds/student Input 3 = average educational level of parents Output 1 = average reading SOL score Output 2 = average math SOL score Output 3 = average history SOL score Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-43 A Data Envelopment Analysis (DEA) Example Problem Data Summary (2 of 5) Inputs School Outputs 1 2 3 1 2 3 Alton .06 $260 11.3 86 75 71 Beeks .05 320 10.5 82 72 67 Carey .08 340 12.0 81 79 80 .06 460 13.1 81 73 69 Delancey Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-44 A Data Envelopment Analysis (DEA) Example Decision Variables and Model Summary (3 of 5) Decision Variables: xi = a price per unit of each output where i = 1, 2, 3 yi = a price per unit of each input where i = 1, 2, 3 Model Summary: Maximize Z = 81x1 + 73x2 + 69x3 subject to: .06 y1 + 460y2 + 13.1y3 = 1 86x1 + 75x2 + 71x3 .06y1 + 260y2 + 11.3y3 82x1 + 72x2 + 67x3 .05y1 + 320y2 + 10.5y3 81x1 + 79x2 + 80x3 .08y1 + 340y2 + 12.0y3 81x1 + 73x2 + 69x3 .06y1 + 460y2 + 13.1y3 xi, yi 0 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-45 A Data Envelopment Analysis (DEA) Example Solution with Excel (4 of 5) =E8*D12+F8*D13+G8*D14 =B5*B12+C5*B13+D5*B14 Value of outputs, also in cell H8 Exhibit 4.22 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-46 A Data Envelopment Analysis (DEA) Example Solution with Solver Window (5 of 5) Scaling constraint Constraint for outputs < inputs Exhibit 4.23 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-47 Example Problem Solution Problem Statement and Data (1 of 5) Canned cat food, Meow Chow; dog food, Bow Chow. ■ Ingredients/week: 600 lb horse meat; 800 lb fish; 1000 lb cereal. ■ Recipe requirement: Meow Chow at least half fish Bow Chow at least half horse meat. ■ 2,250 sixteen-ounce cans available each week. ■ Profit /can: Meow Chow $0.80 Bow Chow $0.96. How many cans of Bow Chow and Meow Chow should be produced each week in order to maximize profit? Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-48 Example Problem Solution Model Formulation (2 of 5) Step 1: Define the Decision Variables xij = ounces of ingredient i in pet food j per week, where i = h (horse meat), f (fish) and c (cereal), and j = m (Meow chow) and b (Bow Chow). Step 2: Formulate the Objective Function Maximize Z = $0.05(xhm + xfm + xcm) + 0.06(xhb + xfb + xcb) Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-49 Example Problem Solution Model Formulation (3 of 5) Step 3: Formulate the Model Constraints Amount of each ingredient available each week: xhm + xhb 9,600 ounces of horse meat xfm + xfb 12,800 ounces of fish xcm + xcb 16,000 ounces of cereal additive Recipe requirements: Meow Chow: xfm/(xhm + xfm + xcm) 1/2 or - xhm + xfm- xcm 0 Bow Chow: xhb/(xhb + xfb + xcb) 1/2 or xhb- xfb - xcb 0 Can Content: xhm + xfm + xcm + xhb + xfb+ xcb 36,000 ounces Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-50 Example Problem Solution Model Summary (4 of 5) Step 4: Model Summary Maximize Z = $0.05xhm + $0.05xfm + $0.05xcm + $0.06xhb + 0.06xfb + 0.06xcb subject to: xhm + xhb 9,600 ounces of horse meat xfm + xfb 12,800 ounces of fish xcm + xcb 16,000 ounces of cereal additive - xhm + xfm- xcm 0 xhb- xfb - xcb 0 xhm + xfm + xcm + xhb + xfb+ xcb 36,000 ounces xij 0 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-51 Example Problem Solution Solution with QM for Windows (5 of 5) Solution to the Bark’s Pet Food Company problem using QM for Windows To determine the number of cans of each flavor, we must sum the ingredient amounts for each and divide by 16 ounces (the size of a can). xhm+xfm+xcm=0+8,400+8,400=16,800 oz of Meow Chow 16,800 / 16 = 1,050 cans of Meow Chow Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-52 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 4-53