5 Tom is going on a driving holiday and wishes to drive from \(A\) to \(K\).
The network below shows a system of roads. The number on each edge represents the maximum altitude of the road, in hundreds of metres above sea level. Tom wants to ensure that the maximum altitude of any road along the route from \(A\) to \(K\) is minimised.
\includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-14_1522_1363_660_342}

1. Working backwards from \(\boldsymbol { K }\), use dynamic programming to find the optimal route when driving from \(A\) to \(K\). You must complete the table opposite as your solution.
2. Tom finds that the road \(C F\) is blocked. Find Tom's new optimal route and the maximum altitude of any road on this route.
   [0pt] [2 marks] \section*{Answer space for question 5}

   Stage	State	From	Value
   1	H	\(K\)
   	I	\(K\)
   	\(J\)	\(K\)
   2

3. Optimal route is \(\_\_\_\_\)
4. Tom's route is \(\_\_\_\_\)
   Maximum altitude is \(\_\_\_\_\) Figure 4 below shows a network of pipes.
   The capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-18_1039_1623_561_191}
   \end{figure}
5. Find the value of the initial flow.
6. 1. Use the initial flow and the labelling procedure on Figure 5 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 6, illustrate a possible flow along each edge corresponding to this maximum flow.
7. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
8. On a particular day, there is a restriction at vertex \(G\) which allows a maximum flow through \(G\) of 30 . Find, by inspection, the maximum flow through the network on this day.
9. Initial flow \(=\) \(\_\_\_\_\)
10. 1. Figure 5
       \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-19_2158_1559_543_296}
       \(7 \quad\) Arsene and Jose play a zero-sum game. The game is represented by the following pay-off matrix for Arsene, where \(x\) is a constant. The value of the game is 2.5 .

       Jose
       \cline { 2 - 4 }	Strategy	C	D
       \cline { 2 - 4 } Arsene	A	\(x + 3\)	1
       \cline { 2 - 4 }	B	\(x + 1\)	3
       \cline { 2 - 4 }
       \cline { 2 - 4 }

11. Find the optimal mixed strategy for Arsene.
12. Find the value of \(x\).
    \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-22_1636_1707_1071_153}
    \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-24_2288_1705_221_155}