| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 13 |
| 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 following a prescribed method with clear steps. While it requires careful arithmetic and systematic application of the algorithm, it's essentially a procedural exercise with no novel problem-solving or insight required. The question guides students through each stage (transformation, reduction, covering, allocation), making it slightly easier than average for A-level but still requiring sustained accuracy across multiple steps. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Alice | Baji | Cath | Dip | Ede | |
| Game 1 | 17 | 16 | 19 | 17 | 20 |
| Game 2 | 20 | 13 | 15 | 16 | 18 |
| Game 3 | 16 | 17 | 15 | 18 | 13 |
| Game 4 | 13 | 14 | 18 | 15 | 17 |
| Game 5 | 15 | 16 | 20 | 16 | 15 |
| 3 | 1 | 1 | 1 | 0 |
| 0 | 4 | 5 | 2 | 2 |
| 4 | 0 | 5 | 0 | 7 |
| 5 | 1 | 0 | 1 | 1 |
| 5 | 1 | 0 | 2 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Replacing \(x\) by \(20-x\) converts a maximisation problem to a minimisation problem | M1 | |
| The Hungarian algorithm is used to minimise, so this substitution allows it to be applied | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Subtract each entry from 20 to get new table | M1 | |
| Reduce columns (subtract column minimum) | M1 | |
| Reduce rows (subtract row minimum) to obtain given table | A1 | Correct final table shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cover zeros with one horizontal line (row 1 or row 2) and three vertical lines (columns 3, 4, 5 or similar) | B1 | |
| Find minimum uncovered value, subtract from uncovered, add to doubly covered | M1 | |
| Produce augmented table requiring 5 lines to cover zeros | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify zeros allowing complete assignment | M1 | |
| Two possible allocations identified correctly | A2 | A1 for each valid complete allocation |
| e.g. Alice–G2, Baji–G3, Cath–G5, Dip–G1, Ede–G4 or similar | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum total score = 89 | B1 | Follow through from part (d) |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Replacing $x$ by $20-x$ converts a maximisation problem to a minimisation problem | M1 | |
| The Hungarian algorithm is used to minimise, so this substitution allows it to be applied | A1 | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Subtract each entry from 20 to get new table | M1 | |
| Reduce columns (subtract column minimum) | M1 | |
| Reduce rows (subtract row minimum) to obtain given table | A1 | Correct final table shown |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cover zeros with one horizontal line (row 1 or row 2) and three vertical lines (columns 3, 4, 5 or similar) | B1 | |
| Find minimum uncovered value, subtract from uncovered, add to doubly covered | M1 | |
| Produce augmented table requiring 5 lines to cover zeros | A1 | |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify zeros allowing complete assignment | M1 | |
| Two possible allocations identified correctly | A2 | A1 for each valid complete allocation |
| e.g. Alice–G2, Baji–G3, Cath–G5, Dip–G1, Ede–G4 or similar | A1 | |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum total score = 89 | B1 | Follow through from part (d) |
---2 The following table shows the scores of five people, Alice, Baji, Cath, Dip and Ede, after playing five different computer games.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Alice & Baji & Cath & Dip & Ede \\
\hline
Game 1 & 17 & 16 & 19 & 17 & 20 \\
\hline
Game 2 & 20 & 13 & 15 & 16 & 18 \\
\hline
Game 3 & 16 & 17 & 15 & 18 & 13 \\
\hline
Game 4 & 13 & 14 & 18 & 15 & 17 \\
\hline
Game 5 & 15 & 16 & 20 & 16 & 15 \\
\hline
\end{tabular}
\end{center}
Each of the five games is to be assigned to one of the five people so that the total score is maximised. No person can be assigned to more than one game.
\begin{enumerate}[label=(\alph*)]
\item Explain why the Hungarian algorithm may be used if each number, $x$, in the table is replaced by $20 - x$.
\item Form a new table by subtracting each number in the table above from 20, and hence show that, by reducing columns first and then rows, the resulting table of values is as below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
3 & 1 & 1 & 1 & 0 \\
\hline
0 & 4 & 5 & 2 & 2 \\
\hline
4 & 0 & 5 & 0 & 7 \\
\hline
5 & 1 & 0 & 1 & 1 \\
\hline
5 & 1 & 0 & 2 & 5 \\
\hline
\end{tabular}
\end{center}
\item Show that the zeros in the table in part (b) can be covered with one horizontal and three vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
\item Hence find the possible allocations of games to the five people so that the total score is maximised.
\item State the value of the maximum total score.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2008 Q2 [13]}}