| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming order sequencing |
| Difficulty | Moderate -0.8 This is a straightforward application of standard dynamic programming to a small sequencing problem with only 3 items. The table directly provides all state transitions, requiring students to simply construct a network and apply the basic longest-path algorithm they've been taught. No novel insight or complex reasoning is needed—just methodical execution of a textbook technique. |
| Spec | 7.05e Cascade charts: scheduling and effect of delays |
| \multirow[b]{2}{*}{Month} | \multirow[b]{2}{*}{Already built} | Profit (in units of £1000) | ||
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | ||
| 1 | - | 52 | 47 | 48 |
| \multirow[t]{3}{*}{2} | A | - | 58 | 54 |
| B | 70 | - | 54 | |
| \(\boldsymbol { C }\) | 68 | 63 | - | |
| \multirow[t]{3}{*}{3} | \(\boldsymbol { A }\) and \(\boldsymbol { B }\) | - | - | 64 |
| \(\boldsymbol { A }\) and \(\boldsymbol { C }\) | - | 67 | - | |
| \(\boldsymbol { B }\) and \(\boldsymbol { C }\) | 69 | - | - | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Network diagram drawn | M1 | SCA |
| Correct network | A1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Clear attempt to use Dynamic Programming working backwards through network | M1 | Complete enumeration M0; forwards through network also acceptable |
| Month 3 combinations correct: \(A\&B\ C\ 64^*\); \(A\&C\ B\ 67^*\); \(B\&C\ A\ 69^*\) | M1 | \(A\ 52,\ 52^*\); \(B\ 47,\ 47^*\); \(C\ 48,\ 48^*\); \(AB\ 110,\ 117\); \(AC\ 106,\ 116\); \(BC\ 101,\ 111\) – six possibilities |
| Month 2 combinations: \(B\to A\ 70+64=134^*\); \(B\to C\ 54+69=123\); \(C\to A\ 68+67=135^*\); \(C\to B\ 63+69=132\); \(-\to A\ 52+122=174\); Month 1: \(-\to B\ 47+134=181\) | A1 | Correct max identified and rest correct: \(BA\ 117^*\); \(CA\ 116^*\); \(CB\ 111^*\) |
| \(-\to C\ 48+135=183^*\) | A1 | 5 – \(BAC\ 181\); \(CAB\ 183\); \(CBA\ 180\); everything correct and route clearly traceable |
| The machine should be built in the order \(C\) then \(A\) then \(B\) | B1 | |
| Max profit \(= £183000\) | B1 | 2 – condone 183 |
## Question 2:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Network diagram drawn | M1 | SCA |
| Correct network | A1 | **2** |
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Clear attempt to use Dynamic Programming working backwards through network | M1 | Complete enumeration M0; forwards through network also acceptable |
| Month 3 combinations correct: $A\&B\ C\ 64^*$; $A\&C\ B\ 67^*$; $B\&C\ A\ 69^*$ | M1 | $A\ 52,\ 52^*$; $B\ 47,\ 47^*$; $C\ 48,\ 48^*$; $AB\ 110,\ 117$; $AC\ 106,\ 116$; $BC\ 101,\ 111$ – six possibilities |
| Month 2 combinations: $B\to A\ 70+64=134^*$; $B\to C\ 54+69=123$; $C\to A\ 68+67=135^*$; $C\to B\ 63+69=132$; $-\to A\ 52+122=174$; Month 1: $-\to B\ 47+134=181$ | A1 | Correct max identified and rest correct: $BA\ 117^*$; $CA\ 116^*$; $CB\ 111^*$ |
| $-\to C\ 48+135=183^*$ | A1 | **5** – $BAC\ 181$; $CAB\ 183$; $CBA\ 180$; everything correct and route clearly traceable |
| The machine should be built in the order $C$ then $A$ then $B$ | B1 | |
| Max profit $= £183000$ | B1 | **2** – condone 183 |
---2 A manufacturing company is planning to build three new machines, $A , B$ and $C$, at the rate of one per month. The order in which they are built is a matter of choice, but the profits will vary according to the number of workers available and the suppliers' costs. The expected profits in thousands of pounds are given in the table.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multirow[b]{2}{*}{Month} & \multirow[b]{2}{*}{Already built} & \multicolumn{3}{|c|}{Profit (in units of £1000)} \\
\hline
& & $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ \\
\hline
1 & - & 52 & 47 & 48 \\
\hline
\multirow[t]{3}{*}{2} & A & - & 58 & 54 \\
\hline
& B & 70 & - & 54 \\
\hline
& $\boldsymbol { C }$ & 68 & 63 & - \\
\hline
\multirow[t]{3}{*}{3} & $\boldsymbol { A }$ and $\boldsymbol { B }$ & - & - & 64 \\
\hline
& $\boldsymbol { A }$ and $\boldsymbol { C }$ & - & 67 & - \\
\hline
& $\boldsymbol { B }$ and $\boldsymbol { C }$ & 69 & - & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Draw a labelled network such that the most profitable order of manufacture corresponds to the longest path within that network.
\item Use dynamic programming to determine the order of manufacture that maximises the total profit, and state this maximum profit.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q2 [9]}}