| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.3 This is a standard application of the Hungarian algorithm with routine steps: transformation explanation, row/column reduction, covering zeros, and finding optimal assignment. While it requires careful arithmetic and understanding of the algorithm, it follows a well-defined procedure taught in D2 with no novel problem-solving required. The multi-part structure and computational length are typical for Decision Maths questions, making it slightly easier than average A-level difficulty overall. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Topic 1 | Topic 2 | Topic 3 | Topic 4 | Topic 5 | |
| Abby | 27 | 29 | 25 | 35 | 31 |
| Bob | 33 | 22 | 17 | 29 | 29 |
| Cait | 23 | 29 | 25 | 33 | 21 |
| Drew | 22 | 29 | 29 | 27 | 31 |
| Ellie | 27 | 27 | 19 | 21 | 27 |
| 8 | 6 | 8 | 0 | 4 |
| 0 | 11 | \(p\) | 4 | 4 |
| 10 | 4 | 6 | 0 | 12 |
| \(q\) | 2 | 0 | 4 | 0 |
| 0 | 0 | 6 | 6 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Replacing \(x\) by \(35-x\) converts a maximisation problem into a minimisation problem | B1 | |
| The Hungarian algorithm is used to solve minimisation (assignment) problems | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct table formed by subtracting from 35 | B1 | |
| Row reductions performed correctly | M1 | |
| \(p = 18\), \(q = 13\) | A1 | Both values correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Zeros covered by 2 horizontal lines (rows 2 and 5) and 2 vertical lines (columns 4 and 5) | B1 | Correct identification of covering lines |
| Augmentation step: subtract minimum uncovered value, add to doubly covered | M1 | |
| Resulting table requires 5 lines to cover zeros | A1 | Table shown correctly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Abby – Topic 4, Bob – Topic 1, Cait – Topic 2 or Topic 3, Drew – Topic 5, Ellie – Topic 2 or Topic 3 | B1 | |
| Complete valid allocation stated | M1 A1 | Two valid allocations acceptable |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Maximum total score = \(35 + 33 + 29 + 31 + 27 = \mathbf{155}\) | B1 | 1 mark |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Replacing $x$ by $35-x$ converts a maximisation problem into a minimisation problem | B1 | |
| The Hungarian algorithm is used to solve minimisation (assignment) problems | B1 | |
**2 × B1**
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct table formed by subtracting from 35 | B1 | |
| Row reductions performed correctly | M1 | |
| $p = 18$, $q = 13$ | A1 | Both values correct |
**B1, M1, A1**
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Zeros covered by 2 horizontal lines (rows 2 and 5) and 2 vertical lines (columns 4 and 5) | B1 | Correct identification of covering lines |
| Augmentation step: subtract minimum uncovered value, add to doubly covered | M1 | |
| Resulting table requires 5 lines to cover zeros | A1 | Table shown correctly |
**B1, M1, A1**
## Part (d)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Abby – Topic 4, Bob – Topic 1, Cait – Topic 2 or Topic 3, Drew – Topic 5, Ellie – Topic 2 or Topic 3 | B1 | |
| Complete valid allocation stated | M1 A1 | Two valid allocations acceptable |
**3 marks**
## Part (d)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Maximum total score = $35 + 33 + 29 + 31 + 27 = \mathbf{155}$ | B1 | **1 mark** |2 A team with five members is training to take part in a quiz. The team members, Abby, Bob, Cait, Drew and Ellie, attempted sample questions on each of the five topics and their scores are given in the table.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Topic 1 & Topic 2 & Topic 3 & Topic 4 & Topic 5 \\
\hline
Abby & 27 & 29 & 25 & 35 & 31 \\
\hline
Bob & 33 & 22 & 17 & 29 & 29 \\
\hline
Cait & 23 & 29 & 25 & 33 & 21 \\
\hline
Drew & 22 & 29 & 29 & 27 & 31 \\
\hline
Ellie & 27 & 27 & 19 & 21 & 27 \\
\hline
\end{tabular}
\end{center}
For the actual quiz, each topic must be allocated to exactly one of the team members. The maximum total score for the sample questions is to be used to allocate the different topics to the team members.
\begin{enumerate}[label=(\alph*)]
\item Explain why the Hungarian algorithm may be used if each number, $x$, in the table is replaced by $35 - x$.
\item Form a new table by subtracting each number in the table above from 35 . Hence show that, by reducing rows first then columns, the resulting table of values is as below, stating the values of the constants $p$ and $q$.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
8 & 6 & 8 & 0 & 4 \\
\hline
0 & 11 & $p$ & 4 & 4 \\
\hline
10 & 4 & 6 & 0 & 12 \\
\hline
$q$ & 2 & 0 & 4 & 0 \\
\hline
0 & 0 & 6 & 6 & 0 \\
\hline
\end{tabular}
\end{center}
\item Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
\item \begin{enumerate}[label=(\roman*)]
\item Hence find the possible allocations of topics to the five team members so that the total score for the sample questions is maximised.
\item State the value of this maximum total score.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2012 Q2 [12]}}