Homework SourseIn going from Quincy to Old Brainbridge there are 10 possibl
In going from Quincy to Old Brainbridge, there are 10 possible roads that George Olin can take. Each road can be considered a branch in the shortest-route problem.
a) Determine the best way to get from Quincy (node 1) to Old Brainbridge (node 8) that will minimize total distance traveled.All distances are in hundreds of miles.
Branch
Start Node
End Node
Distance (in hundreds of miles)
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
b) George Olin made a mistake in estimating the distances from Quincy to Old Bainbridge.The new distances are in the following table.What impact does this have on the shortest route from Quincy to Old Bainbridge?
Branch
Start Node
End Node
Distance (in hundreds of miles)
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
| Branch | Start Node | End Node | Distance (in hundreds of miles) |
| 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 |
Solution
The shortest route problem has an objective to determine the shortest distance from one location to another. In a network this often involves determining the shortest route from one node to each of the other nodes. The points on the network are called nodes and the lines connecting the nodes are arcs. In the QM program in Excel the number of arcs are first entered and then the starting node, ending node and the capacity in each direction for each arc are entered. When the problem is solved one additional column labeled flow is added to the table and this column contains the optimal solution.
So, using this, we can say in A, answer is : all giving same distance that is 13.
And in b, it is Branch 2 + Branch 4 + Branch 7 + Branch 10
