| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2023 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Standard +0.8 This is a standard Hungarian algorithm application for maximisation requiring conversion to minimisation (subtracting from maximum), row reduction, column reduction, and covering zeros to find optimal allocation. While mechanical, it requires careful arithmetic across multiple stages and proper documentation of each step, making it moderately challenging for Further Maths students but still a textbook procedure. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | 1 | 2 | 3 | 4 |
| A | 34 | 20 | 18 | 15 |
| B | 49 | 31 | 12 | 34 |
| C | 48 | 27 | 23 | 26 |
| D | 52 | 45 | 42 | 42 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Subtract all elements from value \(\geq 52\), e.g. \(\begin{bmatrix}18&32&34&37\\3&21&40&18\\4&25&29&26\\0&7&10&10\end{bmatrix}\) | B1 | Converting correctly from minimisation to maximisation |
| Reduce rows then columns: \(\begin{bmatrix}0&14&16&19\\0&18&37&15\\0&21&25&22\\0&7&10&10\end{bmatrix} \rightarrow \begin{bmatrix}0&7&6&9\\0&11&27&5\\0&14&15&12\\0&0&0&0\end{bmatrix}\) | M1, A1 | Simplifying by reducing rows then columns (allow up to 2 independent slips); CAO |
| \(\begin{bmatrix}0&2&1&4\\0&6&22&0\\0&9&10&7\\5&0&0&0\end{bmatrix}\) followed by \(\begin{bmatrix}0&1&0&3\\1&6&22&0\\0&8&9&6\\6&0&0&0\end{bmatrix}\) or \(\begin{bmatrix}0&1&0&4\\0&5&21&0\\0&8&9&7\\6&0&0&1\end{bmatrix}\) | M1, A1ft, A1 | Develop improved solution (double covered +e, uncovered −e, single covered unchanged); CAO f/t from previous table; CSO on final table |
| Optimal allocation: A=3, B=4, C=1, D=2 | A1ft | Correct allocation ft from optimal table |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Total score \(= 18 + 34 + 48 + 45 = 145\) | B1 | CAO – solution of original problem (both previous M marks must have been awarded) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| No conversion applied | B0 | No conversion |
| Reduce rows: \(\begin{bmatrix}19&5&3&0\\37&19&0&22\\25&4&0&3\\10&3&0&0\end{bmatrix}\) then columns: \(\begin{bmatrix}9&2&3&0\\27&16&0&22\\15&1&0&3\\0&0&0&0\end{bmatrix}\) | M1, A1 | Reducing rows then columns; CAO |
| Followed by: \(\begin{bmatrix}8&1&3&0\\26&15&0&22\\14&0&0&3\\0&0&1&1\end{bmatrix}\) or \(\begin{bmatrix}9&2&4&0\\26&15&0&21\\14&0&0&2\\0&0&1&0\end{bmatrix}\) | M1, A1, A0 | Develop improved solution; CAO; no further marks |
| Optimal allocation stated | A0 | No further marks awarded |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Total score | B0 | No further marks awarded |
## Question 4:
### Part (a) – Maximisation case:
| Answer/Working | Marks | Guidance |
|---|---|---|
| Subtract all elements from value $\geq 52$, e.g. $\begin{bmatrix}18&32&34&37\\3&21&40&18\\4&25&29&26\\0&7&10&10\end{bmatrix}$ | B1 | Converting correctly from minimisation to maximisation |
| Reduce rows then columns: $\begin{bmatrix}0&14&16&19\\0&18&37&15\\0&21&25&22\\0&7&10&10\end{bmatrix} \rightarrow \begin{bmatrix}0&7&6&9\\0&11&27&5\\0&14&15&12\\0&0&0&0\end{bmatrix}$ | M1, A1 | Simplifying by reducing rows then columns (allow up to 2 independent slips); CAO |
| $\begin{bmatrix}0&2&1&4\\0&6&22&0\\0&9&10&7\\5&0&0&0\end{bmatrix}$ followed by $\begin{bmatrix}0&1&0&3\\1&6&22&0\\0&8&9&6\\6&0&0&0\end{bmatrix}$ or $\begin{bmatrix}0&1&0&4\\0&5&21&0\\0&8&9&7\\6&0&0&1\end{bmatrix}$ | M1, A1ft, A1 | Develop improved solution (double covered +e, uncovered −e, single covered unchanged); CAO f/t from previous table; CSO on final table |
| Optimal allocation: A=3, B=4, C=1, D=2 | A1ft | Correct allocation ft from optimal table |
### Part (b) – Maximisation case:
| Answer/Working | Marks | Guidance |
|---|---|---|
| Total score $= 18 + 34 + 48 + 45 = 145$ | B1 | CAO – solution of original problem (both previous M marks must have been awarded) |
### Part (a) – Special Case (minimisation, max 4/8):
| Answer/Working | Marks | Guidance |
|---|---|---|
| No conversion applied | B0 | No conversion |
| Reduce rows: $\begin{bmatrix}19&5&3&0\\37&19&0&22\\25&4&0&3\\10&3&0&0\end{bmatrix}$ then columns: $\begin{bmatrix}9&2&3&0\\27&16&0&22\\15&1&0&3\\0&0&0&0\end{bmatrix}$ | M1, A1 | Reducing rows then columns; CAO |
| Followed by: $\begin{bmatrix}8&1&3&0\\26&15&0&22\\14&0&0&3\\0&0&1&1\end{bmatrix}$ or $\begin{bmatrix}9&2&4&0\\26&15&0&21\\14&0&0&2\\0&0&1&0\end{bmatrix}$ | M1, A1, A0 | Develop improved solution; CAO; no further marks |
| Optimal allocation stated | A0 | No further marks awarded |
### Part (b) – Special Case:
| Answer/Working | Marks | Guidance |
|---|---|---|
| Total score | B0 | No further marks awarded |\begin{enumerate}
\item Four students, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D , are to be allocated to four rounds, $1,2,3$ and 4 , in a competition. Each student is to take part in exactly one round and no two students may play in the same round.
\end{enumerate}
Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & 1 & 2 & 3 & 4 \\
\hline
A & 34 & 20 & 18 & 15 \\
\hline
B & 49 & 31 & 12 & 34 \\
\hline
C & 48 & 27 & 23 & 26 \\
\hline
D & 52 & 45 & 42 & 42 \\
\hline
\end{tabular}
\end{center}
(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total estimated score. You must make your method clear and show the table after each stage.\\
(b) Find this total estimated score.\\
\hfill \mbox{\textit{Edexcel FD2 2023 Q4 [8]}}