| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.3 This is a standard textbook application of the Hungarian algorithm with a 3×4 matrix requiring dummy row addition. While it has 13 marks indicating multiple steps, it's a direct procedural application with no problem-solving insight needed—students follow the algorithm mechanically (row reduction, column reduction, covering zeros, adjusting). The unbalanced matrix adds minor complexity but is routine in D2. Slightly easier than average due to its purely algorithmic nature. |
| Spec | 7.03m Packing extensions: 2D/3D packing and knapsack problems |
| Windows | Conservatory | Doors | Greenhouse | |
| Team A | 27 | 80 | 8 | 81 |
| Team B | 28 | 60 | 5 | 71 |
| Team C | 30 | 90 | 7 | 73 |
5. A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job:
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Windows & Conservatory & Doors & Greenhouse \\
\hline
Team A & 27 & 80 & 8 & 81 \\
\hline
Team B & 28 & 60 & 5 & 71 \\
\hline
Team C & 30 & 90 & 7 & 73 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment.\\
(13 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q5 [13]}}