| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Standard +0.3 This is a standard textbook application of the Hungarian algorithm to a 4×3 assignment problem with minimization. While it requires careful execution through multiple steps (row/column reduction, covering zeros, adjusting matrix), the algorithm is entirely procedural with no problem-solving insight needed. The 11 marks reflect the length of working rather than conceptual difficulty. Slightly easier than average since it's pure algorithm application. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Stage | |||
| 1 | 2 | 3 | |
| Alex | 19 | 69 | 168 |
| Darren | 22 | 64 | 157 |
| Leroy | 20 | 72 | 166 |
| Suraj | 23 | 66 | 171 |
Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.
\begin{tabular}{c|ccc}
& \multicolumn{3}{c}{Stage} \\
& 1 & 2 & 3 \\
\hline
Alex & 19 & 69 & 168 \\
Darren & 22 & 64 & 157 \\
Leroy & 20 & 72 & 166 \\
Suraj & 23 & 66 & 171 \\
\end{tabular}
Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm. [11 marks]
\hfill \mbox{\textit{Edexcel D2 Q5 [11]}}