2.4 GENERALIZATIONS TO BLENDING, ECONOMICS AND SCHEDULING 39 least, it takes a more powerful solver to optimize the resulting mathematical programs. Chapters 17 through 20 discuss these issues in more detail. Bibliography George B. Dantzig, ''The Diet Problem.'' Interfaces 20, 4 (1990) pp. 43-47. An entertaining account of the origins of the diet problem. Susan Garner Garille and Saul I. Gass, ''Stigler's Diet Problem Revisited.'' Operations Research 49, 1 (2001) pp. 1-13. A review of the diet problem's origins and its influence over the years on linear programming and on nutritionists. Said S. Hilal and Warren Erikson, ''Matching Supplies to Save Lives: Linear Programming the Production of Heart Valves.'' Interfaces 11, 6 (1981) pp. 48-56. A less appetizing equivalent of the diet problem, involving the choice of pig heart suppliers. Exercises 2-1. Suppose the foods listed below have calories, protein, calcium, vitamin A, and costs per pound as shown. In what amounts should these food be purchased to meet at least the daily requirements listed while minimizing the total cost? (This problem comes from George B. Dantzig's classic book, Linear Programming and Extensions, page 118. We will take his word on nutritional values, and for nostalgic reasons have left the prices as they were when the book was published in 1963.) bread meat potatoes cabbage milk gelatin calories protein calcium vitamin A 1254 39 418 0 1457 73 41 0 318 8 42 70 46 4 141 860 309 16 536 720 1725 43 0 0 cost/pound $0.30 $1.00 $0.05 $0.08 $0.23 $0.48 required 3000 70 g. 800 mg. 500 I.U. 2-2. (a) You have been advised by your doctor to get more exercise, specifically, to burn off at least 2000 extra calories per week by some combination of walking, jogging, swimming, exercisemachine, collaborative indoor recreation, and pushing yourself away from the table at mealtimes. You have a limited tolerance for each activity in hours/week; each expends a certain number of calories per hour, as shown below: Calories Tolerance walking jogging swimming machine indoor pushback 100 5 200 2 300 3 150 3.5 300 3 500 0.5 How should you divide your exercising among these activities to minimize the amount of time you spend? 40 DIET AND OTHER INPUT MODELS: MINIMIZING COSTS CHAPTER 2 (b) Suppose that you should also have some variety in your exercise you must do at least one hour of each of the first four exercises, but no more than four hours total of walking, jogging, and exercise-machine. Solve the problem in this form. 2-3. (a) A manufacturer of soft drinks wishes to blend three sugars in approximately equal quantities to ensure uniformity of taste in a product. Suppliers only provide combinations of the sugars, at varying costs/ton: SUPPLIER Sugar A B C D E F G Cane Corn Beet 10% 30% 60% 10 40 50 20 40 40 30 20 50 40 60 0 20 70 10 60 10 30 $10 11 12 13 14 12 15 Cost/ton Formulate an AMPL model that minimizes the cost of supply while producing a blend that contains 52 tons of cane sugar, 56 tons of corn sugar, and 59 tons of beet sugar. (b) The manufacturer feels that to ensure good relations with suppliers it is necessary to buy at least 10 tons from each. How does this change the model and the minimum-cost solution? (c) Formulate an alternative to the model in (a) that finds the lowest-cost way to blend one ton of supplies so that the amount of each sugar is between 30 and 37 percent of the total. 2-4. At the end of Chapter 1, we indicated how to interpret the marginal (or dual) values of constraints and the reduced costs of variables in a production model. The same ideas can be applied to this chapter's diet model. (a) Going back to the diet problem that was successfully solved in Section 2.3, we can display the marginal values as follows: ampl: display Diet.lb,Diet.body,Diet.ub,Diet; : Diet.lb Diet.body Diet.ub Diet A 700 1956.29 20000 0 B1 700 1036.26 20000 0 B2 700 700 20000 0.404585 C 700 1682.51 20000 0 CAL 16000 19794.6 24000 0 NA 0 50000 50000 -0.00306905 ; := How can you interpret the two that are nonzero? (b) For the same problem, this listing gives the reduced costs: ampl: display : Buy.lb BEEF 2 CHK 2 FISH 2 HAM 2 MCH 2 MTL 2 SPG 2 TUR 2 ; Buy.lb,Buy,Buy.ub,Buy.rc; Buy Buy.ub Buy.rc 5.36061 10 8.88178e-16 2 10 1.18884 2 10 1.14441 10 10 -0.302651 10 10 -0.551151 10 10 -1.3289 9.30605 10 0 2 10 2.73162 := SECTION 2.4 GENERALIZATIONS TO BLENDING, ECONOMICS AND SCHEDULING 41 Based on this information, if you want to save money by eating more than 10 packages of some food, which one is likely to be your best choice? 2-5. A chain of fast-food restaurants operates 7 days a week, and requires the following minimum number of kitchen employees from Monday through Sunday: 45, 45, 40, 50, 65, 35, 35. Each employee is scheduled to work one weekend day (Saturday or Sunday) and four other days in a week. The management wants to know the minimum total number of employees needed to satisfy the requirements on every day. (a) Set up and solve this problem as a linear program. (b) In light of the discussion in Section 2.4, explain how this problem can be viewed as a special case of the blending model in Figure 2-4. 2-6. The output of a paper mill consists of standard rolls 110 inches (110") wide, which are cut into smaller rolls to meet orders. This week there are orders for rolls of the following widths: Width 20" 45" 50" 55" 75" Orders 48 35 24 10 8 The owner of the mill wants to know what cutting patterns to apply so as to fill the orders using the smallest number of 110" rolls. (a) A cutting pattern consists of a certain number of rolls of each width, such as two of 45" and one of 20", or one of 50" and one of 55" (and 5" of waste). Suppose, to start with, that we consider only the following six patterns: Width 20" 45" 50" 55" 75" 1 3 0 1 0 0 2 1 2 0 0 0 3 0 0 1 1 0 4 2 0 0 1 0 5 1 0 0 0 1 6 3 1 0 0 0 How many rolls should be cut according to each pattern, to minimize the number of 110" rolls used? Formulate and solve this problem as a linear program, assuming that the number of smaller rolls produced need only be greater than or equal to the number ordered. (b) Re-solve the problem, with the restriction that the number of rolls produced in each size must be between 10% under and 40% over the number ordered. (c) Find another pattern that, when added to those above, improves the optimal solution. (d) All of the solutions above use fractional numbers of rolls. Can you find solutions that also satisfy the constraints, but that cut a whole number of rolls in each pattern? How much does your whole-number solution cause the objective function value to go up in each case? (See Chapter 20 for a discussion of how to find optimal whole-number, or integer, solutions.) 2-7. In the refinery model of Exercise 1-6, the amount of premium gasoline to be produced is a decision variable. Suppose instead that orders dictate a production of 42,000 barrels. The octane rating of the product is permitted to be in the range of 89 to 91, and the vapor pressure in a range of 11.7 to 12.7. The five feedstocks that are blended to make premium gasoline have the following production and/or purchase costs: 42 DIET AND OTHER INPUT MODELS: MINIMIZING COSTS SRG N RF CG B CHAPTER 2 9.57 8.87 11.69 10.88 6.75 Other data are as in Exercise 1-6. Construct a blending model and data file to represent this problem. Run them through AMPL to determine the optimal composition of the blend. 2-8. Recall that Figure 2-4 generalizes the diet model as a minimum-cost input selection model, with constraints on the outputs. (a) In the same way, generalize the production model of Figure 1-6a as a maximum-revenue output selection model, with constraints on the inputs. (b) The concept of an ''input-output'' model was one of the first applications of linear programming in economic analysis. Such a model can be described in terms of a set A of activities and a set M of materials. The decision variables are the levels X j 0 at which the activities are run; they have lower limits u j and upper limits u j . Each activity j has either a revenue per unit c j 0, or a cost per unit represented by c j 0. Thus total profit from all activities is c X , which is to be maximized. j A j j Each unit of activity j produces an amount of material i given by a i j 0, or consumes an amount of material i represented by a i j 0. Thus if a i j X j is 0 it is the total production of material j A i by all activities; if 0, it is the total consumption of material i by all activities. For each material i, there is either an upper limit on the total production given by b i 0, or a lower limit on the total consumption given by b i 0. Similarly, there is either a lower limit on the total production given by b i 0, or an upper limit on the total consumption given by b i 0. Write out a formulation of this model in AMPL. (c) Explain how the minimum-cost input selection model and maximum-revenue output-selection model can be viewed as special cases of the input-output model