Quantitative Analysis for Management, 11e (Render)
Chapter 11 Network Models
1) The minimal–spanning tree technique finds the shortest route to a series of destinations.
2) In the minimal–spanning tree technique, it is necessary to start at the last node in the network.
3) The maximal–flow technique would be helpful to city planners in determining how freeways should be
expanded.
4) The minimal–spanning tree technique determines the path through the network that connects all the points
while minimizing total distance.
5) The shortest–route technique is the same as the minimal–spanning tree technique.
6) Busy highways are often analyzed with the maximal–flow technique.
7) Transportation companies would definitely be interested in the shortest–route technique to optimize travel.
8) Cable television companies would employ the shortest–route technique to lay out the cables connecting
individual houses.
9) We may begin the maximal–flow technique by picking an arbitrary path through the network.
10) The maximal–flow technique finds the maximum flow of any quantity or substance through a network.
11) The maximal–flow technique might be used by the U.S. Army Corps of Engineers to study water run–off in an
attempt to minimize the danger from floods.
12) The shortest–route technique might be used by someone planning a vacation in order to minimize the
required amount of driving.
13) The points on the network are referred to as nodes.
14) Lines connecting nodes on a network are called links.
15) A traveling salesperson might use the shortest route technique to minimize the distance traveled to reach one
of his/her customers.
16) In the minimal–spanning tree technique, if there is a tie for the nearest node, that suggests that there may be
more than one optimal solution.
17) The maximal–flow model might be of use to an engineer looking for spare capacity in an oil pipeline system.
18) The shortest–route model assumes that one is trying to connect two end points in the shortest manner
possible, rather than attempting to connect all the nodes in the model.
19) In the maximal–flow technique, a zero (0) means no flow or a one–way arc.
20) The maximal–flow model assumes that there is a net flow from “source” to “sink.”
21) If your goal was to construct a network in which all points were connected and the distance between them
was as short as possible, the technique that you would use is
A) shortest–route.
B) maximal–flow.
C) shortest–spanning tree.
D) minimal–flow.
E) minimal–spanning tree.
22) The minimal–spanning technique would best be used
A) to assign workers to jobs in the cheapest manner.
B) to determine LAN network wiring within a building.
C) to minimize traffic flow on a busy highway.
D) by a trucking company making frequent but repeatable drops.
E) to determine the number of units to ship from each source to each destination.
23) The maximal–flow technique would best be used
A) to assign workers to jobs in the cheapest manner.
B) to determine the number of units to ship from each source to each destination.
C) to determine LAN network wiring within a building.
D) to maximize traffic flow on a busy highway.
E) by a trucking company making frequent but repeatable drops.
24) A line in a network that may represent a path or a route is called a(n) ________.
A) arc
B) branch
C) line
D) fork
E) sink
25) A point in the network, that is at the beginning or end of a route is called a(n) ________.
A) arc
B) branch
C) line
D) node
E) source
26) The final node or destination in a network is called a(n) ________.
A) arc
B) branch
C) source
D) mouth
E) sink
27) The origin or beginning node in a network is called ________.
A) home
B) delta
C) source
D) mouth
E) sink
28) A technique that allows a researcher to determine the greatest amount of material that can move through a
network is called
A) maximal–flow.
B) maximal–spanning.
C) shortest–route.
D) maximal–tree.
29) The first step in the maximal–flow technique is to
A) pick the node with the maximum flow.
B) pick any path with some flow.
C) eliminate any node that has a zero flow.
D) add a dummy flow from the start to the finish.
E) None of the above
30) The shortest–route technique would best be used to ________
A) assign workers to jobs in the cheapest manner.
B) determine the number of units to ship from each source to each destination.
C) determine the amount of LAN network wiring within a building.
D) minimize the amount of traffic flow on a busy highway.
E) determine the path for a truck making frequent but repeatable drops.
31) When using the shortest–route technique, the first step is to
A) connect the nearest node that minimizes the total distance to the origin.
B) trace the path from the warehouse to the plant.
C) determine the average distance traveled from source to end.
D) find the nearest node to the origin and put a distance box by the node.
E) None of the above
32) The shortest–route technique might be logically used for
A) finding the longest time to travel between two points.
B) finding the shortest travel distance between two points.
C) finding the most scenic route to allow travel to several places during a trip on spring break.
D) connecting all the points of a network together while minimizing the distance between them.
E) None of the above
33) All the nodes must be connected in which of the following techniques?
A) minimal–flow
B) maximal–spanning tree
C) shortest–route
D) maximal–flow
E) minimal–spanning tree
34) The minimal–spanning tree technique would best be used
A) by a forest ranger seeking to minimize the risk of forest fires.
B) by a telephone company attempting to lay out wires in a new housing development.
C) by an airline laying out flight routes.
D) None of the above
E) All of the above
35) Which of the following techniques is not discussed in Chapter 11?
A) shortest–route
B) maximal–flow
C) linear programming
D) minimal–flow
E) minimal–spanning tree
36) The maximal–flow technique might be used
A) to help design the moving sidewalks transporting passengers from one terminal to another in a busy airport.
B) by someone designing the traffic approaches to an airport.
C) by someone attempting to design roads that would limit the flow of traffic through an area.
D) All of the above
E) None of the above
37) Which of the following problems can be solved using linear programming?
A) maximal–flow problem
B) shortest–route problem
C) minimal–spanning tree problem
D) A and B
E) A, B, and C
38) Which of the following problems can be solved as a linear program using binary decision variables?
A) maximal–flow problem
B) shortest–route problem
C) minimal–spanning tree problem
D) A and B
E) A, B, and C
7
39) Which of the following problems can be solved as a linear program using integer decision variables?
A) maximal–flow problem
B) shortest–route problem
C) minimal–spanning tree problem
D) A and B
E) A, B, and C
40) The second step in the maximal–flow technique is to
A) pick the node with the maximum flow.
B) pick any path with some flow.
C) decrease the flow as much as possible.
D) add capacity to the path with minimum flow.
E) find the arc on the previously chosen path with the smallest flow capacity available.
41) The shortest–route technique would best be used to
A) plan the routes for a vacation driving tour.
B) plan the route for a school bus.
C) determine the path for a truck making frequent runs from a factory to a warehouse.
D) All of the above
E) None of the above
42) When using the shortest–route technique, the second step is to
A) find the next–nearest node to the origin and put the distance in a box by the node.
B) trace the path from the warehouse to the plant.
C) determine the average distance traveled from source to end.
D) find the nearest node to the origin and put a distance box by the node.
E) None of the above
43) In network models, the lines connecting the nodes are called ________.
A) bridges
B) arrows
C) spans
D) arcs
E) links
44) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 300
2 3 150
1 3 200
A) 450
B) 150
C) 350
D) 650
E) None of the above
45) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 200
1 3 300
2 3 350
2 4 350
3 4 250
A) 100
B) 750
C) 850
D) 900
E) None of the above
46) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 100
2 4 150
1 3 200
2 3 50
3 4 175
4 5 250
3 5 300
A) 100
B) 150
C) 550
D) 1225
E) None of the above
47) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 100
1 3 50
2 3 200
2 5 325
1 4 50
3 4 350
3 5 400
4 5 450
A) 300
B) 525
C) 675
D) 1925
E) None of the above
48) Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 3.
From
Node To
Node Fluid
Flow
1 3 400
3 1 100
1 2 300
2 1 0
2 3 100
3 2 100
A) 100
B) 400
C) 500
D) 700
E) None of the above
49) Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 4.
From
Node To
Node Fluid
Flow
1 2 400
2 1 0
1 4 200
4 1 200
1 3 200
3 1 0
2 4 200
4 2 200
3 4 300
4 3 300
A) 200
B) 300
C) 600
D) 700
E) None of the above
50) Find the shortest route from Node 1 to Node 4 using the shortest–route technique.
From
Node To
Node
Distance
1 2 300
1 3 200
2 3 50
2 4 250
3 4 450
A) 650
B) 450
C) 550
D) 500
E) 800
51) Find the shortest route from Node 1 to Node 4.
From
Node To
Node
Distance
1 2 250
1 3 400
1 4 600
2 3 50
2 4 300
3 4 200
A) 750
B) 500
C) 550
D) 600
E) 50
52) Find the shortest route from Node 1 to Node 6.
From
Node To
Node
Distance
1 2 150
1 3 200
2 4 200
2 3 50
4 6 100
3 4 300
3 5 350
5 6 100
A) 300
B) 450
C) 550
D) 650
E) None of the above
53) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 120
2 3 100
1 3 200
2 4 150
3 5 90
4 5 170
A) 290
B) 310
C) 620
D) 460
E) None of the above
54) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 200
1 3 300
1 5 400
2 3 300
2 4 400
3 4 200
3 5 200
4 5 100
4 6 300
5 6 400
A) 1000
B) 800
C) 700
D) 1100
E) None of the above
55) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 100
1 3 200
2 3 100
2 4 150
2 5 200
3 4 150
3 5 300
4 5 250
4 6 200
5 6 100
A) 900
B) 650
C) 400
D) 1200
E) None of the above
56) Given the following distances between destination nodes, what is the minimum distance that connects all the
nodes?
From To Distance
1 2 100
1 3 50
2 3 200
2 5 300
1 4 50
3 4 350
3 5 400
3 6 400
4 5 450
4 6 350
5 6 200
A) 900
B) 1200
C) 1100
D) 700
E) None of the above
57) Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 4.
From
Node To
Node Fluid
Flow
1 3 200
3 1 0
1 2 150
2 1 50
2 3 100
3 2 100
3 4 150
4 3 50
A) 100
B) 150
C) 200
D) 50
E) None of the above
58) Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 5.
From
Node To
Node Fluid
Flow
1 2 300
2 1 0
1 3 0
3 1 150
1 4 200
4 1 200
1 5 100
5 1 100
2 4 200
4 2 200
3 4 250
4 3 300
3 5 300
5 3 250
4 5 100
5 4 0
A) 300
B) 400
C) 600
D) 500
E) None of the above
59) Find the shortest route from Node 1 to Node 5 using the shortest–route technique.
From
Node To
Node
Distance
1 2 200
1 3 150
2 3 50
2 4 300
3 4 250
3 5 200
4 5 150
A) 350
B) 400
C) 450
D) 600
E) None of the above
60) Find the shortest route from Node 1 to Node 5.
From
Node To
Node
Distance
1 2 250
1 3 150
1 4 200
2 3 50
2 4 150
3 4 150
3 5 100
2 5 150
A) 200
B) 350
C) 250
D) 450
E) None of the above