Questions

Extra Problems for Chapter 6

CD-355

EXTRA PROBLEMS FOR CHAPTER 6 CD6.1.

Socker Shoes manufactures ‘‘Made in the USA’’ sneakers at plants in Tallahassee, Florida, and Tucson, Arizona. The shoes are shipped weekly in truckloads from each of the two plants to four regional distribution warehouses located in Allentown, Pennsylvania, Gary, Indiana, Houston, Texas, and Riverside, California. Inventory at each warehouse is evaluated on a weekly basis, and forecasts of demands for additional shoes are faxed to Socker Shoe’s management. This information determines the weekly production schedule for each plant and the shipping pattern between the plants and warehouses. During the week of February 14, the following requests were received from the individual warehouses: Warehouse Request Allentown 6000 Gary 8000 Houston 9000 Riverside 15,000 Each plant can produce up to 19,000 pairs of shoes for the week, and production costs for a pair of shoes are the same at each plant. The shoes are shipped via truck in lots of 1000 pairs. The forecasted shipping cost per truckload from each plant to each warehouse is given in the following table.

SHIPPING COST PER TRUCKLOAD To From Tallahassee Tucson

CD6.2.

CD6.3.

Allentown

Gary

Houston

Riverside

$2,500 $3,000

$2,800 $2,900

$2,200 $2,200

$3,500 $1,800

a. For the week of February 14, how many pairs of shoes should be produced in Tallahassee? in Tucson? b. What is Socker Shoes’ minimum cost shipping pattern for the week of February 14? What will be the total shipping cost? Consider the Socker Shoe problem in problem CD6.1. a. What is the largest value for the shipping cost from Tucson to Riverside for which this solution remains optimal? b. Suppose that the maximum weekly production capacity at each plant were 15,000 instead of 19,000. What is the new minimum cost shipping pattern? What are the ramifications of this situation? Do you think this minimum cost solution is tolerable? Explain. c. Suppose that weekly production capacity is 25,000 at Tallahassee and 25,000 at Tucson. What is the new optimal shipping pattern? How should production be scheduled between the two plants? Does this seem practical and sensible from a management point of view? Consider the Socker Shoe problem in problem CD6.1. Suppose Socker decided to locate a plant in Juarez, Mexico, which is also capable of producing 19,000 pairs of shoes per week. (It will therefore change the ‘‘Made in the USA’’ slogan to ‘‘Made in North America.’’) Mexican drivers’ wages and benefits are lower, a factor that has been taken into account in the following estimates of the shipping cost (per truckload) from Juarez to the warehouse distribution centers: To Allentown Gary Houston Riverside From Juarez $2800 $2400 $2000 $1500 a. Suppose a tariff of $2 per pair of shoes from Mexico exists. If this plant were in operation, what is the effect on the production schedule for the week of

CD-356

Additional Problems and Cases

CD6.4.

February 14 given that production costs per shoe are the same for the Juarez plant as for the Tallahassee and Tucson plants? b. Mexican production costs are substantially lower than U.S. costs, for both labor and material. Estimates indicate that overall production costs in Mexico are only 40% of U.S. costs. Currently, it costs roughly $5.00 to produce each pair of sneakers in the United States. Considering both the tariff costs and the savings in production costs, what would be the effect on the production schedule for the week of February 14? c. Suppose that under union contract, Socker Shoe has agreed to produce at least 30,000 pairs of sneakers each week in the United States. Modify your formulation of part (b) and express the results in a transportation format. Solve for the optimal production and shipping schedule for the week of February 14. d. Under the North American Free Trade Agreement (NAFTA), all tariffs between Mexico and the United States will be eliminated. At the same time, Mexican wages should rise. Assume that the increase in driver wages would add $400 per truckload to the figures given above. To what level (in terms of the percentage of U.S. production costs) would Mexican production costs have to rise for there to be no difference between producing all the units in the United States and producing some units in Mexico? TransGlobal Airlines (TGA), based in New York City, is a charter airline with seven pilots. In assigning routes, the most senior pilot chooses first, then the next most senior, and so on. TGA discovered, however, that some pilots had very little preference, while others cared a great deal about which route they were assigned. Hence, a senior pilot sometimes selected a route that a more junior pilot would have preferred, even though the senior pilot was ambivalent about his or her choice. As a result of complaints from some of the junior pilots, TGA is considering implementing a new policy. Each pilot, regardless of seniority, would rate in numerical order his or her five most preferred cities as well as standby and vacation preference. (Each period, one pilot is on standby and another pilot is on vacation.) TGA would then create a schedule that maximizes overall pilot satisfaction (giving the lowest total overall preference value). a. Given the following rankings submitted by the pilots for the current scheduling period, what schedule should be assigned? Route Captain Smith Captain Jones Captain Heinz Captain Chang Captain Wells Captain Blinn Captain Klein

London

Paris

Moscow

Hawaii

Tokyo

Standby

Vacation

1 2 7 2 1 2 5

2 1 2 1 3 3 4

5 7 6 6 7 7 7

3 3 3 4 2 1 3

4 6 4 7 4 6 2

6 4 5 5 6 5 6

7 5 1 3 5 4 1

b. The pilots are listed in order of seniority. Explain why Captain Smith and Captain Jones, the two most senior pilots, are particularly upset with this period’s schedule. CD6.5. Consider the TGA problem in problem CD6.4. When TGA attempted to schedule pilots using the new policy, it found that there can be many options for the total minimal ranked schedule. Furthermore, sometimes the most senior pilots are relegated to routes they truly do not prefer, while more junior pilots receive their first choice. Another problem is that such a ranking procedure does not show the depth of displeasure between one route and the next. For example, Captain Smith may be relatively indifferent to the London and Paris routes, but certainly prefers either to Hawaii (his third choice).

Extra Problems for Chapter 6

CD-357

In an effort to take seniority into account, a young management consultant has suggested another method. Each pilot would receive 10 points for each year of service to distribute in any manner among the five routes, standby, and vacation. Suppose this method yielded the following point scores for this period. Route Captain Smith Captain Jones Captain Heinz Captain Chang Captain Wells Captain Blinn Captain Klein

CD6.6.

London

Paris

Moscow

Hawaii

Tokyo

Standby

Vacation

115 50 0 75 160 0 20

115 150 50 100 0 0 10

0 0 0 0 0 0 10

0 10 50 0 0 80 1

0 0 50 0 0 0 4

0 0 0 0 0 0 3

0 0 50 15 0 0 2

a. Construct a lost opportunity matrix from these points by replacing the numbers in each column by the difference between the numbers and the maximum number in the column. b. Solve the optimal assignment using this approach. c. Why is Captain Smith still unhappy? How could Captain Smith be assured of always getting his first preference using this approach? d. List some other potential pitfalls that might occur using this approach. Suggest other approaches that might be fairer. The Orange County Transportation Commission is planning to develop a road system linking Mission Viejo (City 1) and Fullerton (City 10). Two proposals are under serious consideration: a. A series of six-lane ‘‘superstreets’’ linking all 10 Orange County cities between Mission Viejo and Fullerton. b. A 10-lane freeway extension connecting Mission Viejo with Fullerton (which does not necessarily pass through all 10 cities). Forecasts indicate that either proposal will improve north-south traffic flow through the county and ease traffic congestion on other secondary streets. The proposed transportation corridors are depicted in the following network, including mileages between various Orange County cities. 5

2

5 8

9 6

8

2

8

7

1 12

7

4

11

7 6

3

10

8

2

1

5

5

Mission Viejo

4

9

3

6

8

Fullerton

9

Orange County Transportation Corridors

CD6.7.

Superstreets are estimated to cost taxpayers $500,000 per mile to build, whereas each mile of freeway will cost $700,000. Although many factors should be considered, if total cost is the primary consideration, which system would Orange County taxpayers prefer? The Wichita State University (WSU) baseball team is preparing for the upcoming college world series. It has two games left in the regular season, followed by at least two games in the double elimination world series tournament. WSU has

Additional Problems and Cases already played three of the four teams—Texas (UT), Arizona State (ASU), and Florida State (FSU)—and is very familiar with its other opponent, California State University, Fullerton (CSUF). WSU has four starting pitchers and will start a different one against each team. Based on past performance, the WSU coach has compiled an effectiveness statistic for each pitcher based on the pitcher’s and the opponent team’s strengths and weaknesses. He has used these statistics throughout the year, which may account for his successful 45–12 won–lost record. The effectiveness statistics for these opponents are as follows.

EFFECTIVENESS FACTORS Clyde Rollins Carlos Pascual Sid Thompson Ted Quillici

ASU

FSU

CSUF

62 76 75 45

65 70 40 48

80 82 77 50

50 55 57 36

a. Based on these factors, which pitcher should WSU start against each team to maximize the total overall effectiveness rating? b. Suppose the WSU coach will let a pitcher start up to two games. Modify the problem and solve first as an assignment problem and then as a transportation problem. c. Use the transportation model format to determine the starting pitchers if the WSU coach will allow a pitcher to start as many as three games. During the early 1970s, the political scandal Watergate shook the United States and toppled a presidency. While there were many aspects to the episode (robbery, enemies lists, abuse of power, cover-ups, etc.), a key component was the ‘‘laundering’’ of funds from big money contributors to campaign coffers. This practice consists of channeling a large ‘‘gift’’ of money through various banks and individuals so that its source cannot be traced. Unfortunately, such activities continue today as evidenced by congressional investigations beginning in 1997. Suppose millionaire I. S. Halverson has $5000 (in reality, he would probably have 10 or 100 times this amount) that he would like to donate ‘‘anonymously’’ to the Independent National Party (INP). He might first split the money up in smaller units and deposit the money in several bank accounts spread throughout the world. Money from these accounts could be mixed or further divided and sent to other accounts or individuals, who, in turn, would do the same, until several checks for $1000 or less eventually arrive at party headquarters. To avert suspicion, a limit has been placed on the amount of each transaction between intermediaries. These limits are given in the following network depicting

1500 200

1

6

30 0

4

100

0

00

5

10

0

2

10

100

2000

400

0 10

00

0

I.S. Halverson 25

CD6.8.

UT

20 00

CD-358

200

0

INP 1000

3 Numbers on the arcs represent the maximum amount that can be laundered in either direction.

Extra Problems for Chapter 6

CD6.9.

CD-359

I. S. Halverson, the intermediaries, and the INP. Given these limitations, how much of the $5000 can I. S. Halverson launder to the INP? (Note: The federal government employs management scientists who also use such models to help determine transaction limits that should be monitored.) Luxor Motorhomes has two plants, one in Riverside, California, and the other in Des Moines, Iowa. Each plant can produce three different models: the Grand Cruiser, the Traveler, and the Weekender. Labor time at the Riverside plant limits production to 600 models per month, while the Des Moines plant can produce up to 1000 models per month. The manufacturing costs and monthly production capacities for each model vary, depending on the plant. These costs are summarized in the following table.

MANUFACTURING COSTS AND MAXIMUM MONTHLY PRODUCTION LEVELS Manufacturing Cost Grand Cruiser Traveler Weekender Maximum Monthly Production Grand Cruiser Traveler Weekender

Riverside

Des Moines

$53,000 $29,000 $18,000

$50,000 $27,000 $17,000

200 500 600

400 500 900

Once the units are manufactured, they are shipped to central distribution locations in Florida, Texas, and California, where they are ultimately purchased by retailers. The demand for motorhomes at the distribution locations for this month’s production is as follows.

DEMAND FOR MOTORHOMES Grand Cruiser Traveler Weekender

Florida

Texas

California

100 200 225

50 100 175

150 300 250

The transportation costs for shipping a motorhome from a plant to a distribution center are independent of the model. These are given in the following table.

MOTORHOME SHIPPING COSTS Des Moines Riverside

Florida

Texas

California

$1,000 $2,000

$800 $700

$1,200 $ 300

Formulate this problem as a capacitated transshipment problem and solve for the optimal production and distribution of motorhomes during this month. (Hint: Define a set of nodes for the plants, a set for the models, and a set for the models at the distribution locations.) CD6.10. Thirteen Savage Beasts is a popular rock group that has toured all over North America. It is now beginning its Japanese tour and will be playing to a sold-out house in a major sports stadium in Osaka. After strategically positioning 12 banks of loudspeakers, the manager for the group has found that the local government requires all cables and wires be housed in specially insulated rigid casings. (In the United States, the group simply lays the cables along the ground or across rafters, but this is unacceptable to the Japanese authorities.) A diagram of the stage area and the 12 banks of loudspeakers is shown in the following figure. What is the minimum amount of the insulated casings the group must purchase before the rock concert can proceed? (Note: Loudspeakers may be connected to one another or directly to the stage.)

Additional Problems and Cases 35

1

70

51

47

30

STAGE

5 71

79

60

33

32

3 29

20

42

43

26

4

40

2

49

7

62

6

81

47

75

43

8 62

26

10

9

70

31

77

61

CD-360

44

55

12

11

Distances are in meters

CD6.11. The small rural town of Campton has only one elementary school. Beginning early every morning, a school bus leaves the school, picks up children at five stops, and returns to the school. The following table gives the distances between the stops.

MILES BETWEEN PICKUP POINTS

School Crossroad Willow Creek Jones House Old Highway General Store

Crossroad

Willow Creek

Jones House

6

29 19

24 21 5

Old Highway

General Store

10 20 27 16

25 10 15 26 37

Red Barn 12 8 7 4 11 18

a. What is the minimum total distance the school bus must travel each morning? b. If the school bus averages 30 miles per hour, at what time must the school bus leave the school each morning in order to deliver the children to the school by 7:55 A.M. (5 minutes before school starts)? c. Prepare a bus schedule giving the pickup time at each stop if the bus averages 30 miles per hour. CD6.12. The Campton Elementary School (problem CD6.11) has been concerned about vandalism that has occurred to the school bus while it is parked overnight in the school parking lot. Accordingly, it has found a secure location eight miles from the school, where the bus can be parked overnight. The distances from the bus facility to the pickup sites are as follows. Willow Jones Old General Crossroad Creek House Highway Store Red Barn Bus facility 14 22 20 18 30 17 a. What is the minimum total distance the school bus must travel each morning? (Be sure that the last route traveled is the one from the school back to the bus facility.) b. If the school bus averages 30 miles per hour, at what time must the bus leave the secure location each morning in order to deliver the children to the school by 7:55 A.M. (5 minutes before school starts)? c. Prepare a bus schedule giving the pickup time at each stop if the bus averages 30 miles per hour.

Extra Problems for Chapter 6

CD-361

CD6.13. John Stanford is at the end of a two-year lease on his Lincoln Town Car, and, although he is determined to drive a Lincoln Town Car for the next four years (until his twins go to college), he simply refuses to lease another car, claiming, ‘‘Ownership is the only way.’’ John can either purchase his two-year-old Lincoln or purchase a new one. At the start of any subsequent year, he can trade in his Lincoln for a new one. At the end of the fourth year, however, he will definitely trade in his Lincoln for a Porsche, which he and his wife will share. John would like to determine the optimal purchase/trade-in policy for the next four years. To aid him in his decision process, the salesperson at the LincolnMercury/Porsche dealership (in whom John places complete trust) has given him the following information.

PROJECTED COST OF A NEW LINCOLN TOWN CAR This Year

Year 2

Year 3

Year 4

$40,000

$42,000

$45,000

$50,000

TRADE-IN VALUE OF A LINCOLN TOWN CAR (Percent of original purchase price) Age of Vehicle 1 Year

2 Years

3 Years

4 Years

5 Years

6 Years

70%

50%

34%

20%

10%

5%

YEARLY OPERATING COST Age of Car at the Beginning of the Year New

1 Year

2 Years

3 Years

4 Years

5 Years

$2,000

$3,000

$5,000

$6,000

$9,000

$8,000

The yearly operating costs include insurance, license, and normal repairs and reflect the fact that the first year carries a full warranty, the second year a limited warranty, and in the fifth year (when the car is four years old at the beginning of the year) there is a major 60,000-mile service. Since John has been a valued lease customer, the dealership will allow him to purchase his current two-year-old vehicle (which cost $36,000 new) for the twoyear trade-in price of .50($36,000) 5 $18,000. a. Complete the following shortest path representation of this problem. b. Solve this shortest path problem to determine the optimal purchase/trade-in policy. Operating Cost Age at Beginning of Year 2

4

60

Purchase + Operating Cost

00 ep Ke

Purchase + Operating CostTrade-in

3 31

0 r ,76 Ca w Ne

y Bu

ar

00 ld C ,0 O 23 ar Ye 2 uy

2

B

START

Buy

Year 1

0

0 30

42,00

0

New

Car

1 Year 2

ep Ke 14,000

Buy New Car

1 Year 3

Year 4

Year 5

CD-362

Additional Problems and Cases CD6.14. Topless City is a small chain of car dealerships that sells vintage convertibles throughout the Southern United States. It is owned and managed by Brandon and Kyle Winslow. Each month Brandon and Kyle attend two car auctions, at which they purchase convertibles: one in Atlanta, the other in Miami. The cars are then shipped to one of three locations: Jackson, Mississippi, Birmingham, Alabama, or Orlando, Florida. There, the cars are refurbished, repainted, safety inspected, and sold at the Topless City dealership in that city. In August, Brandon found 20 cars at the Atlanta auction, and Kyle found 50 cars at the Miami auction which met the needs of the company. Only 15 cars can be worked on at each city during the month, however. Another auction is coming up in September; thus, only 45 cars are to be purchased in August. Topless City wishes to minimize its costs of transporting the cars to the refurbishing locations. The cost to transport cars between cities is as follows.

Atlanta Miami

Jackson

Birmingham

Orlando

$200 $250

$100 $200

$175 $125

a. Give a linear programming formulation for this problem. b. Formulate the problem as a transportation problem and solve. c. Do the assumptions of the transportation model appear to be valid for this problem? Comment. CD6.15. Consider the problem faced by Topless City in problem CD6.14. For some time now, Brandon and Kyle have been considering converting their facilities in these three cities to sales lots only and performing all refurbishing operations in other cities. If they do so, they can actually use all 70 cars: 15 in Jackson, 25 in Birmingham, and 30 in Orlando. One plan under consideration is to contract out the painting to shops in Tuscaloosa, Alabama, and Columbus, Georgia, and then transport the cars for mechanical work to shops in Montgomery, Alabama, and Gainesville, Florida, before delivery to a Topless City location. Alternatively, a full-service operation in Jacksonville could handle both the painting and mechanical work. a. Given the following tables, which reflect the average unit transportation costs per vehicle between locations, formulate the problem as a transshipment problem and solve for the optimal shipping patterns. How many cars are painted and fixed mechanically in each location? Explain. To FROM Atlanta Miami

Tuscaloosa

Columbus

Jacksonville

$150 $200

$ 75 $175

$150 $125 To

FROM Tuscaloosa Columbus

Montgomery

Gainesville

$50 $50

$100 $ 75 To

FROM Montgomery Gainesville Jacksonville

Jackson

Birmingham

Orlando

$130 $150 $180

$ 70 $135 $130

$110 $ 45 $ 60

b. After painting and refurbishing the vehicles and deducting other expenses (sales personnel, utilities, etc.), the average gross profit is $x per car. Based

Case CD6.1: The Sandy Company

CD-363

on the August auction figures, what breakeven value of x would justify implementing the new plan of buying and selling all 70 cars, rather than maintaining the current policy of purchasing 45 cars and doing all the work at Topless City locations? c. Solve for the shortest path (in terms of cost) from Atlanta to the Topless City locations; solve for the shortest path from Miami to the Topless City locations. d. Use the results of part (c) to convert the transshipment problem to a transportation problem. Solve and show that the solutions are equivalent to those found in part (a).

CASE CD6.1: The Sandy Company1 pose. The transportation cost per bulldozer is $200 plus $6 per mile from any storage location to any excavation site. The four sites require a total of 21 bulldozers: five at Los Bungalos; six at Buffalo Valley; six at Parker Falls; and four at Upper Lufferton. Thus, the fixed cost, over which the Sandy Company has no control, is $4200 each way (5 21 3 $200). The company must determine the most efficient routes to travel from each of the storage sites to the excavation sites and how many bulldozers it wishes to transport from each storage site to each excavation site. The Sandy Company has 24 bulldozers: eight at Groveton; nine at High Point; and seven at Grand River. The bulldozers must be returned to their original sites. A map detailing the distances between junction points of the construction roads and between the storage sites and the excavation sites follows. Complicating the process is the possibility that the project will not be completed until late Oc-

The Sandy Company is an excavation company located in southwestern Colorado. In recent months, the company has expanded its activities, purchased several new bulldozers, and sought out new contracts. This past week it successfully obtained a contract for a new project to begin on July 15. The contract involves excavation at four separate sites in the area: (1) Los Bungalos, (2) Buffalo Valley, (3) Parker Falls, and (4) Upper Lufferton. A major cost faced by the Sandy Company is the transportation of bulldozers from their sites at the three storage locations of Groveton, High Point, and Grand River along some very narrow construction roads to the excavation sites. The bulldozers will be transported by the Emmons Company using commercial trailers specifically designed for this pur1

This case is based on a problem developed by Dr. Zvi Goldstein, California State University, Fullerton.

Parker Falls

Upper Lufferton

120

15

60

150 30

30

12 0

80

15

10

120

210

15

3

2

4

0 12

18

150

90

60

135

15 0

8

48

7

6

30

18

45

5 45

13

12

11 4 5 24

6 30

0

12

105

3 12

Los Bungalos

1

81

9

1

120

15

15

Groveton High Point Grand River

18

0

Buffalo Valley

36

12

16 2 1

45

14

CD-364

Additional Problems and Cases

tober. By that time snow could make certain roads impassable. In particular, the roads between Grand River and Junction 4, and between Junction 13 and Los Bungalos are very susceptible to closure. In addition, a new 70-mile construction road between Junction 2 and Junction 15 may be open. Prepare a report that includes the following. 1. The minimum cost distribution and transportation plan to the excavation sites under current conditions 2. Given that the bulldozers have been allocated as in (1), a minimum cost return transportation plan under each of the eight possible sets of conditions: Grand River– Junction 4 1. Open 2. Open 3. Open

Junction 13– Los Bungalos Open Open Closed

Junction 2– Junction 15 Closed (Current) Open Closed

4. 5. 6. 7. 8.

Grand River– Junction 4 Open Closed Closed Closed Closed

Junction 13– Los Bungalos Closed Open Open Closed Closed

Junction 2– Junction 15 Open Closed Open Closed Open

3. An analysis of the situation in which Sandy knows in advance that both the Grand River–Junction 4 road and the Junction 13–Los Bungalos road will be closed on the return trip (i.e., suppose the roads automatically close on October 1). Recommend a minimum cost distribution and transportation plan for both the case in which the Junction 2–Junction 15 road is open and the case in which it is closed (cases 7 and 8). (Hint: Since the bulldozers must be returned to their original sites, round-trip mileages must now be considered.)

EXTRA PROBLEMS FOR CHAPTER 7 CD7.1.

St. Paul’s Episcopal Church has a parking lot in need of repair. It has determined that these repairs will cost around $150,000, although formal bids have not yet been solicited from construction companies. The clergy has determined that the following set of activities make up the project. Activity A: B: C: D: E: F: G:

CD7.2.

Immediate Predecessors

Inform congregation of upcoming project Solicit funds in church and newsletter Obtain bids Do volunteer parking lot preparation work Solicit by telephone Borrow remaining funds Choose company and have work performed

— A A C C B, D, E F

Draw an activity on node representation of this project. George Washington High School is planning a reunion for the graduating class of 1975. The D’Onofrio twins, who are in charge of planning the entire event, have determined the following tasks. Immediate Time Estimates (Days) Tasks A: Determine current addresses of graduates B: Determine a budget C: Choose a site D: Hire a band E: Design commemorative sweatshirts F: Write/mail announcements G: Hire a photographer H: Determine excess funds I: Buy door prizes

CD7.3.

Predecessors

Best

Probable

Worse

— — B B — A, C B D, F, G E, H

20 3 10 5 10 8 3 32 2

25 5 14 14 10 14 4 40 5

50 12 21 18 14 25 7 50 8

What is the probability that the D’Onofrio twins will have to commit more than three months (90 days) to this project? Keith Littlefield is a racecar driver on the NASCAR circuit. He has promised to participate in the Pocono 300, to be held 15 weeks from now. In order to be