| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Moderate -0.5 This is a standard Hungarian algorithm application with a straightforward setup (unequal sets requiring a dummy). The method is algorithmic and procedural with no conceptual difficulty beyond following the steps taught in D2. Slightly easier than average A-level due to its mechanical nature, though the 9 marks reflect the need to show multiple iterations clearly. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 1 | 2 | 3 | 4 | |
| \(A\) | 14 | 12 | 11 | 17 |
| \(B\) | 14 | 13 | 15 | 16 |
| \(C\) | 17 | 16 | 10 | 12 |
| \(D\) | 16 | 14 | 13 | 12 |
| \(E\) | 13 | 15 | 13 | 15 |
\begin{enumerate}
\item A company has five machines $A , B , C , D$ and $E$, which it can assign to four tasks $1,2,3$ and 4 . Each task must be assigned to just one machine and each machine may only be assigned to just one task.
\end{enumerate}
The profit, in $\pounds 100$ s, of using each machine to do each task is given in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
$A$ & 14 & 12 & 11 & 17 \\
\hline
$B$ & 14 & 13 & 15 & 16 \\
\hline
$C$ & 17 & 16 & 10 & 12 \\
\hline
$D$ & 16 & 14 & 13 & 12 \\
\hline
$E$ & 13 & 15 & 13 & 15 \\
\hline
\end{tabular}
\end{center}
(a) Explain why it is necessary to add a dummy column to the table.\\
(2)\\
(b) Use the Hungarian algorithm to allocate machines to tasks in order to maximise the total profit. You must make your method clear and show the state of the table after each iteration.\\
(7)\\
(Total 9 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q1 [9]}}