M8-13 The management of the Executive Furniture Corporation decided to expand the production capacity at its Des Moines factory and to cut back production at its other factories. It also recognizes a shifting market for its desks and revises the requirements at its three warehouses. (See the data table on the previous page.)

Table for Problem M8-13

1. Use the northwest corner rule to establish an initial feasible shipping schedule and calculate its cost. (See the transportation table on the previous page.)

2. Use the stepping-stone method to test whether an improved solution is possible.

3. Explain the meaning and implications of an improvement index that is equal to 0. What decisions might management make with this information? Exactly how is the final solution affected?

M8-14 The Hardrock Concrete Company has plants in three locations and is currently working on three major construction projects, each located at a different site. The shipping costs per truckload of concrete, daily plant capacities, and daily project requirements are provided in the table on this page.

1. Formulate an initial feasible solution to Hard-rock’s transportation problem using the northwest corner rule. Then evaluate each unused shipping route by computing all improvement indices. Is this solution optimal? Why?

2. Is there more than one optimal solution to this problem? Why?

M8-15 Hardrock Concrete’s owner has decided to increase the capacity at his smallest plant (see Problem M8-14). Instead of producing 30 loads of concrete per day at plant 3, that plant’s capacity is doubled to 60 loads. Find the new optimal solution using the northwest corner rule and stepping-stone method. How has changing the third plant’s capacity altered the optimal shipping assignment? Discuss the concepts of degeneracy and multiple optimal solutions with regard to this problem.

M8-16 The Saussy Lumber Company ships pine flooring to three building supply houses from its mills in Pineville, Oak Ridge, and Mapletown. Determine the best transportation schedule for the data given in the table on this page. Use the northwest corner rule and the stepping-stone method.

M8-17 The Krampf Lines Railway Company specializes in coal handling. On Friday, April 13, Krampf had empty cars at the following towns in the quantities indicated:

By Monday, April 16, the following towns will need coal cars as follows:

Table for Problem M8-17

M8-18 An air conditioning manufacturer produces room air conditioners at plants in Houston, Phoenix, and Memphis. These are sent to regional distributors in Dallas, Atlanta, and Denver. The shipping costs vary, and the company would like to find the least-cost way to meet the demands at each of the distribution centers. Dallas needs to receive 800 air conditioners per month, Atlanta needs 600, and Denver needs 200. Houston has 850 air conditioners available each month, Phoenix has 650, and Memphis has 300. The shipping cost per unit from Houston to Dallas is $8, to Atlanta is $12, and to Denver is $10. The cost per unit from Phoenix to Dallas is $10, to Atlanta is $14, and to Denver is $9. The cost per unit from Memphis to Dallas is $11, to Atlanta is $8, and to Denver is $12. How many units should be shipped from each plant to each regional distribution center? What is the total cost for this?

M8-19 Finnish Furniture manufactures tables in facilities located in three cities—Reno, Denver, and Pittsburgh. The tables are then shipped to three retail stores located in Phoenix, Cleveland, and Chicago. Management wishes to develop a distribution schedule that will meet the demands at the lowest possible cost. The shipping cost per unit from each of the sources to each of the destinations is shown in the following table:

The available supplies are 120 units from Reno, 200 units from Denver, and 160 units from Pittsburgh. Phoenix has a demand of 140 units, Cleveland has a demand of 160 units, and Chicago has a demand of 180 units. How many units should be shipped from each manufacturing facility to each of the retail stores if cost is to be minimized? What is the total cost?

M8-20 Finnish Furniture has experienced a decrease in the demand for tables in Chicago; the demand has fallen to 150 units (see Problem M8-19). What special condition would exist? What is the minimum-cost solution? Will there be any units remaining at any of the manufacturing facilities?

M8-21 Consider the transportation table on this page. Find an initial solution using the northwest corner rule. What special condition exists? Explain how you will proceed to solve the problem.

M8-22 The B. Hall Real Estate Investment Corporation has identified four small apartment buildings in which it would like to invest. Mrs. Hall has approached three savings and loan companies regarding financing. Because Hall has been a good client in the past and has maintained a high credit rating in the community, each savings and loan company is willing to consider providing all or part of the mortgage loan needed on each property. Each loan officer has set differing interest rates on each property (rates are affected by the neighborhood of the apartment building, condition of the property, and desire by the individual savings and loan to finance various-size buildings), and each loan company has placed a maximum credit ceiling on how much it will lend Hall in total. This information is summarized in the table on this page.

Each apartment building is equally attractive as an investment to Hall, so she has decided to purchase all buildings possible at the lowest total payment of interest. From which savings and loan companies should she borrow to purchase which buildings? More than one savings and loan can finance the same property.

Table for Problem M8-21

Table for Problem M8-22

M8-23 The J. Mehta Company’s production manager is planning for a series of 1-month production periods for stainless steel sinks. The demand for the next 4 months is as follows:

The Mehta firm can normally produce 100 stainless steel sinks in a month. This is done during regular production hours at a cost of $100 per sink. If demand in any 1 month cannot be satisfied by regular production, the production manager has three other choices: (1) he can produce up to 50 more sinks per month in overtime but at a cost of $130 per sink; (2) he can purchase a limited number of sinks from a friendly competitor for resale (the maximum number of outside purchases over the 4-month period is 450 sinks, at a cost of $150 each); or (3) he can fill the demand from his on-hand inventory. The inventory carrying cost is $10 per sink per month. Back orders are not permitted. Inventory on hand at the beginning of month 1 is 40 sinks. Set up this “production smoothing” problem as a transportation problem to minimize cost. Use the northwest corner rule to find an initial level for production and outside purchases over the 4-month period.

M8-24 In a job shop operation, four jobs may be performed on any of four machines. The hours required for each job on each machine are presented in the following table. The plant supervisor would like to assign jobs so that total time is minimized. Find the best solution.

M8-25 Four automobiles have entered Bubba’s Repair Shop for various types of work, ranging from a transmission overhaul to a brake job. The experience level of the mechanics is quite varied, and Bubba would like to minimize the time required to complete all of the jobs. He has estimated the time in minutes for each mechanic to complete each job. Billy can complete job 1 in 400 minutes, job 2 in 90 minutes, job 3 in 60 minutes, and job 4 in 120 minutes. Taylor will finish job 1 in 650 minutes, job 2 in 120 minutes, job 3 in 90 minutes, and job 4 in 180 minutes. Mark will finish job 1 in 480 minutes, job 2 in 120 minutes, job 3 in 80 minutes, and job 4 in 180 minutes. John will complete job 1 in 500 minutes, job 2 in 110 minutes, job 3 in 90 minutes, and job 4 in 150 minutes. Each mechanic should be assigned to just one of these jobs. What is the minimum total time required to finish the four jobs? Who should be assigned to each job?

M8-26 Baseball umpiring crews are currently in four cities where three-game series are beginning. When these are finished, the crews are needed to work games in four different cities. The distances (miles) from each of the cities where the crews are currently working to each of the the cities where the new games will begin are shown in the following table:

The X indicates that the crew in Oakland cannot be sent to Toronto. Determine which crew should be sent to each city to minimize the total distance traveled. How many miles will be traveled if these assignments are made? To see how much better this solution is than the assignments that might have been made, find the assignments that would give the maximum distance traveled.

M8-27 Roscoe Davis, chairman of a college’s business department, has decided to apply a new method in assigning professors to courses next semester. As a criterion for judging who should teach each course, Professor Davis reviews the past two years’ teaching evaluations (which were filled out by students). Since each of the four professors taught each of the four courses at one time or another during the two-year period, Davis is able to record a course rating for each instructor. These ratings are shown in the following table. Find the best assignment of professors to courses to maximize the overall teaching rating.

M8-28 The hospital administrator at St. Charles General must appoint head nurses to four newly established departments: urology, cardiology, orthopedics, and obstetrics. In anticipation of this staffing problem, she had hired four nurses: Hawkins, Condriac, Bardot, and Hoolihan. Believing in the quantitative analysis approach to problem solving, the administrator has interviewed each nurse, considered his or her background, personality, and talents, and developed a cost scale ranging from 0 to 100 to be used in the assignment. A 0 for Nurse Bardot being assigned to the cardiology unit implies that she would be perfectly suited to that task. A value close to 100, on the other hand, would imply that she is not at all suited to head that unit. The accompanying table gives the complete set of cost figures that the hospital administrator felt represented all possible assignments. Which nurse should be assigned to which unit?

M8-29 The Fix-It Shop (see Section M8.2) has added a fourth repairman, Davis. Solve the cost table on this page for the new optimal assignment of workers to projects. Why did this solution occur?

M8-30 The XYZ Corporation is expanding its market to include Texas. Each salesperson is assigned to potential distributors in one of five different areas. It is anticipated that the salesperson will spend about 3 to 4 weeks in the assigned area. A statewide marketing campaign will begin once the product has been delivered to the distributors. The five salespeople who will be assigned to these areas (one person for each area) have rated the areas on the desirability of the assignment as shown in the table on the previous page. The scale is 1 (least desirable) to 5 (most desirable). Which assignments should be made if the total of the ratings is to be maximized?

M8-31 Bechtold Construction is in the process of installing power lines to a large housing development. Steve Bechtold wants to minimize the total length of wire used, which will minimize his costs. The housing development is shown as a network in Figure M8.15. Each house has been numbered, and the distances between houses are given in hundreds of feet. What do you recommend?

Figure M8.15 Network for Problem M8-31

M8-32 The city of New Berlin is considering making several of its streets one-way. What is the maximum number of cars per hour that can travel from east to west? The network is shown in Figure M8.16.

M8-33 Transworld Moving has been hired to move the office furniture and equipment of Cohen Properties to its new headquarters. What route do you recommend? The network of roads is shown in Figure M8.17.

M8-34 Because of a sluggish economy, Bechtold Construction has been forced to modify its plans for the housing development in Problem M8-31. The result is that the path from node 6 to 7 now has a distance of 7. What impact does this have on the total length of wire needed to install the power lines?

M8-35 The director of security wants to connect security video cameras to the main control site from five potential trouble locations. Ordinarily, cable would simply be run from each location to the main control site. However, because the environment is potentially explosive, the cable must be run in a special conduit that is continually air purged. This conduit is very expensive but large enough to handle five cables (the maximum that might be needed). Use the minimal-spanning tree technique to find a minimum distance route for the conduit between the locations noted in Figure M8.18. (Note that it makes no difference which one is the main control site.)

M8-36 One of our best customers has had a major plant breakdown and wants us to make as many widgets for him as possible during the next few days, until he gets the necessary repairs done. With our general-purpose equipment, there are several ways to make widgets (ignoring costs). Any sequence of activities that takes one from node 1 to node 6 in Figure M8.19 will produce a widget. How many widgets can we produce per day? Quantities given are number of widgets per day.

M8-37 The road system from the hotel complex on International Drive (node 1) to Disney World (node 11) in Orlando, Florida, is shown in the network of Figure M8.20. The numbers by the nodes represent the traffic flow in hundreds of cars per hour. What is the maximum flow of cars from the hotel complex to Disney World?

M8-38 A road construction project would increase the road capacity around the outside roads from International Drive to Disney World by 200 cars per hour (see Problem M8-37). The two paths affected would be 1–2–6–9–11 and 1–5–8–10–11. What impact would this have on the total flow of cars? Would the total flow of cars increase by 400 cars per hour?

M8-39 Solve the maximal-flow problem presented in the network of Figure M8.21. The numbers in the network represent thousands of gallons per hour as they flow through a chemical processing plant.

M8-40 Two terminals in the chemical processing plant, represented by nodes 6 and 7, require emergency repair (see Problem M8-39). No material can flow into or out of these nodes. What impact does this have on the capacity of the network?

M8-41 Solve the shortest-route problem presented in the network of Figure M8.22, going from node 1 to node 16. All numbers represent kilometers between German towns near the Black Forest.

M8-42 Due to bad weather, the roads going through nodes 7 and 8 have been closed (see Problem M8-41). No traffic can get onto or off of these roads. Describe the impact that this will have (if any) on the shortest route through this network.

M8-43 Grey Construction would like to determine the least expensive way of providing houses it is building with cable TV. It has identified 11 possible branches or routes that could be used to connect the houses. The cost in hundreds of dollars and the branches are summarized in the following table.

1. What is the least expensive way to run cable to the houses?

   BRANCH	START NODE	END NODE	COST ($100S)
   Branch 1	1	2	5
   Branch 2	1	3	6
   Branch 3	1	4	6
   Branch 4	1	5	5
   Branch 5	2	6	7
   Branch 6	3	7	5
   Branch 7	4	7	7
   Branch 8	5	8	4
   Branch 9	6	7	1
   Branch 10	7	9	6
   Branch 11	8	9	2

2. After reviewing cable and installation costs, Grey Construction would like to alter the costs for providing cable TV to its houses. The first branches need to be changed. The changes are summarized in the following table. What is the impact on total costs?

   BRANCH	START NODE	END NODE	COST ($100S)
   Branch 1	1	2	5
   Branch 2	1	3	1
   Branch 3	1	4	1
   Branch 4	1	5	1
   Branch 5	2	6	7
   Branch 6	3	7	5
   Branch 7	4	7	7
   Branch 8	5	8	4
   Branch 9	6	7	1
   Branch 10	7	9	6
   Branch 11	8	9	2

M8-44 In going from Quincy to Old Bainbridge, there are 10 possible roads that George Olin can take. Each road can be considered a branch in the shortest-route problem.

1. Determine the best way to get from Quincy (node 1) to Old Bainbridge (node 8) that will minimize total distance traveled. All distances are in hundreds of miles.

   BRANCH	START NODE	END NODE	DISTANCE (IN HUNDREDS OF MILES)
   Branch 1	1	2	3
   Branch 2	1	3	2
   Branch 3	2	4	3
   Branch 4	3	5	3
   Branch 5	4	5	1
   Branch 6	4	6	4
   Branch 7	5	7	2
   Branch 8	6	7	2
   Branch 9	6	8	3
   Branch 10	7	8	6

2. George Olin made a mistake in estimating the distances from Quincy to Old Bainbridge. The new distances are in the following table. What impact does this have on the shortest route from Quincy to Old Bainbridge?

   BRANCH	START NODE	END NODE	DISTANCE (IN HUNDREDS OF MILES)
   Branch 1	1	2	3
   Branch 2	1	3	2
   Branch 3	2	4	3
   Branch 4	3	5	1
   Branch 5	4	5	1
   Branch 6	4	6	4
   Branch 7	5	7	2
   Branch 8	6	7	2
   Branch 9	6	8	3
   Branch 10	7	8	6

M8-45 South Side Oil and Gas, a new venture in Texas, has developed an oil pipeline network to transport oil from exploration fields to the refinery and other locations. There are 10 pipelines (branches) in the network. The oil flow in hundreds of gallons and the network of pipelines are given in the following table.

1. What is the maximum that can flow through the network?

   BRANCH	START NODE	END NODE	CAPACITY	REVERSE CAPACITY	FLOW
   Branch 1	1	2	10	4	10
   Branch 2	1	3	8	2	5
   Branch 3	2	4	12	1	10
   Branch 4	2	5	6	6	0
   Branch 5	3	5	8	1	5
   Branch 6	4	6	10	2	10
   Branch 7	5	6	10	10	0
   Branch 8	5	7	5	5	5
   Branch 9	6	8	10	1	10
   Branch 10	7	8	10	1	5

2. South Side Oil and Gas needs to modify its pipe-line network flow patterns. The new data are in the following table. What impact does this have on the maximum flow through the network?

   BRANCH	START NODE	END NODE	CAPACITY	REVERSE CAPACITY	FLOW
   Branch 1	1	2	10	4	10
   Branch 2	1	3	8	2	5
   Branch 3	2	4	12	1	10
   Branch 4	2	5	0	0	0
   Branch 5	3	5	8	1	5
   Branch 6	4	6	10	2	10
   Branch 7	5	6	10	10	0
   Branch 8	5	7	5	5	5
   Branch 9	6	8	10	1	10
   Branch 10	7	8	10	1	5

M8-46 Northwest University is in the process of completing a computer bus network that will connect computer facilities throughout the university. The prime objective is to string a main cable from one end of the campus to the other (nodes 1–25) through underground conduits. These conduits are shown in the network of Figure M8.23; the distance between nodes is in hundreds of feet. Fortunately, these underground conduits have remaining capacity through which the bus cable can be placed.

1. Given the network for this problem, how far (in hundreds of feet) is the shortest route from node 1 to node 25?

2. In addition to the computer bus network, a new phone system is being planned. The phone system would use the same underground conduits. If the phone system were installed, the following paths along the conduit would be at capacity and would not be available for the computer bus network: 6–11, 7–12, and 17–20. What changes (if any) would you have to make to the path used for the computer bus if the phone system were installed?

3. The university did decide to install the new phone system before the cable for the computer network. Because of unexpected demand for computer networking facilities, an additional cable is needed for node 1 to node 25. Unfortunately, the cable for the first or original network has completely used up the capacity along its path. Given this situation, what is the best path for the second network cable?