| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with parameters |
| Difficulty | Standard +0.3 This is a standard Hungarian algorithm application with a straightforward parameter. Part (a) is routine dummy row addition, part (b) follows the standard algorithm mechanically with algebraic entries, and part (c) requires re-solving with fixed assignment. The parameter x doesn't create significant complexity since the algorithm proceeds normally. This is slightly easier than average as it's a textbook application of a learned algorithm with minimal problem-solving required. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Ron | Sam | Tim | Vic | Zac | |
| Task 1 | 8 | 7 | 9 | 10 | 8 |
| Task 2 | 9 | \(x\) | 8 | 7 | 11 |
| Task 3 | 12 | 10 | 9 | 9 | 10 |
| Task 4 | 11 | 9 | 8 | 11 | 11 |
2 The following table shows the times taken, in minutes, by five people, Ron, Sam, Tim, Vic and Zac, to carry out the tasks $1,2,3$ and 4 . Sam takes $x$ minutes, where $8 \leqslant x \leqslant 12$, to do task 2.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Ron & Sam & Tim & Vic & Zac \\
\hline
Task 1 & 8 & 7 & 9 & 10 & 8 \\
\hline
Task 2 & 9 & $x$ & 8 & 7 & 11 \\
\hline
Task 3 & 12 & 10 & 9 & 9 & 10 \\
\hline
Task 4 & 11 & 9 & 8 & 11 & 11 \\
\hline
\end{tabular}
\end{center}
Each of the four tasks is to be given to a different one of the five people so that the total time for the four tasks is minimised.
\begin{enumerate}[label=(\alph*)]
\item Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
\item \begin{enumerate}[label=(\roman*)]
\item Use the Hungarian algorithm, reducing columns first and then rows, to reduce the matrix to a form, in terms of $x$, from which the optimum matching can be made.
\item Hence find the possible way of allocating the four tasks so that the total time is minimised.
\item Find the minimum total time.
\end{enumerate}\item After special training, Sam is able to complete task 2 in 7 minutes and is assigned to task 2.
Determine the possible ways of allocating the other three tasks so that the total time is minimised.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2010 Q2 [11]}}