| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| 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 algorithmic question requiring mechanical application of the Hungarian algorithm with clear step-by-step instructions. While it involves multiple parts and careful arithmetic, it requires no problem-solving insight or novel thinking—students simply follow the prescribed procedure they've been taught. The question explicitly guides them through each stage (transformation, row/column reduction, line covering, finding allocation), making it slightly easier than a typical A-level question that might require more independent decision-making. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Course 1 | Course 2 | Course 3 | Course 4 | Course 5 | |
| Ron | 13 | 13 | 9 | 10 | 13 |
| Sam | 13 | 14 | 12 | 17 | 15 |
| Tom | 16 | 10 | 8 | 14 | 14 |
| Una | 11 | 14 | 12 | 16 | 10 |
| Viv | 12 | 14 | 14 | 13 | 15 |
| 0 | 0 | 3 | 3 | 0 |
| 4 | 3 | 4 | 0 | 2 |
| 0 | 6 | 7 | 2 | 2 |
| 5 | 2 | 3 | 0 | 6 |
| 3 | 1 | 0 | 2 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | 1 | 0 |
| P | x | y |
| 3 | D | H |
| Answer | Marks |
|---|---|
| Path | Extra Flow |
Question 3:
3 | 1 | 0 | 2 | 0
P | x | y | z | s | t | value
3 | D | H
I
Path | Extra Flow3 Five lecturers were given the following scores when matched against criteria for teaching five courses in a college.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Course 1 & Course 2 & Course 3 & Course 4 & Course 5 \\
\hline
Ron & 13 & 13 & 9 & 10 & 13 \\
\hline
Sam & 13 & 14 & 12 & 17 & 15 \\
\hline
Tom & 16 & 10 & 8 & 14 & 14 \\
\hline
Una & 11 & 14 & 12 & 16 & 10 \\
\hline
Viv & 12 & 14 & 14 & 13 & 15 \\
\hline
\end{tabular}
\end{center}
Each lecturer is to be allocated to exactly one of the courses so as to maximise the total score of the five lecturers.
\begin{enumerate}[label=(\alph*)]
\item Explain why the Hungarian algorithm may be used if each number, $x$, in the table is replaced by $17 - x$.
\item Form a new table by subtracting each number in the table above from 17. Hence show that, by reducing rows first and then columns, the resulting table of values is as below.
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\hline
0 & 0 & 3 & 3 & 0 \\
\hline
4 & 3 & 4 & 0 & 2 \\
\hline
0 & 6 & 7 & 2 & 2 \\
\hline
5 & 2 & 3 & 0 & 6 \\
\hline
3 & 1 & 0 & 2 & 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 Hence find the possible allocations of courses to the five lecturers so that the total score is maximised.
\item State the value of the maximum total score.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2009 Q3 [13]}}