Management since
tmubi11
448 CHAPTER 11 • NETWORK MODELS
3. The first step of the maximal-flow technique is to a. select any node. b. pick any path from the start to the finish with some
flow. c. pick the path with the maximum flow. d. pick the path with the minimal flow. e. pick a path where the flow going into each node is
greater than the flow coming out of each node. 4. In which technique do you connect the nearest node to
the existing solution that is not currently connected? a. maximal tree b. shortest route c. minimal-spanning tree d. maximal flow e. minimal flow
5. In the shortest-route technique, the objective is to deter- mine the route from an origin to a destination that passes through the fewest number of other nodes. a. True b. False
6. Adjusting the flow capacity numbers on a path is an im- portant step in which technique? a. maximal flow b. minimal flow c. maximal-spanning tree d. minimal-spanning tree e. shortest route
7. Which of the following may be considered a transshipment problem in which there is one source with a supply of 1? a. a maximal-flow problem b. a minimal-spanning tree problem c. a minimal-flow problem d. a shortest-route problem
8. If the maximal-flow problem is formulated as a linear program, the objective is to a. maximize the flow from the sink to the source. b. minimize the total distance. c. minimize the flow from the sink to the source. d. find the shortest distance from the source to the sink.
9. When the optimal solution has been reached with the maximal-flow technique, every node will be connected with at least one other node. a. True b. False
10. A large city is planning for delays during rush hour when roads are closed for maintenance. On a normal weekday, 160,000 vehicles travel on a freeway from downtown to a point 15 miles to the west. Which of the techniques dis- cussed in this chapter would help the city planners deter- mine if alternate routes provide sufficient capacity for all the traffic? a. minimal-spanning tree technique b. maximal-flow technique c. shortest-route technique
11. The computing center at a major university is installing new fiber optic cables for a campuswide computer network. Which of the techniques in this chapter could be used to determine the least amount of cable needed to connect the 20 buildings on campus? a. minimal-spanning tree technique b. maximal-flow technique c. shortest-route technique
12. In a minimal-spanning tree problem, the optimal solution has been found when a. the start node and the finish node are connected by a
continuous path. b. the flow from the start node is equal to the flow into
the finish node. c. all arcs have been selected to be a part of the tree. d. all nodes have been connected and are a part of the
tree. 13. ______________ is a technique that is used to find how a
person or an item can travel from one location to another while minimizing the total distance traveled.
14. The technique that allows us to determine the maximum amount of a material that can flow through a network is called ______________.
15. The ______________ technique can be used to connect all of the points of a network together while minimizing the distance between them.
Discussion Questions and Problems
Discussion Questions 11-1 What is the minimal-spanning tree technique? What
types of problems can be solved using this quantita- tive analysis technique?
11-2 Describe the steps of the maximal-flow technique.
11-3 Give several examples of problems that can be solved using the maximal-flow technique.
11-4 What are the steps of the shortest-route technique?
11-5 Describe a problem that can be solved by the shortest- route technique.
11-6 Is it possible to get alternate optimal solutions with the shortest-route technique? Is there an automatic way of knowing if you have an alternate optimal solution?
11-7 Describe how the maximal-flow problem is modeled as a transshipment problem.
11-8 Describe how the shortest-route problem is modeled as a transshipment problem.
DISCUSSION QUESTIONS AND PROBLEMS 449
Problems* 11-9 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 11.21. Each house has been numbered, and the distances between houses are given in hundreds of feet. What do you recommend?
11-10 The city of New Berlin is considering making sev- eral 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 11.22.
11-11 Transworld Moving has been hired to move the of- fice furniture and equipment of Cohen Properties to their new headquarters. What route do you rec- ommend? The network of roads is shown in Figure 11.23.
11-12 Because of a sluggish economy, Bechtold Construc- tion has been forced to modify its plans for the hous- ing development in Problem 11-9. 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?
11-13 Due to increased property taxes and an aggressive road development plan, the city of New Berlin has been able to increase the road capacity of two of its roads (see Problem 11-10). The capacity along the road rep- resented by the path from node 1–node 2 has been in- creased from 2 to 5. In addition, the capacity from node 1–node 4 has been increased from 1 to 3. What impact do these changes have on the number of cars per hour that can travel from east to west?
11-14 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 poten- tially 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 11.24. (Note that it makes no differ- ence which one is the main control site.)
11-15 One of our best customers has had a major plant breakdown and wants us to make as many widgets
*Note: means the problem may be solved with QM for Windows.
1
2
4
5
7
63 8 12
14
9 13
11 10
1
3 7 7 4
5
5 332
2
4 4
5
6
7
4
3
3
6 6
5
FIGURE 11.21 Network for Problem 11-9
8 4
6
3 1
25
7
2
0
0
2
2
2 2 2
0 2
2
2 04
4 3 1
1
2 5
0
1
FIGURE 11.22 Network for Problem 11-10
450 CHAPTER 11 • NETWORK MODELS
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 11.25 will produce a widget. How many widgets can we produce per day? Quantities given are number of widgets per day.
11-16 Transworld Moving, like other moving companies, closely follows the impact of road construction to make sure that its routes remain the most efficient. Unfortunately, there has been unexpected road construction due to a lack of planning for road repair
around the town of New Haven, represented by node 9 in the network. (See Problem 11-11.) All roads leading to node 9, except the road from node 9 to node 11, can no longer be traveled. Does this have any impact on the route that should be used to ship the office furniture and equipment of Cohen Proper- ties to their new headquarters?
11-17 Solve the minimal-spanning tree problem in the net- work shown in Figure 11.26. Assume that the numbers in the network represent distance in hundreds of yards.
11-18 Refer to Problem 11-17. What impact would chang- ing the value for path 6–7 to 500 yards have on the solution to the problem and the total distance?
1 3
4
2
6
5
9
8
7
11
10
12
13
10 0
1301 00
120
70
100 60
100
100
50
40 20
100
40
100
100
200
100
50
50
Old Office
New Office
FIGURE 11.23 Network for Problem 11-11
75
65
50 37
53
56
41
48 23
26
1
2
3
4
5
6
FIGURE 11.24 Network for Problem 11-14
40
110
127 55
32160
70
45
200
1 2
3
5
4
6
FIGURE 11.25 Network for Problem 11-15
DISCUSSION QUESTIONS AND PROBLEMS 451
1
2
3
4
5
6
7
8 93
4 7
4
3
3
5
2
3
4
4
5
2 8
1
FIGURE 11.26 Network for Problem 11-17
11-19 The road system around the hotel complex on Inter- national Drive (node 1) to Disney World (node 11) in Orlando, Florida, is shown in the network of Figure 11.27. 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?
11-20 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 11-19). 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?
11-21 Refer to Problem 11-19 and model this problem us- ing linear programming. Solve it with any software.
11-22 In Problem 11-21, a linear program was developed for the road system at Disney World. Modify this linear program to make the changes detailed in Problem 11-20. Solve this problem and compare it to the solution without the changes.
11-23 Solve the maximal-flow problem presented in the net- work of Figure 11.28 below. The numbers in the net- work represent thousands of gallons per hour as they flow through a chemical processing plant.
11-24 Two terminals in the chemical processing plant, rep- resented by nodes 6 and 7, require emergency repair (see Problem 11-23). No material can flow into or out of these nodes. What impact does this have on the capacity of the network?
11-25 Solve the shortest-route problem presented in the network of Figure 11.29 below, going from node 1 to
1
2 6
7
9
10
11
8
3
4
5
4
15
14 2
15
4
1
3
2 0
3
3
1
0
0
0 8
8
8 8 00
08
2
10
10 0
FIGURE 11.27 Network for Problem 11-19
1 3
4
2 5
6
7
8
11
13
12 9
10 144
1 1
3
3
2 2
2 1
1 1 4
0
2 2
2 1
6 0
3 1
5 0
6 05
2
1
0
4 41 0
0
3 1 5
1
FIGURE 11.28 Network for Problem 11-23
1 3
4
2
5
6
7
8 12
11
10
9
13
14
15
1615
20
11
8
12
22
12
18
10
10 16
16 12
18
18
20
15
15
25
16
17
14
1810
FIGURE 11.29 Network for Problem 11-25
452 CHAPTER 11 • NETWORK MODELS
node 16. All numbers represent kilometers between German towns near the Black Forest.
11-26 Due to bad weather, the roads going through nodes 7 and 8 have been closed (see Problem 11-25). 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.
11-27 Refer to Problem 11-25 and model this problem using linear programming. Solve it with any software.
11-28 In Problem 11-27, a linear program was developed for the shortest-route problem. Modify this linear program to make the changes detailed in Problem 11-26. Solve this problem and compare it to the so- lution without the changes.
11-29 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. (a) What is the least expensive way to run cable to
the houses?
START END COST BRANCH NODE NODE ($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
START END COST BRANCH NODE NODE ($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
11-30 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. (a) 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.
DISTANCE START END (IN HUNDREDS
BRANCH NODE NODE 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 (b) 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?
(b) George Olin made a mistake in estimating the distances from Quincy to Old Bainbridge. The new distances are in the following table. What
DISCUSSION QUESTIONS AND PROBLEMS 453
DISTANCE START END (IN HUNDREDS
BRANCH NODE NODE 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
impact does this have on the shortest route from Quincy to Old Bainbridge?
START END REVERSE BRANCH NODE NODE CAPACITY 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
START END REVERSE BRANCH NODE NODE CAPACITY 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
(b) South Side Oil and Gas needs to modify its pipe- line network flow patterns. The new data is in the following table. What impact does this have on the maximum flow through the network?
11-32 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 to find the minimum distance required to con- nect 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
11-33 The network in Figure 11.30 represents streets of a city with the indicated number of cars per hour that can travel these streets. Find the maximum number of cars that could travel per hour through this sys- tem. How many cars would travel on each street (arc) to allow this maximum flow?
11-34 Refer to Problem 11-33. How would the maximum number of cars be affected if the street from node 3 to node 6 were temporarily closed?
11-35 Use the shortest route algorithm to determine the min- imum distance from node 1 to node 7 in Figure 11.31. Which nodes are included in this route?
11-31 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 is given in the following table. (a) What is the maximum that can flow through the
network?
454 CHAPTER 11 • NETWORK MODELS
11-36 Northwest University is in the process of completing a computer bus network that will connect computer facilities throughout the university. The prime objec- tive is to string a main cable from one end of the campus to the other (nodes 1–25) through under- ground conduits. These conduits are shown in the network of Figure 11.32; the distance between them is in hundreds of feet. Fortunately, these under- ground conduits have remaining capacity through which the bus cable can be placed. (a) Given the network for this problem, how far (in
hundreds of feet) is the shortest route from node 1 to node 25?
(b) 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 net- work: 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?
(c) 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 ca- ble is needed for node 1 to node 25. Unfortu- nately, 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?
1 3 6 8
2 5
4 7
60 0
60
80
0 0
0
0
0
0
0
30
30
80
60
70
0
20
20
0
3040 50
70
90
30 50
40
FIGURE 11.30 Network for Problem 11-33
1 4 7
2 5
3 6
9
3
6 7
4 4
3
7
4 5
8
8
FIGURE 11.31 Network for Problem 11-35
1
2
3
4
9
8
7
6
5
10
11
12
13
16
17
15
14 18
19
20
21
24
23
22
25
10
9
10
15
7
6
10
15
17
8 6 20
10 10
8
8
8 5
5
5
5
6
6
6
7
7
20
8
15
FIGURE 11.32 Network for Problem 11-36
CASE STUDY 455
Case Study
Binder’s Beverage
Bill Binder’s business nearly went under when Colorado al- most passed the bottle bill. Binder’s Beverage produced soft drinks for many of the large grocery stores in the area. After the bottle bill failed, Binder’s Beverage flourished. In a few short years, the company had a major plant in Denver with a warehouse in east Denver. The problem was getting the fin- ished product to the warehouse. Although Bill was not good with distances, he was good with times. Denver is a big city with numerous roads that could be taken from the plant to the warehouse, as shown in Figure 11.33.
The soft drink plant is located at the corner of North Street and Columbine Street. High Street also intersects North and Columbine Street at the plant. Twenty minutes due north of the plant on North Street is I-70, the major east–west highway in Denver.
North Street intersects I-70 at Exit 135. It takes five minutes driving east on I-70 to reach Exit 136. This exit connects I-70 with High Street and 6th Avenue. Ten minutes east on I-70 is Exit 137. This exit connects I-70 with Rose Street and South Avenue.
From the plant, it takes 20 minutes on High Street, which goes in a northeast direction, to reach West Street. It takes an- other 20 minutes on High Street to reach I-70 and Exit 136.
It takes 30 minutes on Columbine Street to reach West Street from the plant. Columbine Street travels east and slightly north.
West Street travels east and west. From High Street, it takes 15 minutes to get to 6th Avenue on West Street. Columbine Street also comes into this intersection. From this intersection, it takes an additional 20 minutes on West Street to get to Rose Street, and another 15 minutes to get to South Avenue.
From Exit 136 on 6th Avenue, it takes 5 minutes to get to West Street. Sixth Avenue continues to Rose Street, requiring 25 minutes. Sixth Avenue then goes directly to the warehouse. From Rose Street, it takes 40 minutes to get to the warehouse on 6th Avenue.
At Exit 137, Rose Street travels southwest. It takes 20 min- utes to intersect with West Street, and another 20 minutes to get to 6th Avenue. From Exit 137, South Avenue goes due south. It takes 10 minutes to get to West Street and another 15 minutes to get to the Warehouse.
Discussion Question
1. What route do you recommend?
See our Internet home page, at www.pearsonhighered.com/render, for additional homework problems 11-37 through 11-41.
Internet Homework Problems
2
1
4
3 5
6
10
97
8
Exit 135
Exit 136
Exit 137
I -70
North Street
Plant
West Street
Ro se
St re
et
Hi gh
S tre
et
Colum bine S
treet
6 th Avenue
S outh A
venue
Warehouse
FIGURE 11.33 Street Map for Binder’s Beverage Case
456 CHAPTER 11 • NETWORK MODELS
Case Study
Southwestern University Traffic Problems
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 com- plaints 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 Plan- ning 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 an- ticipated traffic problems, some of the current streets leading from the university to the interstate highway are being consid- ered for widening to increase the capacity. The current street ca- pacities with the number of cars (in 1,000s) per hour are shown in Figure 11.34. Since the major problem will be after the game, only the flows away from the stadium are indicated. These flows include some streets closest to the stadium being trans- formed into one-way streets for a short period after each game with police officers directing traffic.
Alexander Lee, a member of the University Planning Com- mittee, has said that a quick check of the road capacities in the diagram in Figure 11.34 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 sug- gested that the current capacity is 33,000 cars per hour. He has also suggested that a recommendation be made to the city man- ager for expansion of one of the routes from the stadium to the highway to permit an additional 2,000 cars per hour. He recom- mends expanding whichever route is cheapest. If the city chooses not to expand the roads, it is felt that the traffic prob- lem 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 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.
Discussion Questions 1. If there is no expansion, what is the maximum number of
cars that may actually travel from the stadium to the inter- state per hour? Why is this number not equal to 33,000, as Dr. Lee suggested?
2. If the cost for 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?
1
2
4
3
5
6
7
8
4
Stadium Interstate12 0 6 8
0
0 7
5 55
0 0
0
12 0
80
6
160
15
0
0
FIGURE 11.34 Roads from Stadium to interstate
See our Internet home page, at www.pearsonhighered.com/render, for the additional case study Ranch Development Project, which involves finding the least-cost way to provide water and sewer services to homes in a new housing development.
Internet Case Study