Simplex Algorithm
Student's Night Out Problem
To illustrate the Shortest Path Problem, we will find the shortest path from node 1 (Engineering Building) to node 14 (Springbok’s).
Our network will have fourteen nodes, node i (i = 1;2;3;…;14). For i<j, an arc length, (i, j), corresponds to the distance (call it lij) between the nodes.
lij = The direct length (distance) of a single arc between Node i and Node j
Applying this formula to the information in the problem, yields:
Our network will have fourteen nodes, node i (i = 1;2;3;…;14). For i<j, an arc length, (i, j), corresponds to the distance (call it lij) between the nodes.
lij = The direct length (distance) of a single arc between Node i and Node j
Applying this formula to the information in the problem, yields:
l12 = 1200
l13 = 1400 l14 = 1100 l25 = l12 + 550 l26 = l12 + 350 l27 = l12 + 750 l36 = l13 + 100 l38 = l13 + 500 l45 = l14 + 50 l47 = l14 + 950 l48 = l14 + 350 l59 = l25 + 240 OR l45 + 240 l610 = l26 + 200 OR l36 +200 |
l79 = l27 + 700 OR l47 + 700
l710 = l27 + 800 OR l47 + 800 l89 = l38 + 100 OR l48 + 100 l911 = l59 + 500 OR l79 + 500 OR l89 + 500 l912 = l59 + 350 OR l79 + 350 OR l89 + 350 l913 = l59 + 130 OR l79 + 130 OR l89 + 130 l1011 = l610 + 750 OR l710 + 750 l1012 = l610 + 800 OR l710 + 800 l1114 = l911 +30 l1214 = l912 + 180 OR l1012 + 180 l1314 = l913 + 450 |
Analyzingthe formulas, the following 26 paths are available:
1200 + 550 + 240+ 130 + 390 = 2510
1100 + 50 + 240 + 130 + 390 = 1910 1200 + 750 + 700 + 130 + 390 = 170 1100 + 950 + 700 + 130 + 390 = 3270 1400 + 500 + 100 + 130 + 390 = 2520 1100 + 350 + 100 + 130 + 390 = 2070 1200 + 350 + 200 + 800 + 180 = 2730 1400 + 100 + 200 + 800 + 180 = 2680 1200 + 750 + 800 + 800 + 180 = 3730 1100 + 950 + 800 + 800 + 180 = 3830 1200 + 550 + 240 + 350 + 180 = 2520 1100 + 50 + 240 + 350 + 180 = 1920 1200 + 750 + 700 + 350 + 180 = 3180 |
1100 + 950 + 700 + 350 + 180 = 3280
1400 + 500 + 100 + 350 +180 = 2530 1100 + 350 + 100 + 350 +180 = 2080 1200 + 550 + 240 + 500 + 40 = 2530 1100 + 50 + 240 + 500 + 40 = 1930 1200 + 750 + 700 + 500 + 40 = 3190 1100 + 950 + 700 + 500 + 40 = 3290 1400 + 500 + 100 + 500 + 40 = 2540 1100 + 350 + 100 + 500 + 40 = 2090 1200 + 350 + 100 + 500 + 40 = 2190 1400 + 100 + 200 + 750 + 40 = 2490 1200 + 750 + 800 + 750 + 40 = 3540 1100 + 950 + 800 + 750 + 40 = 3640 |
From the paths available it is clear that the three shortest paths are as follow:
1100 + 50 + 240 + 500 + 40 = 1930
1100 + 50 + 240 + 350 + 180 = 1920
1100 + 50 + 240 + 180 + 390 = 1910
From the paths available it is clear that the three shortest paths are as follow:
Node1 - Node4 - Node5 - Node9 - Node11 - Node14
Node1 - Node4 - Node5 - Node9 - Node12 - Node14
Node1 - Node4 - Node5 - Node9 - Node13 - Node14
They all have the following first three nodes in common:
[Node1 Node4 Node5 Node9]
The single shortest path can be deducted,
1100 + 50 + 240 + 180 + 390 = 1910
[l14, l45, l59, l913, l1314]
[Node1 Node4 Node5 Node9 Node13 Node14]
The Shortest Path length (distance) from node 1 to node 14 is thus 1910m and follows the path above.
1100 + 50 + 240 + 500 + 40 = 1930
1100 + 50 + 240 + 350 + 180 = 1920
1100 + 50 + 240 + 180 + 390 = 1910
From the paths available it is clear that the three shortest paths are as follow:
Node1 - Node4 - Node5 - Node9 - Node11 - Node14
Node1 - Node4 - Node5 - Node9 - Node12 - Node14
Node1 - Node4 - Node5 - Node9 - Node13 - Node14
They all have the following first three nodes in common:
[Node1 Node4 Node5 Node9]
The single shortest path can be deducted,
1100 + 50 + 240 + 180 + 390 = 1910
[l14, l45, l59, l913, l1314]
[Node1 Node4 Node5 Node9 Node13 Node14]
The Shortest Path length (distance) from node 1 to node 14 is thus 1910m and follows the path above.
shortest_path_problem.pptx | |
File Size: | 55 kb |
File Type: | pptx |