4.1Linear Programming and Mixture Problems: Combining Resources to Maximize Profit

1. Find the coordinates of all points where the lines , and intersect.

2. Find the - and -intercepts of the line .

3. Graph the lines , and on the same set of axes. For each pair of these three lines, find the - and -coordinates where the lines intersect.

4. Using intercepts, the points where the lines cross the axes, graph each line.

5. Using intercepts, the points where the lines cross the axes, graph each line.

6.

7. Graph both lines on the same axes. Put a dot where the lines intersect. Use algebra to find the - and -coordinates of the point of intersection.

8. Graph both lines on the same axes. Put a dot where the lines intersect. Use algebra to find the - and -coordinates of the point of intersection.

9. Graph both lines on the same axes. Put a dot where the lines intersect. Use algebra to find the - and -coordinates of the point of intersection.

10. Graph the line and half-plane corresponding to the inequality, a typical constraint from a mixture problem.

11. Graph the line and half-plane corresponding to the inequality, a typical constraint from a mixture problem.

12.

13.

165

14. Manufacturing one salami requires 12 oz of beef and 4 oz of pork. Manufacturing one bologna requires 10 oz of beef and 3 oz of pork. There are 40 lb of beef and 480 oz of pork available.

15.; ;

16.; ; ;

17.; ;

18.; ;

19.; ;

20.; ;

21. Exercises 15, 17, and 19.

22. Exercises 16, 18, and 20.

23. In the toy problem, represents the number of skateboards and the number of dolls. Using the version of that problem whose feasible region is presented in Figure 4.3b, with the profit formula , write a sentence giving the maximum profit and describing the production policy that gives that profit.

24. In the toy problem, represents the number of skateboards and the number of dolls. Using the version of that problem whose feasible region is presented in Figure 4.3b, with the profit formula , write a sentence giving the maximum profit and describing the production policy that gives that profit.

25. Graph both lines on the same axes. Put a dot where the lines intersect. Use algebra to find the - and -coordinates of the point of intersection.

26.; ; ;

27.; ; ;

28.; ; ;

29.; ; ;

30. Determine whether the points (4, 2) and/or (1, 3) are points of the given feasible regions of Exercises 27 and 29.

31. Determine the maximum value of given by subject to the constraints , and .

32. A linear-programming problem has constraints given by , , , and .

4.2 Finding the Optimal Production Policy

4.3 Why the Corner Point Principle Works

4.4 Linear Programming: Life Is Complicated

33. A linear-programming problem has constraints given by , , , and .

34. Nuts Galore sells two spiced nut mixtures: Grade A and Grade B. Grade A requires 7 oz of peanuts for every 8 oz of almonds. Grade B requires 9 oz of peanuts for every 8 oz of almonds. There are 630 oz of peanuts and 640 oz of almonds available. Grade A makes Nuts Galore a profit of $1.70, and Grade B makes a profit of $2.40 per unit assembled. How many units of Grade A and Grade B nut mixtures should be made to maximize the company’s profit, assuming that all units made can be sold?

35. Find the maximum value of where subject to the constraints , , , .

36. Find the maximum value of where subject to the constraints , , , and .

37. Find the maximum value of where subject to the constraints , , and .

38. Given profit subject to the constraints :

39.

1. Make a mixture chart for the problem.
2. Using the mixture chart, write the profit formula and the resource- and minimum-constraint inequalities.
3. Draw the feasible region for those constraints and find the coordinates of the corner points.
4. Evaluate the profit information at the corner points to determine the production policy that best answers the question.
5. (Requires technology) Compare your answer with the one you get from running the same problem on a simplex algorithm computer program.

40. A clothing manufacturer has 600 yd of cloth available to make shirts and decorated vests. Each shirt requires 3 yd of material and provides a profit of $5. Each vest requires 2 yd of material and provides a profit of $2. The manufacturer wants to guarantee that under all circumstances, there are minimums of 100 shirts and 30 vests produced. How many of each garment should be made to maximize profit? If there are no minimum quantities, how, if at all, does the optimal production policy change?

41. A car maintenance shop must decide how many oil changes and how many tune-ups can be scheduled in a typical week. The oil change takes 20 min, and the tune-up requires 100 min. The maintenance shop makes a profit of $15 on an oil change and $65 on a tune-up. What mix of services should the shop schedule if the typical week has 8000 min available for these two types of services? How, if at all, do the maximum profit and optimal production policy change if the shop is required to schedule at least 50 oil changes and 20 tune-ups?

42. A clerk in a bookstore has 90 min at the end of each workday to process orders received by mail or on voice mail. The store has found that a typical mail order brings in a profit of $30 and a typical voice-mail order brings in a profit of $40. Each mail order takes 10 min to process and each voice-mail order takes 15 min. How many of each type of order should the clerk process? How, if at all, do the maximum profit and optimal processing policy change if the clerk must process at least three mail orders and two voice-mail orders?

43. In a certain medical office, a routine office visit requires 5 min of doctors’ time and a comprehensive office visit requires 25 min of doctors’ time. In a typical week, there are 1800 min of doctors’ time available. If the medical office clears $30 from a routine visit and $50 from a comprehensive visit, how many of each should be scheduled per week? How, if at all, do the maximum profit and optimal production policy change if the office is required to schedule at least 20 routine visits and 30 comprehensive ones?

44. A bakery makes 600 specialty breads—multigrain or herb—each week. Standing orders from restaurants are for 100 multigrain breads and 200 herb breads. The profit on each multigrain bread is $8 and on herb bread, $10. How many breads of each type should the bakery make to maximize profit? How, if at all, do the maximum profit and optimal production policy change if the bakery has no standing orders?

45. A student has decided that passing a mathematics course will, in the long run, be twice as valuable as passing any other kind of course. The student estimates that passing a typical math course will require 12 hr a week to study and do homework. The student estimates that any other course will require only 8 hr a week. The student has 48 hr available for study per week. How many of each kind of course should the student take?

167

(Hint: The profit could be viewed as 2 “value points” for passing a math course and 1 “value point” for passing any other course.) How, if at all, do the maximum value and optimal course mix change if the student decides to take at least two math courses and two other courses?

Exercises 46–49 require finding the point of intersection of two lines, each corresponding to a resource constraint.

46. The firm WebsAreUs creates and maintains websites for client companies. There are two types of websites: “Hot” sites change their layout frequently but keep their content for long times; “cool” sites keep their layout for a while but frequently change their content. Maintaining a hot site requires 1.5 hr of layout time and 1 hr for content changes. Maintaining a cool site requires 1 hr of layout time and 2 hr for content changes. Every day, WebsAreUs has 12 hr available for layout changes and 16 hr for content changes. Net profit is $50 for a set of changes on a hot site and $250 for a set of changes on a cool site. To maximize profit, how many of each type of site should WebsAreUs maintain daily? How, if at all, do the maximum profit and optimal policy change if the company must maintain at least two hot and three cool sites daily?

47. A paper recycling company uses scrap cloth and scrap paper to make two different grades of recycled paper. A single batch of grade A recycled paper is made from 25 lb of scrap cloth and 10 lb of scrap paper, whereas one batch of grade B recycled paper is made from 10 lb of scrap cloth and 20 lb of scrap paper. The company has 100 lb of scrap cloth and 120 lb of scrap paper on hand. A batch of grade A paper brings a profit of $500, whereas a batch of grade B paper brings a profit of $250. What amounts of each grade should be made? How, if at all, do the maximum profit and optimal production policy change if the company is required to produce at least one batch of each type?

48. Jerry Wolfe has a 100-acre farm that he is dividing into one-acre plots, on each of which he builds a house. He then sells the house and land. It costs him $20,000 to build a modest house and $40,000 to build a deluxe house. He has $2,600,000 to cover these costs. The profits are $25,000 for a modest house and $60,000 for a deluxe house. How many of each type of house should he build to maximize profit? How, if at all, do the maximum profit and optimal production policy change if Wolfe is required to build at least 20 of each type of house?

49. The maximum production of a soft-drink bottling company is 5000 cartons per day. The company produces regular and diet drinks and must make at least 600 cartons of regular and 1000 cartons of diet per day. Production costs are $1.00 per carton of regular and $1.20 per carton of diet. The daily operating budget is $5400. How many cartons of each type of drink should be produced if the profit is $0.10 per regular and $0.11 per diet? How, if at all, do the maximum profit and optimal bottling policy change if the company has no minimum required production?

50. Wild Things raises pheasants and partridges to restock the woodlands and has room to raise 100 birds during the season. The cost of raising one bird is $20 per pheasant and $30 per partridge. The Wildlife Foundation pays Wild Things for the birds; the latter clears a profit of $14 per pheasant and $16 per partridge. Wild Things has $2400 available to cover costs. How many of each type of bird should they raise? How, if at all, do the maximum profit and optimal restocking policy change if Wild Things is required to raise at least 20 pheasants and 10 partridges?

51. Lights Aglow makes desk lamps and floor lamps, on which the profits are $2.65 and $4.67, respectively. The company has 1200 hr of labor and $4200 for materials each week. A desk lamp takes 0.8 hr of labor and $4 for materials; a floor lamp takes 1.0 hr of labor and $3 for materials. What production policy maximizes profit? How, if at all, do the maximum profit and optimal production policy change if Lights Aglow wants to produce at least 150 desk lamps and 200 floor lamps per week?

1. Make a mixture chart for each problem.
2. Using the mixture chart, write the resource- and minimum-constraint inequalities. Also write the profit formula.
3. (Requires software) If you have a simplex method program available, run the program to obtain the optimal production policy.

52. A toy company makes three types of toys, each of which must be processed by three machines: a shaper, a smoother, and a painter. Each Toy A requires 1 hr in the shaper, 2 hr in the smoother, and 1 hr in the painter, and brings in a $4 profit. Each Toy B requires 2 hr in the shaper, 1 hr in the smoother, and 3 hr in the painter, and brings in a $5 profit. Each Toy C requires 3 hr in the shaper, 2 hr in the smoother, and 1 hr in the painter, and brings in a $9 profit. The shaper can work at most 50 hr per week, the smoother 40 hr, and the painter 60 hr. What production policy would maximize the toy company’s profit?

53. A rustic furniture company handcrafts chairs, tables, and beds. It has three workers, Chris, Sue, and Juan. Chris can work only 80 hr per month, but Sue and Juan can each put in 200 hr. Each of these artisans has special skills. To make a chair takes 1 hr of Chris’s time, 3 from Sue, and 2 from Juan. A table needs 3 hr from Chris, 5 from Sue, and 4 from Juan. A bed requires 5 hr from Chris, 4 from Sue, and 8 from Juan. Even artisans are concerned about maximizing their profit, so what product mix should the company stick with if it gets $100 profit per chair, $250 per table, and $350 per bed?

54. A candy manufacturer has 1000 lb of chocolate, 200 lb of nuts, and 100 lb of fruit in stock. The Special Mix requires 3 lb of chocolate, 1 lb each of nuts and fruit, and it brings in $10. The Regular Mix requires 4 lb of chocolate, 0.5 lb of nuts, and no fruit, and brings in $6. The Purist Mix requires 5 lb of chocolate, no nuts or fruit, and brings in $4. How many boxes of each type should be produced to maximize profit?

55. A gourmet coffee distributor has on hand 17,600 lb of African coffee, 21,120 oz of Brazilian coffee, and 12,320 oz of Colombian coffee. It sells four blends—Excellent, Southern, World, and Special—on which it makes these per-pound profits, respectively: $1.80, $1.40, $1.20, and $1.00. One pound of Excellent is 16 oz of Colombian; it is not a blend at all. One pound of Southern consists of 12 oz of Brazilian and 4 oz of Colombian. One pound of World requires 6 oz of African, 8 oz of Brazilian, and 2 oz of Colombian. One pound of Special is made up of 10 oz of African and 6 oz of Brazilian. What product mix should the gourmet coffee distributor prepare to maximize profit?

56. Minimize given by over the feasible region for Exercise 35.

57. Minimize given by over the feasible region for Exercise 36.

58. Show by example that a feasible region that has the nonnegativity constraints , and can have no feasible points with integer coordinates other than (0, 0).

59. Courtesy Calls makes telephone calls for businesses and charities. A profit of $0.50 is made for each business call and $0.40 for each charity call. It takes 4 min (on average) to make a business call and 6 min (on average) to make a charity call. If there are 240 min of calling time to be distributed each day, how should that time be spent so that Courtesy Calls makes a maximum profit? What changes, if any, occur in the maximum profit and optimal production policy if they must make at least 12 business and 10 charity calls every day?

60. A refinery mixes high-octane and low-octane fuels to produce regular and premium gasolines. The profits per gallon on the two gasolines are $0.30 and $0.40, respectively. One gallon of premium gasoline is produced by mixing 0.5 gal of each of the fuels. One gallon of regular gasoline is produced by mixing 0. 25 gal of high octane with 0.75 gal of low octane. If there are 500 gal of high octane and 600 gal of low octane available, how many gallons of each gasoline should the refinery make? How, if at all, do the maximum profit and optimal production policy change if the refinery is required to produce at least 100 gal of each gasoline?

61. A toy manufacturer makes bikes, for a profit of $12, and wagons, for a profit of $10. To produce a bike requires 2 hr of machine time and 4 hr painting time. To produce a wagon requires 3 hr machine time and 2 hr painting time. There are 12 hr of machine time and 16 hr of painting time available per day. How many of each toy should be produced to maximize profit? How, if at all, do the maximum profit and optimal production policy change if the manufacturer must produce at least two bikes and two wagons daily?

4.5 A Transportation Problem: Delivering Perishables

4.6 Improving on the Current Solution

62. Apply the Northwest Corner Rule, thereby finding a feasible solution that obeys the rim conditions, to the following transportation problem tableaux.

63. The accompanying tableau represents the shipping costs and supply-and-demand constraints for supplies of purified water to be shipped to companies that resell the water to office buildings.

64. The accompanying tableau represents the shipping costs and supply-and-demand constraints for supplies of purified water to be shipped to companies that resell the water to office buildings.

65.

66. Apply the Northwest Corner Rule, thereby finding a feasible solution that obeys the rim conditions for the following transportation problem diagrams.

67. The accompanying tableau arose by applying the Northwest Corner Rule.

The accompanying graph was constructed so that there is one edge for each circled vertex in the tableau above.

68.

171

69.

70.

71. For each of the situations below, explain whether it seems reasonable to try to model it as a transportation problem.

72. Apply the Northwest Corner Rule to find a feasible solution for the transportation problem given in the accompanying tableau, and find the cost of shipping using this feasible solution (circled cells).

73.

Chapter Review

74. Graph on the same set of axes the equations , , and . In the diagram:

75. If maximal profit is given by , what is the maximal value of for the constraints , and ?

76. Two dairies supply three supermarket chains with the demands for milk, as shown in the table below. Also indicated in a cell is the cost of shipping between pairs of sites.