| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm with a 4×4 matrix. The question explicitly tells students which algorithm to use and even specifies to reduce rows first, making it purely procedural. While it requires careful arithmetic through multiple steps (row reduction, column reduction, covering zeros, adjusting matrix), there's no problem-solving or insight needed—just methodical execution of a learned algorithm. The 11 marks reflect the length rather than conceptual difficulty. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt |
| Job 1 | Job 2 | Job 3 | Job 4 | |
| Machine 1 | 14 | 5 | 8 | 7 |
| Machine 2 | 2 | 12 | 6 | 5 |
| Machine 3 | 7 | 8 | 3 | 9 |
| Machine 4 | 2 | 4 | 6 | 10 |
An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.
\begin{tabular}{c|cccc}
& Job 1 & Job 2 & Job 3 & Job 4 \\
\hline
Machine 1 & 14 & 5 & 8 & 7 \\
Machine 2 & 2 & 12 & 6 & 5 \\
Machine 3 & 7 & 8 & 3 & 9 \\
Machine 4 & 2 & 4 & 6 & 10
\end{tabular}
Use the Hungarian algorithm, \emph{reducing rows first}, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time. [11]
\hfill \mbox{\textit{Edexcel D2 Q5 [11]}}