| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming production scheduling |
| Difficulty | Moderate -0.5 This is a standard dynamic programming allocation problem with a small state space (4 months, 3 projects + holiday). The backward recursion is straightforward with clear structure, requiring systematic enumeration rather than algorithmic insight. Easier than average A-level as it's a template application of the DP algorithm taught in D2, though the bookkeeping across states requires care. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | May | June | July | August |
| Project \(\boldsymbol { A }\) | 17 | 16 | 18 | 16 |
| Project \(\boldsymbol { B }\) | 14 | 13 | 12 | 10 |
| Project \(\boldsymbol { C }\) | 14 | 17 | 15 | 14 |
5 [Figure 3, printed on the insert, is provided for use in this question.]\\
A landscape gardener has three projects, $A , B$ and $C$, to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & May & June & July & August \\
\hline
Project $\boldsymbol { A }$ & 17 & 16 & 18 & 16 \\
\hline
Project $\boldsymbol { B }$ & 14 & 13 & 12 & 10 \\
\hline
Project $\boldsymbol { C }$ & 14 & 17 & 15 & 14 \\
\hline
\end{tabular}
\end{center}
By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.
\hfill \mbox{\textit{AQA D2 2010 Q5 [10]}}