# Example Problem Solution

[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:

Introduction to Management Science (10th Edition)
ISBN: 0136064361
EAN: 2147483647
Year: 2006
Pages: 358

Similar book on Amazon