| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Standard +0.3 This is a straightforward application of the maximin dynamic programming algorithm to a small network with clear structure. Part (a) requires simple comparison of minimum values, and part (b) involves systematic tabulation through 3 stages with only 2-3 nodes per stage. The concept is more procedural than conceptually deep, and the network size makes it manageable within typical exam time constraints. |
| Spec | 7.05e Cascade charts: scheduling and effect of delays |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(SAET\) has least day's sunshine of 5 hours whereas for \(SACT\) least value is only 4 hours | M1, A1 | Reasonable understanding; mention of 4 and 5 hours and clear idea that minimum is larger in \(SAET\); Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| General table with stage and state structure | M1 | General idea of stage and state |
| Stage 1, Initial States \(C, D, E\); Actions \(CT, DT, ET\); Values \(7^*, 9^*, 5^*\) | A1 | First stage correct (may be reversed) |
| Stage 2, State \(A\): \(AC\ \min(4,7)=4\); \(AD\ \min(4,9)=4\); \(AE\ \min(5,5)=5^*\) | M1 | Finding least value from 2 legs |
| Max of minima (star values) | m1 | Finding max of minima (star values) |
| Stage 2, State \(B\): \(BC\ \min(6,7)=6^*\); \(BD\ \min(5,9)=5\); \(BE\ \min(7,5)=5\) | A1 | All values in second stage correct |
| Stage 3, State \(S\): \(SA\ \min(9,5)=5\); \(SB\ \min(8,6)=6^*\) | A1 | All values in third stage correct |
| All values correct including max of min all correct and minimum comparison clearly shown at each stage, particularly \((9,5)\) and \((8,6)\) in third stage | A1 | |
| Maximin route is \(SBCT\) | B1 | Award B1 even without dynamic programming; Total: 8 |
## Question 5:
### Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $SAET$ has least day's sunshine of 5 hours whereas for $SACT$ least value is only 4 hours | M1, A1 | Reasonable understanding; mention of 4 and 5 hours and clear idea that minimum is larger in $SAET$; Total: 2 |
### Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| General table with stage and state structure | M1 | General idea of stage and state |
| Stage 1, Initial States $C, D, E$; Actions $CT, DT, ET$; Values $7^*, 9^*, 5^*$ | A1 | First stage correct (may be reversed) |
| Stage 2, State $A$: $AC\ \min(4,7)=4$; $AD\ \min(4,9)=4$; $AE\ \min(5,5)=5^*$ | M1 | Finding least value from 2 legs |
| Max of minima (star values) | m1 | Finding max of minima (star values) |
| Stage 2, State $B$: $BC\ \min(6,7)=6^*$; $BD\ \min(5,9)=5$; $BE\ \min(7,5)=5$ | A1 | All values in second stage correct |
| Stage 3, State $S$: $SA\ \min(9,5)=5$; $SB\ \min(8,6)=6^*$ | A1 | All values in third stage correct |
| All values correct including max of min all correct and minimum comparison clearly shown at each stage, particularly $(9,5)$ and $(8,6)$ in third stage | A1 | |
| Maximin route is $SBCT$ | B1 | Award B1 even without dynamic programming; Total: 8 |
---5 A three-day journey is to be made from $S$ to $T$, with overnight stops at the end of the first day at either $A$ or $B$ and at the end of the second day at one of the locations $C , D$ or $E$. The network shows the number of hours of sunshine forecast for each day of the journey.\\
\includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-05_753_1284_479_386}
The optimal route, known as the maximin route, is that for which the least number of hours of sunshine during a day's journey is as large as possible.
\begin{enumerate}[label=(\alph*)]
\item Explain why the three-day route $S A E T$ is better than $S A C T$.
\item Use dynamic programming to find the optimal (maximin) three-day route from $S$ to $T$. (8 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2007 Q5 [10]}}