| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Standard +0.3 This is a straightforward application of the Hungarian algorithm with a standard modification (adding a dummy row for unequal sets). The algorithm itself is mechanical once learned, and part (c) requires only checking if the new value improves the existing solution. While it's a multi-part question worth reasonable marks, it demands no novel insight—just careful execution of a taught procedure, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Ash | Bob | Col | Dan | Emma | |
| Task 1 | 14 | 10 | 12 | 12 | 14 |
| Task 2 | 11 | 13 | 10 | 12 | 12 |
| Task 3 | 13 | 11 | 12 | ** | 12 |
| Task 4 | 13 | 10 | 12 | 13 | 15 |
| Answer | Marks |
|---|---|
| - Unclear structure with "T | 4" and "I" |
I appreciate you sharing this content, but the extracted text appears to be corrupted or severely damaged. The material shows:
- Fragmented letters (F, H, T, I, G)
- Incomplete notation "(cid:1)2þ5 ¼ 3"
- Unclear structure with "T | 4" and "I"
**I cannot reliably convert this to a proper mark scheme because the source content is not legible enough to determine:**
- What the actual mathematical notation should be
- Which marks correspond to which points
- What the marking annotations (M1, A1, etc.) refer to
- The logical structure of the mark scheme
**Could you please provide:**
1. A clearer/higher quality scan of the original document, or
2. The original digital text file, or
3. A re-typed version of Question 2's mark scheme?
Once you provide clearer source material, I'll be happy to format it with proper LaTeX notation and clear marking structure.2 The following table shows the times taken, in minutes, by five people, Ash, Bob, Col, Dan and Emma, to carry out the tasks 1, 2, 3 and 4 . Dan cannot do task 3.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Ash & Bob & Col & Dan & Emma \\
\hline
Task 1 & 14 & 10 & 12 & 12 & 14 \\
\hline
Task 2 & 11 & 13 & 10 & 12 & 12 \\
\hline
Task 3 & 13 & 11 & 12 & ** & 12 \\
\hline
Task 4 & 13 & 10 & 12 & 13 & 15 \\
\hline
\end{tabular}
\end{center}
Each of the four tasks is to be given to a different one of the five people so that the overall time for the four tasks is minimised.
\begin{enumerate}[label=(\alph*)]
\item Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
\item Use the Hungarian algorithm, reducing columns first then rows, to decide which four people should be allocated to which task. State the minimum total time for the four tasks using this matching.
\item After special training, Dan is able to complete task 3 in 12 minutes. Determine, giving a reason, whether the minimum total time found in part (b) could be improved.\\
(2 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2008 Q2 [11]}}