Chapter 9 Transportation, Assignment, and Network Models

71) 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

72) Find the shortest route from Node 1 to Node 6.

From Node	To Node	Distance
1	2	150
1	3	200
2	3	100
2	4	200
2	5	50
3	4	350
3	5	300
4	6	100
5	6	100

A) 300

B) 450

C) 550

D) 650

E) None of the above

73) Given the following traffic flows, in hundreds of cars per hour, what is the maximum traffic flow from City 1 to City 7?

	From City	To City	Flow
1	1	2	4
2	1	3	8
3	1	5	5
4	2	1	0
5	2	4	3
6	2	5	3
7	3	1	0
8	3	5	3
9	3	6	1
10	4	2	3
11	4	5	3
12	4	7	4
13	5	1	1
14	5	2	0
15	5	3	2
16	5	4	0
17	5	6	1
18	5	7	5
19	6	3	1
20	6	5	4
21	6	7	1
22	7	4	2
23	7	5	1
24	7	6	0

A) 1200

B) 1400

C) 900

D) 800

E) None of the above

74) Solve the minimal-spanning tree problem defined below:

Branch	Start Node	End Node	Cost
1	1	3	5
2	1	2	1
3	2	4	3
4	2	5	4
5	3	4	6
6	4	6	2

A) total cost = 13

B) total cost = 15

C) total cost = 17

D) total cost = 11

E) None of the above

75) Find the shortest route from Node 1 to Node 6.

	From Node	To Node	Distance
1	1	2	100
2	1	4	215
3	2	3	70
4	2	4	200
5	2	5	110
6	3	4	320
7	4	5	200
8	4	6	200
9	5	6	200

A) total distance = 350

B) total distance = 410

C) total distance = 270

D) total distance = 520

E) None of the above

76) Given the following traffic flows, in hundreds of cars per hour, what is the maximum traffic flow from Town 1 to Town 7?

	From Town	To Town	Flow
1	1	2	4
2	1	3	7
3	1	5	9
4	2	1	0
5	2	4	3
6	2	5	5
7	3	1	1
8	3	5	3
9	3	6	4
10	4	2	3
11	4	5	1
12	4	7	0
13	5	1	1
14	5	2	0
15	5	3	3
16	5	4	0
17	5	6	5
18	5	7	1
19	6	3	1
20	6	5	6
21	6	7	3
22	7	4	5
23	7	5	2
24	7	6	0

A) max flow = 4 units

B) max flow = 6 units

C) max flow = 3 units

D) max flow = 9 units

E) None of the above

77) Find the shortest route from Node 6 to Node 1.

Branch	From Node	To Node	Distance
1	1	2	150
2	1	3	200
3	2	3	100
4	2	4	200
5	2	5	50
6	3	4	350
7	3	5	300
8	4	6	100
9	5	6	100

A) branches 9, 7, and 2

B) branches 8, 6, and 2

C) branches 8, 6, 7, and 1

D) branches 9, 5, and 1

E) None of the above

78) Given the pipeline fluid flows indicated below, determine the maximum flow from Node 1 to Node 5.

	From Node	To Node	Fluid Flow
1	1	2	300
2	2	1	0
3	1	3	0
4	3	1	150
5	1	4	200
6	4	1	200
7	1	5	100
8	5	1	100
9	2	4	200
10	4	2	200
11	3	4	250
12	4	3	300
13	3	5	300
14	5	3	250
15	4	5	100
16	5	4	0

A) 250

B) 300

C) 350

D) 450

E) None of the above

79) Find the least amount of cable that will allow Jack's Cable Company to connect the following nodes (houses).

From Node	To Node	Distance
1	2	250
1	3	150
1	4	400
2	3	50
2	4	100
3	4	200

A) 250

B) 400

C) 350

D) 300

E) None of the above

80) Given the following nodes and distances, determine the minimum length of cable necessary to connect all six nodes.

	From Node	To Node	Distance
1	1	2	150
2	1	3	200
3	2	3	100
4	2	4	200
5	2	5	50
6	3	4	350
7	3	5	300
8	4	6	100
9	5	6	100

A) 200

B) 300

C) 400

D) 500

E) None of the above

81) Given the following nodes and distances, determine the minimal length of cable necessary to connect all nodes, using Node 2 as the starting point.

	From	To	Distance
1	1	2	200
2	1	3	300
3	1	5	400
4	2	3	300
5	2	4	400
6	3	4	200
7	3	5	200
8	4	5	100
9	4	6	300
10	5	6	400

A) 1200

B) 1100

C) 900

D) 700

E) None of the above

82) A certain firm has four different operations that must be assigned to four locations. The profit (in thousands of dollars) associated with each operation at each location is presented below. The firm's vice president would like to assign the various operations so that the total profit is maximized. Find the appropriate assignments.

83) Four projects must be completed, and each of four employees will be assigned to work on exactly one of the four projects. The table below presents an estimate of the cost that each employee would incur if working on the respective projects. What is the minimum-cost assignment of workers to projects?

84) SE Appliances manufacturers refrigerators in Richmond, Charlotte, and Atlanta. Refrigerators then must be shipped to meet demand in Washington, New York, and Miami. The table below lists the shipping costs, supply, and demand information.

How many units should be shipped from each plant to each retail store in order to minimize shipping costs?

85) Neki Sports Company manufactures treadmills in factories located in Pittsburgh and Kansas City. These are shipped to regional distribution centers in Chicago, Phoenix, and Philadelphia. Ultimately they are delivered to supply houses in New York and Los Angeles. The available supplies at the factories, demands at the final destinations, and shipping costs are illustrated in the table below.

Formulate this problem as a linear program.

86) Neki Sports Company manufactures treadmills in factories located in Pittsburgh and Kansas City. These are shipped to regional distribution centers in Chicago, Phoenix, and Philadelphia. Ultimately they are delivered to supply houses in New York and Los Angeles. The available supplies at the factories, demands at the final destinations, and shipping costs are illustrated in the table below.

Determine how many units should be shipped for all possible origin and destination points (final or intermediate) in the distribution network in order to minimize shipping costs.

87) Find the shortest route from Node 1 to each of the other nodes in the transportation network represented below.

Route from Node	Distance
1 to 2	50
1 to 3	100
2 to 3	75
2 to 4	65
3 to 4	80
3 to 5	70
4 to 5	65
4 to 6	200
5 to 6	130

88) As part of the planning for a major office development project, it is necessary to install telephone line to the buildings. Information about the project is given below. The distances are provided in hundreds of feet. Which offices should be connected so that total wiring costs (i.e., total distance) are minimized? What is the total length of this?

Building	Distances (100s ft)
1 to 2	4
1 to 4	3
2 to 3	2
2 to 4	4
3 to 5	1
3 to 6	5
4 to 5	3
4 to 7	3
5 to 7	2
6 to 7	6

89) A cable company must provide service for 7 houses in a particular neighborhood. They would like to wire the neighborhood in a way to minimize the wiring costs (or distance). How should the cable company wire the neighborhood and what would be the minimal length of the network?

House	Distances (yards)
1 to 2	100
1 to 3	400
1 to 4	300
2 to 3	300
2 to 4	250
2 to 5	400
3 to 5	350
3 to 6	450
4 to 5	300
4 to 7	250
5 to 7	100
6 to 7	150

90) Given a network with the following distances:

From Node	To Node	Distance
1	2	4
1	3	1
2	3	2
2	4	3
3	4	6
3	5	3
3	6	9
4	5	7
5	6	5

(a) Determine which nodes should be connected to get the minimum distance from Nodes 1 through 6.

(b) Determine the minimum distance.