| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2020 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Standard +0.3 This is a standard Hungarian algorithm application with straightforward restrictions (two forbidden assignments). The method is algorithmic and well-practiced in FD2, requiring row/column reduction and covering lines but no novel problem-solving. Slightly easier than average A-level due to its mechanical nature and small matrix size (4×4). |
| 1 | 2 | 3 | 4 | |
| A | 29 | 20 | - | 23 |
| B | 32 | 30 | 28 | - |
| C | 35 | 32 | 34 | 25 |
| D | 29 | 31 | 27 | 30 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Subtracting each entry from a constant value \(\geq 35\) to convert from maximisation to minimisation | M1 | Convert from maximisation to minimisation (allow at most two errors) |
| Add a sufficiently large number (\(> 15\)) to cells A3 and B4, e.g. \(\begin{pmatrix} 6 & 15 & 100 & 12 \\ 3 & 5 & 7 & 100 \\ 0 & 3 & 1 & 10 \\ 6 & 4 & 8 & 5 \end{pmatrix}\) | B1 | Adding a large number (at least 16) to cells A3 and B4 |
| Reduce rows \(\begin{pmatrix} 0 & 9 & 94 & 6 \\ 0 & 2 & 4 & 97 \\ 0 & 3 & 1 & 10 \\ 2 & 0 & 4 & 1 \end{pmatrix}\) and then columns \(\begin{pmatrix} 0 & 9 & 93 & 5 \\ 0 & 2 & 3 & 96 \\ 0 & 3 & 0 & 9 \\ 2 & 0 & 3 & 0 \end{pmatrix}\) | M1 A1ft | Simplifying by reducing rows then columns; cao following from earlier subtraction |
| followed by \(\begin{pmatrix} 0 & 7 & 93 & 3 \\ 0 & 0 & 3 & 94 \\ 0 & 1 & 0 & 7 \\ 4 & 0 & 5 & 0 \end{pmatrix}\) or \(\begin{pmatrix} 0 & 7 & 91 & 3 \\ 0 & 0 & 1 & 94 \\ 2 & 3 & 0 & 9 \\ 4 & 0 & 3 & 0 \end{pmatrix}\) | M1 A1ft | Develop improved solution — need one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 3 lines needed to 4 lines needed; cao following from row and column reduction final table |
| \(A-1,\ B-2,\ C-3,\ D-4\) | B1ft | Correct allocation ft their optimal table (all previous M marks must have been awarded) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| £123 | B1 | cao — solution of original problem |
## Question 1:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Subtracting each entry from a constant value $\geq 35$ to convert from maximisation to minimisation | M1 | Convert from maximisation to minimisation (allow at most two errors) |
| Add a sufficiently large number ($> 15$) to cells A3 and B4, e.g. $\begin{pmatrix} 6 & 15 & 100 & 12 \\ 3 & 5 & 7 & 100 \\ 0 & 3 & 1 & 10 \\ 6 & 4 & 8 & 5 \end{pmatrix}$ | B1 | Adding a large number (at least 16) to cells A3 and B4 |
| Reduce rows $\begin{pmatrix} 0 & 9 & 94 & 6 \\ 0 & 2 & 4 & 97 \\ 0 & 3 & 1 & 10 \\ 2 & 0 & 4 & 1 \end{pmatrix}$ and then columns $\begin{pmatrix} 0 & 9 & 93 & 5 \\ 0 & 2 & 3 & 96 \\ 0 & 3 & 0 & 9 \\ 2 & 0 & 3 & 0 \end{pmatrix}$ | M1 A1ft | Simplifying by reducing rows then columns; cao following from earlier subtraction |
| followed by $\begin{pmatrix} 0 & 7 & 93 & 3 \\ 0 & 0 & 3 & 94 \\ 0 & 1 & 0 & 7 \\ 4 & 0 & 5 & 0 \end{pmatrix}$ or $\begin{pmatrix} 0 & 7 & 91 & 3 \\ 0 & 0 & 1 & 94 \\ 2 & 3 & 0 & 9 \\ 4 & 0 & 3 & 0 \end{pmatrix}$ | M1 A1ft | Develop improved solution — need one double covered $+e$; one uncovered $-e$; one single covered unchanged. 3 lines needed to 4 lines needed; cao following from row and column reduction final table |
| $A-1,\ B-2,\ C-3,\ D-4$ | B1ft | Correct allocation ft their optimal table (all previous M marks must have been awarded) |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| £123 | B1 | cao — solution of original problem |
**Total: 8 marks**\begin{enumerate}
\item Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4 . Each worker must be assigned to exactly one task and each task must be done by exactly one worker.
\end{enumerate}
Worker A cannot do task 3 and worker B cannot do task 4
The table below shows the profit, in pounds, that each worker would earn if assigned to each of the tasks.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 29 & 20 & - & 23 \\
\hline
B & 32 & 30 & 28 & - \\
\hline
C & 35 & 32 & 34 & 25 \\
\hline
D & 29 & 31 & 27 & 30 \\
\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 2020 Q1 [8]}}