Waiting Lines and Queuing Theory Models
Minimal Spanning Tree In this tutorial, we will cover the concept of minimal spanning tree, or finding the shortest distance to connect all nodes in a network. Note that this is not the shortest path through the network, but rather the shortest distance to connect all nodes.
In this example, we have 14 houses in a new housing development and need to install power lines to connect all the houses, minimizing the total length of wire that is used, thus minimizing our cost. The house numbers and distances between the houses in feet are given in the table below–taken from the network above (Figure 21, p. 309 in your textbook).
House 1 House 2 Distance
1 3 1
1 4 2
1 2 4
2 5 5
3 4 2
3 6 3
4 5 4
4 7 5
5 7 6
5 10 7
6 7 3
6 8 7
7 9 6
8 12 7
8 9 3
9 10 4
7 5
3
4
6 3 4 4
2 3 3 5
5
4
1
3
1
2 5
4
6
7
10
8 12
9
11
13
14
3 7 7
6 6 5 2
9 12 5
9 13 6
10 11 3
11 13 3
12 14 4
13 14 5
Open POM QM for Windows and select Networks from the Module dropdown menu.
Then click File New Minimum Spanning Tree.
A Create data set for Networks/Minimum Spanning Tree window will display. Enter 22 for Number of Branches and make sure Branch 1, Branch 2, Branch 3, … is selected.
Click OK. A table will display. Now enter the information from the table at the beginning of the tutorial as shown here. In this case, House 1 data will go under Start node, House 2 data will go under End node, and the distance data will go under Cost.
Now click Solve.
We can see from our solution that we connect 1 to 3, 1 to 4, 1 to 2, 3 to 6, 4 to 5, 6 to 7, 7 to 9, 8 to 9, 9 to 10, 9 to 12, 10 to 11, 11 to 13, and 12 to 14. Alternate solutions can be found by substituting 3 to 4 for 1 to 4 and substituting 13 to 14 for 9 to 12. The total distance = 45. This concludes the tutorial on minimal spanning tree, or finding the shortest distance to connect all nodes in a network.