Categories

# Introduction to Management Science 11th Edition Taylor Test Bank

Product Code: 222
Availability: In Stock
Price: \$24.99
Qty:     - OR -

## Description

Introduction to Management Science, 11e (Taylor)
Chapter 7 Network Flow Models

1) A network is an arrangement of paths connected at various points through which items move.
Diff: 1 Page Ref: 290
Keywords: network flow models

2) Networks are popular because they provide a picture of a system and because a large number of systems can be easily modeled as networks.
Diff: 1 Page Ref: 290
Keywords: network flow models

3) Nodes represent junction points connecting branches.
Diff: 1 Page Ref: 290
Keywords: network flow models, nodes

4) Branches connect nodes and show flow from one point to another.
Diff: 1 Page Ref: 290
Keywords: network flow models, branches

5) The values assigned to branches typically represent distance, time, or cost.
Diff: 1 Page Ref: 291
Keywords: network flow models, branches

6) Flows in a network can only be in one direction.
Diff: 1 Page Ref: 290
Keywords: network flow models
7) The shortest route problem is to find the shortest distance between an origin and various destination points.
Diff: 1 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: shortest route problem

8) Once the shortest route to a particular node has been determined, that node becomes part of the permanent set.
Diff: 1 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem

9) The shipping company manager wants to determine the best routes for the trucks to take to reach their destinations. This problem can be solved using the minimal spanning tree.
Diff: 1 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills

10) The shortest route network problem could help identify the best route for pizza delivery drivers from the pizza parlor to a specific customer.
Diff: 2 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: network flow models, shortest route
AACSB: Analytic skills

11) The minimal spanning tree problem is to connect all nodes in a network so that the total branch lengths are minimized.
Diff: 1 Page Ref: 298
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

12) The first step of the minimal spanning tree solution to compute the distance of any path through the network.
Diff: 2 Page Ref: 299
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem
13) The last step of the minimal spanning tree solution method is to make sure all nodes have joined the spanning tree.
Diff: 2 Page Ref: 301
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

14) In a minimal spanning tree, the source and destination nodes must be connected along a single path.
Diff: 1 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

15) The choice of the initial node in the minimal spanning tree technique must be the first node.
Diff: 1 Page Ref: 301
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

16) The minimal spanning tree allows the visitation of each node without backtracking.
Diff: 2 Page Ref: 298-301
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

17) The shortest route network problem could help identify the best plan for running cables for televisions throughout a building.
Diff: 2 Page Ref: 298-299
Section Heading: The Minimal Spanning Tree Problem
Keywords: network flow models, shortest route, minimal spanning tree
AACSB: Analytic skills

18) Regardless of the number of nodes in a network, the minimal spanning tree always contains the two nodes with the shortest distance between them.
Diff: 2 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
19) Regardless of the number of nodes in a network, the minimal spanning tree never contains the two nodes with the greatest distance between them.
Diff: 2 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills

20) The goal of the maximal flow problem is to maximize the amount of flow of items from an origin to a destination.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

21) For a directed branch, flow is possible in only one direction.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

22) To determine the maximum possible flow of railroad cars through the rail system, they should first select the longest path from origin to destination and ship as much as possible on that path.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

23) The shortest route problem requires that there be a branch from each destination to every other destination.
Diff: 1 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: maximal flow problem

24) The maximal flow algorithm may end with capacity remaining at the source.
Diff: 2 Page Ref: 306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem
AACSB: Analytic skills
25) The source node is the input node in a maximal flow problem.
Diff: 1 Page Ref: 303-306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

26) The direction of the flow is not critical in the maximal flow problem.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

27) In networks with fewer than five nodes, the minimal spanning tree algorithm will yield answers identical to the maximal flow solution approach.
Diff: 1 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem

28) The maximal flow solution algorithm allows the user to choose a path through the network from the origin to the destination by any criteria.
Diff: 1 Page Ref: 304
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills

29) A traffic system could be represented as a network in order to determine bottlenecks using the maximal flow network algorithm.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: network flow models, maximal flow
AACSB: Analytic skills

30) In a network flow problem, ________ represent junction points connecting branches.
Diff: 1 Page Ref: 290
Keywords: network flow models, nodes
31) In a network flow problem, ________ connect nodes and show flow from one point to another.
Diff: 1 Page Ref: 290
Keywords: network flow models, branches

32) In a network flow problem, the values assigned to ________ typically represent distance, time, or cost.
Diff: 1 Page Ref: 291
Keywords: network flow models, branches

33) The shipping company manager wants to determine the best routes for the trucks to take to reach their destinations. This problem can be solved using the ________ solution technique.
Diff: 1 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills

34) The ________ connects all nodes in a network so that the total branch lengths are minimized.
Diff: 1 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

35) The goal of the ________ problem is to maximize the amount of flow of items from an origin to a destination.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

36) A ________ network model could be used to represent the capacity of a series of dams for flood control.
Diff: 2 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: network flow models, maximal flow
37) A courier service located at the south edge of downtown dispatches three bicycle couriers with identical sets of architectural renderings that must go to three different downtown law offices as quickly as possible. This problem is a likely candidate for analysis using ________.
Diff: 2 Page Ref: 291-292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

38) The shortest route problem formulation requires a statement that mandates that what goes in to a node must equal what comes out of that node. This is referred to as ________.
Diff: 2 Page Ref: 294
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

39) A company plans to use an automatic guided vehicle for delivering mail to ten departments. The vehicle will begin from its docking area, visit each department, and return to the docking area. Cost is proportional to distance traveled. The type of network model that best represent this situation is ________.
Diff: 2 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: network flow models, shortest route
AACSB: Analytic skills

40) Determining where to build roads at the least cost within a park that reaches every popular sight represents a ________ network model.
Diff: 1 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: network flow models, minimal spanning tree
AACSB: Analytic skills

41) A one-way street in a downtown area should be modeled as a(n) ________ branch in a maximal flow model.
Diff: 1 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: directed branch

42) In a typical network flow problem, the branches show flow from one node to the next. The nodes themselves are ________ points.
Diff: 1 Page Ref: 288
Keywords: network flow models, nodes

43) Once a decision maker has determined the shortest route to any node in the network, that node becomes a member of the ________.
Diff: 1 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution

44) Determining where to build one way roads at the least cost within a park that takes visitors to every popular sight and returns them to the entrance represents a ________ network model.
Diff: 2 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: network flow models, shortest route
AACSB: Analytic skills

45) Determining where capacity needs to be added within a series of one-way roads within a park represents a ________ model.
Diff: 2 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: network flow models, maximal flow
AACSB: Analytic skills

Figure 1. Delivery Routes

46) Consider the network diagram given in Figure 1. Assume that the amount on each branch is the distance in miles between the respective nodes. What is the shortest route from the source node (node 1) to nodes 2, 3, and 4? Indicate the total distance for each route.
Answer: (node 1) (node 2): 6 miles
(node 1) (node 2) (node 3): 8 miles
(node 1) (node 2) (node 4): 11 miles
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

47) Consider the network diagram given in Figure 1. Assume that the amount on each branch is the distance in miles between the respective nodes. What is the shortest route from the source node (node 1) to nodes 5 and 6? Indicate the total distance for each route.
Answer: (node 1) (node 2) (node 3) (node 5) : 13 miles
(node 1) (node 2) (node 4) (node 6): 13 miles
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

48) Consider the network diagram given in Figure 1. Assume that the amount on each branch is the distance in miles between the respective nodes. Also assume that it is not possible to travel from a node with a higher number to a node with a lower number. Write the constraint associated with the second node (node 2) for the 0-1 integer linear programming formulation of the shortest route problem.
Answer: X12 X24 X23 = 0
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: short route prob, integer linear prog form of the short route prob
AACSB: Analytic skills

49) Consider the network diagram given in Figure 1. Assume that the amount on each branch is the distance in miles between the respective nodes. Also assume that it is not possible to travel from a node with a higher number to a node with a lower number. Write the constraint associated with the fifth node (node 5) for the 0-1 integer linear programming formulation of the shortest route problem.
Answer: X35 + X45 X46 = 0
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: short route prob, integer linear prog form of the short route prob
AACSB: Analytic skills

50) Consider the network diagram given in Figure 1. Assume that the numbers on the branches indicate the length of cable (in miles) between each pair of the six nodes on a telecommunication network. What is the minimum number of miles of cable to be used to connect all six nodes?
Diff: 2 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal span tree prob, solution of minimal span tree prob
AACSB: Analytic skills
Pro-Carpet company manufactures carpets in Northwest Indiana and delivers them to warehouses and retail outlets. The network diagram given in the figure below shows the possible routes and travel times (in minutes) from the carpet plant to the various warehouses or retail outlets.

V = Valparaiso, P=Portage, G=Gary, Ha=Hammond, Hi=Highland, M = Merillville, L = Lansing

51) Determine the shortest route for a carpet delivery truck from the carpet plant in Valparaiso, Indiana, to warehouses in Hammond, Gary, and Merillville. State the total completion time in minutes or each route
Valparaiso Portage Merillville: 19 minutes
Valparaiso Portage Gary: 25 minutes
Valparaiso Portage Merillville Hammond: 30 minutes
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

52) Determine the shortest route for a carpet delivery truck from the carpet plant in Valparaiso, Indiana, to retail outlets in Portage, Highland, and Lansing. State the total completion time in minutes or each route
Valparaiso Portage: 13 minutes
Valparaiso Portage Merillville Hammond Highland: 35 minutes
Valparaiso Portage Merillville Hammond Lansing: 37 minutes
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills
53) Write the constraint associated with the Valparasio (source) node for the 0-1 integer linear programming formulation of the shortest route problem.
Answer: XVP + XVM = 1
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: short route prob, integer linear prog form of the short route prob
AACSB: Analytic skills

54) Write the constraint associated with the Lansing (destination) node for the 0-1 integer linear programming formulation of the shortest route problem.
Answer: XHi-L + XHa-L = 1
Diff: 2 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: short route prob, integer linear prog form of the short route prob
AACSB: Analytic skills

55) Draw the network associated with the following constraints for a shortest route problem.
X12 + X13 = 1
X12 X24 = 0
X13 X34 = 0
X24 + X34 X45 = 0
X45 = 1

Diff: 3 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: network flow problem, shortest route
AACSB: Analytic skills

Consider the following network, which shows the location of various facilities within a youth camp and the distances (in tens of yards) between each facility.

56) Walking trails will be constructed to connect all the facilities. In order to preserve the natural beauty of the camp (and to minimize the construction time and cost), the directors want to determine which paths should be constructed. Use this network to determine which paths should be built.
Answer: Minimal spanning tree shown in bold.

Diff: 1 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills
57) The camp nurse is stationed at Facility B. What is the shortest route from B to C?
Answer: B to G to E to C for a total of 30.
Diff: 1 Page Ref: 291-298
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills

Consider the following network, which shows the location of various facilities within a youth camp and the distances (in tens of yards) between each facility. There is a swampy area between facilities A and E.

58) Walking trails will be constructed to connect all the facilities. In order to preserve the natural beauty of the camp (and to minimize the construction time and cost), the directors want to determine which paths should be constructed. Use this network to determine which paths should be built.
Answer: Minimal spanning tree shown in bold.

Diff: 1 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills
59) A clean-up crew is stationed at facility D and wants to take the shortest route to each site. They usually clean up facilities C, E, A and F on the same day and therefore want the shortest route from D to each facility. Recommend a route for the crew to leave from D, clean up each facility one after the other, and return to facility D. (Assume all paths are accessible.)
Answer: D to E to F to C to A to D. Total distance = 47. This is really a small version of the traveling salesman problem. Doing the minimal spanning tree prior to this problem may be helpful.
Diff: 2 Page Ref: 291-298
Keywords: shortest route problem
AACSB: Analytic skills

60) A clean-up crew is stationed at facility F and wants to take the shortest route to each site. They usually clean up facilities B and A on the same day and therefore want the shortest route from F to each facility. Recommend a route for the crew to leave from F, clean up each facility A and B, and then return to facility F. (Assume all paths are accessible.)
Answer: F-E-G-B-D-A-C-F for a total of 77. (This is a small version of the traveling salesmen problem. Doing the minimal spanning tree prior to this problem may be helpful.). The clean-up crew may want to add additional facilities on the days they clean up A and B if they have time.
Diff: 2 Page Ref: 291-298
Keywords: shortest route problem
AACSB: Analytic skills
Refer to the figure below to answer the following questions.

Figure 3

61) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. Determine the maximal flow from source node 1 to destination node 9.
Diff: 3 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills

62) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. Determine the maximal flow on the following path: node 1 to node 2 to node 7 to destination node 9.
Diff: 2 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills

63) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. What is the objective function for the 0-1 integer linear programming formulation of the maximal flow problem?
Diff: 3 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: max flow prob, 0-1 integer linear prog formulation of the max flow prob
AACSB: Analytic skills
64) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. What is the input- output constraint associated with the first node of the network diagram for the 0-1 integer linear programming formulation of the maximal flow problem?
Answer: X91 X12 X13 X14 = 0
Diff: 3 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: max flow prob, 0-1 integer linear prog formulation of the max flow prob
AACSB: Analytic skills

65) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. What is the input-output constraint associated with the ninth node of the network diagram for the 0-1 integer linear programming formulation of the maximal flow problem?
Answer: X79 + X89 X91 = 0
Diff: 3 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: max flow prob, 0-1 integer linear prog formulation of the max flow prob
AACSB: Analytic skills

66) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. What is the capacity constraint associated with the branch from node 7 to node 9 of the network diagram for the 0-1 integer linear programming formulation of the maximal flow problem?
Diff: 3 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: max flow prob, 0-1 integer linear prog formulation of the max flow prob
AACSB: Analytic skills

67) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. What is the input-output constraint associated with the fifth node of the network diagram for the 0-1 integer linear programming formulation of the maximal flow problem?
Answer: X25 + X35 + X65 X56 X57 = 0
Diff: 3 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: max flow prob, 0-1 integer linear prog formulation of the max flow prob
AACSB: Analytic skills

68) Using the network shown and the conventional method discussed in your textbook, what are the first two nodes in the network and why? Now avoid convention and pick the first two nodes that must be part of the correct solution. Why is this the case?
Answer: Convention dictates that a solution begins with node 1 and proceeds to the nearest node, which is node 3 at a distance of 11. Tossing convention out, one should pick the two closest nodes, which in this network are nodes 4 and 5, separated by only 6 units.
Diff: 3 Page Ref: 299
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills

69) If the origin node for this network is node number 1 and flow proceeds from node 1 to node 6, what is the shortest route through the network?
Diff: 1 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills

70) The origin node for this network is node number 1 and flow proceeds from node 1 to node 6. If the distance from node three to node six doubles , what is the change in the shortest route through the network?
Answer: The shortest route changes from 1-3-6=21 to 1-4-5-6=29, so a total increase of 8.
Diff: 2 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills
71) The origin node for this network is node number 1 and flow proceeds from node 1 to node 6. If each of the three longest branches is reduced in length by 10, what is the change in the shortest route through the network?
Answer: The shortest route changes from 1-3-6=21 to 1-2-5-6=18 for a total decrease of 3.
Diff: 2 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

72) Consider the network shown in the figure. The architect decides to remove a few of the (undirected) arcs but still have each node connected to at least one other node within a single network. Which arcs should be removed and what is the total arc length that is removed?
Answer: The arcs to be removed are arcs 1-2=13, 2-5=17, 3-6=10, 1-4=15, for a total arc length removed of 13+17+10+15=55 units. The remaining arc length is 40. Not too shabby!
Diff: 2 Page Ref: 298-302
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills

73) In a network flow model, a directed branch
A) is a branch with a positive distance value.
B) is a branch in which flow is possible in only one direction.
C) is a branch on which the flow capacity is exhausted.
D) is a branch in which flow is not possible in either direction.
Diff: 2 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: directed branch

74) In a network modeling problem, the linear programming decision variables are given by
A) source node.
B) sink node.
C) network branches.
D) network nodes.
Diff: 2 Page Ref: 296
Section Heading: The Shortest Route Problem
Keywords: network flow model, linear programming decision variables
75) A branch where flow is permissible in either direction is a(n)
A) directed branch.
B) undirected branch .
C) labeled branch.
D) unlabeled branch.
Diff: 2 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: network flow model, branches

76) If we wanted to represent water resources as a network flow problem, which of the following would be represented as nodes?
A) canals
B) pumping stations
C) rivers
D) pipelines
Diff: 1 Page Ref: 290
Keywords: network flow model

77) If we wanted to represent an office layout as a network flow problem, which of the following would be represented as a branch?
A) offices
B) waiting areas
C) heating and ventilation systems
D) computer rooms
Diff: 1 Page Ref: 290
Keywords: network flow model

78) If we wanted to represent an urban transportation system as a network flow problem, which of the following would be represented as nodes?
A) streets
B) railway lines
C) street intersections
D) pedestrian right of ways
Diff: 1 Page Ref: 290
Keywords: network flow model
79) The shipping company manager wants to determine the best routes for the trucks to take to reach their destinations. This problem can be solved using the
A) shortest route solution technique.
B) minimal spanning tree solution method.
C) maximal flow solution method.
D) minimal flow solution method.
Diff: 2 Page Ref: 291
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills

80) In the linear programming formulation of the shortest route problem, the constraint for each node represents
A) capacity on each path.
B) conservation of flow.
C) capacity on each branch.
D) minimum flow.
Diff: 2 Page Ref: 96
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills

81) The first step in the shortest route solution method is to
A) select the node with the shortest direct route from the origin
B) determine all nodes directly connected to the permanent set nodes
C) arbitrarily select any path in the network from origin to destination
D) make sure that all nodes have joined the permanent set
Diff: 2 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem

Figure 2

82) Consider the network diagram given in Figure 2. Assume that the amount on each branch is the distance in miles between the respective nodes. What is the distance for the shortest route from the source node (node 1) to node 4?
A) 8
B) 9
C) 10
D) 11
Diff: 2 Page Ref: 295
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

83) Consider the network diagram given in Figure 2. Assume that the amount on each branch is the distance in miles between the respective nodes. What is the distance for the shortest route from the source node (node 1) to node 5?
A) 13
B) 14
C) 15
D) 16
Diff: 2 Page Ref: 295
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills
Pro-Carpet company manufactures carpets in Northwest Indiana and delivers them to warehouses and retail outlets. The network diagram given in figure below shows the possible routes and distances from the carpet plant in Valparaiso to the various warehouses or retail outlets.

V = Valparaiso, P=Portage, G=Gary, Ha=Hammond, Hi=Highland, M = Merillville, L = Lansing

84) What is the distance for the shortest route from the carpet plant in Valparaiso to retail outlet in Lansing, Illinois. State the total completion time in minutes.
A) 36
B) 37
C) 39
D) 41
Diff: 2 Page Ref: 295
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills

85) Determine the shortest route for a carpet delivery truck from the carpet plant in Valparaiso to retail outlet in Hammond.
A) 26
B) 28
C) 30
D) 32
Diff: 2 Page Ref: 295
Section Heading: The Shortest Route Problem
Keywords: shortest route problem, shortest route problem solution
AACSB: Analytic skills
86) The minimal spanning tree problem determines the
A) minimum amount that should be transported along any one path.
B) maximum amount that can be transported along any one path.
C) shortest distance between a source node and a destination node.
D) minimum total branch lengths connecting all nodes in the network.
Diff: 2 Page Ref: 298
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

87) The first step of the minimal spanning tree solution method is to
A) select any starting node.
B) select the node closest to the starting node to join the spanning tree.
C) select the closest node not presently in the spanning tree.
D) arbitrarily select any path in the network from origin to destination.
Diff: 2 Page Ref: 298
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem

88) The local Internet provider wants to develop a network that will connect its server at its satellite center in Valparaiso with the main city computer centers in Northwest Indiana to improve the Internet service and to minimize the amount of cable used to connect network nodes. If we represent this problem with a network,
A) the cities are branches and cables are nodes.
B) the cables are the branches and the cities are the nodes.
C) the length of cables in miles are the branches, and the cities are the nodes.
D) the cities are the branches and the length of cables in miles are the nodes.
Diff: 2 Page Ref: 298
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree problem
AACSB: Analytic skills

Figure 2

89) Consider the network diagram given in Figure 2. Assume that the numbers on the branches indicate the length of cable (in miles) six nodes on a telecommunication network. What is the minimum number of miles of cable to be used to connect all six nodes?
A) 16 miles
B) 17 miles
C) 18 miles
D) 19 miles
Diff: 2 Page Ref: 301
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal span tree prob, solution of minimal span tree prob
AACSB: Analytic skills

Consider the following network, which shows the location of various facilities within a youth camp and the distances (in tens of yards) between each facility. There is a swampy area between facilities A and E.

90) Walking trails will be constructed to connect all the facilities. In order to preserve the natural beauty of the camp (and to minimize the construction time and cost), the directors want to determine which paths should be constructed. What is the minimum number of paths (in tens of yards) that must be built to connect each facility?
A) 54
B) 56
C) 60
D) 65
Diff: 2 Page Ref: 301
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills

91) The objective of the maximal flow solution approach is to
A) maximize resource allocation .
B) maximize the total amount of flow from an origin to a destination.
C) determine the longest distance between an originating point and one or more destination points.
D) determine the shortest distance between an originating point and one or more destination points.
Diff: 2 Page Ref: 303
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem
92) The first step of the maximal flow solution method is to
A) arbitrarily select any path in the network from origin to destination.
B) select the node with the shortest direct route from the origin.
C) add the maximal flow along the path to the flow in the opposite direction at each node.
D) select any starting node.
Diff: 2 Page Ref: 306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem

93) The shortest route problem requires
A) each destination to be visited only once.
B) finding the quickest route from the source to each node.
C) that there be a branch from each destination to every other destination.
D) that there be no two-way branches between nodes.
Diff: 2 Page Ref: 282
Section Heading: The Shortest Route Problem
Keywords: shortest route problem

94) The maximal flow algorithm
A) does not require flow on every branch for the final solution.
B) may end with capacity remaining at the source.
C) may end with capacity at those nodes leading immediately to the destination.
D) all of the above
Diff: 2 Page Ref: 306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem
AACSB: Analytic skills
Refer to the figure below to answer the following questions.

Figure 3

95) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. Determine the maximal flow from source node 1 to destination node 9.
A) 10
B) 11
C) 12
D) 13
Diff: 2 Page Ref: 294-297
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills

96) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. Determine the maximal flow on the following path: node 1 to node 4 to node 3 to node 5 to node 8 to destination node 9.
A) 2
B) 3
C) 4
D) 5
Diff: 2 Page Ref: 306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills
97) Consider the network diagram given in Figure 3 with the indicated flow capacities along each branch. Determine the maximal flow on the following path: node 1 to node 2 to node 7 to destination node 9.
A) 3
B) 4
C) 5
D) 6
Diff: 2 Page Ref: 306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills

Figure 4

98) Determine the maximal flow through the network in Figure 4. Assume that all branches are directed branches.
A) 10
B) 11
C) 13
D) 16
Diff: 2 Page Ref: 306
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem
AACSB: Analytic skills
99) Determine the minimum distance required to connect all nodes in Figure 4.
A) 22
B) 24
C) 26
D) 30
Diff: 2 Page Ref: 291-293
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills

100) Which of these is the shortest route through the network?
A) 1-3-6
B) 1-2-5-6
C) 1-4-5-6
D) 1-2-4-5-6
Diff: 1 Page Ref: 292
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
AACSB: Analytic skills
101) This network has been targeted for the innovative new Redundancy Elimination program that offers a compromise between two competing factions. The plan is to remove paths one at a time until all of the nodes are interconnected without any loops in the network while minimizing the sum of all of the path lengths. Which of these paths is part of the new network?
A) 3-6
B) 1-3
C) 1-2
D) 2-5
Diff: 1 Page Ref: 299
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree

102) How much longer is the total arc length in the current network than twice the total arc length of the minimal spanning tree?
A) 5
B) 10
C) 15
D) 20
Diff: 2 Page Ref: 298
Section Heading: The Minimal Spanning Tree Problem
Keywords: minimal spanning tree
AACSB: Analytic skills

103) If the two shortest paths in this network are increased by 100%, and the two longest paths in this network are reduced by 50%, what is the shortest route through this network?
A) 10.5
B) 17.5
C) 19.5
D) 21
Diff: 2 Page Ref: 292-293
Section Heading: The Shortest Route Problem
Keywords: shortest route problem
104) Use the network pictured and assume all labeled flows are forward flows. Suppose the reverse flows for each path are exactly half of the forward flows. What is the maximum flow through this network?
A) 18
B) 28
C) 10
D) 8
Diff: 2 Page Ref: 303-309
Section Heading: The Maximal Flow Problem
Keywords: maximal flow problem, solution of the maximal flow problem
AACSB: Analytic skills

## Write a review

Your Review: Note: HTML is not translated!