Optimization Methods in Management Science, Problem Set 4 Solutions

Optimization Methods in Management Science MIT 15.053, Spring 2013 Problem Set 4, Due: Thursday March 7th, 2013 Problem Set Rules: 1. Each student should hand in an individual problem set. 2. Discussing problem sets with other students is permitted. Copying from another person or solution set is not permitted. 3. Late assignments will not be accepted. No exceptions. 4. There is no Excel submission . Problem 1 (50 points) This problem is based on Problem 1 of Applied Mathematical Programming, Chap­ ter 3. We provide you with information on the optimal solution to the model and a sensitivity analysis report. The questions are geared towards understanding the problem formulation, and analyzing the outcome of several possible scenarios. None of the answers requires you to solve additional Linear Programs: the information that we provide is sufficient to answer all ques­ tions. Motivate your answers: when we ask you to compute a number, write how you computed it. Do not be scared by the length of the problem’s description! Outdoors, Inc. has, as one of its product lines, lawn furniture. They currently have three items in that line: a lawn chair, a standard bench, and a table. These products are produced in a two-step manufacturing process involving the tube-bending department and the welding department. The time required by each item in each department is as follows: Tube bending Welding Product Lawn chair Bench 1.2 1.7 0.8 0 Table 1.2 2.3 Present capacity 1000 1200 The contribution that Outdoors, Inc. receives from the manufacture and sale of one unit of each product is $3 for a chair, $3 for a bench, and $5 for a table. The company is trying to plan its production mix for the current selling season. It predicts that it can sell any number it produces, but production is further limited by available material, because of a prolonged strike. The company currently has on hands 2000 lbs. of tubing. The three products require the following amounts of this tubing: 2 lbs. per chair, 3 lbs. per bench, and 4.5 lbs. per table. In order to determine the optimal product mix, the production manager has formulated the following linear program: Label Bending Welding Material Availability Contribution Chair 1.2 0.8 2 3 Bench 1.7 0 3 3 Table 1.2 2.3 4.5 5 ≤ ≤ ≤ Limit 1000 1200 2000 Solving this linear program with Excel and asking for a sensitivity report on the solution yields the information reported in Figure 1. Objective Cell (Max) Cell Name $B$4 Contribution Original Value Final Value 0 2766.666667 Variable Cells Cell $B$1 Chair $B$2 Bench $B$3 Table Original Value Final Value Integer 0 700 Contin 0 0 Contin 0 133.3333333 Contin Name Constraints Cell Name $B$5 Bending $B$6 Welding $B$7 Material Availability Cell Value Formula 1000 $B$5<=1000 866.6666667 $B$6<=1200 2000 $B$7<=2000 Status Binding Not Binding Binding Slack 0 333.3333333 0 Variable Cells Cell $B$1 Chair $B$2 Bench $B$3 Table Name Final Value Reduced Cost Objective Allowable Allowable Coefficient Increase Decrease 700 0 3 2 0.777778 0 -1.38333333 3 1.383333333 1E+30 133.3333333 0 5 1.75 2 Constraints Cell Name $B$5 Bending $B$6 Welding $B$7 Material Availability Final Value Shadow Constraint Allowable Price R.H. Side Increase 1000 1.166666667 1000 200 866.6666667 0 1200 1E+30 2000 0.8 2000 555.5555556 Allowable Decrease 466.6667 333.3333 333.3333 Figure 1: Solution information and sensitivity analysis for Problem 1. Note that “contin” in the second table means continuous and can be ignored 2 Use solution and sensitivity report to answer the following questions. (a) (5 points) What is the optimal production mix? What contribution can the firm anticipate by producing this mix? Solution. The optimal production mix consists in 700 Chairs and 133.33 Tables (we assume that a fractional solution is acceptable), with a total contribution of $2766.66. In practice, we may want to round the number of Tables down to 133, and the corresponding contribution will be $2765. However, note that in general it is not guaranteed that the solution obtained by rounding down is optimal for the problem where we require the variables to take on integer values. In this case, we are content with this solution. (b) (5 points) What is the value of one more unit of tube-bending time? of welding time? of metal tubing? Guess the value of one more unit of welding time just by looking at the third table in Figure 1, under the column “Slack”. Solution. The required values are the shadow prices. We can just look them up in the sensitivity analysis report. One unit of tube-bending time is worth $1.16667, and one unit of metal tubing is worth $0.8. Welding time is worth 0$. This is also clear from the fact that the Welding constraint is not binding and the corresponding slack variable is nonzero at value 333.3333. (c) (6 points) A local distributor has offered to sell Outdoors, Inc. some additional metal tubing for $0.70/lb. Should Outdoors buy it? If yes, how much would the firm’s contribution increase if they bought 550 lbs. and used it in an optimal fashion? Solution. The shadow price for the Material Availability constraint is $0.8/lb. There­ fore, buying additional metal tubing for $0.7/lb is a good investment. We also see from the sensitivity report that the allowable increase in the rhs of the Material Availability constraint is 555.5556. This means that the shadow price of the constraint will be the same if the rhs increases by 550. The contribution of the firm would therefore revenue increase by 0.8 · 550 = $440 by buying 550 lbs. of tubing and with a cost of $0.7/lb, the impact on profit is 0.1 · 550 = $55. (d) (6 points) If Outdoors, Inc. feels that it must produce at least 50 benches to round out its product line, what effect will that have on its contribution? (Hint: First answer the question for one bench and then extend it for 50 benches). Solution. The reduced cost for Bench is −1.38333 (recall that the reduced cost of a variable can be interpreted as the shadow price of the corresponding nonnegativity constraint). Hence, if the firm produces at least 50 benches it can expect a modification of the objective function value of −1.38333 · 50. To summarize, contribution will decrease by $69.1665. (e) (7 points) The R&D department has been redesigning the bench to make it more profitable. The new design will require 1.2 hours of tube-bending time, 3.0 hours of welding time, and 2.4 lbs. of metal tubing. If it can sell one unit of this bench with a unit contribution of $2.5, what would be overall contribution if they produce a single unit? 3 Solution. We can treat the redesigned benches as a new product, and price the corre­ sponding variable. To price the variable, we compute its reduced cost as c̄j = cj − πAj , where cj = 2.5 is the cost coefficient, π = (1.166667, 0, 0.8) is the vector of shadow prices, and Aj = (1.2, 3.0, 2.4) is the vector of coefficients in the column of the constraint matrix corresponding to the new product. The calculation yields c̄j = 2.5 − 3.32 = −0.82. The reduced cost of the redesigned benches is negative, therefore we should choose not to produce any units. (f) (7 points) Marketing has suggested a new patio awning that would require 1.8 hours of tubebending time, 0.5 hours of welding time, and 1.3 lbs. of metal tubing. What contribution must this new product have to make it attractive to produce this season? Solution. We should price the new variable, using the same calculations as in Part 1.E. Computing πAj with aj = (1.8, 0.5, 1.3) yields $3.14. The reduced cost of the corre­ sponding variable will be positive if the contribution of the patio awning is greater than $3.14. In this case, it will be attractive to produce the item. (g) (7 points) Outdoors, Inc. has a chance to sell some of its capacity in tube bending at cost of $1.50/hour. If it sells 200 hours at that price, how will this affect contribution? Solution. The sensitivity analysis report tells us that the shadow price of the Bending constraint is $1.166667/hour, and that this value will not change if the rhs of the constraint is decreased by up to 466.6667. Hence, decreasing the Bending capacity by 200 hours will decrease contribution by 1.166667 · 200 = $233.3334. If we compare this number with the income derived from selling the capacity, which is equal to $300, we conclude that we should pursue this chance. (h) (7 points) If the contribution on chairs were to decrease to $2.40, what would be the optimal production mix and what contribution would this production plan give? Solution. The current contribution of chairs is $3, therefore we are looking at a decrease of $0.6. The sensitivity report tells us that the allowable decrease for the objective function coefficient of Chair is 0.777778. Therefore, decreasing the contribution of chairs by $0.6 will not change the optimal production mix. The total contribution can be computed as the current contribution minus 0.6 times the number of produced chairs, i.e. 2766.66 − 0.6 · 700 = $2346.66. (24 points, 4 points each) A wood furniture manufacturing firm asked your help in analyzing their production schedule. The firm can produce four types of furniture: Chairs, Desks, Tables, Wardrobes. Each item requires a certain number of man-hours in three departments: Cutting, Sanding, Finishing. On the next page, a solution report is given in Figure 2, where Revenue is expressed in dollars. A sensitivity report is given in Figure 3. Using these two exhibits, answer the following questions. Note that three values, identified by “A”, “B” and “C”, are missing from Figure 3. Two of the questions will ask you to compute “A” and “B”. The missing values are not needed for the remaining questions. (a) By how much should the revenue for selling one unit of Chairs increase, before Chairs could be considered for production in the optimal production mix? Solution. It should increase by 130 (the negative of the reduced cost of Chairs). 4 Objective Cell (Max) Cell Name $C$11 Revenue Original Value 0 Final Value 18000 Variable Cells Cell Name $C$2 Chairs $D$2 Desks $E$2 Tables $F$2 Wardrobes Original Value 0 0 0 0 Final Value 0 0 140 25 Cell Value 480 800 800 Status Binding Binding Not Binding Constraints Cell $C$15 $C$16 $C$17 Name Cutting Sanding Finishing Slack 0 0 100 Figure 2: Solution report for Problem 1. Variable Cells Cell $C$2 $D$2 $E$2 $F$2 Name Chairs Desks Tables Wardrobes Final Reduced Objective Allowable Allowable Value Cost Coefficient Increase Decrease 0 -130 40 B 1E+30 0 A 90 C 1E+30 140 0 100 100 10 25 0 160 240 80 Constraints Cell $C$15 $C$16 $C$17 Name Cutting Sanding Finishing Final Shadow Value Price 480 12.5 800 15 800 0 Constraint R.H. Side 480 800 900 Allowable Allowable Increase Decrease 1120 160 100 560 1E+30 100 Figure 3: Sensitivity report for Problem 2. 5 (b) The firm is considering the possibility of buying equipment to increase the current Sanding capacity. What is the maximum amount that the firm should be willing to pay to increase the number of available Sanding hours from 800 to 850? Solution. The shadow price for Sanding is 15, and the allowable increase for the rhs value is 100. Therefore, increasing Sanding by 50 hours yields an increase in Revenue by 50 × 15 = $750. This is also the maximum amount that the firm should be willing to pay. (c) Suppose the profit of Tables decreased from 100 to 95. What would be the new optimal solution? What would be the new profit? (If there is not enough information in the problem to give the answer, please state so.) Solution. The allowable decrease for the objective function coefficient of Tables is 10. Thus, an decrease by 5 does not affect the optimal solution. It follows that the total revenue will be 18000 − 5 × 140 = 17300. (d) To cut costs, the firm wants to reduce the number of hours in the Finishing department from 900 to 700. Which of the following statements is the most accurate? • Reducing the number of Finishing hours by 200 will not affect total revenue. • Reducing the number of Finishing hours by 200 will decrease revenue by $100. • Reducing the number of Finishing hours by 200 could affect total revenue, but we do not have enough information to compute the magnitude of the change. (e) The contribution of each unit of Desks to Revenue is 90. Producing one unit of Desks requires 2 hours of Cutting, 5 hours of Sanding, and 7 hours of Finishing. Compute the missing value “A” in Figure 3, that is, the reduced costs of Desks. Show your work. Solution. The vector of shadow prices is (12.5, 15, 0). The reduced cost of Desks is 90 − (12.5, 15, 0) · (2, 5, 7) = −10. (f) Compute the missing value “B” in Figure 3, that is, the allowable increase in the row labeled “Chairs”. Solution. We observe that Chairs is nonbasic at the optimum, and its reduced cost is −130. It follows that the maximum amount by which its contribution can increase before the basis changes is 130: if the contribution increases by 130, the reduced cost of Chairs becomes 0. Problem 3 (26 points) The Red Sox are playing the Yankees. It’s the bottom of the 9th inning, with two outs and bases loaded. The score is tied 3 to 3. Mariano Rivera is pitching for the Yankees. David Ortiz is batting for the Red Sox. What pitch should Rivera throw? How should David Ortiz bat? In this simplified version of the problem, Rivera can throw one of three pitches: a high inside fastball, a high outside fastball, or a high inside curve. Ortiz can prepare for the pitch by expecting a curveball or a fastball. The probability of Ortiz scoring a run is given in Table 1. If he doesn’t score a run, then he is out, and the inning ends. 6 Prepare for Curveball Prepare for Fastball High Inside fastball 0.3 0.5 High Outside fastball 0.3 0.2 High Inside Curve 0.4 0.3 Table 1: The probability of Ortiz scoring a run under different scenarios. Assume in the following that Ortiz and Rivera both take a conservative strategy with regards to their mixed strategies. (That is, take the conservative analysis developed in class wrt mixed strategies.) (a) (7 points) Formulate Ortiz’s problem (the row player’s problem) as a linear program. Solution. Let xc be the probability of expecting a curveball, and xf the probability of expecting a fastball. ⎫ max z ⎪ ⎪ ⎪ ⎪ subject to: ⎪ ⎪ ⎪ High Inside Fastball: .3xc + .5xf ≥ z ⎪ ⎬ High Outside Fastball: .3xc + .2xf ≥ z ⎪ High Inside Curveball: .4xc + .2xf ≥ z ⎪ ⎪ ⎪ ⎪ ⎪ Probability: x c + xf = 1 ⎪ ⎪ ⎭ xc , xf , z ≥ 0 (b) (7 points) Formulate Mariano Rivera’s problem (the column player’s problem) as a linear program. Solution. Let xHIF , xHOF , xHIC be the probabilities of pitching a high inside fastball, high outside fastball, and high inside curveball, respectively. We obtain: ⎫ min w ⎪ ⎪ ⎪ ⎪ subject to: ⎪ ⎪ ⎬ Prepare for Curveball: .3xHIF + .3xHOF + .4xHIC ≤ w Prepare for Fastball: .5xHIF + .2xHOF + .3xHIC ≤ w ⎪ ⎪ ⎪ ⎪ Probability: xHIF + xHOF + xHIC = 1 ⎪ ⎪ ⎭ xHIF , xHOF , xHIC , w ≥ 0 (c) (8 points) Solve Ortiz’s problem using a graphical approach. What is the optimum mixed strategy? What is the probability of Ortiz scoring a run if he uses the optimal mixed strategy. 7 Solution. for xc : The problem for Ortiz can be rewritten as the following by substituting p max z s. t.: High Inside Fastball: .3p + .5(1 − p) High Outside Fastball: .3p + .2(1 − p) High Inside Curveball: .4p + .3(1 − p) Probability: p p, w ≤ ≤ ≤ ≤ ≥ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ z ⎪ ⎬ z ⎪ z ⎪ ⎪ ⎪ ⎪ ⎪ 1 ⎪ ⎪ ⎭ 0 To solve graphically, z is plotted as a function of p above. From the plot above, we note that Ortiz’s best mixed strategy is actually to prepare for a curveball 100% of the time; this solution is represented on the plot by the dot at (1, .3), representing the maximin solution. (d) (4 points) Without solving Rivera’s problem, what is the probability that Ortiz is out if Rivera uses his best mixed strategy. (Choose the largest value that is correct.) Briefly justify your answer. Solution. Without solving Rivera’s prolbem, we know his best mixed strategy will get Ortiz out 70% of the time (probability of .7). We know this because, for any 2-player, zero sum game, the maximin value is equal to the minimax value. Therefore, Rivera’s best strategy will allow Ortiz to get a hit with probability .3 (from the optimal value for Ortiz’s best strategy), leaving Rivera with a .7 probability of getting an out. 8