Floyd's algorithm with route extraction

3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. Distance Matrix

\(\mathbf { 4 }\) & 9 & 7 & 6 & 12
\hline Route Matrix Fig. 3.1 \begin{figure}[h] \end{figure}

1. Draw the complete network of shortest distances.
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \begin{table}[h]

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	1	2	3	4
   5	-	3	-	1

   \captionsetup{labelformat=empty} \caption{Fig. 3.3}
   \end{table}
3. Draw the extended network and the complete 5 -node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.)
4. Produce the shortest distance matrix and the route matrix for the extended 5-node network.
5. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network.
6. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm.
7. In the original 5-node network find a shortest route starting at vertex \(\mathbf { 1 }\) and using each of the 6 arcs at least once. Give the length of your route. 4 Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10 ml of oil and between 3 and 6 ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: $$\begin{array} { l c } \text { Maximise } & \frac { x } { x + y } \\ \text { subject to } & 0 \leqslant x \leqslant 10 , \\ & 0 \leqslant y \leqslant 6 , \\ & x - 2 y \leqslant 0 . \end{array}$$
8. Explain why this problem is not an LP.
9. Use the simplex method to solve the following LP. $$\begin{array} { l c } \text { Maximise } & x - y \\ \text { subject to } & 0 \leqslant x \leqslant 10 \\ & 0 \leqslant y \leqslant 6 \\ & x - 2 y \leqslant 0 \end{array}$$
10. Kassi prefers to have more vinegar than oil. She formulates the following LP. $$\begin{array} { l l } \text { Maximise } & y - x \\ \text { subject to } & 5 \leqslant x \leqslant 10 , \\ & 3 \leqslant y \leqslant 6 , \\ & x - 2 y \leqslant 0 . \end{array}$$ Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii).
11. Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii).
12. Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed.

1. Perform the fourth (final) iteration of the algorithm.
2. Explain how to use the final matrices to find the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex \(\mathbf { 3 }\), and give the distance and route.
3. Draw the complete network of shortest distances.
4. Apply the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to your complete network of shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route through the original network.
5. By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to the travelling salesperson problem in the original network.
6. Explain what you can deduce from your answers to parts (iv) and (v). 4 Noel is designing a hotel patio. It will consist of decking and paving.
   Decking costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and paving costs \(\pounds 2\) per \(\mathrm { m } ^ { 2 }\). He has a budget of \(\pounds 2500\).
   Noel prefers paving to decking, and he wants the area given to paving to be at least twice that given to decking. He wants to have as large a patio as possible.
   Noel's problem is formulated as the following LP.
   Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of decking.
   Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of paving. $$\begin{aligned} \text { Maximise } \quad P & = x + y \\ \text { subject to } 2 x + y & \leqslant 1250 \\ 2 x - y & \leqslant 0 \\ x & \geqslant 0 \\ y & \geqslant 0 \end{aligned}$$
7. Use the simplex algorithm to solve this LP. Pivot first on the positive element in the \(y\) column. Noel would like to have at least \(200 \mathrm {~m} ^ { 2 }\) of decking.
8. Add a line corresponding to this constraint to your solution tableau from part (i), and modify the resulting table either for two-stage simplex or the big-M method. Hence solve the problem. Noel finally decides that he will minimise the annual cost of maintenance, which is given by \(\pounds ( 0.75 x + 1.25 y )\), subject to the additional constraint that there is at least \(1000 \mathrm {~m} ^ { 2 }\) of patio.
9. Starting from your solution to part (ii), use simplex to solve this problem.

(ii) Perform the fourth iteration. There are no changes on the fifth iteration, so your answer to part (ii) should give the complete network of shortest distances.
(iii) Use your matrices to find the shortest distance and route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 1 }\), and explain how you do it.
(iv) Draw the complete network of shortest distances, not including the loops.
(v) Apply the nearest neighbour algorithm to your network in part (iv), starting at vertex 2. Give the length of the Hamilton cycle that is produced. Interpret the Hamilton cycle in terms of the original diagram and state what the algorithm has achieved. }{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1PB.
OCR is part of the

3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances. \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}

1. The printed answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex 5 to vertex 2.
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 4 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
3. Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
4. Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
5. Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
6. Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.

3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times. \includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \end{table}

\(\mathbf { 4 }\) & 10 & 5 & 7 & 10
\hline \end{tabular} \end{center} \end{table} \begin{table}[h] \end{table}

1. Draw the complete network of shortest times.
2. Explain how to use the final route matrix to find the quickest route from node \(\mathbf { 4 }\) to node \(\mathbf { 1 }\) in the original incomplete network. Give this quickest route. A new node, node 5, is added to the original incomplete network. The new journey times are shown in the table. \begin{center} \begin{tabular}{ | l | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) \hline

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline

1. Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
2. Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
3. (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
   (B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
4. By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
5. In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

   Driving times	to A	to W
   From G	20 min	15 min

   \multirow{2}{*}{Train journey}	To V			To LB
   	normal time	probability of delay	delay	normal time	probability of delay	delay
   From A	1 hr 40 min	0.05	10 min	1 hr 45 min	0.05	10 min
   From W	1 hr 30 min	0.10	20 min	1 hr 35 min	0.10	20 min

   \multirow{2}{*}{ Tube journey }	To KC
   \cline { 2 - 4 }	normal time	probability of delay	delay
   From V	7 min	0.20	2 min
   From LB	9 min	0.10	2 min

   Helen wants to choose the route which will give the shortest expected journey time.
6. Draw a decision tree to model Helen's decisions and the possible outcomes.
7. Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
8. Find the value of the radio information, explaining your calculation.
9. Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

1. Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.
2. Show how to use the matrices to give the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex 2.
3. Draw the complete network of shortest distances.
4. Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
5. By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.

The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. \includegraphics{figure_3} \includegraphics{figure_4}

1. Draw the complete network of shortest distances. [2]
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. [2]

A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \includegraphics{figure_5}

1. Draw the extended network and the complete 5-node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.) [3]
2. Produce the shortest distance matrix and the route matrix for the extended 5-node network. [3]
3. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network. [3]
4. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm. [4]
5. In the original 5-node network find a shortest route starting at vertex 1 and using each of the 6 arcs at least once. Give the length of your route. [3]