Schank marketing research case study solution

DISCUSSION QUESTIONS AND PROBLEMS 419

Discussion Questions and Problems

Discussion Questions 10-1 Compare the similarities and differences of linear

and goal programming.

10-2 A linear programming problem was developed, and the feasible region was found. If the additional re- striction that all variables must be integers were added to the problem, how would the size of the fea- sible region change? How would the optimal value of the objective function change?

10-3 List the advantages and disadvantages of solving inte- ger programming problems by (a) rounding off and (b) enumeration.

10-4 What is the difference between the three types of integer programming problems? Which do you think is most common, and why?

10-5 What is meant by “satisficing,” and why is the term often used in conjunction with goal programming?

10-6 What are deviational variables? How do they differ from decision variables in traditional LP problems?

Self-Test

� Before taking the self-test, refer to the learning objectives at the beginning of the chapter, the notes in the margins, and the glossary at the end of the chapter.

� Use the key at the back of the book to correct your answers. � Restudy pages that correspond to any questions that you answered incorrectly or material you feel uncertain about.

7. Nobel Laureate Herbert A. Simon of Carnegie-Mellon University says that modern managers should always op- timize, not satisfice. a. True b. False

8. The fixed charge problem is typically classified as a. a goal programming problem. b. a 0–1 integer problem. c. a quadratic programming problem. d. an assignment problem.

9. The 0–1 integer programming problem a. requires the decision variables to have values between

0 and 1. b. requires that the constraints all have coefficients

between 0 and 1. c. requires that the decision variables have coefficients

between 0 and 1. d. requires the decision variables to be equal to 0 or 1.

10. Goal programming a. requires only that you know whether the goal is direct

profit maximization or cost minimization. b. allows you to have multiple goals. c. is an algorithm with the goal of a quicker solution to

the pure integer programming problem. d. is an algorithm with the goal of a quicker solution to

the mixed-integer programming problem. 11. Nonlinear programming includes problems

a. in which the objective function is linear but some constraints are not linear.

b. in which the constraints are linear but the objective function is not linear.

c. in which both the objective function and all of the con- straints are not linear.

d. solvable by quadratic programming. e. all of the above.

1. If all of the decision variables require integer solutions, the problem is a. a pure integer programming type of problem. b. a simplex method type of problem. c. a mixed-integer programming type of problem. d. a Gorsky type of problem.

2. In a mixed-integer programming problem a. some integers must be even and others must be odd. b. some decision variables must require integer results

only and some variables must allow for continuous results.

c. different objectives are mixed together even though they sometimes have relative priorities established.

3. A model containing a linear objective function and linear constraints but requiring that one or more of the decision variables take on an integer value in the final solution is called a. an integer programming problem. b. a goal programming problem. c. a nonlinear programming problem. d. a multiple objective LP problem.

4. An integer programming solution can never produce a greater profit than the LP solution to the same problem. a. True b. False

5. In goal programming, if all the goals are achieved, the value of the objective function will always be zero. a. True b. False

6. The objective in a goal programming problem with one priority level is to maximize the sum of the deviational variables. a. True b. False

420 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING

10-7 If you were the president of the college you are attending and were employing goal programming to assist in decision making, what might your goals be? What kinds of constraints would you include in your model?

10-8 What does it mean to rank goals in goal program- ming? How does this affect the problem’s solution?

10-9 Which of the following are NLP problems, and why?

(a)

(b)

(c)

(d)

(e)

Are any of these quadratic programming problems?

Problems* 10-10 Elizabeth Bailey is the owner and general manager of

Princess Brides, which provides a wedding planning service in Southwest Louisiana. She uses radio adver- tising to market her business. Two types of ads are available—those during prime time hours and those at other times. Each prime time ad costs $390 and reaches 8,200 people, while the offpeak ads each cost $240 and reach 5,100 people. Bailey has budgeted $1,800 per week for advertising. Based on comments from her customers, Bailey wants to have at least 2 prime time ads and no more than 6 off peak ads. (a) Formulate this as a linear program. (b) Find a good or optimal integer solution part (a)

by rounding off or making an educated guess at the answer.

(c) Solve this as an integer programming problem using a computer.

X1 + X2 Ú 18 subject to 4X1 - 3X2 Ú 8 Minimize cost = 18X1 + 5X2 + X22

3X1 + 4X2 Ú 12 subject to X12 - 5X2 Ú 8 Maximize profit = 3X1 + 4X2

X1 + d3- - d3+ = 100 X2 + d2- - d2+ = 200

subject to X1 + X2 + d1- - d1+ = 300 Maximize Z = P1d1- + P2d2+ + P3+

0.0005X1 - X2 = 11 X1 + X2 Ú 12

subject to X1 Ú 8 Maximize cost = 25X1 + 30X2 + 8X1X2

X3 Ú 18 X2 … 5

subject to X1 Ú 10 Maximize profit = 3X1 + 5X2 + 99X3

10-11 A group of college students is planning a camping trip during the upcoming break. The group must hike several miles through the woods to get to the campsite, and anything that is needed on this trip must be packed in a knapsack and carried to the campsite. One particular student, Tina Shawl, has identified eight items that she would like to take on the trip, but the combined weight is too great to take all of them. She has decided to rate the utility of each item on a scale of 1 to 100, with 100 being the most beneficial. The item weights in pounds and their utility values are given below.

ITEM 1 2 3 4 5 6 7 8

WEIGHT 8 1 7 6 3 12 5 14

UTILITY 80 20 50 55 50 75 30 70

Recognizing that the hike to the campsite is a long one, a limit of 35 pounds has been set as the maxi- mum total weight of the items to be carried. (a) Formulate this as a 0–1 programming problem to

maximize the total utility of the items carried. Solve this knapsack problem using a computer.

(b) Suppose item number 3 is an extra battery pack, which may be used with several of the other items. Tina has decided that she will only take item number 5, a CD player, if she also takes item number 3. On the other hand, if she takes item number 3, she may or may not take item number 5. Modify this problem to reflect this and solve the new problem.

10-12 Student Enterprises sells two sizes of wall posters, a large 3- by 4-foot poster and a smaller 2- by 3-foot poster. The profit earned from the sale of each large poster is $3; each smaller poster earns $2. The firm, although profitable, is not large; it consists of one art student, Jan Meising, at the University of Kentucky. Because of her classroom schedule, Jan has the fol- lowing weekly constraints: (1) up to three large posters can be sold, (2) up to five smaller posters can be sold, (3) up to 10 hours can be spent on posters during the week, with each large poster requiring 2 hours of work and each small one taking 1 hour. With the semester almost over, Jan plans on taking a three-month summer vacation to England and doesn’t want to leave any unfinished posters behind. Find the integer solution that will maximize her profit.

10-13 An airline owns an aging fleet of Boeing 737 jet air- planes. It is considering a major purchase of up to 17 new Boeing model 757 and 767 jets. The decision must take into account numerous cost and capability factors, including the following: (1) the airline can

Note: means the problem may be solved with QM for Windows; means the problem may be

solved with Excel; and means the problem may be solved with QM for Windows and/or Excel.

DISCUSSION QUESTIONS AND PROBLEMS 421

finance up to $1.6 billion in purchases; (2) each Boeing 757 will cost $80 million, and each Boeing 767 will cost $110 million; (3) at least one-third of the planes purchased should be the longer-range 757; (4) the annual maintenance budget is to be no more than $8 million; (5) the annual maintenance cost per 757 is estimated to be $800,000, and it is $500,000 for each 767 purchased; and (6) each 757 can carry 125,000 passengers per year, whereas each 767 can fly 81,000 passengers annually. Formulate this as an integer programming problem to maxi- mize the annual passenger-carrying capability. What category of integer programming problem is this? Solve this problem.

10-14 Trapeze Investments is a venture capital firm that is currently evaluating six different investment oppor- tunities. There is not sufficient capital to invest in all of these, but more than one will be selected. A 0–1 integer programming model is planned to help determine which of the six opportunities to choose. Variables represent the six choices. For each of the following situations, write a constraint (or several constraints) that would be used. (a) At least 3 of these choices are to be selected. (b) Either investment 1 or investment 4 must be

undertaken, but not both. (c) If investment 4 is selected, then investment

6 must also be selected. However, if investment 4 is not selected, it is still possible to select num- ber 6.

(d) Investment 5 cannot be selected unless both in- vestments 2 and 3 are also selected.

(e) Investment 5 must be selected if both invest- ments 2 and 3 are also selected.

10-15 Horizon Wireless, a cellular telephone company, is expanding into a new era. Relay towers are neces- sary to provide wireless telephone coverage to the different areas of the city. A grid is superimposed on a map of the city to help determine where the towers should be located. The grid consists of 8 areas labeled A through H. Six possible tower locations (numbered 1–6) have been identified, and each loca- tion could serve several areas. The table below indi- cates the areas served by each of the towers.

X1, X2, X3, X4, X5, and X6

Innis has identified eight potential locations to con- struct new single-family dwellings, but he cannot put up homes on all of the sites because he has only $300,000 to invest in all projects. The accompany- ing table shows the cost of constructing homes in each area and the expected profit to be made from the sale of each home. Note that the home-building costs differ considerably due to lot costs, site prepa- ration, and differences in the models to be built. Note also that a fraction of a home cannot be built.

TOWER LOCATION 1 2 3 4 5 6

AREAS SERVED A, B, D B, C, G C, D, E, F E, F, H E, G, H A, D, F

Formulate this as a 0–1 programming model to min- imize the total number of towers required to cover all the areas. Solve this using a computer.

10-16 Innis Construction Company specializes in building moderately priced homes in Cincinnati, Ohio. Tom

COST OF BUILDING EXPECTED PROFIT LOCATION AT THIS SITE ($) ($)

Clifton 60,000 5,000

Mt. Auburn 50,000 6,000

Mt. Adams 82,000 10,000

Amberly 103,000 12,000

Norwood 50,000 8,000

Covington 41,000 3,000

Roselawn 80,000 9,000

Eden Park 69,000 10,000

(a) Formulate Innis’s problem using 0–1 integer programming.

(b) Solve with QM for Windows or Excel.

10-17 A real estate developer is considering three possible projects: a small apartment complex, a small shop- ping center, and a mini-warehouse. Each of these re- quires different funding over the next two years, and the net present value of the investments also varies. The following table provides the required invest- ment amounts (in $1,000s) and the net present value (NPV) of each (also expressed in $1,000s):

INVESTMENT

NPV YEAR 1 YEAR 2

Apartment 18 40 30

Shopping center 15 30 20

Mini-warehouse 14 20 20

The company has $80,000 to invest in year 1 and $50,000 to invest in year 2. (a) Develop an integer programming model to max-

imize the NPV in this situation. (b) Solve the problem in part (a) using computer

software. Which of the three projects would be undertaken if NPV is maximized? How much money would be used each year?

10-18 Refer to the real estate investment situation in Prob- lem 10-17. (a) Suppose that the shopping center and the apart-

ment would be on adjacent properties, and the

422 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING

shopping center would only be considered if the apartment were also built. Formulate the con- straint that would stipulate this.

(b) Formulate a constraint that would force exactly two of the three projects to be undertaken.

10-19 Triangle Utilities provides electricity for three cities. The company has four electric generators that are used to provide electricity. The main generator oper- ates 24 hours per day, with an occasional shutdown for routine maintenance. Three other generators (1, 2, and 3) are available to provide additional power when needed. A startup cost is incurred each time one of these generators is started. The startup costs are $6,000 for 1, $5,000 for 2, and $4,000 for 3. These generators are used in the following ways: A generator may be started at 6:00 A.M. and run for either 8 hours or 16 hours, or it may be started at 2:00 P.M. and run for 8 hours (until 10:00 P.M.). All generators except the main generator are shut down at 10:00 P.M. Forecasts indicate the need for 3,200 megawatts more than provided by the main genera- tor before 2:00 P.M., and this need goes up to 5,700 megawatts between 2:00 and 10:00 P.M. Generator 1 may provide up to 2,400 megawatts, generator 2 may provide up to 2,100 megawatts, and generator 3 may provide up to 3,300 megawatts. The cost per megawatt used per eight hour period is $8 for 1, $9 for 2, and $7 for 3. (a) Formulate this problem as an integer program-

ming problem to determine the least-cost way to meet the needs of the area.

(b) Solve using computer software.

10-20 The campaign manager for a politician who is run- ning for reelection to a political office is planning the campaign. Four ways to advertise have been se- lected: TV ads, radio ads, billboards, and newspaper ads. The cost of these are $900 for each TV ad, $500 for each radio ad, $600 for a billboard for one month, and $180 for each newspaper ad. The audi- ence reached by each type of advertising has been estimated to be 40,000 for each TV ad, 32,000 for each radio ad, 34,000 for each billboard, and 17,000 for each newspaper ad. The total monthly advertis- ing budget is $16,000. The following goals have been established and ranked:

1. The number of people reached should be at least 1,500,000.

2. The total monthly advertising budget should not be exceeded.

3. Together, the number of ads on either TV or radio should be at least 6.

4. No more than 10 ads of any one type of ad- vertising should be used.

(a) Formulate this as a goal programming problem. (b) Solve this using computer software. (c) Which goals are completely met and which of

them are not?

10-21 Geraldine Shawhan is president of Shawhan File Works, a firm that manufactures two types of metal file cabinets. The demand for her two-drawer model is up to 600 cabinets per week; demand for a three- drawer cabinet is limited to 400 per week. Shawhan File Works has a weekly operating capacity of 1,300 hours, with the two-drawer cabinet taking 1 hour to produce and the three-drawer cabinet requiring 2 hours. Each two-drawer model sold yields a $10 profit, and the profit for the large model is $15. Shawhan has listed the following goals in order of importance:

1. Attain a profit as close to $11,000 as possi- ble each week.

2. Avoid underutilization of the firm’s produc- tion capacity.

3. Sell as many two- and three-drawer cabinets as the demand indicates.

Set this up as a goal programming problem.

10-22 Solve Problem 10-21. Are any goals unachieved in this solution? Explain.

10-23 Hilliard Electronics produces specially coded com- puter chips for laser surgery in 64MB, 256MB, and 512MB sizes. (1MB means that the chip holds 1 mil- lion bytes of information.) To produce a 64MB chip requires 8 hours of labor, a 256MB chip takes 13 hours, and a 512MB chip requires 16 hours. Hilliard’s monthly production capacity is 1,200 hours. Mr. Blank, the firm’s sales manager, esti- mates that the maximum monthly sales of the 64MB, 256MB, and 512MB chips are 40, 50, and 60, respectively. The company has the following goals (ranked in order from most important to least important):

1. Fill an order from the best customer for thirty 64MB chips and thirty-five 256MB chips.

2. Provide sufficient chips to at least equal the sales estimates set by Mr. Blank.

3. Avoid underutilization of the production capacity.

Formulate this problem using goal programming.

10-24 An Oklahoma manufacturer makes two products: speaker telephones and pushbutton telephones

. The following goal programming model has been formulated to find the number of each to pro- duce each day to meet the firm’s goals:

Find the optimal solution using a computer.

10-25 Major Bill Bligh, director of the Army War Col- lege’s new 6-month attaché training program, is

all Xi, di Ú 0 8X1 + 6X2 + d3- - d3+ = 240 8X1 + 10X2 + d2- - d2+ = 320

subject to 2X1 + 4X2 + d1- - d1+ = 80 Minimize P1d1- + P2d2- + P3d3+ + P4d1+

1X22 1X12

DISCUSSION QUESTIONS AND PROBLEMS 423

concerned about how the 20 officers taking the course spend their precious time while in his charge. Major Bligh recognizes that there are 168 hours per week and thinks that his students have been using them rather inefficiently. Bligh lets

He thinks that students should study 30 hours a week to have time to absorb material. This is his most im- portant goal. Bligh feels that students need at most 7 hours sleep per night on average and that this goal is number 2. He believes that goal number 3 is to pro- vide at least 20 hours per week of social time. (a) Formulate this as a goal programming problem. (b) Solve the problem using computer software.

10-26 Mick Garcia, a certified financial planner (CFP) has been asked by a client to invest $250,000. This money may be placed in stocks, bonds, or a mutual fund in real estate. The expected return on investment is 13% for stocks, 8% for bonds, and 10% for real estate. While the client would like a very high expected re- turn, she would be satisfied with a 10% expected re- turn on her money. Due to risk considerations, several goals have been established to keep the risk at an ac- ceptable level. One goal is to put at least 30% of the money in bonds. Another goal is that the amount of money in real estate should not exceed 50% of the money invested in stocks and bonds combined. In ad- dition to these goals, there is one absolute restriction. Under no circumstances should more than $150,000 be invested in any one area. (a) Formulate this as a goal programming problem.

Assume that all of the goals are equally important. (b) Use any available software to solve this problem.

How much money should be put in each of the investment options? What is the total return? Which of the goals are not met?

10-27 Hinkel Rotary Engine, Ltd., produces four- and six- cylinder models of automobile engines. The firm’s profit for each four-cylinder engine sold during its quarterly production cycle is , where is the number sold. Hinkel makes

for each of the larger engines sold, with equal to the number of six-cylinder engines sold. There are 5,000 hours of production time avail- able during each production cycle. A four-cylinder engine requires 100 hours of production time, whereas six-cylinder engines take 130 hours to man- ufacture. Formulate this production planning prob- lem for Hinkel.

10-28 Motorcross of Wisconsin produces two models of snowmobiles, the XJ6 and the XJ8. In any given

X2

$2,400 - $70X2 X1

$1,800 - $50X1

1dating, sports, family visits, and so on2X4 = number of hours of social time off base X3 = number of hours of class and studying

hygiene, handling laundary, and so on2X2 = number of personal hours 1eating, personal X1 = number of hours of sleep needed per week

production-planning week Motorcross has 40 hours available in its final testing bay. Each XJ6 requires 1 hour to test and each XJ8 takes 2 hours. The revenue (in $1,000s) for the firm is nonlinear and is stated as (Number of XJ6s)(4 � 0.1 number of XJ6s) + (Number of XJ8s)(5 � 0.2 number of XJ8s). (a) Formulate this problem. (b) Solve using Excel.

10-29 During the busiest season of the year, Green-Gro Fertilizer produces two types of fertilizers. The stan- dard type (X) is just fertilizer, and the other type (Y) is a special fertilizer and weed-killer combination. The following model has been developed to deter- mine how much of each type should be produced to maximize profit subject to a labor constraint:

Find the optimal solution to this problem.

10-30 Pat McCormack, a financial advisor for Investors R Us, is evaluating two stocks in a particular industry. He wants to minimize the variance of a portfolio consisting of these two stocks, but he wants to have an expected return of at least 9%. After obtaining historical data on the variance and returns, he devel- ops the following nonlinear program:

where

Solve this using Excel and determine how much to in- vest in each of the two stocks. What is the return for this portfolio? What is the variance of this portfolio?

10-31 Summertime Tees sells two very popular styles of embroidered shirts in southern Florida: a tank top and a regular T-shirt. The cost of the tank top is $6, and the cost of the T-shirt is $8. The demand for these is sensitive to the price, and historical data in- dicate that the weekly demands are given by

where

P2 = price for regular T-shirt

X1 = demand for regular T-shirt

P1 = price for tank top

X1 = demand for tank top

X2 = 400 - 15P2

X1 = 500 - 12P1

Y = proportion of money invested in stock 2 X = proportion of money invested in stock 1

X, Y Ú 0 investment2 0.11X + 0.08Y Ú 0.09 1return on the be invested2 subject to X + Y = 1 1all funds must

Minimize portfolio variance = 0.16X2 + 0.2XY + 0.09Y2

X, Y Ú 0 subject to 2X + 4Y … 160 hours Maximize profit = 12X - 0.04X2 + 15Y - 0.06Y2

424 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING

(a) Develop an equation for the total profit. (b) Use Excel to find the optimal solution to the fol-

lowing nonlinear program. Use the profit func- tion developed in part (a).

10-32 The integer programming problem in the box below has been developed to help First National Bank decide where, out of 10 possible sites, to locate four new branch offices:

where Xi represents Winter Park, Maitland, Osceola, Downtown, South Orlando, Airport, Winter Garden, Apopka, Lake Mary, Cocoa Beach, for i equals 1 to 10, respectively. (a) Where should the four new sites be located, and

what will be the expected return? (b) If at least one new branch must be opened in Mait-

land or Osceola, will this change the answers? Add the new constraint and rerun.

X1, P1, X2, P2 Ú 0 P2 … 25 P1 … 20 X2 = 400 - 15P2

subject to X1 = 500 - 12P1 Maximize profit

(c) The expected return at Apopka was overesti- mated. The correct value is $160,000 per year (that is, 160). Using the original assumptions (namely, ignoring (b)), does your answer to part (a) change?

10-33 In Solved Problem 10-3, nonlinear programming was used to find the best value for the smoothing constant, �, in an exponential smoothing forecasting problem. To see how much the MAD can vary due to the selection of the smoothing constant, use Excel and the data in Program 10.13A to find the value of the smoothing constant that would maximize the MAD. Compare this MAD to the minimum MAD found in the solved problem.

10-34 Using the data in Solved Problem 10-3, develop a spreadsheet for a 2-period weighted moving average forecast with weights of 0.6 (w1) for the most recent period and 0.4 (w2) for the other period. Note these weights sum to 1, so the forecast is simply

Find the weights for this 2-period weighted moving average that would minimize the MAD. (Hint: The weights must sum to 1.)

current period2 + w21Value in last period2 Forecast for next period = w11Value in

IP for Problem 10-32

subject to

= 120X1 + 100X2 + 110X3 + 140X4 + 155X5 + 128X6 + 145X7 + 190X8 + 170X9 + 150X10Maximize expected returns

all Xi = 0 or 1 X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10 … 4 X1 + X3 + X10 Ú 1

X2 + X3 + X5 + X8 + X9 Ú 2 X2 + X6 + X7 + X9 + X10 … 3

15X1 + 5X2 + 20X3 + 20X4 + 5X5 + 5X6 + 10X7 + 20X8 + 5X9 + 20X10 … 50 20X1 + 30X2 + 20X3 + 25X4 + 30X5 + 30X6 + 25X7 + 20X8 + 25X9 + 30X10 … 110

See our Internet home page, at www.pearsonhighered.com/render, for additional home- work problems 10-35 to 10-40.

INTERNET HOMEWORK PROBLEMS

CASE STUDY 425

Case Study

Schank Marketing Research

Schank Marketing Research has just signed contracts to con- duct studies for four clients. At present, three project managers are free for assignment to the tasks. Although all are capable of handling each assignment, the times and costs to complete the studies depend on the experience and knowledge of each man- ager. Using his judgment, John Schank, the president, has been able to establish a cost for each possible assignment. These costs, which are really the salaries each manager would draw on each task, are summarized in the following table.

Schank is very hesitant about neglecting NASA, which has been an important customer in the past. (NASA has employed the firm to study the public’s attitude toward the Space Shuttle and proposed Space Station.) In addition, Schank has promised to try to provide Ruth a salary of at least $3,000 on his next as- signment. From previous contracts, Schank also knows that Gardener does not get along well with the management at CBT Television, so he hopes to avoid assigning her to CBT. Finally, as Hines Corporation is also an old and valued client, Schank

feels that it is twice as important to assign a project manager im- mediately to Hines’s task as it is to provide one to General Foundry, a brand-new client. Schank wants to minimize the to- tal costs of all projects while considering each of these goals. He feels that all of these goals are important, but if he had to rank them, he would put his concern about NASA first, his worry about Gardener second, his need to keep Hines Corpora- tion happy third, his promise to Ruth fourth, and his concern about minimizing all costs last.

Each project manager can handle, at most, one new client.

Discussion Questions 1. If Schank were not concerned about noncost goals, how

would he formulate this problem so that it could be solved quantitatively?

2. Develop a formulation that will incorporate all five objectives.

CLIENT

PROJECT MANAGER HINES CORP. NASA GENERAL FOUNDRY CBT TELEVISION

Gardener $3,200 $3,000 $2,800 $2,900

Ruth 2,700 3,200 3,000 3,100

Hardgraves 1,900 2,100 3,300 2,100

Case Study

Oakton River Bridge

The Oakton River had long been considered an impediment to the development of a certain medium-sized metropolitan area in the southeast. Lying to the east of the city, the river made it difficult for people living on its eastern bank to com- mute to jobs in and around the city and to take advantage of the shopping and cultural attractions that the city had to offer. Similarly, the river inhibited those on its western bank from access to the ocean resorts lying one hour to the east. The bridge over the Oakton River had been built prior to World War II and was grossly inadequate to handle the existing traf- fic, much less the increased traffic that would accompany the forecasted growth in the area. A congressional delegation

from the state prevailed upon the federal government to fund a major portion of a new toll bridge over the Oakton River and the state legislature appropriated the rest of the needed monies for the project.

Progress in construction of the bridge has been in accor- dance with what was anticipated at the start of construction. The state highway commission, which will have operational jurisdiction over the bridge, has concluded that the opening of the bridge for traffic is likely to take place at the beginning of the next summer, as scheduled. A personnel task force has been established to recruit, train, and schedule the workers needed to operate the toll facility.

426 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING

The personnel task force is well aware of the budgetary problems facing the state. They have taken as part of their man- date the requirement that personnel costs be kept as low as pos- sible. One particular area of concern is the number of toll collectors that will be needed. The bridge is scheduling three shifts of collectors: shift A from midnight to 8 A.M., shift B from 8 A.M. to 4 P.M., and shift C from 4 P.M. to midnight. Recently, the state employees union negotiated a contract with the state which requires that all toll collectors be permanent, full-time employees. In addition, all collectors must work a five-on, two-off schedule on the same shift. Thus, for example, a worker could be assigned to work Tuesday, Wednesday, Thursday, Friday, and Saturday on shift A, followed by Sunday and Monday off. An employee could not be scheduled to work, say, Tuesday on shift A followed by Wednesday, Thursday, Fri- day, and Saturday on shift B or on any other mixture of shifts during a 5-day block. The employees would choose their as- signments in order of their seniority.

The task force has received projections of traffic flow on the bridge by day and hour. These projections are based on ex- trapolations of existing traffic patterns—the pattern of commut- ing, shopping, and beach traffic currently experienced with growth projections factored in. Standards data from other state- operated toll facilities have allowed the task force to convert these traffic flows into toll collector requirements, that is, the minimum number of collectors required per shift, per day, to handle the anticipated traffic load. These toll collector require- ments are summarized in the following table:

The numbers in the table include one or two extra collec- tors per shift to fill in for collectors who call in sick and to pro- vide relief for collectors on their scheduled breaks. Note that each of the eight collectors needed for shift A on Sunday, for example, could have come from any of the A shifts scheduled to begin on Wednesday, Thursday, Friday, Saturday, or Sunday.

Discussion Questions 1. Determine the minimum number of toll collectors that

would have to be hired to meet the requirements ex- pressed in the table.

2. The union had indicated that it might lift its opposition to the mixing of shifts in a 5-day block in exchange for addi- tional compensation and benefits. By how much could the number of toll collectors required be reduced if this is done?

Source: Based on B. Render, R. M. Stair, and I. Greenberg. Cases and Readings in Management Science, 2nd ed., 1990, pp. 55–56. Reprinted by permission of Pren- tice Hall, Upper Saddle River, NJ.

SHIFT SUN. MON. TUE. WED. THU. FRI. SAT.

A 8 13 12 12 13 13 15

B 10 10 10 10 10 13 15

C 15 13 13 12 12 13 8

Minimum Number of Toll Collectors Required per Shift

Bibliography Aköz, Onur, and Dobrila Petrovic. “A Fuzzy Goal Programming Method with

Imprecise Goal Hierarchy,” European Journal of Operational Research 181, 3 (September 2007): 1427–1433.

Araz, Ceyhun, Pinar Mizrak Ozfirat, and Irem Ozkarahan. “An Integrated Multicriteria Decision-Making Methodology for Outsourcing Manage- ment,” Computers & Operations Research 34, 12 (December 2007): 3738–3756.

Bertsimas, Dimitris, Christopher Darnell, and Robert Soucy. “Portfolio Con- struction through Mixed-Integer Programming at Grantham, Mayo, Van Otterloo and Company,” Interfaces 29, 1 (January 1999): 49–66.

Chang, Ching-Ter. “Multi-Choice Goal Programming,” Omega 25, 4 (August 2007): 389–396.

Charnes, A., and W. W. Cooper. Management Models and Industrial Applica- tions of Linear Programming, Vols. I and II. New York: John Wiley & Sons, Inc.1961.

Dawid, Herbert, Johannes Konig, and Christine Strauss. “An Enhanced Ros- tering Model for Airline Crews,” Computers and Operations Research 28, 7 (June 2001): 671–688.

Drees, Lawrence David, and Wilbert E. Wilhelm. “Scheduling Experiments on a Nuclear Reactor Using Mixed Integer Programming,” Computers and Operations Research 28, 10 (September 2001): 1013–1037.

Hueter, Jackie, and William Swart. “An Integrated Labor-Management System for Taco Bell,” Interfaces 28, 1 (January–February 1998): 75–91.

Ignizio, James P. Introduction to Linear Goal Programming. Beverly Hills: Sage Publications, 1985.

Katok, Elena, and Dennis Ott. “Using Mixed-Integer Programming to Reduce Label Changes in the Coors Aluminum Can Plant,” Interfaces 30, 2 (March 2000): 1–12.

Land, Alisa, and Susan Powell. “A Survey of the Operational Use of ILP Models,” Annals of Operations Research 149, 1 (2007): 147–156.

Lee, Sang M., and Marc J. Schniederjans. “A Multicriterial Assignment Prob- lem: A Goal Programming Approach, ”Interfaces 13, 4 (August 1983): 75–79.