Solved Problem

Solved Problem M2-1

Lindsey Cortizan would like to travel from the university to her hometown over the holiday season. A road map from the university (node 1) to her home (node 7) is shown in Figure M2.9. What is the best route that will minimize total distance traveled?

A graph with 7 nodes and 9 edges illustrate the road map for Lindsey Cortizan.

Figure M2.9 Road Map for Lindsey Cortizan

Solution

The solution to this problem is identical to the one presented earlier in the chapter. First, the problem is broken into three stages. See the network in Figure M2.10. Working backward, we start by solving stage 3. The closest and only distance from node 6 to 7 is 13, and the closest and only distance from node 5 to node 7 is 10. We proceed to stage 2. The minimum distances are 52, 41, and 28 from node 4, node 3, and node 2 to node 7. Finally, we complete stage 3. The optimal solution is 50. The shortest route is 1–2–5–7 and is shown in the following network. This problem can also be solved using tables, as shown following the network solution.

A graph with 7 nodes and 9 edges illustrate the solution for Lindsey Cortizan problem.

Figure M2.10 Solution for the Lindsey Cortizan Problem

Problem type: Minimization network
Number of stages: 3
Transition function type: sn−1=sn−dn
Recursion function type: fn=rn+fn−1
STAGE NUMBER OF DECISIONS
3 3
2 4
1 2
STAGE STARTING NODE ENDING NODE RETURN VALUE
3 1 2 22
1 3 18
1 4 20
2 2 5 18
2 6 36
3 6 28
4 6 39
1 5 7 10
6 7 13
STAGE 1
s1 d1 r1 s0 f0 f1
6 6–7 13 7 0 13
5 5–7 10 7 0 10

STAGE 2
s2 d2 r2 s1 f1 f2
4 4–6 39 6 13 52
3 3–6 28 6 13 41
2 2–6 36 6 13 49
2–5 18 5 10 28
STAGE 3
s3 d3 r3 s2 f2 f3
1 1–4 20 4 52 72
1–3 18 3 41 59
1–2 22 2 28 50
FINAL SOLUTION
STAGE OPTIMAL DECISION OPTIMAL RETURN
3 1–2 22
2 2–5 18
1 5–7 10
Total 50
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset