| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Moderate -0.5 This is a routine dynamic programming question requiring completion of a partially-filled table using standard maximin algorithm. The working values are already provided, students only need to select maximum values and trace back the optimal route - this is mechanical application of a learned procedure with no problem-solving or novel insight required, making it easier than average. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Stage | State | Action | Working | Maximin |
| \multirow{2}{*}{1} | 0 | 0 | 4 | 4 |
| 1 | 0 | 3 | 3 | |
| \multirow{6}{*}{2} | 0 | 0 | \(\min ( 6,4 ) = 4\) | \multirow{2}{*}{} |
| 1 | \(\min ( 2,3 ) = 2\) | |||
| \multirow{2}{*}{1} | 0 | \(\min ( 2,4 ) =\) | \multirow{2}{*}{} | |
| 1 | \(\min ( 4,3 ) =\) | |||
| \multirow{2}{*}{2} | 0 | min(2, | \multirow{2}{*}{} | |
| 1 | min(3, | |||
| \multirow{3}{*}{3} | \multirow{3}{*}{0} | 0 | min(5, | \multirow{3}{*}{} |
| 1 | \(\min ( 5\), | |||
| 2 | \(\min ( 2\), |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | Stage 1: State 0, Action 0, Working 4, Maximin 4 / State 1, Action 0, Working 3, Maximin 3 | B1 |
| Stage 2: State 0, Action 0, Working min(6,4)=4, Maximin 4 / Action 1, Working min(2,3)=2 | M1 | Completing working column of (2,1) |
| State 1, Action 0, Working min(2,4)=2, Maximin 2 / Action 1, Working min(4,3)=3 | A1 | Maximin value correct for (2,1) |
| State 2, Action 0, Working min(2,4)=2, Maximin 2 / Action 1, Working min(3,3)=3 | M1 | Completing working column for (2,2) |
| A1 | Maximin value correct for (2,2) | |
| Stage 3: State 0, Action 0, Working min(5,4)=4, Maximin 4 / Action 1, Working min(5,3)=3 / Action 2, Working min(2,3)=2 | B1 ft | Transferring maximin values from stage 2 |
| M1 ft | Completing working column for stage 3 | |
| A1 ft | Maximin value correct for stage 3 | |
| [8] | ||
| (ii) | 4 | B1 ft |
| \((3:0) - (2:0) = (1:0) - (0:0)\) (or in reverse) | M1 ft | (3:0) – (2:0), or if their table if possible |
| M1 ft | (2:0) – (1:0), or if their table if possible | |
| A1 | For maximin route correct | |
| [4] |
(i) | Stage 1: State 0, Action 0, Working 4, Maximin 4 / State 1, Action 0, Working 3, Maximin 3 | B1 | Maximin value correct for (2,0) |
| Stage 2: State 0, Action 0, Working min(6,4)=4, Maximin 4 / Action 1, Working min(2,3)=2 | M1 | Completing working column of (2,1) |
| | State 1, Action 0, Working min(2,4)=2, Maximin 2 / Action 1, Working min(4,3)=3 | A1 | Maximin value correct for (2,1) |
| | State 2, Action 0, Working min(2,4)=2, Maximin 2 / Action 1, Working min(3,3)=3 | M1 | Completing working column for (2,2) |
| | | A1 | Maximin value correct for (2,2) |
| Stage 3: State 0, Action 0, Working min(5,4)=4, Maximin 4 / Action 1, Working min(5,3)=3 / Action 2, Working min(2,3)=2 | B1 ft | Transferring maximin values from stage 2 |
| | | M1 ft | Completing working column for stage 3 |
| | | A1 ft | Maximin value correct for stage 3 |
| | | [8] | |
(ii) | 4 | B1 ft | 4, or if their table if possible |
| | $(3:0) - (2:0) = (1:0) - (0:0)$ (or in reverse) | M1 ft | (3:0) – (2:0), or if their table if possible |
| | | M1 ft | (2:0) – (1:0), or if their table if possible |
| | | A1 | For maximin route correct |
| | | [4] | |
---6 Answer this question on the insert provided.
The table shows a partially completed dynamic programming tabulation for solving a maximin problem.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Working & Maximin \\
\hline
\multirow{2}{*}{1} & 0 & 0 & 4 & 4 \\
\hline
& 1 & 0 & 3 & 3 \\
\hline
\multirow{6}{*}{2} & 0 & 0 & $\min ( 6,4 ) = 4$ & \multirow{2}{*}{} \\
\hline
& & 1 & $\min ( 2,3 ) = 2$ & \\
\hline
& \multirow{2}{*}{1} & 0 & $\min ( 2,4 ) =$ & \multirow{2}{*}{} \\
\hline
& & 1 & $\min ( 4,3 ) =$ & \\
\hline
& \multirow{2}{*}{2} & 0 & min(2, & \multirow{2}{*}{} \\
\hline
& & 1 & min(3, & \\
\hline
\multirow{3}{*}{3} & \multirow{3}{*}{0} & 0 & min(5, & \multirow{3}{*}{} \\
\hline
& & 1 & $\min ( 5$, & \\
\hline
& & 2 & $\min ( 2$, & \\
\hline
\end{tabular}
\end{center}
(i) Complete the last two columns of the table in the insert.\\
(ii) State the maximin value and write down the maximin route.
\hfill \mbox{\textit{OCR D2 2007 Q6 [12]}}