| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm with the routine modification of adding a dummy row for unequal sets. The algorithm itself is mechanical and procedural once learned, requiring no problem-solving insight—just careful arithmetic and following the steps. While it's a multi-mark question, it's easier than average A-level maths because it tests algorithmic execution rather than mathematical reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Ali | Bo | Chas | Dee | Eve | |
| Team 1 | 16 | 19 | 18 | 25 | 24 |
| Team 2 | 22 | 21 | 20 | 26 | 25 |
| Team 3 | 21 | 22 | 23 | 21 | 24 |
| Team 4 | 20 | 21 | 21 | 23 | 20 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Add extra row with all values the same | B1 | Usually all equal to 26 and below the other rows |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Reduce columns first | M1 | |
| Correct reduced matrix after column reduction | A1 | |
| Reduce rows | M1 | These 2 marks available for those who reduce rows first |
| Correct reduced matrix after row reduction | A1 | Total so far: 4 marks |
| Covering zeros requires 4 lines; adjust with least entry remaining being 2 | M1 | |
| Correct adjusted matrix shown with zeros boxed | A1 | 2 – Other solutions possible |
| Match: \(A{-}1;\ C{=}2;\ D{-}3;\ E{-}4\) | B1 | |
| Expected minimum time: \(16+20+21+20 = 77\) min | B1 | 2 |
## Question 1:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Add extra row with all values the same | B1 | Usually all equal to 26 and below the other rows |
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Reduce columns first | M1 | |
| Correct reduced matrix after column reduction | A1 | |
| Reduce rows | M1 | These 2 marks available for those who reduce rows first |
| Correct reduced matrix after row reduction | A1 | **Total so far: 4 marks** |
| Covering zeros requires 4 lines; adjust with least entry remaining being 2 | M1 | |
| Correct adjusted matrix shown with zeros boxed | A1 | **2** – Other solutions possible |
| Match: $A{-}1;\ C{=}2;\ D{-}3;\ E{-}4$ | B1 | |
| Expected minimum time: $16+20+21+20 = 77$ min | B1 | **2** |
---1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Ali & Bo & Chas & Dee & Eve \\
\hline
Team 1 & 16 & 19 & 18 & 25 & 24 \\
\hline
Team 2 & 22 & 21 & 20 & 26 & 25 \\
\hline
Team 3 & 21 & 22 & 23 & 21 & 24 \\
\hline
Team 4 & 20 & 21 & 21 & 23 & 20 \\
\hline
\end{tabular}
\end{center}
Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.
\begin{enumerate}[label=(\alph*)]
\item Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
\item Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q1 [9]}}