Management Chapter 11 Homework Grey can make the necessary calculations using the minimal-spanning tree model

11-29. a. Given the problem data, Grey can use the minimal-spanning tree model to determine

the least-cost approach to connect all houses to cable TV. As seen below, Grey should use

branches 1, 2, 3, 4, 6, 8, 9, and 11.

Beginning Data

Start Node

End Node

Cost

Branch 1

1

2

5

Branch 2

1

3

6

Branch 3

1

4

6

Branch 4

1

5

Branch 5

2

6

7

Branch 6

3

7

5

Branch 7

4

7

Branch 8

5

8

4

Branch 9

6

7

1

Branch 10

7

9

6

Branch 11

8

9

2

Results

Start

End

Node

Cost

Include

Cost

Branch 1

1

2

5

Y

5

Branch 2

1

3

6

Y

6

Branch 3

1

4

6

Y

6

Branch 4

1

5

Y

5

Branch 5

2

6

7

Branch 6

3

7

5

Y

5

Branch 7

4

7

Branch 8

5

8

4

Y

4

Branch 9

6

7

1

Y

1

Branch 10

7

9

6

Branch 11

8

9

2

Y

2

Total

34

Solution steps

Starting

Ending

Cumulative

Branch

Node

Cost

Branch 11

8

9

2

Branch 8

5

8

4

6

Branch 4

1

5

Branch 1

1

2

5

Branch 2

1

3

6

Branch 6

3

7

5

Branch 9

6

7

1

11-29. b. Grey can make the necessary calculations using the minimal-spanning tree model. The

results are below.

Results

Start

End

Node

Cost

Include

Cost

Branch 1

1

2

5

Y

5

Branch 2

1

3

1

Y

1

Branch 3

1

4

1

Y

1

Branch 4

1

5

1

Y

1

Branch 5

2

6

7

Branch 6

3

7

5

Y

5

Branch 7

4

7

Branch 8

5

8

4

Y

4

Branch 9

6

7

1

Y

1

Branch 10

7

9

6

Branch 11

8

9

2

Y

2

Total

20

Solution steps

Starting

Ending

Cumulative

Branch

Node

Cost

Branch 11

8

9

2

Branch 8

5

8

4

6

Branch 4

1

5

1

7

Branch 2

1

3

1

8

Branch 3

1

4

1

9

Branch 1

1

2

5

Branch 6

3

7

5

11-30. a. Using the shortest-route technique, George can determine the best way to go from

Quincy to Old Bainbridge. The data and results are below. As can be seen, the shortest route is to

take branches 2, 4, 7, 8 and 9 with a minimum distance of 1,200 miles.

Start Node

End Node

Distance

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

Shortest Path

Total distance = 12

Start

End

Cumulative

Node

Distance

Branch 2

1

3

2

Branch 4

3

5

3

5

Branch 7

5

7

2

7

Branch 8

7

6

2

9

Branch 9

6

8

3

12

Minimum distance matrix

Node

1

2

3

4

Node 1

0

3

2

6

Node 2

3

0

5

3

Node 3

2

5

0

4

Node 4

6

3

4

0

Node 5

5

4

3

1

9

7

4

Node 7

7

6

5

3

Node 8

7

Node

5

6

7

8

Node 1

5

9

7

12

Node 2

4

7

6

10

Node 3

3

7

5

10

Node 4

1

4

3

7

Node 5

0

4

2

7

Node 6

4

0

2

3

Node 7

2

0

5

Node 8

7

3

5

0

11-30. b. George can use the shortest-route model to determine the impact of the changes. The

results are below. As you can see, the new shortest route is 1,000 miles (10 in the printout since

units are in 100s).

Start Node

End Node

Distance

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

Shortest Path

Total distance = 10

Start

End

Cumulative

Node

Distance

Branch 2

1

3

2

Branch 4

3

5

1

3

Branch 7

5

7

2

5

Branch 8

7

6

2

7

Branch 9

6

8

3

10

Minimum distance matrix

Node

1

2

3

4

Node 1

0

3

2

4

Node 2

3

0

5

3

Node 3

2

5

0

2

Node 4

4

3

2

0

Node 5

3

4

1

Node 6

7

5

4

Node 7

5

6

3

Node 8

10

8

7

Node

5

6

7

8

Node 1

3

7

5

10

Node 2

4

7

6

10

Node 3

1

5

3

8

Node 4

1

4

3

7

Node 5

0

4

2

7

Node 6

4

0

2

3

Node 7

2

0

5

Node 8

7

3

5

0

11-31. a. South Side Oil and Gas can use the maximal-flow technique to determine the maxi-

mum flow through the network. As seen in the tables below, two paths are used with a total flow

rate of 1,500 gallons.

Total Flow 15

Start

End

Reverse

Node

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

0

Branch 5

3

5

8

1

5

Branch 6

4

6

10

2

10

Branch 7

5

6

10

0

Branch 8

5

7

5

Branch 9

6

8

10

1

10

Branch 10

7

8

10

1

5

Iterations

Iteration

Path

Flow

Cumulative Flow

1

1→ 2→ 4→ 6→ 8

10

2

1→ 3→ 5→ 7→ 8

5

15

11-31. b. The results for South Side Oil and Gas are below. As you can see, the changes did not

have any impact on the maximal flow, which remains at 15 or 1,500 gallons. The calculations are

summarized below.

Total Flow 15

Start

End

Reverse

Node

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

Branch 5

3

5

8

1

5

Branch 6

4

6

10

2

10

Branch 7

5

6

10

0

Branch 8

5

7

5

Branch 9

6

8

10

1

10

Branch 10

7

8

10

1

5

Iterations

Iteration

1

2

11-32. Given the problem data, the network module in QM for Windows gives the following

minimal-spanning tree results. The branches 1–3, 3–2, 3–5, 5–4 and 5–6 are used to connect the

nodes, and the total distance is 40.

Start node

End node

Cost

Include

Cost

1

2

12

1

3

8

Y

8

2

3

7

Y

7

2

4

10

3

4

9

4

5

8

Y

8

4

6

11

5

6

9

Y

9

Figure for Problem 11-32

11-33. Using the maximal-flow technique in the network module of QM for Windows we have a

maximum flow of 190 as shown in the table.

Maximal Network Flow 190

Start

End

Reverse

Node

Capacity

Flow

Branch 1

1

2

80

0

80

Branch 2

1

3

50

0

50

Branch 3

1

4

60

0

60

Branch 4

2

3

30

20

Branch 5

2

5

60

0

60

Branch 6

3

4

40

Branch 7

3

5

70

0

10

Branch 8

3

6

60

0

50

Branch 9

4

7

80

0

70

Branch 10

5

6

20

Branch 11

5

8

90

0

80

Branch 12

6

7

30

Branch 13

6

8

70

0

60

Branch 14

7

8

50

0

50

Iteration

Path

Flow

Cumulative Flow

1

1→ 2→ 5→ 8

60

2

1→ 3→ 6→ 8

50

110

3

1→ 4→ 7→ 8

50

4

1→ 2→ 3→ 4→

20

180

7→ 6→ 5→ 8

5

1→ 4→ 3→

10

190

5→ 6→ 8

11-34. QM for Windows indicates that total capacity is not affected. Other streets can be used to

still accommodate 190 cars.

Cumulative

Iteration

Path

Flow

1

1→ 2→ 5→ 8

60

2

1→ 4→ 7→ 8

50

110

3

1→ 3→ 4→ 7→ 6→ 8

4

1→ 2→ 3→ 5→ 6→ 8

20

160

5

1→ 3→ 5→ 8

20

180

6

1→ 4→ 3→ 5→ 8

10

190

30

140

11-35. Using the shortest-route technique in QM for Windows, we find the minimum total dis-

tance to be 16 as shown in the table.

Start

End

Cumulative

Node

Distance

Branch 2

1

3

6

Branch 7

3

6

3

9

Branch 12

6

7

16

11-36. a. The solution is 4,900 feet. This is almost 1 mile. The solution along with the final

network is given below and on the next page.

Value

1–3

9

3–7

6

7–12

8

5

6

7

8

Shortest path:

Figure for Problem 11-36a

b. Eliminating the paths 6–11, 7–12, and 17–20 has changed the shortest route to 5,500 feet

(55). This is higher than the solution in part a, as you would expect. The solution (below)

along with the final network (on the next page) are given. When using the software, the dis-

tance for paths 6–11, 7–12, and 17–20 should be increased to a very high relative value

(10,000) to force the paths out of the solution.

Value

1–4

10

4–8

10

8–13

8

6

7

8

Shortest path:

Total shortest distance: 55.

Figure for Problem 11-36b

c. In addition to eliminating paths 6–11, 7–12, and 17–20 from the network, the paths used

in the solution presented in part b are also eliminated. Thus we eliminate the path 1–4–8–13–

16–20–23–25. Again, this is done in the software by increasing the distances along these

paths to a very high relative value (10,000) to force them out of the solution. The new short-

est path is 6,400 feet (64). The solution along with the final network follows.

Flow

1–2

10

2–5

15

5–10

8

5

6

15

Shortest path:

Total shortest distance: 64.

Figure for Problem 11-36c

SOLUTIONS TO INTERNET HOMEWORK PROBLEMS

11-37. The shortest distance from farm 1 to farm 6 is found using QM for Windows. The results

are: Total distance = 17

Start

End

Cumulative

Node

Cost

Distance

Branch 2

1

3

10

Branch 7

3

5

2

12

Branch 12

5

6

5

17

11-38. Using the minimal-spanning tree in QM for Windows, the minimum amount of cable is

22 miles.

Start

End

Cumulative

Node

Cost

Branch 1

1

2

8

Branch 3

2

3

4

12

Branch 7

3

5

2

14

Branch 8

4

5

3

17

Branch 10

5

6

5

22

11-39. Using the minimal-spanning tree in QM for Windows, the minimum amount of cable is

27 miles.

Start

End

Node

Cost

Include

Cost

Branch 1

1

2

8

Y

8

Branch 2

1

3

10

Branch 3

2

3

4

Y

4

Branch 4

2

4

9

Branch 5

2

5

Branch 6

3

4

6

Branch 7

3

5

2

Y

2

Branch 8

4

5

3

Y

3

Branch 9

4

6

Branch 10

5

6

5

Y

5

Branch 11

4

7

8

Branch 12

5

7

9

Branch 13

6

7

5

Y

5

Total

11-40. Using QM for Windows, the maximal flow is 7 hundred. The paths are

Iteration

Path

Flow

Cumulative Flow

1

1→ 3→ 4→ 6

3

11-41. The increased capacity from node 1 to node 3 does not increase the maximal flow. It is

still 7 hundred. There is already sufficient capacity from node 1.

SOLUTION TO BINDER’S BEVERAGE CASE

This is a shortest-route problem. With the data given in the problem, the shortest-route model

can be used to determine the minimum time in minutes required to go from the plant to the ware-

house in east Denver. The results are on the next page. As you can see, the best route is to take

North Street to I-70. At Exit 137, South Street is taken to the warehouse. This route takes one

hour (60 minutes).

Data

Start Node

End Node

Distance

North Street

1

2

20

I 70—A

2

4

5

I 70—B

4

8

10

High Street—A

1

3

20

High Street—B

3

4

20

Columbine Street

1

5

30

West Street—A

3

5

15

West Street—B

5

7

20

West Street—C

7

9

15

6 Ave—A

4

5

15

6 Ave—B

5

6

25

6 Ave—C

6

10

40

Rose Street—A

6

7

20

Rose Street—B

7

8

20

South Ave—A

8

9

10

South Ave—B

9

15

Shortest Path

Total distance = 60

Start

End

Cumulative

Node

Distance

North Street

1

2

20

I 70—A

2

4

5

25

I 70—B

4

8

10

35

South Ave—A

8

9

10

45

South Ave—B

9

10

15

60

Minimum distance matrix

Node

1

2

3

4

5

Node 1

0

20

25

30

Node 2

20

0

25

5

20

Node 3

20

25

0

20

15

Node 4

25

5

20

0

15

Node 5

30

20

15

0

Node 6

55

45

40

25

Node 7

50

35

30

20

Node 8

35

15

30

10

25

Node 9

45

25

40

20

35

Node 10

60

40

55

35

50

Node

6

7

8

9

10

Node 1

55

50

35

45

60

Node 2

45

35

15

25

40

Node 3

40

35

30

40

55

Node 4

40

30

10

20

35

Node 5

25

20

25

35

50

Node 6

20

40

35

40

Node 7

20

15

30

Node 8

40

20

10

25

Node 9

35

15

10

15

Node 10

40

30

25

15

SOLUTION TO SOUTHWESTERN UNIVERSITY TRAFFIC PROBLEMS

This is a maximal-flow problem. Using QM for Windows we have the following results:

Iteration

Path

Flow

Cumulative Flow

1

1→ 2→ 5→ 8

12

3

23

5

28

1. The capacity without any expansion is 28 (thousand) cars per hour. This would indicate that a

serious problem will exist if there are 33,000 cars per hour leaving the stadium. The problem is

2. To get the capacity to 33, we must add an additional 5 units. You could add 3 units of capacity

from node 1 to node 4. This matches the inflow to the outflow at node 4. Also, expanding the

SOLUTIONS TO INTERNET CASE

SOLUTION TO RANCH DEVELOPMENT PROJECT CASE

1. The minimum distance that will connect all houses to the water and sewer lines is 10,000 feet

(100). The solution along with the final network follows:

Start

End

Branch

Node

Cost

Include

Cost

Branch 1

1

2

3

Y

3

Branch 2

1

5

2

Y

2

Branch 3

2

3

1

Y

1

Branch 4

2

10

6

Branch 5

3

4

1

Y

1

Branch 6

3

8

5

Y

5

Branch 7

4

8

5

Branch 8

5

6

2

Y

2

Branch 9

5

10

5

Y

5

Branch 10

6

7

2

Y

2

Branch 11

6

11

4

Y

4

Branch 12

7

12

4

Branch 13

8

9

2

Y

2

Branch 14

9

13

7

Y

7

Branch 15

10

11

8

Branch 16

10

15

11

Branch 17

11

12

2

Y

2

Branch 18

11

16

8

Y

8

Branch 19

12

17

9

Branch 20

13

14

4

Y

4

Branch 21

13

18

6

Y

6

Branch 22

14

15

4

Y

4

Branch 23

15

20

7

Branch 24

16

22

8

Branch 25

17

23

8

Y

8

Branch 26

18

19

2

Y

2

Branch 27

19

20

2

Y

2

Branch 28

19

24

5

Y

5

Branch 29

20

21

4

Y

4

Branch 30

21

22

1

Y

1

Branch 31

21

25

4

Y

4

Branch 32

22

23

6

Y

6

Branch 33

22

25

5

Branch 34

23

26

7

Y

7

Branch 35

24

27

11

Branch 36

25

27

3

Y

3

Branch 37

26

27

10

2. Moving footprint number 16 to accommodate the expansion of the pond area has increased

the minimum total distance to 10,100 feet (101). A decision now has to be made about whether

the increased distance and cost for the water and sewer system is worth the additional expected

property prices. The solution along with the final network follows.

Start

End

Branch

Node

Cost

Include

Cost

Branch 1

1

2

3

Y

3

Branch 2

1

5

2

Y

2

Branch 3

2

3

1

Y

1

Branch 4

2

10

6

Branch 5

3

4

1

Y

1

3

8

5

Y

5

Branch 7

4

8

5

Branch 8

5

6

2

Y

2

Branch 9

5

10

5

Y

5

Branch 10

6

7

2

Y

2

Branch 11

6

11

4

Y

4

Branch 12

7

12

4

Branch 13

8

9

2

Y

2

Branch 14

9

13

7

Y

7

Branch 15

10

11

8

Branch 16

10

15

11

Branch 17

11

12

2

Y

2

Branch 18

11

16

9

Y

9

Branch 19

12

17

9

Branch 20

13

14

4

Y

4

Branch 21

13

18

6

Y

6

Branch 22

14

15

4

Y

4

Branch 23

15

20

7

Branch 24

16

22

12

Branch 25

17

23

8

Y

8

Branch 26

18

19

2

Y

2

Branch 27

19

20

2

Y

2

Branch 28

19

24

5

Y

5

Branch 29

20

21

4

Y

4

Branch 30

21

22

1

Y

1

Branch 31

21

25

4

Y

4

Branch 32

22

23

6

Y

6

Branch 33

22

25

5

Branch 34

23

26

7

Y

7

Branch 35

24

27

11

Branch 36

25

27

3

Y

3

Branch 37

26

27

10

Total