| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Standard +0.3 This is a standard dynamic programming table completion exercise requiring systematic application of the maximin algorithm. While it involves multiple stages and careful bookkeeping, it follows a routine algorithmic procedure with no novel problem-solving required. The network drawing and interpretation questions are straightforward applications of the method, making this easier than average for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| 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\), |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Stage 1, State 0, Action 0: \(\min(3, 3) = 3\) | B1 | Correct working for stage 1 rows |
| Stage 1, State 0, Action 1: \(\min(4, 2) = 2\) | ||
| Stage 1, State 1, Action 1: \(\min(3, 2) = 2\) | ||
| Stage 1, State 2, Action 1: \(\min(3, 2) = 2\) | ||
| Stage 1, State 2, Action 2: \(\min(1, 1) = 1\) | ||
| Suboptimal maximin for Stage 1 State 0 = 3, State 1 = 2, State 2 = 2 | B1 | |
| Stage 0, State 0, Action 0: \(\min(5, 3) = 3\) | B1 | Correct working for stage 0 rows |
| Stage 0, State 0, Action 1: \(\min(3, 2) = 2\) | ||
| Stage 0, State 0, Action 2: \(\min(4, 2) = 2\) | ||
| Suboptimal maximin for Stage 0 = 3 | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximin value = 3 | B1 | ft from (i) |
| Route: \((0;0) \to (1;0) \to (2;0) \to (3;0) \to (4;0)\) | M1 A1 | M1 for valid attempt to trace route; A1 for correct route in (stage; state) notation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Network drawn with 5 nodes in a column at each stage (states 0,1,2) | B1 | Correct nodes |
| Arcs with correct weights connecting appropriate nodes | B1 | Correct arc weights |
| Correct overall network structure matching the table | B1 | All arcs correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The maximum flow through the network / the maximum amount of water per second that can flow through the pipe system | B1 | Accept equivalent statements about maximum flow rate in litres per second |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The sum of the maximin values from each iteration gives the maximum flow / each route found carries flow equal to its maximin value until capacity is reached | B1 | Accept equivalent explanation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum flow drawn on original network showing flow of 3 litres per second | B1 | Correct flow values shown |
| Cut drawn with value = 3 | B1 | Cut must separate source from sink with correct value |
# Question 6:
## Part (i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Stage 1, State 0, Action 0: $\min(3, 3) = 3$ | B1 | Correct working for stage 1 rows |
| Stage 1, State 0, Action 1: $\min(4, 2) = 2$ | | |
| Stage 1, State 1, Action 1: $\min(3, 2) = 2$ | | |
| Stage 1, State 2, Action 1: $\min(3, 2) = 2$ | | |
| Stage 1, State 2, Action 2: $\min(1, 1) = 1$ | | |
| Suboptimal maximin for Stage 1 State 0 = 3, State 1 = 2, State 2 = 2 | B1 | |
| Stage 0, State 0, Action 0: $\min(5, 3) = 3$ | B1 | Correct working for stage 0 rows |
| Stage 0, State 0, Action 1: $\min(3, 2) = 2$ | | |
| Stage 0, State 0, Action 2: $\min(4, 2) = 2$ | | |
| Suboptimal maximin for Stage 0 = 3 | B1 | cao |
## Part (ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximin value = 3 | B1 | ft from (i) |
| Route: $(0;0) \to (1;0) \to (2;0) \to (3;0) \to (4;0)$ | M1 A1 | M1 for valid attempt to trace route; A1 for correct route in (stage; state) notation |
## Part (iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Network drawn with 5 nodes in a column at each stage (states 0,1,2) | B1 | Correct nodes |
| Arcs with correct weights connecting appropriate nodes | B1 | Correct arc weights |
| Correct overall network structure matching the table | B1 | All arcs correct |
## Part (iv):
| Answer | Marks | Guidance |
|--------|-------|----------|
| The maximum flow through the network / the maximum amount of water per second that can flow through the pipe system | B1 | Accept equivalent statements about maximum flow rate in litres per second |
## Part (v)(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| The sum of the maximin values from each iteration gives the maximum flow / each route found carries flow equal to its maximin value until capacity is reached | B1 | Accept equivalent explanation |
## Part (v)(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow drawn on original network showing flow of 3 litres per second | B1 | Correct flow values shown |
| Cut drawn with value = 3 | B1 | Cut must separate source from sink with correct value |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.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Working & Suboptimal maximin \\
\hline
\multirow[t]{3}{*}{3} & 0 & 0 & 6 & 6 \\
\hline
& 1 & 0 & 1 & 1 \\
\hline
& 2 & 0 & 3 & 3 \\
\hline
\multirow[t]{5}{*}{2} & 0 & 0 & $\min ( 3,6 ) = 3$ & 3 \\
\hline
& \multirow{3}{*}{1} & 0 & $\min ( 1,6 ) = 1$ & \multirow[b]{3}{*}{2} \\
\hline
& & 1 & $\min ( 1,1 ) = 1$ & \\
\hline
& & 2 & $\min ( 2,3 ) = 2$ & \\
\hline
& 2 & 2 & $\min ( 1,3 ) = 1$ & 1 \\
\hline
\multirow[t]{5}{*}{1} & \multirow[t]{2}{*}{0} & 0 & $\min ( 3$, & \multirow{2}{*}{} \\
\hline
& & 1 & $\min ( 4$, & \\
\hline
& 1 & 1 & $\min ( 3$, & \\
\hline
& \multirow[t]{2}{*}{2} & 1 & $\min ( 3$, & \multirow{2}{*}{} \\
\hline
& & 2 & $\min ( 1$, & \\
\hline
\multirow[t]{3}{*}{0} & \multirow[t]{3}{*}{0} & 0 & $\min ( 5$, & \multirow{3}{*}{} \\
\hline
& & 1 & $\min ( 3$, & \\
\hline
& & 2 & $\min ( 4$, & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Complete the working and suboptimal maximin columns on the copy of the table in your answer book.
\item Use your answer to part (i) to write down the maximin value and the corresponding route. Give your route using (stage; state) variables.
\item 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.
\item 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}
\item (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 {勾 } }$}
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2014 Q6 [14]}}