3 [Answer this question on the insert provided.]
A flying doctor travels between islands using small planes. Each flight has a weight limit that restricts how much he can carry. A plague has broken out on Farr Island and the doctor needs to take several crates of medical supplies to the island. The crates must be carried on the same planes as the doctor.
The diagram shows a network with (stage; state) variables at the vertices representing the islands, arcs representing flight routes that can be used, and weights on the arcs representing the number of crates that the doctor can carry on each flight.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-03_506_1084_671_477}
\captionsetup{labelformat=empty}
\caption{Stage 0}
\end{figure}
Stage 1
Stage 2
- It is required to find the route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) for which the minimum number of crates that can be carried on any stage is a maximum (the maximin route). The insert gives a dynamic programming tabulation showing stages, states and actions, together with columns for working out the route minimum at each stage and for indicating the current maximin.
Complete the table on the insert sheet and hence find the maximin route and the maximum number of crates that can be carried.
- It is later found that the number of crates that can be carried on the route from ( \(2 ; 0\) ) to ( \(3 ; 0\) ) has been recorded incorrectly and should be 15 instead of 5 . What is the maximin route now, and how many crates can be carried?