| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2016 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm for maximisation with clear instructions to reduce rows first. The 4×4 matrix requires systematic but routine application of the algorithm (convert to minimisation, reduce rows, reduce columns, cover zeros, adjust). While it has multiple steps worth 8 marks, it requires no problem-solving insight—just careful execution of a learned procedure. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 1 | 2 | 3 | 4 | |
| Alexa | 61 | 50 | 47 | 23 |
| Ewan | 71 | 62 | 20 | 61 |
| Faith | 70 | 49 | 48 | 49 |
| Zak | 72 | 68 | 67 | 67 |
| Answer | Marks | Guidance |
|---|---|---|
| Convert to minimisation: subtract all values from largest (72): | M1 | |
| 1 | 2 | 3 |
| Alexa | 11 | 22 |
| Ewan | 1 | 10 |
| Faith | 2 | 23 |
| Zak | 0 | 4 |
| Row reduction (subtract row minima): | M1 A1 | |
| Column reduction: | M1 A1 | |
| Cover zeros, augment as needed | M1 | |
| Optimal allocation found | A1 A1 | |
| Alexa→Round 3, Ewan→Round 2, Faith→Round 1, Zak→Round 4 (or similar valid allocation) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Maximum total score = \(47+62+70+67 = \mathbf{246}\) | B1 | ft from (a) |
## Question 3:
**(a)**
Convert to minimisation: subtract all values from largest (72): | M1 |
| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
|Alexa|11|22|25|49|
|Ewan|1|10|52|11|
|Faith|2|23|24|23|
|Zak|0|4|5|5|
Row reduction (subtract row minima): | M1 A1 |
Column reduction: | M1 A1 |
Cover zeros, augment as needed | M1 |
Optimal allocation found | A1 A1 |
Alexa→Round 3, Ewan→Round 2, Faith→Round 1, Zak→Round 4 (or similar valid allocation) | A1 |
**(b)**
Maximum total score = $47+62+70+67 = \mathbf{246}$ | B1 | ft from (a)
---3. Four pupils, Alexa, Ewan, Faith and Zak, are to be allocated to four rounds, 1, 2, 3 and 4, in a mathematics competition. Each pupil is to be allocated to exactly one round and each round must be allocated to exactly one pupil.
Each pupil has been given a score, based on previous performance, to show how suitable they are for each round. The higher the score the more suitable the pupil is for that round. The scores for each pupil are shown in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
Alexa & 61 & 50 & 47 & 23 \\
\hline
Ewan & 71 & 62 & 20 & 61 \\
\hline
Faith & 70 & 49 & 48 & 49 \\
\hline
Zak & 72 & 68 & 67 & 67 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total score. You must make your method clear and show the table after each stage.\\
(8)
\item State the maximum total score.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2016 Q3 [9]}}