| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2019 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.8 This is a standard textbook application of the Hungarian algorithm with clear instructions to reduce rows first. The method is algorithmic and routine for D2 students, requiring no problem-solving insight—just careful execution of a learned procedure on a small 5×5 matrix. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| A | B | C | D | E | |
| Frank | 5 | 0 | 7 | 3 | 4 |
| Gill | 5 | 3 | 8 | 10 | 1 |
| Harry | 4 | 3 | 7 | 9 | 0 |
| Imogen | 6 | 3 | 6 | 5 | 4 |
| Jiao | 0 | 2 | 7 | 3 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Since maximising, subtract all elements from some value \(\geq 10\), e.g. subtract from 10 to give \(\begin{bmatrix} 5 & 10 & 3 & 7 & 6 \\ 5 & 7 & 2 & 0 & 9 \\ 6 & 7 & 3 & 1 & 10 \\ 4 & 7 & 4 & 5 & 6 \\ 10 & 8 & 3 & 7 & 8 \end{bmatrix}\) | M1 | Subtracting from some value which must be \(\geq 10\) or all values made negative and then adding a value which must be \(\geq 10\). Condone no more than two errors |
| Reduce rows: \(\begin{bmatrix} 2 & 7 & 0 & 4 & 3 \\ 5 & 7 & 2 & 0 & 9 \\ 5 & 6 & 2 & 0 & 9 \\ 0 & 3 & 0 & 1 & 2 \\ 7 & 5 & 0 & 4 & 5 \end{bmatrix}\) and then columns \(\begin{bmatrix} 2 & 4 & 0 & 4 & 1 \\ 5 & 4 & 2 & 0 & 7 \\ 5 & 3 & 2 & 0 & 7 \\ 0 & 0 & 0 & 1 & 0 \\ 7 & 2 & 0 & 4 & 3 \end{bmatrix}\) | M1 A1 | Reducing rows and then columns – candidates may combine the two stages of converting from a maximum to a minimum problem and row reduction which is acceptable. (Condone two errors). CAO |
| \(\begin{bmatrix} 1 & 3 & 0 & 4 & 0 \\ 4 & 3 & 2 & 0 & 6 \\ 4 & 2 & 2 & 0 & 6 \\ 0 & 0 & 1 & 2 & 0 \\ 6 & 1 & 0 & 4 & 2 \end{bmatrix}\) followed by (eg) \(\begin{bmatrix} 1 & 3 & 0 & 6 & 0 \\ 2 & 1 & 0 & 0 & 4 \\ 2 & 0 & 0 & 0 & 4 \\ 0 & 0 & 1 & 4 & 0 \\ 6 & 1 & 0 & 6 & 2 \end{bmatrix}\) | M1 A1ft | Follow through on their previous table – no errors |
| M1 A1 | One double covered \(+e\); one uncovered \(-e\); and one single covered unchanged. 4 lines needed to 5 lines needed (so getting to an optimal table). CSO on final table | |
| Optimal allocation is \(F=E,\ G=D,\ H=B,\ I=A,\ J=C\) | A1 | CAO – this mark is dependent on all M marks being awarded. Allocation must be written clearly. Just labelling zeros in their table scores A0 |
# Question 3:
| Answer/Working | Mark | Guidance |
|---|---|---|
| Since maximising, subtract all elements from some value $\geq 10$, e.g. subtract from 10 to give $\begin{bmatrix} 5 & 10 & 3 & 7 & 6 \\ 5 & 7 & 2 & 0 & 9 \\ 6 & 7 & 3 & 1 & 10 \\ 4 & 7 & 4 & 5 & 6 \\ 10 & 8 & 3 & 7 & 8 \end{bmatrix}$ | M1 | Subtracting from some value which must be $\geq 10$ or all values made negative and then adding a value which must be $\geq 10$. Condone no more than two errors |
| Reduce rows: $\begin{bmatrix} 2 & 7 & 0 & 4 & 3 \\ 5 & 7 & 2 & 0 & 9 \\ 5 & 6 & 2 & 0 & 9 \\ 0 & 3 & 0 & 1 & 2 \\ 7 & 5 & 0 & 4 & 5 \end{bmatrix}$ and then columns $\begin{bmatrix} 2 & 4 & 0 & 4 & 1 \\ 5 & 4 & 2 & 0 & 7 \\ 5 & 3 & 2 & 0 & 7 \\ 0 & 0 & 0 & 1 & 0 \\ 7 & 2 & 0 & 4 & 3 \end{bmatrix}$ | M1 A1 | Reducing rows and then columns – candidates may combine the two stages of converting from a maximum to a minimum problem and row reduction which is acceptable. (Condone two errors). CAO |
| $\begin{bmatrix} 1 & 3 & 0 & 4 & 0 \\ 4 & 3 & 2 & 0 & 6 \\ 4 & 2 & 2 & 0 & 6 \\ 0 & 0 & 1 & 2 & 0 \\ 6 & 1 & 0 & 4 & 2 \end{bmatrix}$ followed by (eg) $\begin{bmatrix} 1 & 3 & 0 & 6 & 0 \\ 2 & 1 & 0 & 0 & 4 \\ 2 & 0 & 0 & 0 & 4 \\ 0 & 0 & 1 & 4 & 0 \\ 6 & 1 & 0 & 6 & 2 \end{bmatrix}$ | M1 A1ft | Follow through on their previous table – no errors |
| | M1 A1 | One double covered $+e$; one uncovered $-e$; and one single covered unchanged. 4 lines needed to 5 lines needed (so getting to an optimal table). CSO on final table |
| Optimal allocation is $F=E,\ G=D,\ H=B,\ I=A,\ J=C$ | A1 | CAO – this mark is dependent on all M marks being awarded. Allocation must be written clearly. Just labelling zeros in their table scores A0 |
**Total: 8 marks**
---3. Five friends have rented a house that has five bedrooms. They each require their own bedroom. The table below shows how each friend rated the five bedrooms, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }$ and E , where 0 is low and 10 is high.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& A & B & C & D & E \\
\hline
Frank & 5 & 0 & 7 & 3 & 4 \\
\hline
Gill & 5 & 3 & 8 & 10 & 1 \\
\hline
Harry & 4 & 3 & 7 & 9 & 0 \\
\hline
Imogen & 6 & 3 & 6 & 5 & 4 \\
\hline
Jiao & 0 & 2 & 7 & 3 & 2 \\
\hline
\end{tabular}
\end{center}
Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total of all the ratings. You must make your method clear and show the table after each stage.\\
(Total 8 marks)\\
\hfill \mbox{\textit{Edexcel D2 2019 Q3 [8]}}