| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | January |
| 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 straightforward application of the Hungarian algorithm with clear step-by-step instructions. Part (a) is mechanical arithmetic (row/column reduction), part (b) follows the standard covering procedure, and parts (c)-(d) involve reading off the optimal allocation. The algorithm is procedural with no problem-solving insight required, making it easier than average A-level questions that require mathematical reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| P | Q | R | S | T | |
| Task 1 | 17 | 20 | 19 | 17 | 17 |
| Task 2 | 19 | 18 | 18 | 18 | 15 |
| Task 3 | 13 | 16 | 16 | 14 | 12 |
| Task 4 | 13 | 13 | 15 | 13 | 13 |
| Task 5 | 10 | 11 | 12 | 14 | 13 |
| 3 | 5 | 3 | 0 | 1 |
| 6 | 4 | 3 | 2 | 0 |
| 3 | 5 | 4 | 1 | 0 |
| 3 | 2 | 3 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
1 The times taken in minutes for five people, $\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }$ and T , to complete each of five different tasks are recorded in the table.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& P & Q & R & S & T \\
\hline
Task 1 & 17 & 20 & 19 & 17 & 17 \\
\hline
Task 2 & 19 & 18 & 18 & 18 & 15 \\
\hline
Task 3 & 13 & 16 & 16 & 14 & 12 \\
\hline
Task 4 & 13 & 13 & 15 & 13 & 13 \\
\hline
Task 5 & 10 & 11 & 12 & 14 & 13 \\
\hline
\end{tabular}
\end{center}
Using the Hungarian algorithm, each of the five people is to be allocated to a different task so that the total time for completing the five tasks is minimised.
\begin{enumerate}[label=(\alph*)]
\item By reducing the columns first and then the rows, show that the new table of values is as follows.
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\hline
3 & 5 & 3 & 0 & 1 \\
\hline
6 & 4 & 3 & 2 & 0 \\
\hline
3 & 5 & 4 & 1 & 0 \\
\hline
3 & 2 & 3 & 0 & 1 \\
\hline
0 & 0 & 0 & 1 & 1 \\
\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 people to the five tasks so that the total completion time is minimised.
\item Find the minimum total time for completing the five tasks.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2009 Q1 [12]}}