1.7 AMPL INTERFACES 21 Exercises 1-1. This exercise starts with a two-variable linear program similar in structure to the one of Sections 1.1 and 1.2, but with a quite different story behind it. (a) You are in charge of an advertising campaign for a new product, with a budget of $1 million. You can advertise on TV or in magazines. One minute of TV time costs $20,000 and reaches 1.8 million potential customers; a magazine page costs $10,000 and reaches 1 million. You must sign up for at least 10 minutes of TV time. How should you spend your budget to maximize your audience? Formulate the problem in AMPL and solve it. Check the solution by hand using at least one of the approaches described in Section 1.1. (b) It takes creative talent to create effective advertising; in your organization, it takes three person-weeks to create a magazine page, and one person-week to create a TV minute. You have only 100 person-weeks available. Add this constraint to the model and determine how you should now spend your budget. (c) Radio advertising reaches a quarter million people per minute, costs $2,000 per minute, and requires only 1 person-day of time. How does this medium affect your solutions? (d) How does the solution change if you have to sign up for at least two magazine pages? A maximum of 120 minutes of radio? 1-2. The steel model of this chapter can be further modified to reflect various changes in production requirements. For each part below, explain the modifications to Figures 1-6a and 1-6b that would be required to achieve the desired changes. (Make each change separately, rather than accumulating the changes from one part to the next.) (a) How would you change the constraints so that total hours used by all products must equal the total hours available for each stage? Solve the linear program with this change, and verify that you get the same results. Explain why, in this case, there is no difference in the solution. (b) How would you add to the model to restrict the total weight of all products to be less than a new parameter, max_weight? Solve the linear program for a weight limit of 6500 tons, and explain how this extra restriction changes the results. (c) The incentive system for mill managers may tend to encourage them to produce as many tons as possible. How would you change the objective function to maximize total tons? For the data of our example, does this make a difference to the optimal solution? (d) Suppose that instead of the lower bounds represented by commit[p] in our model, we want to require that each product represent a certain share of the total tons produced. In the algebraic notation of Figure 1-1, this new constraint might be represented as Xj sj X k , for each j P k P where s j is the minimum share associated with project j. How would you change the AMPL model to use this constraint in place of the lower bounds c o mmi t [ p ] ? If the minimum shares are 0.4 for bands and plate, and 0.1 for coils, what is the solution? Verify that if you change the minimum shares to 0.5 for bands and plate, and 0.1 for coils, the linear program gives an optimal solution that produces nothing, at zero profit. Explain why this makes sense. 22 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1 (e) Suppose there is an additional finishing stage for plates only, with a capacity of 20 hours and a rate of 150 tons per hour. Explain how you could modify the data, without changing the model, to incorporate this new stage. 1-3. This exercise deals with some issues of ''sensitivity'' in the steel models. (a) For the linear program of Figures 1-5a and 1-5b, display Time and Make.rc. What do these values tell you about the solution? (You may wish to review the explanation of marginal values and reduced costs in Section 1.6.) (b) Explain why the reheat time constraints added in Figure 1-6a result in a higher production of plate and a lower production of bands. (c) Use AMPL to verify the following statements: If the available reheat time is increased from 35 to 36 in the data of Figure 1-6b, then the profit goes up by $1800 as predicted in Section 1.6. If the reheat time is further increased to 37, the profit goes up by another $1800. However, if the reheat time is increased to 38, there is a smaller increase in the profit, and further increases past 38 have no effect on the optimal profit at all. To change the reheat time to, say, 26 without changing and reading the data file over again, type the command let avail["reheat"] := 36; By trying some other values of the reheat time, confirm that the profit increases by $1800 per extra hour for any number of hours between 35 and 37 9/14, but that any increase in the reheat time beyond 37 9/14 hours doesn't give any further profit. Draw a plot of the profit versus the number of reheat hours available, for hours 35. (d) To find the slope of the plot from (c) profit versus reheat time available at any particular reheat time value, you need only look at the marginal value of Time["reheat"]. Using this observation as an aid, extend your plot from (c) down to 25 hours of reheat time. Verify that the slope of the plot remains at $6000 per hour from 25 hours down to less than 12 hours of reheat time. Explain what happens when the available reheat time drops to 11 hours. 1-4. Here is a similar profit-maximizing model, but in a different context. An automobile manufacturer produces several kinds of cars. Each kind requires a certain amount of factory time per car to produce, and yields a certain profit per car. A certain amount of factory time has been scheduled for the next week, and it is desired to use all this time; but at least a certain number of each kind of car must be manufactured to meet dealer requirements. (a) What are the data values that define this problem? How would you declare the sets and parameter values for this problem in AMPL? What are the decision variables, and how would you declare them in AMPL? (b) Assuming that the objective is to maximize total profit, how would you declare an objective in AMPL for this problem? How would you declare the constraints? (c) For purposes of experiment, suppose that there are three kinds of cars, known at the factory as T, C and L, that 120 hours are available, and that the time per car, profit per car and dealer orders for each kind of car are as follows: Car time profit orders T C L 1 2 3 200 500 700 10 20 15 SECTION 1.7 AMPL INTERFACES 23 How much of each car should be produced, and what is the maximum profit? You should find that your solution specifies a fractional amount of one of the cars. As a practical matter, how could you make use of this solution? (d) If you maximize the total number of cars produced instead of the total profit, how many more cars do you make? How much less profit? (e) Each kind of car achieves a certain fuel efficiency, and the manufacturer is required by law to maintain a certain ''fleet average'' efficiency. The fleet average is computed by multiplying the efficiency of each kind of car times the number of that kind produced, summing all of the resulting products, and dividing by the total of all cars produced. Extend your AMPL model to contain a minimum fleet average efficiency constraint. Rearrange the constraint as necessary to make it linear no variables divided into other variables. (f) Find the optimal solution for the case where cars T, C and L achieve fuel efficiencies of 50, 30 and 20 miles/gallon, and the fleet average efficiency must be at least 35 miles/gallon. Explain how this changes the production amounts and the total profit. Dealing with the fractional amounts in the solution is not so easy in this case. What might you do? If you had 10 more hours of production time, you could make more profit. Does the addition of the fleet average efficiency constraint make the extra 10 hours more or less valuable? (g) Explain how you could further refine this model to account for different production stages that have different numbers of hours available per stage, much as in the steel model of Section 1.6. 1-5. A group of young entrepreneurs earns a (temporarily) steady living by acquiring inadequately supervised items from electronics stores and re-selling them. Each item has a street value, a weight, and a volume; there are limits on the numbers of available items, and on the total weight and volume that can be managed at one time. (a) Formulate an AMPL model that will help to determine how much of each item to pick up, to maximize one day's profit. (b) Find a solution for the case given by the following table, TV radio camera CD player VCR camcorder Value Weight Volume Available 50 15 85 40 50 120 35 5 4 3 15 20 8 1 2 1 5 4 20 50 20 30 30 15 and by limits of 500 pounds and 300 cubic feet. (c) Suppose that it is desirable to acquire some of each item, so as to always have stock available for re-sale. Suppose in addition that there are upper bounds on how many of each item you can reasonably expect to sell. How would you add these conditions to the model? (d) How could the group use the dual variables on the maximum-weight and maximum-volume constraints to evaluate potential new partners for their activities? (e) Through adverse circumstances the group has been reduced to only one member, who can carry a mere 75 pounds and five cubic feet. What is the optimum strategy now? Given that this requires a non-integral number of acquisitions, what is the best all-integer solution? (The integrality constraint converts this from a standard linear programming problem into a much harder problem called a Knapsack Problem. See Chapter 20.) 24 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1 1-6. Profit-maximizing models of oil refining were one of the first applications of linear programming. This exercise asks you to model a simplified version of the final stage of the refining process. A refinery breaks crude oil into some collection of intermediate materials, then blends these materials back together into finished products. Given the volumes of intermediates that will be available, we want to determine how to blend the intermediates so that the resulting products are most profitable. The decision is made more complicated, however, by the existence of upper limits on certain attributes of the products, which must be respected in any feasible solution. To formulate an algebraic linear programming model for this problem, we can start by defining sets I of intermediates, J of final products, and K of attributes. The relevant technological data may be represented by ai r ik u jk barrels of intermediate i available, for each i I units of attribute k contributed per barrel of intermediate i, for each i I and k K maximum allowed units of attribute k per barrel of final product j, for each j J and k K 1 if intermediate i is allowed in the blend for product j, or 0 otherwise, for each i I and j J ij and the economic data can be given by cj revenue per barrel of product j, for each j J There are two collections of decision variables: X ij Yj barrels of intermediate i used to make product j, for each i I and j J barrels of product j made, for each j J The objective is to maximize j J c j Y j, which is the sum of the revenues from the various products. It remains to specify the constraints. The amount of each intermediate used to make products must equal the amount available: j J X ij a i , for each i I. The amount of a product made must equal the sum of amounts of the components blended into it: i I X ij Y j , for each j J. For each product, the total attributes contributed by all intermediates must not exceed the total allowed: i r X I ik i j u j k Y j , for each j J and k K. Finally, we bound the variables as follows: 0 0 X ij i j a i , for each i I, j J, Y j , for each j J. SECTION 1.7 AMPL INTERFACES 25 The upper bound on X i j assures that only the appropriate intermediates will be used in blending. If intermediate i is not allowed in the blend for product j, as indicated by i j being zero, then the upper bound on X i j is zero; this ensures that X i j cannot be positive in any solution. Otherwise, the upper bound on X i j is just a i , which has no effect since there are only a i barrels of intermediate i available for blending in any case. (a) Transcribe this model to AMPL, using the same names as in the algebraic form for the sets, parameters and variables as much as possible. (b) Re-write the AMPL model using meaningful names and comments, in the style of Figure 1-4a. (c) In a representative small-scale instance of this model, the intermediates are SRG (straight run gasoline), N (naphtha), RF (reformate), CG (cracked gasoline), B (butane), DI (distillate intermediate), GO (gas oil), and RS (residuum). The final products are PG (premium gasoline), RG (regular gasoline), D (distillate), and HF (heavy fuel oil). Finally, the attributes are vap (vapor pressure), oct (research octane), den (density), and sul (sulfur). The following amounts of the intermediates are scheduled to be available: SRG N RF CG B DI GO RS 21170 500 16140 4610 370 250 11600 25210 The intermediates that can be blended into each product, and the amounts of the attributes that they possess, are as follows (with blank entries representing zeros): SRG N RF CG B DI GO RS Premium & regular gasoline vap oct 18.4 -78.5 6.54 -65.0 2.57 -104.0 6.90 -93.7 199.2 -91.8 Distillate den sul 272 .283 292 295 .526 .353 Heavy fuel oil den sul 295 343 .353 4.70 The attribute limits and revenues/barrel for the products are: PG RG D HF vap 12.2 12.7 oct -90 -86 den sul 306 352 0.5 3.5 revenue 10.50 9.10 7.70 6.65 Limits left blank, such as density for gasoline, are irrelevant and may be set to some relatively large number. Create a data file for your AMPL model and determine the optimal blend and production amounts. (d) It looks a little strange that the attribute amounts for research octane are negative. What is the limit constraint for this attribute really saying