| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2019 |
| Session | June |
| Marks | 7 |
| 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 with a 4×4 matrix. While the algorithm itself is mechanical (reduce rows, reduce columns, cover zeros, adjust), students must correctly convert to minimisation, perform multiple iterations of covering/adjusting, and track their work through several stages. The multi-stage bookkeeping and potential for arithmetic errors elevate this above average difficulty, though it remains a textbook application of a learned algorithm rather than requiring novel problem-solving insight. |
| Spec | 7.07f Algebraic interpretation: explain simplex calculations |
| 1 | 2 | 3 | 4 | |
| T | 103 | 97 | 74 | 80 |
| H | 201 | 155 | 145 | 155 |
| J | 111 | 80 | 77 | 92 |
| M | 203 | 188 | 137 | 184 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Subtracting each entry from a value \(\geq 203\), e.g. \(\begin{pmatrix}100&106&129&123\\2&48&58&48\\92&123&126&111\\0&15&66&19\end{pmatrix}\) | 1B1 | CAO |
| Reduce rows then columns: \(\begin{pmatrix}0&6&29&23\\0&46&56&46\\0&31&34&19\\0&15&66&19\end{pmatrix}\) then \(\begin{pmatrix}0&0&0&4\\0&40&27&27\\0&25&5&0\\0&9&37&0\end{pmatrix}\) | 1M1, 1A1ft | Allow \(\leq 1\) error in row reduction and \(\leq 1\) error in column reduction. A1ft follows from their conversion to maximising |
| Improved solution: \(\begin{pmatrix}5&0&0&9\\0&35&22&27\\0&20&0&0\\0&4&32&0\end{pmatrix}\) | 2M1, 2A1ft | 2M1: need one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 3 lines to 4 lines |
| \(T-2,\ H-1,\ J-3,\ M-4\) | 3A1 | CSO. Must have gained all previous marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \((\pounds)559\) | 1B1 | CAO — solution of original problem (ignore units lack or incorrect units) |
# Question 2:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Subtracting each entry from a value $\geq 203$, e.g. $\begin{pmatrix}100&106&129&123\\2&48&58&48\\92&123&126&111\\0&15&66&19\end{pmatrix}$ | 1B1 | CAO |
| Reduce rows then columns: $\begin{pmatrix}0&6&29&23\\0&46&56&46\\0&31&34&19\\0&15&66&19\end{pmatrix}$ then $\begin{pmatrix}0&0&0&4\\0&40&27&27\\0&25&5&0\\0&9&37&0\end{pmatrix}$ | 1M1, 1A1ft | Allow $\leq 1$ error in row reduction and $\leq 1$ error in column reduction. A1ft follows from their conversion to maximising |
| Improved solution: $\begin{pmatrix}5&0&0&9\\0&35&22&27\\0&20&0&0\\0&4&32&0\end{pmatrix}$ | 2M1, 2A1ft | 2M1: need one double covered $+e$; one uncovered $-e$; one single covered unchanged. 3 lines to 4 lines |
| $T-2,\ H-1,\ J-3,\ M-4$ | 3A1 | CSO. Must have gained all previous marks |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $(\pounds)559$ | 1B1 | CAO — solution of original problem (ignore units lack or incorrect units) |
---\begin{enumerate}
\item Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.
\end{enumerate}
The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
T & 103 & 97 & 74 & 80 \\
\hline
H & 201 & 155 & 145 & 155 \\
\hline
J & 111 & 80 & 77 & 92 \\
\hline
M & 203 & 188 & 137 & 184 \\
\hline
\end{tabular}
\end{center}
(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.\\
(b) Determine the resulting total profit.\\
\hfill \mbox{\textit{Edexcel FD2 2019 Q2 [7]}}