| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.8 This is a standard algorithmic question testing the Hungarian algorithm with clear step-by-step instructions. Part (a) is pure mechanical calculation (row/column reduction), part (b) follows the standard covering procedure, and parts (c)-(d) require reading off the solution. While it has multiple parts (7 marks total), each step is routine application of a learned algorithm with no problem-solving insight required, making it easier than average A-level questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | |
| Centre 1 | 10 | 11 | 8 | 12 | 5 |
| Centre 2 | 11 | 5 | 11 | 6 | 7 |
| Centre 3 | 12 | 8 | 7 | 11 | 4 |
| Centre 4 | 10 | 9 | 14 | 10 | 6 |
| Centre 5 | 9 | 9 | 7 | 8 | 9 |
| 3 | 6 | 3 | 6 | 0 |
| 4 | 0 | 6 | 0 | 2 |
| 6 | 4 | 3 | 6 | 0 |
| 2 | 3 | 8 | 3 | 0 |
| 0 | 2 | 0 | 0 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Row reduction: subtract row minima (5,5,4,9,7) | M1 | |
| Correct row-reduced table | A1 | |
| Column reduction: subtract column minima (0,0,0,0,0) giving stated table | A1 | 3 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Zeros covered by 3 lines (e.g. col B, col D, row 5) | B1 M1 | |
| Minimum uncovered element identified (= 2) | A1 | |
| Correct adjusted table produced | A1 A1 | 5 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Allocation 1: A→Centre3, B→Centre2, C→Centre5, D→Centre1(?), E→Centre4 | M1 A1 | |
| Allocation 2: alternative valid allocation stated | A1 | 3 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum total cost = £37 | B1 | 1 mark |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Row reduction: subtract row minima (5,5,4,9,7) | M1 | |
| Correct row-reduced table | A1 | |
| Column reduction: subtract column minima (0,0,0,0,0) giving stated table | A1 | 3 marks total |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Zeros covered by 3 lines (e.g. col B, col D, row 5) | B1 M1 | |
| Minimum uncovered element identified (= 2) | A1 | |
| Correct adjusted table produced | A1 A1 | 5 marks total |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Allocation 1: A→Centre3, B→Centre2, C→Centre5, D→Centre1(?), E→Centre4 | M1 A1 | |
| Allocation 2: alternative valid allocation stated | A1 | 3 marks total |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum total cost = £37 | B1 | 1 mark |
---2 The daily costs, in pounds, for five managers A, B, C, D and E to travel to five different centres are recorded in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& A & B & C & D & E \\
\hline
Centre 1 & 10 & 11 & 8 & 12 & 5 \\
\hline
Centre 2 & 11 & 5 & 11 & 6 & 7 \\
\hline
Centre 3 & 12 & 8 & 7 & 11 & 4 \\
\hline
Centre 4 & 10 & 9 & 14 & 10 & 6 \\
\hline
Centre 5 & 9 & 9 & 7 & 8 & 9 \\
\hline
\end{tabular}
\end{center}
Using the Hungarian algorithm, each of the five managers is to be allocated to a different centre so that the overall total travel cost is minimised.
\begin{enumerate}[label=(\alph*)]
\item By reducing the rows first and then the columns, show that the new table of values is
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\hline
3 & 6 & 3 & 6 & 0 \\
\hline
4 & 0 & 6 & 0 & 2 \\
\hline
6 & 4 & 3 & 6 & 0 \\
\hline
2 & 3 & 8 & 3 & 0 \\
\hline
0 & 2 & 0 & 0 & 2 \\
\hline
\end{tabular}
\end{center}
\item Show that the zeros in the table in part (a) can be covered with three lines and use adjustments to produce a table where five lines are required to cover the zeros.
\item Hence find the two possible ways of allocating the five managers to the five centres with the least possible total travel cost.
\item Find the value of this minimum daily total travel cost.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2007 Q2 [12]}}