| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Standard +0.3 This is a straightforward application of the minimax dynamic programming algorithm taught in D2. Part (a) requires simple comparison of maximum values on two routes, and part (b) follows a standard tabular method working backwards through stages. The algorithm is mechanical with no novel problem-solving required, making it easier than average A-level questions which typically require more conceptual understanding or multi-step reasoning. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities7.05c Total float: calculation and interpretation7.05d Latest start and earliest finish: independent and interfering float7.05e Cascade charts: scheduling and effect of delays |
| \(\ldots . . .\). | \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-11_1000_114_1710_159} |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Route \(PQTV\): days are \(PQ=9\), \(QT=7\), \(TV=9\); longest day \(= 9\) | B1 | Correct identification of longest day for PQTV |
| Route \(PQSV\): days are \(PQ=9\), \(QS=12\), \(SV=11\); longest day \(= 12\)... | ||
| \(PQTV\) longest day \(= 9\); \(PQSV\) longest day \(= 12\); so \(PQTV\) is better than \(PQSV\) (question may be reversed) | B1 | Correct comparison and conclusion |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Stage 1: \(S \to V = 11\); \(T \to V = 9\); \(U \to V = 12\) | B1 | All three stage 1 values correct |
| Stage 2, State Q: \(QS\): \(\max(12, 11)=12\); \(QT\): \(\max(7,9)=9^*\); value \(= 9\) via \(T\) | M1 A1 | Correct max calculations |
| Stage 2, State R: \(RT\): \(\max(10,9)=10\); \(RS\): \(\max(13,11)=13\); \(RU\): \(\max(8,12)=12\)... \(RU\): \(\max(14,12)=14\); \(RT\): \(\max(10,9)=10^*\); value \(=10\) via \(T\) | M1 A1 | |
| Stage 3, State P: \(PQ\): \(\max(9,9)=9^*\); \(PR\): \(\max(11,10)=11\); value \(= 9\) via \(Q\) | M1 A1 | |
| Minimax route from \(P\) to \(V\) is \(PQTV\) with value \(9\) | A1 |
# Question 5:
## Part (a) - Why PQSV better than PQTV (2 marks)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Route $PQTV$: days are $PQ=9$, $QT=7$, $TV=9$; longest day $= 9$ | B1 | Correct identification of longest day for PQTV |
| Route $PQSV$: days are $PQ=9$, $QS=12$, $SV=11$; longest day $= 12$... | | |
| $PQTV$ longest day $= 9$; $PQSV$ longest day $= 12$; so $PQTV$ is better than $PQSV$ (question may be reversed) | B1 | Correct comparison and conclusion |
## Part (b) - Dynamic programming minimax table (8 marks)
| Answer/Working | Mark | Guidance |
|---|---|---|
| **Stage 1:** $S \to V = 11$; $T \to V = 9$; $U \to V = 12$ | B1 | All three stage 1 values correct |
| **Stage 2, State Q:** $QS$: $\max(12, 11)=12$; $QT$: $\max(7,9)=9^*$; value $= 9$ via $T$ | M1 A1 | Correct max calculations |
| **Stage 2, State R:** $RT$: $\max(10,9)=10$; $RS$: $\max(13,11)=13$; $RU$: $\max(8,12)=12$... $RU$: $\max(14,12)=14$; $RT$: $\max(10,9)=10^*$; value $=10$ via $T$ | M1 A1 | |
| **Stage 3, State P:** $PQ$: $\max(9,9)=9^*$; $PR$: $\max(11,10)=11$; value $= 9$ via $Q$ | M1 A1 | |
| Minimax route from $P$ to $V$ is $PQTV$ with value $9$ | A1 | |5 A three-day journey is to be made from $P$ to $V$, with overnight stops at the end of the first day at one of the locations $Q$ or $R$, and at the end of the second day at $S , T$ or $U$. The network shows the journey times, in hours, for each day of the journey.\\
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-10_737_1280_447_388}
The optimal route, known as the minimax route, is that in which the longest day's journey is as small as possible.
\begin{enumerate}[label=(\alph*)]
\item Explain why the route $P Q S V$ is better than the route $P Q T V$.
\item By completing the table opposite, or otherwise, use dynamic programming, working backwards from $\boldsymbol { V }$, to find the optimal (minimax) route from $P$ to $V$.
You should indicate the calculations as well as the values at stages 2 and 3.\\
(8 marks)
\begin{center}
\begin{tabular}{|l|l|}
\hline
$\ldots . . .$. & \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-11_1000_114_1710_159}
\\
\hline
\end{tabular}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2010 Q5 [10]}}