| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2022 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm with a small 4×4 matrix, requiring only standard row and column reductions followed by covering zeros. The algorithm is mechanical with no problem-solving insight needed, making it easier than average A-level questions, though the bookwork nature of Further Maths algorithms prevents it from being trivial. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm |
| 1 | 2 | 3 | 4 | |
| A | 32 | 45 | 34 | 48 |
| B | 37 | 39 | 50 | 46 |
| C | 46 | 44 | 40 | 42 |
| D | 43 | 45 | 48 | 52 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Reduce rows then columns to get \(\begin{bmatrix} 0 & 11 & 2 & 14 \\ 0 & 0 & 13 & 7 \\ 6 & 2 & 0 & 0 \\ 0 & 0 & 5 & 7 \end{bmatrix}\) | M1, A1 | Simplifying initial matrix by reducing rows then columns; allow up to 2 independent slips |
| Followed by \(\begin{bmatrix} 0 & 11 & 0 & 12 \\ 0 & 0 & 11 & 5 \\ 8 & 4 & 0 & 0 \\ 0 & 0 & 3 & 5 \end{bmatrix}\) | M1, A1ft | Develop improved solution: one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 3 lines to 4 lines needed |
| \(A-3,\ B-1,\ C-4,\ D-2\) or \(A-3,\ B-2,\ C-4,\ D-1\) | A1ft | Must be fully written; do not accept just zeros indicated on final matrix |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(158\) | B1 | CAO – solution of original problem |
# Question 1:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Reduce rows then columns to get $\begin{bmatrix} 0 & 11 & 2 & 14 \\ 0 & 0 & 13 & 7 \\ 6 & 2 & 0 & 0 \\ 0 & 0 & 5 & 7 \end{bmatrix}$ | M1, A1 | Simplifying initial matrix by reducing rows then columns; allow up to 2 independent slips |
| Followed by $\begin{bmatrix} 0 & 11 & 0 & 12 \\ 0 & 0 & 11 & 5 \\ 8 & 4 & 0 & 0 \\ 0 & 0 & 3 & 5 \end{bmatrix}$ | M1, A1ft | Develop improved solution: one double covered $+e$; one uncovered $-e$; one single covered unchanged. 3 lines to 4 lines needed |
| $A-3,\ B-1,\ C-4,\ D-2$ or $A-3,\ B-2,\ C-4,\ D-1$ | A1ft | Must be fully written; do not accept just zeros indicated on final matrix |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $158$ | B1 | CAO – solution of original problem |
---\begin{enumerate}
\item Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.
\end{enumerate}
The cost of assigning each worker to each task is shown in the table below.\\
The total cost is to be minimised.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 32 & 45 & 34 & 48 \\
\hline
B & 37 & 39 & 50 & 46 \\
\hline
C & 46 & 44 & 40 & 42 \\
\hline
D & 43 & 45 & 48 & 52 \\
\hline
\end{tabular}
\end{center}
(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total cost. You must make your method clear and show the table after each stage.\\
(b) State the minimum total cost.\\
\hfill \mbox{\textit{Edexcel FD2 2022 Q1 [6]}}