6 The table below shows an incomplete dynamic programming tabulation to solve a maximin problem. Do not write your answer on this copy of the table.
| Stage | State | Action | Working | Suboptimal maximin |
| \multirow[t]{3}{*}{3} | 0 | 0 | 6 | 6 |
| 1 | 0 | 1 | 1 |
| 2 | 0 | 3 | 3 |
| \multirow[t]{5}{*}{2} | 0 | 0 | \(\min ( 3,6 ) = 3\) | 3 |
| \multirow{3}{*}{1} | 0 | \(\min ( 1,6 ) = 1\) | \multirow[b]{3}{*}{2} |
| | 1 | \(\min ( 1,1 ) = 1\) | |
| | 2 | \(\min ( 2,3 ) = 2\) | |
| 2 | 2 | \(\min ( 1,3 ) = 1\) | 1 |
| \multirow[t]{5}{*}{1} | \multirow[t]{2}{*}{0} | 0 | \(\min ( 3\), | \multirow{2}{*}{} |
| | 1 | \(\min ( 4\), | |
| 1 | 1 | \(\min ( 3\), | |
| \multirow[t]{2}{*}{2} | 1 | \(\min ( 3\), | \multirow{2}{*}{} |
| | 2 | \(\min ( 1\), | |
| \multirow[t]{3}{*}{0} | \multirow[t]{3}{*}{0} | 0 | \(\min ( 5\), | \multirow{3}{*}{} |
| | 1 | \(\min ( 3\), | |
| | 2 | \(\min ( 4\), | |
- Complete the working and suboptimal maximin columns on the copy of the table in your answer book.
- Use your answer to part (i) to write down the maximin value and the corresponding route. Give your route using (stage; state) variables.
- Draw the network that is represented in the table.
The network represents a system of pipes and the arc weights show the capacities of the pipes, in litres per second.
- What does the answer to part (ii) represent in this network?
The weights of the arcs in the maximin route are each reduced by the maximin value and then a maximin is found for the resulting network. This is done until the maximin value is 0 . At this point the network is as shown below.
\includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-8_552_1474_438_274} - (a) Describe how this solves the maximum flow problem on the original network.
(b) Draw this maximum flow and draw a cut with value equal to the value of the flow.
\section*{END OF QUESTION PAPER}
\section*{\(\mathrm { OCR } ^ { \text {勾 } }\)}