8-1 (Production problem) Winkler Furniture manufactures two different types of china cabinets: a French Provincial model and a Danish Modern model. Each cabinet produced must go through three departments: carpentry, painting, and finishing. The table on this page contains all relevant information concerning production times per cabinet produced and production capacities for each operation per day, along with net revenue per unit produced. The firm has a contract with an Indiana distributor to produce a minimum of 300 of each cabinet per week (or 60 cabinets per day). Owner Bob Winkler would like to determine a product mix to maximize his daily revenue.

1. Formulate as an LP problem.

2. Solve using an LP software program or spreadsheet.

8-2 (Investment decision problem) The Heinlein and Krampf Brokerage firm has just been instructed by one of its clients to invest $250,000 of her money obtained recently through the sale of land holdings in Ohio. The client has a good deal of trust in the investment house, but she also has her own ideas about the distribution of the funds being invested. In particular, she requests that the firm select whatever stocks and bonds they believe are well rated but within the following guidelines:

• Municipal bonds should constitute at least 20% of the investment.

• At least 40% of the funds should be placed in a combination of electronic firms, aerospace firms, and drug manufacturers.

• No more than 50% of the amount invested in municipal bonds should be placed in a high-risk, high-yield nursing home stock.

Subject to these restraints, the client’s goal is to maximize projected return on investments. The analysts at Heinlein and Krampf, aware of these guidelines, prepare a list of high-quality stocks and bonds and their corresponding rates of return:

1. Formulate this portfolio selection problem using LP.

2. Solve this problem.

8-3 (Restaurant work scheduling problem) The famous Y. S. Chang Restaurant is open 24 hours a day. Waiters and busboys report for duty at 3 a.m., 7 a.m., 11 a.m., 3 p.m., 7 p.m., or 11 p.m., and each works an 8-hour shift. The following table shows the minimum number of workers needed during the six periods into which the day is divided. Chang’s scheduling problem is to determine how many waiters and busboys should report for work at the start of each time period to minimize the total staff required for one day’s operation. (Hint: Let $X_i$ equal the number of waiters and busboys beginning work in time period i, where $i=1, 2, 3, 4, 5, 6.$)

8-4 (Animal feed mix problem) The Battery Park Stable feeds and houses the horses used to pull tourist-filled carriages through the streets of Charleston’s historic waterfront area. The stable owner, an ex-racehorse trainer, recognizes the need to set a nutritional diet for the horses in his care. At the same time, he would like to keep the overall daily cost of feed to a minimum.

The feed mixes available for the horses’ diet are an oat product, a highly enriched grain, and a mineral product. Each of these mixes contains a certain amount of five ingredients needed daily to keep the average horse healthy. The table on this page shows these minimum requirements, units of each ingredient per pound of feed mix, and costs for the three mixes.

8-5 The Kleenglass Corporation makes a dishwasher that has excellent cleaning power. This dishwasher uses less water than most competitors, and it is extremely quiet. Orders have been received from several retail stores for delivery at the end of each of the next 3 months, as shown below:

Due to limited capacity, only 200 of these dishwashers can be made each month on regular time, and the cost is $300 each. However, an extra 15 units per month can be produced if overtime is used, but the cost goes up to $325 each. Also, if there are any dishwashers produced in a month that are not sold in that month, there is a $20 cost to carry this item to the next month. Use linear programming to determine how many units to produce in each month on regular time and on overtime to minimize the total cost while meeting the demand.

8-6 Eddie Kelly is running for reelection as mayor of a small town in Alabama. Jessica Martinez, Kelly’s campaign manager during this election, is planning the marketing campaign, and there is some stiff competition. Martinez has selected four ways to advertise: television ads, radio ads, billboards, and newspaper ads. The costs of these, the audience reached by each type of ad, and the maximum number available are shown in the following table:

In addition, Martinez has decided that there should be at least six ads on TV or social media or some combination of those two. The amount spent on billboards and newspapers together must not exceed the amount spent on TV ads. While fund-raising is still continuing, the monthly budget for advertising has been set at $15,000. How many ads of each type should be placed to maximize the total number of people reached?

8-7 (Media selection problem) The advertising director for Diversey Paint and Supply, a chain of four retail stores on Chicago’s North Side, is considering two media possibilities. One plan is for a series of half-page ads in the Sunday Chicago Tribune newspaper, and the other is for advertising time on Chicago TV. The stores are expanding their lines of do-it-yourself tools, and the advertising director is interested in an exposure level of at least 40% within the city’s neighborhoods and 60% in northwest suburban areas.

The TV viewing time under consideration has an exposure rating per spot of 5% in city homes and 3% in the northwest suburbs. The Sunday newspaper has corresponding exposure rates of 4% and 3% per ad. The cost of a half-page Tribune advertisement is $925; a television spot costs $2,000.

Diversey Paint would like to select the least costly advertising strategy that would meet desired exposure levels.

1. Formulate using LP.

2. Solve the problem.

8-8 (Automobile leasing problem) Sundown Rent-a-Car, a large automobile rental agency operating in the Midwest, is preparing a leasing strategy for the next six months. Sundown leases cars from an automobile manufacturer and then rents them to the public on a daily basis. A forecast of the demand for Sundown’s cars in the next six months follows:

Cars may be leased from the manufacturer for either three, four, or five months. These are leased on the first day of the month and are returned on the last day of the month. Every six months the automobile manufacturer is notified by Sundown about the number of cars needed during the next six months. The automobile manufacturer has stipulated that at least 50% of the cars leased during a six-month period must be on the five-month lease. The cost per month is $420 for the three-month lease, $400 for the four-month lease, and $370 for the five-month lease.

Currently, Sundown has 390 cars. The lease on 120 cars expires at the end of March. The lease on another 140 cars expires at the end of April, and the lease on the rest of these expires at the end of May.

Use LP to determine how many cars should be leased in each month on each type of lease to minimize the cost of leasing over the six-month period. How many cars are left at the end of August?

8-9 Management of Sundown Rent-a-Car (see Problem 8.8) has decided that perhaps the cost during the six-month period is not the appropriate cost to minimize because the agency may still be obligated to additional months on some leases after that time. For example, if Sundown had some cars delivered at the beginning of the sixth month, Sundown would still be obligated for two additional months on a three-month lease. Use LP to determine how many cars should be leased in each month on each type of lease to minimize the cost of leasing over the entire life of these leases.

8-10 (High school busing problem) The Arden County, Maryland, superintendent of education is responsible for assigning students to the three high schools in his county. He recognizes the need to bus a certain number of students, for several sectors of the county are beyond walking distance to a school. The superintendent partitions the county into five geographic sectors as he attempts to establish a plan that will minimize the total number of student miles traveled by bus. He also recognizes that if a student happens to live in a certain sector and is assigned to the high school in that sector, there is no need to bus that student because he or she can walk to school. The three schools are located in sectors B, C, and E.

The following table reflects the number of high-school-age students living in each sector and the busing distance in miles from each sector to each school:

Each high school has a capacity of 900 students. Set up the objective function and constraints of this problem using LP so that the total number of student miles traveled by bus is minimized. Then solve the problem.

8-11 (Pricing and marketing strategy problem) The I. Kruger Paint and Wallpaper Store is a large retail distributor of the Supertrex brand of vinyl wallcoverings. Kruger will enhance its citywide image in Miami if it can sell more rolls of Supertrex next year than other local stores. It is able to estimate the demand function as follows:

Number of rolls of Supertrex sold = 20 × Dollars spent on advertising + 6.8 × Dollars spent on in@store displays + 12 × Dollars invested in on@hand wallpaper inventory - 65,000 × Percentage markup taken above wholesale cost of a roll

The store budgets a total of $17,000 for advertising, in-store displays, and on-hand inventory of Supertrex for next year. It decides it must spend at least $3,000 on advertising; in addition, at least 5% of the amount invested in on-hand inventory should be devoted to displays. Markups on Supertrex seen at other local stores range from 20% to 45%. Kruger decides that its markup had best be in this range as well.

1. Formulate as an LP problem.

2. Solve the problem.

3. What is the difficulty with the answer?

4. What constraint would you add?

8-12 (College meal selection problem) Kathy Roniger, campus dietitian for a small Idaho college, is responsible for formulating a nutritious meal plan for students. For an evening meal, she feels that the following five meal-content requirements should be met: (1) between 900 and 1,500 calories; (2) at least 4 milligrams of iron; (3) no more than 50 grams of fat; (4) at least 26 grams of protein; and (5) no more than 50 grams of carbohydrates. On a particular day, Roniger’s food stock includes seven items that can be prepared and served for supper to meet these requirements. The cost per pound for each of the seven food items and the contribution of each to the five nutritional requirements are given in the table on this page.

What combination and amounts of food items will provide the nutrition Roniger requires at the least total food cost?

1. Formulate as an LP problem.

2. What is the cost per meal?

3. Is this a well-balanced diet?

8-13 (High-tech production problem) Quitmeyer Electronics Incorporated manufactures the following six microcomputer peripheral devices: internal modems, external modems, graphics circuit boards, CD drives, hard disk drives, and memory expansion boards. Each of these technical products requires time, in minutes, on three types of electronic testing devices, as shown in the table on this page.

The first two test devices are available 120 hours per week. The third (device 3) requires more preventive maintenance and may be used only 100hours each week. The market for all six computer components is vast, and Quitmeyer Electronics believes that it can sell as many units of each product as it can manufacture. The table that follows summarizes the revenue and material cost for each product:

In addition, variable labor costs are $15 per hour for test device 1, $12 per hour for test device 2, and $18 per hour for test device 3. Quitmeyer Electronics wants to maximize its profits.

1. Formulate this as an LP model problem.

2. Solve the problem by computer. What is the best product mix?

3. What is the value of an additional minute of time per week on test device 1? Test device 2? Test device 3? Should Quitmeyer Electronics add one or more test devices to make more time available? If so, on which device(s) should it add?

8-14 (Nuclear plant staffing problem) South Central Utilities has just announced the August 1 opening of its second nuclear generator at its Baton Rouge, Louisiana, nuclear power plant. Its personnel department has been directed to determine how many nuclear technicians need to be hired and trained over the remainder of the year.

The plant currently employs 350 fully trained technicians and projects the following personnel needs:

By Louisiana law, a reactor employee can actually work no more than 130 hours per month. (Slightly over 1 hour per day is used for check-in and check-out, recordkeeping, and daily radiation health scans.) Policy at South Central Utilities also dictates that layoffs are not acceptable in those months when the nuclear plant is overstaffed. So if more trained employees are available than are needed in any month, each worker is still fully paid, even though he or she is not required to work the 130 hours.

Training new employees is an important and costly procedure. It takes 1 month of one-on-one classroom instruction before a new technician is permitted to work alone in the reactor facility. Therefore, South Central must hire trainees 1 month before they are actually needed. Each trainee teams up with a skilled nuclear technician and requires 90 hours of that employee’s time, meaning that he or she has 90 fewer hours available that month for actual reactor work.

Personnel department records indicate a turnover rate of trained technicians at 5% per month. In other words, about 5% of the skilled employees at the start of any month resign by the end of that month. A trained technician earns an average monthly salary of $2,000 (regardless of the number of hours worked, as noted earlier). Trainees are paid $900 during their 1 month of instruction.

1. Formulate this staffing problem using LP.

2. Solve the problem. How many trainees must begin each month?

8-15 (Agricultural production planning problem) Margaret Black’s family owns five parcels of farmland, referred to as the southeast sector, north sector, northwest sector, west sector, and southwest sector. Margaret is involved primarily in growing wheat, alfalfa, and barley crops and is currently preparing her production plan for next year. The Pennsylvania Water Authority has just announced its yearly water allotment, with the Black farm receiving 7,400 acre-feet. Each parcel can tolerate only a specified amount of irrigation per growing season, as specified in the following table:

Each of Margaret’s crops needs a minimum amount of water per acre, and there is a projected limit on sales of each crop. Crop data follow:

Margaret’s best estimate is that she can sell wheat at a net profit of $2 per bushel, alfalfa at $40 per ton, and barley at $50 per ton. One acre of land yields an average of 1.5 tons of alfalfa and 2.2 tons of barley. The wheat yield is approximately 50 bushels per acre.

1. Formulate Margaret’s production plan.

2. What should the crop plan be, and what profit will it yield?

3. The Water Authority informs Margaret that for a special fee of $6,000 this year, her farm will qualify for an additional allotment of 600 acre-feet of water. How should she respond?

8-16 (Material blending problem) Amalgamated Products has just received a contract to construct steel body frames for automobiles that are to be produced at a new Japanese auto factory in Tennessee. The Japanese auto manufacturer has strict quality control standards for all of its component subcontractors and has informed Amalgamated that each frame must have the following steel content:

Amalgamated mixes batches of eight different available materials to produce 1 ton of steel for use in the body frames. The table on this page details these materials.

Formulate and solve the LP problem, indicating how much of each of the eight materials should be blended into a 1-ton load of steel so that Amalgamated meets its requirements while minimizing costs.

8-17 Refer to Problem 8.16. Find the cause of the difficulty and recommend how to adjust it. Then solve the problem again.

8-18 (Hospital expansion problem) Mt. Sinai Hospital in New Orleans is a large, private, 600-bed facility, complete with laboratories, operating rooms, and x-ray equipment. In seeking to increase revenues, Mt. Sinai’s administration has decided to build a 90-bed addition on a portion of adjacent land currently used for staff parking. The administrators feel that the labs, operating rooms, and x-ray department are not being fully utilized at present and do not need to be expanded to handle additional patients. The addition of 90 beds, however, requires a decision as to how many beds should be allocated to the medical staff for medical patients and how many to the surgical staff for surgical patients.

The hospital’s accounting and medical records departments have provided the following pertinent information. The average hospital stay for a medical patient is 8 days, and the average medical patient generates $2,280 in revenues. The average surgical patient is in the hospital 5 days and receives a $1,515 bill. The laboratory is capable of handling 15,000 tests per year more than it was handling. The average medical patient requires 3.1 lab tests and the average surgical patient takes 2.6 lab tests. Furthermore, the average medical patient uses one x-ray, whereas the average surgical patient requires two x-rays. If the hospital was expanded by 90 beds, the x-ray department could handle up to 7,000 x-rays without significant additional cost. Finally, the administration estimates that up to 2,800 additional operations could be performed in existing operating room facilities. Medical patients, of course, do not require surgery, whereas each surgical patient generally has one surgery performed.

Formulate this problem so as to determine how many medical beds and how many surgical beds should be added to maximize revenues. Assume that the hospital is open 365 days a year. Then solve the problem.

8-19 Prepare a written report to the CEO of Mt. Sinai Hospital in Problem 8.18 on the expansion of the hospital. Round off your answers to the nearest integer. The format in which you present the results is important. The CEO is a busy person and wants to be able to find your optimal solution quickly in your report. Cover all the areas given in the following sections, but do not mention any variables or shadow prices.

1. What is the maximum revenue per year, how many medical patients/year are there, and how many surgical patients/year are there? How many medical beds and how many surgical beds should be added in the 90-bed addition?

2. Are there any empty beds with this optimal solution? If so, how many empty beds are there? Discuss the effect of acquiring more beds if needed.

3. Are the laboratories being used to their capacity? Is it possible to perform more lab tests/year? If so, how many more? Discuss the effect of acquiring more lab space if needed.

4. Is the x-ray facility being used to its maximum? Is it possible to do more x-rays/year? If so, how many more? Discuss the effect of acquiring more x-ray facilities if needed.

5. Are the operating rooms being used to capacity? Is it possible to do more operations/year? If so, how many more? Discuss the effect of acquiring more operating room facilities if needed. (Source: Professor Chris Vertullo. Reprinted with permission.)

8-20 In the Low Knock Oil Company blending problem in Section 8.6, it was assumed that one barrel of crude would result in one barrel of gasoline as the final product. In processing one barrel of crude, a typical gasoline yield is about 0.46 barrel, although it could be higher or lower than this, depending on the particular crude and processing used. However, other products such as diesel, jet fuel, home fuel oil, and asphalt also come from that same barrel. Assuming that only 46% of the crude turns into gasoline, modify the Low Knock Oil Company linear programming example to account for this. Solve the resulting LP problem using any computer software.

8-21 A paper mill produces rolls of paper that are 10 inches wide and 100 feet long. These rolls are used for creating narrower rolls of paper that are used in cash registers, automatic teller machines (ATMs), and other devices. The narrower widths (2.5, 3, and 3.5 inches) needed for these devices are obtained by cutting the 10-inch rolls using prespecified cutting patterns. Cutting pattern #1 will cut the 10-inch roll into four rolls that are 2.5 inches each. Cutting pattern #2 results in three rolls that are each 3 inches wide (leaving 1 inch of waste on the end). Cutting pattern #3 results in one roll that is 3 inches wide and two rolls that are 3.5 inches wide. Cutting pattern #4 results in one 2.5-inch roll, one 3-inch roll, and one 3.5-inch roll (leaving 1 inch of waste). Cutting pattern #5 results in one roll that is 2.5 inches wide and two rolls that are 3.5 inches wide (leaving 0.5 inch of waste on the end). An order has been received for 2,000 of the 2.5-inch rolls, 4,000 of the 3-inch rolls, and 5,000 of the 3.5-inch rolls. How many rolls should be cut using each pattern if the company wants to minimize the total number of 10-inch rolls used? How many rolls should be cut using each pattern if the company wants to minimize the total waste?

8-22 (Portfolio selection problem) Daniel Grady is the financial advisor for a number of professional athletes. An analysis of the long-term goals for many of these athletes has resulted in a recommendation to purchase stocks with some of the income that they have set aside for investments. Five stocks have been identified as having very favorable expectations for future performance. Although the expected return is important in these investments, the risk, as measured by the beta of the stock, is also important. (A high value of beta indicates that the stock has a relatively high risk.) The expected return and the beta for five stocks are as follows:

Daniel would like to minimize the beta of the stock portfolio (calculated using a weighted average of the amounts put into the different stocks) while maintaining an expected return of at least 11%. Since future conditions may change, Daniel has decided that no more than 35% of the portfolio should be invested in any one stock.

1. Formulate this as a linear program. (Hint: Define each variables as the proportion of the total investment that would be put in that stock. Include a constraint that restricts the sum of these variables to be 1.)

2. Solve this problem. What are the expected return and beta for this portfolio?

8-23 (Airline fuel problem) Coast-to-Coast Airlines is investigating the possibility of reducing the cost of fuel purchases by taking advantage of lower fuel costs in certain cities. Since fuel purchases represent a substantial portion of operating expenses for an airline, it is important that these costs be carefully monitored. However, fuel adds weight to an airplane, and, consequently, excess fuel raises the cost of getting from one city to another. In evaluating one particular flight rotation, a plane begins in Atlanta, flies from Atlanta to Los Angeles, from Los Angeles to Houston, from Houston to New Orleans, and from New Orleans to Atlanta. When the plane arrives in Atlanta, the flight rotation is said to have been completed, and then it starts again. Thus, the fuel on board when the flight arrived in Atlanta must be taken into consideration when the flight begins. Along each leg of this route, there is a minimum and a maximum amount of fuel that may be carried. This and additional information are provided in the table on the following page.

The regular fuel consumption is based on the plane carrying the minimum amount of fuel. If more than this is carried, the amount of fuel consumed is higher. Specifically, for each 1,000 gallons of fuel above the minimum, 5% (or 50 gallons per 1,000 gallons of extra fuel) is lost due to excess fuel consumption. For example, if 25,000 gallons of fuel are on board when the plane takes off from Atlanta, the fuel consumed on this route will be $12+0.05=12.05$ thousand gallons. If 26,000 gallons are on board, the fuel consumed will be increased by 0.05 thousand, for a total of 12.1 thousand gallons.

Formulate this as an LP problem to minimize the cost. How many gallons should be purchased in each city? What is the total cost of this?