Introduction to Management Science (10th Edition)

[Page 293 ( continued )]

The following example illustrates the solution methods for the shortest route and minimal spanning tree network flow problems.

Problem Statement

A salesman for Healthproof Pharmaceutical Company travels each week from his office in Atlanta to one of five cities in the Southeast where he has clients . The travel time (in hours) between cities along interstate highways is shown along each branch in the following network:

  1. Determine the shortest route from Atlanta to each of the other five cities in the network.

  2. Assume that the network now represents six different communities in a city and that the local transportation authority wants to design a rail system that will connect all six communities with the minimum amount of track. The miles between each community are shown on each branch. Develop a minimal spanning tree for this problem.

Solution

Step  1.

(Part A): Determine the Shortest Route Solution

[Page 294]
     

1. Permanent Set

Branch

Time

{1}

12

 

13

5

 

14

7

2. Permanent Set

Branch

Time

{1, 2}

13

14

7

 

25

11

3. Permanent Set

Branch

Time

{1, 2, 3}

14

 

25

11

 

34

7

4. Permanent Set

Branch

Time

{1, 2, 3, 4}

45

10

 

46

5. Permanent Set

Branch

Time

{1, 2, 3, 4, 6}

45

 

65

13

6. Permanent Set

   

{1, 2, 3, 4, 5, 6}

   

The shortest route network follows :

Step  2.

(Part B): Determine the Minimal Spanning Tree

  1. The closest unconnected node to node 1 is node 2.

  2. The closest unconnected node to 1 and 2 is node 3.

  3. The closest unconnected node to 1, 2, and 3 is node 4.

  4. The closest unconnected node to 1, 2, 3, and 4 is node 6.

  5. The closest unconnected node to 1, 2, 3, 4, and 6 is node 5.

The minimal spanning tree follows; the shortest total distance is 17 miles:

Related

Категории