9-7 The management of the Executive Furniture Corporation decided to expand the production capacity at its Des Moines factory and to cut back the production capacities at its other two factories. It also recognizes a shifting market for its desks and revises the requirements at its three warehouses.

The table on this page provides the requirement at each of the warehouses, the capacity at each of the factories, and the shipping cost per unit to ship from each factory to each warehouse. Find the least-cost way to meet the requirements given the capacity at each factory.

9-8 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 cost per truckload of concrete, daily plant capacities, and daily project requirements are provided in the table on this page.

Formulate this as a linear program to determine the least-cost way to meet the requirements. Solve using any computer software.

9-9 Hardrock Concrete’s owner has decided to increase the capacity at his smallest plant (see Problem 9.8). Instead of producing 30 loads of concrete per day at plant 3, that plant’s capacity has been doubled to 60 loads. Does this change the schedule developed previously?

9-10 The Saussy Lumber Company ships pine flooring to three building-supply houses from its mills in Pine­ville, Oak Ridge, and Mapletown. Determine the best transportation schedule for the data given in the table on this page.

9-11 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 the numbers of coal cars listed:

Using a railway city-to-city distance chart, the dispatcher constructs a mileage table for the preceding towns. The result is shown in the table on this page. Minimizing total miles over which cars are moved to new locations, compute the best shipment of coal cars.

9-12 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 shipping cost per unit from Phoenix to Dallas is $10, to Atlanta is $14, and to Denver is $9. The shipping 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?

9-13 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 stores’ 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 from Denver, and 160 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?

9-14 The state of Missouri has three major power-generating companies (A, B, and C). During the months of peak demand, the Missouri Power Authority authorizes these companies to pool their excess supply and to distribute it to smaller, independent power companies that do not have generators large enough to handle the demand. Excess supply is distributed on the basis of cost per kilowatt hour transmitted. The following table shows the demand and supply in millions of kilowatt hours and the cost per kilowatt hour of transmitting electric power to four small companies in cities W, X, Y, and Z:

Find the least-cost distribution system.

9-15 The three blood banks in Franklin County are coordinated through a central office that facilitates blood delivery to four hospitals in the region. The cost to ship a standard container of blood from each bank to each hospital is shown in the table on this page. Also given are the biweekly number of containers of blood available at each bank and the biweekly number of containers needed at each hospital. How many shipments should be made biweekly from each blood bank to each hospital so that total shipment costs are minimized?

9-16 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 the previous page.

Each apartment building is equally attractive as an investment to Hall, so she has decided to purchase all four buildings 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.

9-17 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.

9-18 Ashley’s Auto Top Carriers currently maintains plants in Atlanta and Tulsa that supply major distribution centers in Los Angeles and New York. Because of an expanding demand, Ashley has decided to open a third plant and has narrowed the choice to one of two cities—New Orleans or Houston. The pertinent production and distribution costs, as well as the plant capacities and distribution demands, are shown in the table on this page.

Which of the new possible plants should be opened?

Data for Problem 9-18

9-19 Marc Smith, vice president for operations of HHN, Inc., a manufacturer of cabinets for telephone switches, is constrained from meeting the 5-year forecast by limited capacity at the existing three plants. These three plants are Waterloo, Pusan, and Bogota. You, as his able assistant, have been told that because of existing capacity constraints and the expanding world market for HHN cabinets, a new plant is to be added to the existing three plants. The real estate department has advised Marc that two sites seem particularly good because of a stable political situation and tolerable exchange rate: Dublin, Ireland, and Fontainebleau, France. Marc suggests that you should be able to take the data on the next page and determine where the fourth plant should be located on the basis of production costs and transportation costs. Which location is better?

9-20 Don Levine Corporation is considering adding an additional plant to its three existing facilities in Decatur, Minneapolis, and Carbondale. Both St. Louis and East St. Louis are being considered. Evaluating only the transportation costs per unit, as shown in the tables below, which site is better?

9-21 Using the data from Problem 9-20 plus the unit production costs shown in the following table, which locations yield the lowest cost?

9-22 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. Which assignments should be made?

9-23 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?

9-24 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 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?

9-25 In Problem 9-24, the minimum travel distance was found. 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. Compare this total distance with the distance found in Problem 9-24.

9-26 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.

9-27 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 table below gives the complete set of cost figures that the hospital administrator felt represented all possible assignments. Which nurse should be assigned to which unit?

9-28 The Gleaming Company has just developed a new dishwashing liquid and is preparing for a national television promotional campaign. The firm has decided to schedule a series of 1-minute commercials during the peak homemaker audience viewing hours of 1 p.m. to 5 p.m. To reach the widest possible audience, Gleaming wants to schedule one commercial on each of four networks and to have one commercial appear during each of the four 1-hour time blocks. The exposure ratings for each hour, which represent the number of viewers per $1,000 spent, are presented in the following table. Which network should be scheduled each hour to provide the maximum audience exposure?

9-29 The Patricia Garcia Company is producing seven new medical products. Each of Garcia’s eight plants can add one more product to its current line of medical devices. The unit manufacturing costs for producing the different parts at the eight plants are shown in the table on this page. How should Garcia assign the new products to the plants to minimize manufacturing costs?

9-30 Haifa Instruments, an Israeli producer of portable kidney dialysis units and other medical products, develops an 8-month aggregate plan. Demand and capacity (in units) are forecast as shown in the table on this page.

The cost of producing each dialysis unit is $1,000 on regular time, $1,300 on overtime, and $1,500 on a subcontract. Inventory carrying cost is $100 per unit per month. There is no beginning or ending inventory in stock.

1. Set up a production plan, using the transportation model, that minimizes cost. What is this plan’s cost?

2. Through better planning, regular time production can be set at exactly the same value, 275 per month. Does this alter the solution?

3. If overtime costs rise from $1,300 to $1,400, does this change your answer to part (a)? What if they fall to $1,200?

9-31 NASA’s astronaut crew currently includes 10 mission specialists who hold a doctoral degree in either astrophysics or astromedicine. One of these specialists will be assigned to each of the 10 flights scheduled for the upcoming nine months. Mission specialists are responsible for carrying out scientific and medical experiments in space or for launching, retrieving, or repairing satellites. The chief of astronaut personnel, himself a former crew member with three missions under his belt, must decide who should be assigned and trained for each of the very different missions. Clearly, astronauts with medical educations are more suited to missions involving biological or medical experiments, whereas those with engineering- or physics-oriented degrees are best suited to other types of missions. The chief assigns each astronaut a rating on a scale of 1 to 10 for each possible mission, with a 10 being a perfect match for the task at hand and a 1 being a mismatch. Only one specialist is assigned to each flight, and none is reassigned until all others have flown at least once.

1. Who should be assigned to which flight to maximize ratings?

2. NASA has just been notified that Anderson is getting married in February and has been granted a highly sought publicity tour in Europe that month. (He intends to take his wife and let the trip double as a honeymoon.) How does this change the final schedule?

3. Certo has complained that he was misrated on his January missions. Both ratings should be 10s, he claims to the chief, who agrees and recomputes the schedule. Do any changes occur over the schedule set in part (b)?

4. What are the strengths and weaknesses of this approach to scheduling?

9-32 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 three to four 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 this 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?

9-33 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 on this page. Each house has been numbered, and the distances between houses are given in hundreds of feet. What do you recommend?

9-34 The city of New Berlin is considering making several of its streets one-way (see the network on this page). Also, due to increased property taxes and an aggressive road development plan, the city of New Berlin has been considering increasing the road capacity of two of its roads. If this is done, traffic along road 1–2 (from node 1 to node 2) will be increased from 2 to 5, and traffic capacity along road 1–4 will be increased from 1 to 3. What is the maximum number of cars per hour that can travel from east to west with the current road system? If the increases in capacity for roads 1–2 and 1–4 were both made, how would that change the number of cars per hour that can travel from east to west?

9-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 the network below. (Note that it makes no difference which one is the main control site.)

9-36 The road system between the hotel complex on International Drive (node 1) and Disney World (node 11) in Orlando, Florida, is shown in the network below. 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?

9-37 The numbers in the network below represent thousands of gallons per hour as they flow through a chemical processing plant. Two terminals in the chemical processing plant, represented by nodes 6 and 7, have had problems recently, and repairs on these are being considered. However, these repairs would require that these terminals (nodes) be shut down for a significant amount of time, and no material could flow into or out of these nodes until the repairs are finished. What impact would closing these nodes have on the capacity of the network?

9-38 The German towns around the Black Forest are represented by nodes in the network below. The distances between towns are shown in kilometers. Find the shortest route from city 1 to city 16. If flooding in cities 7 and 8 forces closure of all roads leading into or coming out of those cities, how would that impact the shortest route?

9-39 Grey Construction would like to determine the least expensive way of connecting 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 installing cable TV between 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

9-40 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. Using the following table, determine the route 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 (100s 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 given in the following table. What impact does this have on the shortest route from Quincy to Old Bainbridge?

   BRANCH	START NODE	END NODE	DISTANCE (100s 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

9-41 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 given 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

9-42 The following table represents a network with the arcs identified by their starting and ending nodes. Draw the network and use the minimal-spanning tree technique to find the minimum distance required to connect these nodes.

9-43 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 below; the distance between them 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 long (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 also 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?

   

   9.5-25 Full Alternative Text

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 to connect 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?