9-1 Is the transportation model an example of decision making under certainty or decision making under uncertainty? Why?
9-2 Explain how to determine the number of variables and constraints in a transportation problem when only the number of sources and the number of destinations are known.
9-3 Explain what it means for an assignment model to be balanced.
9-4 Explain the purpose of the transshipment constraints in the linear program for a transshipment model.
9-5 Describe a problem that can be solved by using the shortest-route model.
9-6 Explain how the maximal-flow model might be viewed as a transshipment model.
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.
TO FROM | ALBUQUERQUE | BOSTON | CLEVELAND | CAPACITY |
---|---|---|---|---|
DES MOINES | $5 | $4 | $3 | 300 |
EVANSVILLE | $8 | $4 | $3 | 150 |
FORT LAUDERDALE | $9 | $7 | $5 | 250 |
REQUIREMENTS | 200 | 200 | 300 |
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.
TO FROM | PROJECT A | PROJECT B | PROJECT C | CAPACITY |
---|---|---|---|---|
PLANT 1 | $10 | $4 | $11 | 70 |
PLANT 2 | $12 | $5 | $ 8 | 50 |
PLANT 3 | $ 9 | $7 | $ 6 | 30 |
REQUIREMENTS | 40 | 50 | 60 |
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 Pineville, Oak Ridge, and Mapletown. Determine the best transportation schedule for the data given in the table on this page.
TO FROM | SUPPLY HOUSE 1 | SUPPLY HOUSE 2 | SUPPLY HOUSE 3 | MILL CAPACITY (TONS) |
---|---|---|---|---|
PINEVILLE | $3 | $3 | $2 | 25 |
OAK RIDGE | $4 | $2 | $3 | 40 |
MAPLETOWN | $3 | $2 | $3 | 30 |
SUPPLY-HOUSE DEMAND | 30 | 30 | 35 |
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:
TOWN | SUPPLY OF CARS |
---|---|
Morgantown | 35 |
Youngstown | 60 |
Pittsburgh | 25 |
By Monday, April 16, the following towns will need the numbers of coal cars listed:
TOWN | DEMAND FOR CARS |
---|---|
Coal Valley | 30 |
Coaltown | 45 |
Coal Junction | 25 |
Coalsburg | 20 |
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.
TO FROM | COAL VALLEY | COALTOWN | COAL JUNCTION | COALSBURG |
---|---|---|---|---|
MORGANTOWN | 50 | 30 | 60 | 70 |
YOUNGSTOWN | 20 | 80 | 10 | 90 |
PITTSBURGH | 100 | 40 | 80 | 30 |
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:
TO FROM | PHOENIX | CLEVELAND | CHICAGO |
---|---|---|---|
RENO | 10 | 16 | 19 |
DENVER | 12 | 14 | 13 |
PITTSBURGH | 18 | 12 | 12 |
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:
TO FROM | W | X | Y | Z | EXCESS SUPPLY |
---|---|---|---|---|---|
A | 12¢ | 4¢ | 9¢ | 5¢ | 55 |
B | 8¢ | 1¢ | 6¢ | 6¢ | 45 |
C | 1¢ | 12¢ | 4¢ | 7¢ | 30 |
UNFILLED POWER DEMAND | 40 | 20 | 50 | 20 |
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?
TO FROM | HOSPITAL 1 | HOSPITAL 2 | HOSPITAL 3 | HOSPITAL 4 | SUPPLY |
---|---|---|---|---|---|
BANK 1 | $8 | $9 | $11 | $16 | 50 |
BANK 2 | 12 | 7 | 5 | 8 | 80 |
BANK 3 | 14 | 10 | 6 | 7 | 120 |
DEMAND | 90 | 70 | 40 | 50 |
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.
PROPERTY (INTEREST RATES) (%) | |||||
---|---|---|---|---|---|
SAVINGS AND LOAN COMPANY | HILL ST. | BANKS ST. | PARK AVE. | DRURY LANE | MAXIMUM CREDIT LINE ($) |
FIRST HOMESTEAD | 8 | 8 | 10 | 11 | 80,000 |
COMMONWEALTH | 9 | 10 | 12 | 10 | 100,000 |
WASHINGTON FEDERAL | 9 | 11 | 10 | 9 | 120,000 |
LOAN REQUIRED TO PURCHASE BUILDING | $60,000 | $40,000 | $130,000 | $70,000 |
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:
MONTH | DEMAND FOR STAINLESS STEEL SINKS |
---|---|
1 | 120 |
2 | 160 |
3 | 240 |
4 | 100 |
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?
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?
PLANT LOCATION | |||||
---|---|---|---|---|---|
MARKET AREA | WATERLOO | PUSAN | BOGOTA | FONTAINEBLEAU | DUBLIN |
Canada | |||||
Demand 4,000 | |||||
Production cost | $50 | $30 | $40 | $50 | $45 |
Transportation cost | 10 | 25 | 20 | 25 | 25 |
South America | |||||
Demand 5,000 | |||||
Production cost | 50 | 30 | 40 | 50 | 45 |
Transportation cost | 20 | 25 | 10 | 30 | 30 |
Pacific Rim | |||||
Demand 10,000 | |||||
Production cost | 50 | 30 | 40 | 50 | 45 |
Transportation cost | 25 | 10 | 25 | 40 | 40 |
Europe | |||||
Demand 5,000 | |||||
Production cost | 50 | 30 | 40 | 50 | 45 |
Transportation cost | 25 | 40 | 30 | 10 | 20 |
Capacity | 8,000 | 2,000 | 5,000 | 9,000 | 9,000 |
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?
FROM EXISTING PLANTS | ||||
---|---|---|---|---|
TO | DECATUR | MINNEAPOLIS | CARBONDALE | DEMAND |
Blue Earth | $20 | $17 | $21 | 250 |
Ciro | 25 | 27 | 20 | 200 |
Des Moines | 22 | 25 | 22 | 350 |
Capacity | 300 | 200 | 150 |
FROM PROPOSED PLANTS | ||||
---|---|---|---|---|
TO | EAST ST. LOUIS | ST. LOUIS | ||
Blue Earth | $29 | $27 | ||
Ciro | $30 | $28 | ||
Des Moines | $30 | $31 | ||
Capacity | 150 | 150 |
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?
LOCATION | PRODUCTION COSTS |
---|---|
Decatur | $50 |
Minneapolis | 60 |
Carbondale | 70 |
East ST. Louis | 40 |
ST. Louis | 50 |
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?
MACHINE | ||||
---|---|---|---|---|
JOB | W | X | Y | Z |
A12 | 10 | 14 | 16 | 13 |
A15 | 12 | 13 | 15 | 12 |
B2 | 9 | 12 | 12 | 11 |
B9 | 14 | 16 | 18 | 16 |
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:
TO | ||||
---|---|---|---|---|
FROM | KANSAS CITY | CHICAGO | DETROIT | TORONTO |
Seattle | 1,500 | 1,730 | 1,940 | 2,070 |
Arlington | 460 | 810 | 1,020 | 1,270 |
Oakland | 1,500 | 1,850 | 2,080 | X |
Baltimore | 960 | 610 | 400 | 330 |
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.
COURSE | ||||
---|---|---|---|---|
PROFESSOR | STATISTICS | MANAGEMENT | FINANCE | ECONOMICS |
Anderson | 90 | 65 | 95 | 40 |
Sweeney | 70 | 60 | 80 | 75 |
Williams | 85 | 40 | 80 | 60 |
McKinney | 55 | 80 | 65 | 55 |
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?
DEPARTMENT | ||||
---|---|---|---|---|
NURSE | UROLOGY | CARDIOLOGY | ORTHOPEDICS | OBSTETRICS |
Hawkins | 28 | 18 | 15 | 75 |
Condriac | 32 | 48 | 23 | 38 |
Bardot | 51 | 36 | 24 | 36 |
Hoolihan | 25 | 38 | 55 | 12 |
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?
NETWORK | ||||
---|---|---|---|---|
VIEWING HOURS | A | B | C | INDEPENDENT |
1–2 p.m. | 27.1 | 18.1 | 11.3 | 9.5 |
2–3 p.m. | 18.9 | 15.5 | 17.1 | 10.6 |
3–4 p.m. | 19.2 | 18.5 | 9.9 | 7.7 |
4–5 p.m. | 11.5 | 21.4 | 16.8 | 12.8 |
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?
PLANT | ||||||||
---|---|---|---|---|---|---|---|---|
MEDICAL DEVICES | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
C53 | $0.10 | $0.12 | $0.13 | $0.11 | $0.10 | $0.06 | $0.16 | $0.12 |
C81 | 0.05 | 0.06 | 0.04 | 0.08 | 0.04 | 0.09 | 0.06 | 0.06 |
D5 | 0.32 | 0.40 | 0.31 | 0.30 | 0.42 | 0.35 | 0.36 | 0.49 |
D44 | 0.17 | 0.14 | 0.19 | 0.15 | 0.10 | 0.16 | 0.19 | 0.12 |
E2 | 0.06 | 0.07 | 0.10 | 0.05 | 0.08 | 0.10 | 0.11 | 0.05 |
E35 | 0.08 | 0.10 | 0.12 | 0.08 | 0.09 | 0.10 | 0.09 | 0.06 |
G99 | 0.55 | 0.62 | 0.61 | 0.70 | 0.62 | 0.63 | 0.65 | 0.59 |
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.
Set up a production plan, using the transportation model, that minimizes cost. What is this plan’s cost?
Through better planning, regular time production can be set at exactly the same value, 275 per month. Does this alter the solution?
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?
CAPACITY SOURCE | JAN. | FEB. | MAR. | APR. | MAY | JUNE | JULY | AUG. |
---|---|---|---|---|---|---|---|---|
Labor | ||||||||
Regular time | 235 | 255 | 290 | 300 | 300 | 290 | 300 | 290 |
Overtime | 20 | 24 | 26 | 24 | 30 | 28 | 30 | 30 |
Subcontract | 12 | 15 | 15 | 17 | 17 | 19 | 19 | 20 |
Demand | 255 | 294 | 321 | 301 | 330 | 320 | 345 | 340 |
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.
Who should be assigned to which flight to maximize ratings?
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?
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)?
What are the strengths and weaknesses of this approach to scheduling?
MISSION | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
ASTRONAUT | JAN. 12 | JAN. 27 | FEB. 5 | FEB. 26 | MAR. 26 | APR. 12 | MAY 1 | JUN. 9 | AUG. 20 | SEP. 19 |
Vincze | 9 | 7 | 2 | 1 | 10 | 9 | 8 | 9 | 2 | 6 |
Veit | 8 | 8 | 3 | 4 | 7 | 9 | 7 | 7 | 4 | 4 |
Anderson | 2 | 1 | 10 | 10 | 1 | 4 | 7 | 6 | 6 | 7 |
Herbert | 4 | 4 | 10 | 9 | 9 | 9 | 1 | 2 | 3 | 4 |
Schatz | 10 | 10 | 9 | 9 | 8 | 9 | 1 | 1 | 1 | 1 |
Plane | 1 | 3 | 5 | 7 | 9 | 7 | 10 | 10 | 9 | 2 |
Certo | 9 | 9 | 8 | 8 | 9 | 1 | 1 | 2 | 2 | 9 |
Moses | 3 | 2 | 7 | 6 | 4 | 3 | 9 | 7 | 7 | 9 |
Brandon | 5 | 4 | 5 | 9 | 10 | 10 | 5 | 4 | 9 | 8 |
Drtina | 10 | 10 | 9 | 7 | 6 | 7 | 5 | 4 | 8 | 8 |
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?
AUSTIN/SAN ANTONIO | DALLAS/Ft. WORTH | EL PASO/WEST TEXAS | HOUSTON/GALVESTON | CORPUS CHRISTI/RIO GRANDE VALLEY | |
---|---|---|---|---|---|
Erica | 5 | 3 | 2 | 3 | 4 |
Louis | 3 | 4 | 4 | 2 | 2 |
Maria | 4 | 5 | 4 | 3 | 3 |
Paul | 2 | 4 | 3 | 4 | 3 |
Orlando | 4 | 5 | 3 | 5 | 4 |
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.
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 |
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.
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 |
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.
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 |
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.
ARC | DISTANCE |
---|---|
1–2 | 12 |
1–3 | 8 |
2–3 | 7 |
2–4 | 10 |
3–4 | 9 |
3–5 | 8 |
4–5 | 8 |
4–6 | 11 |
5–6 | 9 |
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.
Given the network for this problem, how long (in hundreds of feet) is the shortest route from node 1 to node 25?
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?
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?
Andrew–Carter, Inc. (A–C), is a major Canadian producer and distributor of outdoor lighting fixtures. Its fixture is distributed throughout North America and has been in high demand for several years. The company operates three plants that manufacture the fixture and distribute it to five distribution centers (warehouses).
During the present recession, A–C has seen a major drop in demand for its fixture as the housing market has declined. Based on the forecast of interest rates, the head of operations feels that demand for housing and thus for its product will remain depressed for the foreseeable future. A–C is considering closing one of its plants, as it is now operating with a forecasted excess capacity of 34,000 units per week. The forecasted weekly demands for the coming year are
Warehouse 1 | 9,000 units |
Warehouse 2 | 13,000 units |
Warehouse 3 | 11,000 units |
Warehouse 4 | 15,000 units |
Warehouse 5 | 8,000 units |
The plant capacities in units per week are
Plant 1, regular time | 27,000 units |
Plant 1, on overtime | 7,000 units |
Plant 2, regular time | 20,000 units |
Plant 2, on overtime | 5,000 units |
Plant 3, regular time | 25,000 units |
Plant 3, on overtime | 6,000 units |
If A–C shuts down any plants, its weekly costs will change, as fixed costs are lower for a nonoperating plant. Table 9.5 shows production costs at each plant, both variable at regular time and overtime and fixed when operating and shut down. Table 9.6 shows the distribution cost from each plant to each warehouse (distribution center).
(Source: Trevor S. Hale)
FIXED COST PER WEEK | |||
---|---|---|---|
PLANT | VARIABLE COST | OPERATING | NOT OPERATING |
No. 1, regular time | $2.80/unit | $14,000 | $6,000 |
No. 1, overtime | 3.52 | ||
No. 2, regular time | 2.78 | 12,000 | 5,000 |
No. 2, overtime | 3.48 | ||
No. 3, regular time | 2.72 | 15,000 | 7,500 |
No. 3, overtime | 3.42 |
(Source: Trevor S. Hale)
TO DISTRIBUTION CENTER | |||||
---|---|---|---|---|---|
FROM PLANT | W1 | W2 | W3 | W4 | W5 |
No. 1 | $0.50 | $0.44 | $0.49 | $0.46 | $0.56 |
No. 2 | 0.40 | 0.52 | 0.50 | 0.56 | 0.57 |
No. 3 | 0.56 | 0.53 | 0.51 | 0.54 | 0.35 |
1.Evaluate the various configurations of operating and closed plants that will meet weekly demand. Determine which configuration minimizes total costs.
2.Discuss the implications of closing a plant.
Source: Professor Emeritus Michael Ballot, ESB, University of the Pacific.
Northeastern Airlines is a regional airline serving nine cities in the New England states, as well as cities in New York, New Jersey, and Pennsylvania. While nonstop flights are available for some of the routes, connecting flights are often necessary. The network shows the cities served and profit in U.S. dollars per passenger along each of these routes. To service these cities, Northeastern operates a fleet of eighteen 122-passenger Embraer E-195 jets. These jets, which were first introduced by Embraer in late 2004, have helped Northeastern Airlines remain profitable for a number of years. However, in recent years, the profit margins have been falling, and Northeastern is facing the prospect of downsizing its operations.
Management at Northeastern Airlines has considered several options to reduce cost and increase profitability. Due to Federal Aviation Administration regulations, the company must continue to serve each of the nine cities. How it serves these cities, however, is up to the management at Northeastern. One suggestion has been made to provide fewer direct flights, which would mean that a city served by Northeastern might have direct flights to only one other city. The company plans to hire a marketing analytics consultant to determine how demand would be impacted by longer flights with more connections and to forecast the demand along each of the routes based on a modified flight operations map. Before hiring the consultant, the company would like to determine the most profitable (on a profit-per-passenger basis) way to continue serving all of the cities.
1. Develop a flight operations map that still serves each of the nine cities but that maximizes the company’s profit per passenger. (Hint: Find the maximal-spanning tree.)
2. Comment on how the 18 jets should be assigned.
Source: Northeastern Airlines by Faizul Huq © Faizul Huq. Reprinted by permission of Faizul Huq.
Southwestern University (SWU), located in the small town of Stephenville, Texas, is experiencing increased interest in its football program now that a big-name coach has been hired. The increase in season ticket sales for the upcoming season means additional revenues, but it also means increased complaints due to the traffic problems associated with the football games. When a new stadium is built, this will only get worse. Marty Starr, SWU’s president, has asked the University Planning Committee to look into this problem.
Based on traffic projections, Dr. Starr would like to have sufficient capacity so that 35,000 cars per hour could travel from the stadium to the interstate highway. To alleviate the anticipated traffic problems, some of the current streets leading from the university to the interstate highway are being considered for widening to increase the capacity. The current street capacities with the number of cars (in 1,000s) per hour are shown below. Since the major problem will be after the game, only the flows away from the stadium are indicated. These flows take into account the fact that some streets closest to the stadium are transformed into one-way streets for a short period after each game, with police officers directing traffic.
Alexander Lee, a member of the University Planning Committee, has said that a quick check of the road capacities in the diagram indicates that the total number of cars per hour that may leave the stadium (node 1) is 33,000. The number of cars that may pass through nodes 2, 3, and 4 is 35,000 per hour, and the number of cars that may pass through nodes 5, 6, and 7 is even greater. Therefore, Dr. Lee has suggested that the current capacity is 33,000 cars per hour. He has also suggested that a recommendation be made to the city manager for expansion of one of the routes from the stadium to the highway to permit an additional 2,000 cars per hour. He recommends expanding whichever route is cheapest. If the city chooses not to expand the roads, it is felt that the traffic problem would be a nuisance but would be manageable.
Based on past experience, it is believed that as long as the street capacity is within 2,500 cars per hour of the number of cars that leave the stadium, the problem is not too severe. However, the severity of the problem grows dramatically for each additional 1,000 cars that are added to the streets.
If there is no expansion, what is the maximum number of cars that may actually travel from the stadium to the interstate per hour? Why is this number not equal to 33,000, as Dr. Lee suggested?
If the cost of expanding a street were the same for each street, which street(s) would you recommend expanding to increase the capacity to 33,000? Which streets would you recommend expanding to get the total capacity of the system to 35,000 per hour?
Adlakha, V., and K. Kowalski. “Simple Algorithm for the Source-Induced Fixed-Charge Transportation Problem,” Journal of the Operational Research Society 55, 12 (2004): 1275–1280.
Bowman, E. “Production Scheduling by the Transportation Method of Linear Programming,” Operations Research 4 (1956): 100–103.
Dawid, Herbert, Johannes Konig, and Christine Strauss. “An Enhanced Rostering Model for Airline Crews,” Computers and Operations Research 28, 7 (June 2001): 671–688.
Hezarkhani, Behzad, and Wieslaw Kubiak. “A Coordinating Contract for Transshipment in a Two-Company Supply Chain,” European Journal of Operational Research 207, 1 (2010): 232–237.
Jacobs, T., B. Smith, and E. Johnson. “Incorporating Network Flow Effects into the Airline Fleet Assignment Process,” Transportation Science 42, 4 (2008): 514–529.
Johnsonbaugh, Richard. Discrete Mathematics, 5th ed. Upper Saddle River, NJ: Prentice Hall, 2001.
Kawatra, R., and D. Bricker. “A Multiperiod Planning Model for the Capacitated Minimal Spanning Tree Problem,” European Journal of Operational Research 121, 2 (2000): 412–419.
Koksalan, Murat, and Haldun Sural. “Efes Beverage Group Makes Location and Distribution Decisions for Its Malt Plants,” Interfaces 29, 2 (March–April, 1999): 89–103.
Liu, Jinming, and Fred Rahbar. “Project Time–Cost Trade-off Optimization by Maximal Flow Theory,” Journal of Construction Engineering & Management 130, 4 (July/August 2004): 607–609.
Liu, Shiang-Tai. “The Total Cost Bounds of the Transportation Problem with Varying Demand and Supply,” Omega 31, 4 (2003): 247–251.
Martello, Silvano. “Jeno Egervary: From the Origins of the Hungarian Algorithm to Satellite Communication,” Central European Journal of Operations Research 18, 1 (2010): 47–58.
McKeown, P., and B. Workman. “A Study in Using Linear Programming to Assign Students to Schools,” Interfaces 6, 4 (August 1976).
Render, B., and R. M. Stair. Introduction to Management Science. Boston: Allyn & Bacon, Inc., 1992.
Sancho, N. G. F. “On the Maximum Expected Flow in a Network,” Journal of the Operational Research Society 39 (May 1988): 481–485.
Sedeño-Noda, Antonio, Carlos González-Martín, and Sergio Alonso. “A Generalization of the Scaling Max-Flow Algorithm,” Computers & Operations Research 31, 13 (November 2004): 2183–2198.
Troutt, M. D., and G. P. White. “Maximal Flow Network Modeling of Production Bottleneck Problems,” Journal of the Operational Research Society 52, 2 (February 2001): 182–187.
QM for Windows has both a transportation module and an assignment module in its menu. Both are easy to use in terms of data entry and easy to interpret in terms of output. Program 9.9A shows the input screen for the Executive Furniture transportation example. The starting solution technique may be specified. The results are shown in Program 9.9B. Program 9.10A provides the input screen for the Fix-It Shop assignment example. Simply enter the costs and then click Solve. Program 9.10B gives the solution to this.