In the rest of this chapter, we lead the reader through the formulation of several more complicated linear programming models. The most important step in formulating an LP model is the proper choice of decision variables. If the decision variables have been properly chosen, the objective function and constraints should follow without much difculty. Trouble in determining an LP's objective function and constraints is usually the result of an incorrect choice of decision variables. PROBLEMS Group A Identify which of Cases 1-4 apply to each of the following LPs: 1 max z x1 x2 s.t. x1 x2 4 x1 x2 5 x1, x2 0 2 max z 4x1 x2 s.t. 8x1 2x2 16 5x1 2x2 12 x1, x2 0 3 max z x1 3x2 s.t. x1 2x2 4 x1 2x2 4 x1, x2 0 4 max z 3x1 x2 s.t. 2x1 3x2 6 x1 3x2 9 x1, x2 0 5 True or false: For an LP to be unbounded, the LP's feasible region must be unbounded. 6 True or false: Every LP with an unbounded feasible region has an unbounded optimal solution. 7 If an LP's feasible region is not unbounded, we say the LP's feasible region is bounded. Suppose an LP has a bounded feasible region. Explain why you can nd the optimal solution to the LP (without an isoprot or isocost line) by simply checking the z-values at each of the feasible region's extreme points. Why might this method fail if the LP's feasible region is unbounded? 3.4 8 Graphically nd all optimal solutions to the following LP: min z x1 x2 s.t. x1 x2 6 x1 x2 0 x2 x1 3 x1, x2 0 9 Graphically determine two optimal solutions to the following LP: min z 3x1 5x2 s.t. 3x1 2x2 36 3x1 5x2 45 x1, x2 0 Group B 10 Money manager Boris Milkem deals with French currency (the franc) and American currency (the dollar). At 12 midnight, he can buy francs by paying .25 dollars per franc and dollars by paying 3 francs per dollar. Let x1 number of dollars bought (by paying francs) and x2 number of francs bought (by paying dollars). Assume that both types of transactions take place simultaneously, and the only constraint is that at 12:01 A.M. Boris must have a nonnegative number of francs and dollars. a Formulate an LP that enables Boris to maximize the number of dollars he has after all transactions are completed. b Graphically solve the LP and comment on the answer. A Diet Problem Many LP formulations (such as Example 2 and the following diet problem) arise from situations in which a decision maker wants to minimize the cost of meeting a set of requirements. 68 CHAPTER 3 Introduction to Linear Programming problem in which 77 types of food were available and 10 nutritional requirements (vitamin A, vitamin C, and so on) had to be satised. When solved by computer, the optimal solution yielded a diet consisting of corn meal, wheat our, evaporated milk, peanut butter, lard, beef, liver, potatoes, spinach, and cabbage. Although such a diet is clearly high in vital nutrients, few people would be satised with it because it does not seem to meet a minimum standard of tastiness (and Stigler required that the same diet be eaten each day). The optimal solution to any LP model will reect only those aspects of reality that are captured by the objective function and constraints. Stigler's (and our) formulation of the diet problem did not reect people's desire for a tasty and varied diet. Integer programming has been used to plan institutional menus for a weekly or monthly period. Menu-planning models do contain constraints that reect tastiness and variety requirements. PROBLEMS Group A 1 There are three factories on the Momiss River (1, 2, and 3). Each emits two types of pollutants (1 and 2) into the river. If the waste from each factory is processed, the pollution in the river can be reduced. It costs $15 to process a ton of factory 1 waste, and each ton processed reduces the amount of pollutant 1 by 0.10 ton and the amount of pollutant 2 by 0.45 ton. It costs $10 to process a ton of factory 2 waste, and each ton processed will reduce the amount of pollutant 1 by 0.20 ton and the amount of pollutant 2 by 0.25 ton. It costs $20 to process a ton of factory 3 waste, and each ton processed will reduce the amount of pollutant 1 by 0.40 ton and the amount of pollutant 2 by 0.30 ton. The state wants to reduce the amount of pollutant 1 in the river by at least 30 tons and the amount of pollutant 2 in the river by at least 40 tons. Formulate an LP that will minimize the cost of reducing pollution by the desired amounts. Do you think that the LP assumptions (Proportionality, Additivity, Divisibility, and Certainty) are reasonable for this problem? 2 U.S. Labs manufactures mechanical heart valves from the heart valves of pigs. Different heart operations require valves of different sizes. U.S. Labs purchases pig valves from three different suppliers. The cost and size mix of the valves purchased from each supplier are given in Table 3. Each month, U.S. Labs places one order with each supplier. At least 500 large, 300 medium, and 300 small valves must be purchased each month. Because of limited availability of pig valves, at most 700 valves per month can be purchased from each supplier. Formulate an LP that can be used to minimize the cost of acquiring the needed valves. 3 Peg and Al Fundy have a limited food budget, so Peg is trying to feed the family as cheaply as possible. However, she still wants to make sure her family members meet their daily nutritional requirements. Peg can buy two foods. Food TA B L E Supplier 1 2 3 3 Cost Per Value ($) Percent Large Percent Medium Percent Small 5 4 3 40 30 20 40 35 20 20 35 60 1 sells for $7 per pound, and each pound contains 3 units of vitamin A and 1 unit of vitamin C. Food 2 sells for $1 per pound, and each pound contains 1 unit of each vitamin. Each day, the family needs at least 12 units of vitamin A and 6 units of vitamin C. a Verify that Peg should purchase 12 units of food 2 each day and thus oversatisfy the vitamin C requirement by 6 units. b Al has put his foot down and demanded that Peg fulll the family's daily nutritional requirement exactly by obtaining precisely 12 units of vitamin A and 6 units of vitamin C. The optimal solution to the new problem will involve ingesting less vitamin C, but it will be more expensive. Why? 4 Goldilocks needs to nd at least 12 lb of gold and at least 18 lb of silver to pay the monthly rent. There are two mines in which Goldilocks can nd gold and silver. Each day that Goldilocks spends in mine 1, she nds 2 lb of gold and 2 lb of silver. Each day that Goldilocks spends in mine 2, she nds 1 lb of gold and 3 lb of silver. Formulate an LP to help Goldilocks meet her requirements while spending as little time as possible in the mines. Graphically solve the LP. Balintfy (1976). Based on Hilal and Erickson (1981). 3 . 4 A Diet Problem 71 revenue, then graphically solve the LP. (A fractional number of cakes is okay.) 3 I now have $100. The following investments are available during the next three years: Investment A Every dollar invested now yields $0.10 a year from now and $1.30 three years from now. Investment B Every dollar invested now yields $0.20 a year from now and $1.10 two years from now. Investment C Every dollar invested a year from now yields $1.50 three years from now. During each year, uninvested cash can be placed in money market funds, which yield 6% interest per year. At most $50 may be placed in each of investments A, B, and C. Formulate an LP to maximize my cash on hand three years from now. 4 Sunco processes oil into aviation fuel and heating oil. It costs $40 to purchase each 1,000 barrels of oil, which is then distilled and yields 500 barrels of aviation fuel and 500 barrels of heating oil. Output from the distillation may be sold directly or processed in the catalytic cracker. If sold after distillation without further processing, aviation fuel sells for $60 per 1,000 barrels, and heating oil sells for $40 per 1,000 barrels. It takes 1 hour to process 1,000 barrels of aviation fuel in the catalytic cracker, and these 1,000 barrels can be sold for $130. It takes 45 minutes to process 1,000 barrels of heating oil in the cracker, and these 1,000 barrels can be sold for $90. Each day, at most 20,000 barrels of oil can be purchased, and 8 hours of cracker time are available. Formulate an LP to maximize Sunco's prots. 5 Finco has the following investments available: Investment A For each dollar invested at time 0, we receive $0.10 at time 1 and $1.30 at time 2. (Time 0 now; time 1 one year from now; and so on.) Investment B For each dollar invested at time 1, we receive $1.60 at time 2. Investment C For each dollar invested at time 2, we receive $1.20 at time 3. mixture of the two alloys can be determined by averaging that of the alloys that are mixed together. For example, a one-ton mixture that is 40% alloy 1 and 60% alloy 2 has a tensile strength of 0.4(42,000) 0.6(50,000). Use linear programming to determine how to minimize the cost of producing a ton of steel. 7 Steelco manufactures two types of steel at three different steel mills. During a given month, each steel mill has 200 hours of blast furnace time available. Because of differences in the furnaces at each mill, the time and cost to produce a ton of steel differs for each mill. The time and cost for each mill are shown in Table 48. Each month, Steelco must manufacture at least 500 tons of steel 1 and 600 tons of steel 2. Formulate an LP to minimize the cost of manufacturing the desired steel. 8 Walnut Orchard has two farms that grow wheat and corn. Because of differing soil conditions, there are differences in the yields and costs of growing crops on the two farms. The yields and costs are shown in Table 49. Each farm has 100 acres available for cultivation; 11,000 bushels of wheat and 7,000 bushels of corn must be grown. Determine a planting plan that will minimize the cost of meeting these demands. How could an extension of this model be used to allocate crop production efciently throughout a nation? 9 Candy Kane Cosmetics (CKC) produces Leslie Perfume, which requires chemicals and labor. Two production processes are available: Process 1 transforms 1 unit of labor and 2 units of chemicals into 3 oz of perfume. Process 2 transforms 2 units of labor and 3 units of chemicals into 5 oz of perfume. It costs CKC $3 to purchase a unit of labor and $2 to purchase a unit of chemicals. Each year, up to 20,000 units of labor and 35,000 units of chemicals can be purchased. In the absence of advertising, CKC believes it can sell 1,000 oz of perfume. To stimulate demand for TA B L E 48 At any time, leftover cash may be invested in T-bills, which pay 10% per year. At time 0, we have $100. At most, $50 can be invested in each of investments A, B, and C. Formulate an LP that can be used to maximize Finco's cash on hand at time 3. Producing a Ton of Steel Mill Cost Time (Minutes) Cost Time (Minutes) 6 All steel manufactured by Steelco must meet the following requirements: 3.2-3.5% carbon; 1.8-2.5% silicon; 0.9-1.2% nickel; tensile strength of at least 45,000 pounds per square inch (psi). Steelco manufactures steel by combining two alloys. The cost and properties of each alloy are given in Table 47. Assume that the tensile strength of a 1 2 3 $10 $12 $14 20 24 28 $11 $ 9 $10 22 18 30 Farm 1 Farm 2 500 100 400 90 650 120 350 80 Steel 1 TA B L E TA B L E 49 47 Alloy 1 Cost per ton ($) Percent silicon Percent nickel Percent carbon Tensile strength (psi) 114 Steel 2 Alloy 2 $190 2 1 3 42,000 $200 2.5 1.5 4 50,000 CHAPTER 3 Introduction to Linear Programming Corn yield/acre (bushels) Cost/acre of corn ($) Wheat yield/acre (bushels) Cost/acre of wheat ($) Based on Heady and Egbert (1964). Leslie, CKC can hire the lovely model Jenny Nelson. Jenny is paid $100/hour. Each hour Jenny works for the company is estimated to increase the demand for Leslie Perfume by 200 oz. Each ounce of Leslie Perfume sells for $5. Use linear programming to determine how CKC can maximize prots. 10 Carco has a $150,000 advertising budget. To increase automobile sales, the rm is considering advertising in newspapers and on television. The more Carco uses a particular medium, the less effective is each additional ad. Table 50 shows the number of new customers reached by each ad. Each newspaper ad costs $1,000, and each television ad costs $10,000. At most, 30 newspaper ads and 15 television ads can be placed. How can Carco maximize the number of new customers created by advertising? 11 Sunco Oil has reneries in Los Angeles and Chicago. The Los Angeles renery can rene up to 2 million barrels of oil per year, and the Chicago renery up to 3 million. Once rened, oil is shipped to two distribution points: Houston and New York City. Sunco estimates that each distribution point can sell up to 5 million barrels per year. Because of differences in shipping and rening costs, the prot earned (in dollars) per million barrels of oil shipped depends on where the oil was rened and on the point of distribution (see Table 51). Sunco is considering expanding the capacity of each renery. Each million barrels of annual rening capacity that is added will cost $120,000 for the Los Angeles renery and $150,000 for the Chicago renery. Use linear programming to determine how Sunco can maximize its prots less expansion costs over a ten-year period. 12 For a telephone survey, a marketing research group needs to contact at least 150 wives, 120 husbands, 100 single adult males, and 110 single adult females. It costs $2 to make a daytime call and (because of higher labor costs) $5 to make an evening call. Table 52 lists the results. Because of limited staff, at most half of all phone calls can be evening calls. Formulate an LP to minimize the cost of completing the survey. TA B L E 50 Number of Ads 1-10 11-20 21-30 1-5 6-10 11-15 Newspaper Television TA B L E New Customers 900 600 300 10,000 5,000 2,000 51 Prot per Million Barrels ($) From Los Angeles Chicago To Houston To New York 20,000 18,000 15,000 17,000 TA B L E 52 Person Responding Wife Husband Single male Single female None Percent of Daytime Calls Percent of Evening Calls 30 10 10 10 40 30 30 15 20 5 13 Feedco produces two types of cattle feed, both consisting totally of wheat and alfalfa. Feed 1 must contain at least 80% wheat, and feed 2 must contain at least 60% alfalfa. Feed 1 sells for $1.50/lb, and feed 2 sells for $1.30/lb. Feedco can purchase up to 1,000 lb of wheat at 50/lb and up to 800 lb of alfalfa at 40/lb. Demand for each type of feed is unlimited. Formulate an LP to maximize Feedco's prot. 14 Feedco (see Problem 13) has decided to give its customer (assume it has only one customer) a quantity discount. If the customer purchases more than 300 lb of feed 1, each pound over the rst 300 lb will sell for only $1.25/lb. Similarly, if the customer purchases more than 300 pounds of feed 2, each pound over the rst 300 lb will sell for $1.00/lb. Modify the LP of Problem 13 to account for the presence of quantity discounts. (Hint: Dene variables for the feed sold at each price.) 15 Chemco produces two chemicals: A and B. These chemicals are produced via two manufacturing processes. Process 1 requires 2 hours of labor and 1 lb of raw material to produce 2 oz of A and 1 oz of B. Process 2 requires 3 hours of labor and 2 lb of raw material to produce 3 oz of A and 2 oz of B. Sixty hours of labor and 40 lb of raw material are available. Demand for A is unlimited, but only 20 oz of B can be sold. A sells for $16/oz, and B sells for $14/oz. Any B that is unsold must be disposed of at a cost of $2/oz. Formulate an LP to maximize Chemco's revenue less disposal costs. 16 Suppose that in the CSL computer example of Section 3.12, it takes two months to train a technician and that during the second month of training, each trainee requires 10 hours of experienced technician time. Modify the formulation in the text to account for these changes. 17 Furnco manufactures tables and chairs. Each table and chair must be made entirely out of oak or entirely out of pine. A total of 150 board ft of oak and 210 board ft of pine are available. A table requires either 17 board ft of oak or 30 board ft of pine, and a chair requires either 5 board ft of oak or 13 board ft of pine. Each table can be sold for $40, and each chair for $15. Formulate an LP that can be used to maximize revenue. 18 The city of Busville contains three school districts. The number of minority and nonminority students in each 2 0 district is given in Table 53. Of all students, 25% (0) are 800 minority students. Based on Franklin and Koenigsberg (1973). Review Problems 115 TA B L E 62 TA B L E 63 Maximum Demand for Trucks Hourly Salary Year Type 1 Type 2 Shift 1 2 3 100 200 300 200 100 150 8 A.M.-4 P.M. 4 P.M.-Midnight Midnight-8 A.M. 28 Describe all optimal solutions to the following LP: min z 4x1 x2 s.t. 3x1 x2 6 4x1 x2 12 x1 x2 2 x1, x2 0 29 Juiceco manufactures two products: premium orange juice and regular orange juice. Both products are made by combining two types of oranges: grade 6 and grade 3. The oranges in premium juice must have an average grade of at least 5, those in regular juice, at least 4. During each of the next two months Juiceco can sell up to 1,000 gallons of premium juice and up to 2,000 gallons of regular juice. Premium juice sells for $1.00 per gallon, while regular juice sells for 80 per gallon. At the beginning of month 1, Juiceco has 3,000 gallons of grade 6 oranges and 2,000 gallons of grade 3 oranges. At the beginning of month 2, Juiceco may purchase additional grade 3 oranges for 40 per gallon and additional grade 6 oranges for 60 per gallon. Juice spoils at the end of the month, so it makes no sense to make extra juice during month 1 in the hopes of using it to meet month 2 demand. Oranges left at the end of month 1 may be used to produce juice for month 2. At the end of month 1 a holding cost of 5 is assessed against each gallon of leftover grade 3 oranges, and 10 against each gallon of leftover grade 6 oranges. In addition to the cost of the oranges, it costs 10 to produce each gallon of (regular or premium) juice. Formulate an LP that could be used to maximize the prot (revenues costs) earned by Juiceco during the next two months. 30 Graphically solve the following linear programming problem: max z 5x1 x2 s.t. 2x1 3x2 12 x1 3x2 0 x1 0, x2 0 31 Graphically nd all solutions to the following LP: min z x1 2x2 s.t. x1 x2 4 x1 x2 8 x1 x2 6 x1, x2 0 32 Each day Eastinghouse produces capacitors during three shifts: 8 A.M.-4 P.M., 4 P.M.-midnight, midnight-8 A.M. The hourly salary paid to the employees on each shift, the price charged for each capacitor made during each shift, and 118 CHAPTER 3 Introduction to Linear Programming Defects (per Capacitor) Price $12 $16 $20 4 3 2 $18 $22 $24 the number of defects in each capacitor produced during a given shift are shown in Table 63. Each of the company's 25 workers can be assigned to one of the three shifts. A worker produces 10 capacitors during a shift, but because of machinery limitations, no more than 10 workers can be assigned to any shift. Each day, at most 250 capacitors can be sold, and the average number of defects per capacitor for the day's production cannot exceed three. Formulate an LP to maximize Eastinghouse's daily prot (sales revenue labor cost). 33 Graphically nd all solutions to the following LP: max z 4x1 x2 s.t. 8x1 2x2 16 x1 x2 12 x1, x2 0 34 During the next three months Airco must meet (on time) the following demands for air conditioners: month 1, 300; month 2, 400; month 3, 500. Air conditioners can be produced in either New York or Los Angeles. It takes 1.5 hours of skilled labor to produce an air conditioner in Los Angeles, and 2 hours in New York. It costs $400 to produce an air conditioner in Los Angeles, and $350 in New York. During each month, each city has 420 hours of skilled labor available. It costs $100 to hold an air conditioner in inventory for a month. At the beginning of month 1, Airco has 200 air conditioners in stock. Formulate an LP whose solution will tell Airco how to minimize the cost of meeting air conditioner demands for the next three months. 35 Formulate the following as a linear programming problem: A greenhouse operator plans to bid for the job of providing owers for city parks. He will use tulips, daffodils, and owering shrubs in three types of layouts. A Type 1 layout uses 30 tulips, 20 daffodils, and 4 owering shrubs. A Type 2 layout uses 10 tulips, 40 daffodils, and 3 owering shrubs. A Type 3 layout uses 20 tulips, 50 daffodils, and 2 owering shrubs. The net prot is $50 for each Type 1 layout, $30 for each Type 2 layout, and $60 for each Type 3 layout. He has 1,000 tulips, 800 daffodils, and 100 owering shrubs. How many layouts of each type should be used to yield maximum prot? 36 Explain how your formulation in Problem 35 changes if both of the following conditions are added: a The number of Type 1 layouts cannot exceed the number of Type 2 layouts. b There must be at least ve layouts of each type. TA B L E 76 Price ($) Stock Shares Owned 1 2 3 4 5 6 7 8 9 10 Tax rate (%) Transaction cost (%) TA B L E Time Period 9-10 10-11 11-Noon Noon-1 1-2 2-3 3-4 4-5 Purchase Current In One Year 100 100 100 100 100 100 100 100 100 100 0.3 0.01 20 25 30 35 40 45 50 55 60 65 30 34 43 47 49 53 60 62 64 66 36 39 42 45 51 55 63 64 66 70 77 Tellers Required 4 3 4 6 5 6 8 8 time teller must work exactly 3 consecutive hours each day. A part-time teller is paid $5/hour (and receives no fringe benets). To maintain adequate quality of service, the bank has decided that at most ve part-time tellers can be hired. Formulate an LP to meet the teller requirements at minimum cost. Solve the LP on a computer. Experiment with the LP answer to determine an employment policy that comes close to minimizing labor cost. 47 The Gotham City Police Department employs 30 police ofcers. Each ofcer works 5 days per week. The crime rate uctuates with the day of the week, so the number of police ofcers required each day depends on which day of the week it is: Saturday, 28; Sunday, 18; Monday, 18; Tuesday, 24; Wednesday, 25; Thursday, 16; Friday, 21. The police department wants to schedule police ofcers to minimize the number whose days off are not consecutive. Formulate an LP that will accomplish this goal. (Hint: Have a constraint for each day of the week that ensures that the proper number of ofcers are not working on the given day.) 48Alexis Cornby makes her living buying and selling corn. On January 1, she has 50 tons of corn and $1,000. On the rst day of each month Alexis can buy corn at the following prices per ton: January, $300; February, $350; March, $400; April, $500. On the last day of each month, Alexis can sell corn at the following prices per ton: January, $250; February, $400; March, $350; April, $550. Alexis stores her corn in a warehouse that can hold at most 100 tons of corn. She must be able to pay cash for all corn at the time of purchase. Use linear programming to determine how Alexis can maximize her cash on hand at the end of April. 49At the beginning of month 1, Finco has $400 in cash. At the beginning of months 1, 2, 3, and 4, Finco receives certain revenues, after which it pays bills (see Table 78). Any money left over may be invested for one month at the interest rate of 0.1% per month; for two months at 0.5% per month; for three months at 1% per month; or for four months at 2% per month. Use linear programming to determine an investment strategy that maximizes cash on hand at the beginning of month 5. 50 City 1 produces 500 tons of waste per day, and city 2 produces 400 tons of waste per day. Waste must be incinerated at incinerator 1 or 2, and each incinerator can process up to 500 tons of waste per day. The cost to incinerate waste is $40/ton at incinerator 1 and $30/ton at 2. TA B L E 78 Month Revenues ($) Bills ($) 400 800 300 300 600 500 500 250 1 2 3 4 Based on Rothstein (1973). Based on Charnes and Cooper (1955). Based on Robichek, Teichroew, and Jones (1965). Review Problems 121