| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2021 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Standard +0.3 This is a standard Hungarian algorithm application with minor modifications (unequal sets, one forbidden assignment, maximization). The question explicitly guides students through the process and asks them to explain standard steps. While it requires careful execution of the algorithm, it involves routine textbook procedures with no novel problem-solving or insight required. |
| Spec | 7.03k Sorting: quick sort |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | \(\mathbf { P }\) | \(\mathbf { Q }\) | \(\mathbf { R }\) | \(\mathbf { S }\) |
| \(\mathbf { A }\) | 55 | 56 | 58 | 57 |
| \(\mathbf { B }\) | 60 | 61 | - | 64 |
| \(\mathbf { C }\) | 59 | 60 | 62 | 63 |
| \(\mathbf { D }\) | 64 | 66 | 71 | 69 |
| \(\mathbf { E }\) | 65 | 68 | 72 | 66 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Subtract each entry from a constant (e.g., 72) to convert from maximisation problem to minimisation | B1 | AO 1.1a |
| Add an additional dummy column with any equal values (e.g., 72) to create a square array and input a suitable large number in cell BR | B1 | AO 3.5c |
| Total: (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| e.g., reduced matrix: \(\begin{pmatrix} & P & Q & R & S & X \\ A & 17 & 16 & 14 & 15 & 72 \\ B & 12 & 11 & 100 & 8 & 72 \\ C & 13 & 12 & 10 & 9 & 72 \\ D & 8 & 6 & 1 & 3 & 72 \\ E & 7 & 4 & 0 & 6 & 72 \end{pmatrix}\) | B1 | AO 1.1b |
| Reduce row A by 14, row B by 8, row C by 9, row D by 1, no reduction in row E. Reduce column P by 3, column Q by 2, no reductions in columns R and S, reduce column X by 58 (or equivalent) | B1 | AO 2.4 |
| Reduced rows and columns matrix: \(\begin{pmatrix} & P & Q & R & S & X \\ A & 0 & 0 & 0 & 1 & 0 \\ B & 1 & 1 & 92 & 0 & 6 \\ C & 1 & 1 & 1 & 0 & 5 \\ D & 4 & 3 & 0 & 2 & 13 \\ E & 4 & 2 & 0 & 6 & 14 \end{pmatrix}\); minimum of three lines required to cover zeros, hence not optimal (augment by 1) | M1 | AO 1.1b |
| After augmentation: \(\begin{pmatrix} & P & Q & R & S & X \\ A & 0 & 0 & 1 & 2 & 0 \\ B & 0 & 0 & 92 & 0 & 5 \\ C & 0 & 0 & 1 & 0 & 4 \\ D & 3 & 2 & 0 & 2 & 12 \\ E & 3 & 1 & 0 & 6 & 13 \end{pmatrix}\); minimum of four lines required to cover zeros, hence not optimal (augment by 1) | M1 | AO 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| M1 | 1.1b | Correct improved matrix shown |
| Minimum of five lines required to cover the zeros hence solution is optimal | B1 | 2.4 |
| \((\pounds)\ 262\) | A1 | 2.2a |
## Question 1:
### Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Subtract each entry from a constant (e.g., 72) to convert from maximisation problem to minimisation | B1 | AO 1.1a |
| Add an additional dummy column with any equal values (e.g., 72) to create a square array and input a suitable large number in cell BR | B1 | AO 3.5c |
| **Total: (2)** | | |
### Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| e.g., reduced matrix: $\begin{pmatrix} & P & Q & R & S & X \\ A & 17 & 16 & 14 & 15 & 72 \\ B & 12 & 11 & 100 & 8 & 72 \\ C & 13 & 12 & 10 & 9 & 72 \\ D & 8 & 6 & 1 & 3 & 72 \\ E & 7 & 4 & 0 & 6 & 72 \end{pmatrix}$ | B1 | AO 1.1b |
| Reduce row A by 14, row B by 8, row C by 9, row D by 1, no reduction in row E. Reduce column P by 3, column Q by 2, no reductions in columns R and S, reduce column X by 58 (or equivalent) | B1 | AO 2.4 |
| Reduced rows and columns matrix: $\begin{pmatrix} & P & Q & R & S & X \\ A & 0 & 0 & 0 & 1 & 0 \\ B & 1 & 1 & 92 & 0 & 6 \\ C & 1 & 1 & 1 & 0 & 5 \\ D & 4 & 3 & 0 & 2 & 13 \\ E & 4 & 2 & 0 & 6 & 14 \end{pmatrix}$; minimum of three lines required to cover zeros, hence not optimal (augment by 1) | M1 | AO 1.1b |
| After augmentation: $\begin{pmatrix} & P & Q & R & S & X \\ A & 0 & 0 & 1 & 2 & 0 \\ B & 0 & 0 & 92 & 0 & 5 \\ C & 0 & 0 & 1 & 0 & 4 \\ D & 3 & 2 & 0 & 2 & 12 \\ E & 3 & 1 & 0 & 6 & 13 \end{pmatrix}$; minimum of four lines required to cover zeros, hence not optimal (augment by 1) | M1 | AO 1.1b |
# Question 1 (Hungarian Algorithm):
**Final Matrix:**
$$\begin{pmatrix} & P & Q & R & S & X \\ A & 0 & 0 & 2 & 2 & 0 \\ B & 0 & 0 & 93 & 0 & 5 \\ C & 0 & 0 & 2 & 0 & 4 \\ D & 2 & 1 & 0 & 1 & 11 \\ E & 2 & 0 & 0 & 5 & 12 \end{pmatrix}$$
| M1 | 1.1b | Correct improved matrix shown |
Minimum of five lines required to cover the zeros hence solution is optimal | B1 | 2.4 |
$(\pounds)\ 262$ | A1 | 2.2a |
**Notes:**
- **M1:** Developing improved solution — double covered $+e$; uncovered $-e$; single covered unchanged. 4 lines to 5 lines needed
- **B1:** Correct statement regarding minimum number of lines to cover zeros
- **A1:** cso on final table (must have scored all previous marks) + correct total earnings
---\begin{enumerate}
\item Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.
\end{enumerate}
Each task must be assigned to exactly one worker and each worker can do at most one task.\\
Worker B cannot be assigned to task R.\\
The amount, in pounds, that each worker will earn if they are assigned to each task is shown in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & $\mathbf { P }$ & $\mathbf { Q }$ & $\mathbf { R }$ & $\mathbf { S }$ \\
\hline
$\mathbf { A }$ & 55 & 56 & 58 & 57 \\
\hline
$\mathbf { B }$ & 60 & 61 & - & 64 \\
\hline
$\mathbf { C }$ & 59 & 60 & 62 & 63 \\
\hline
$\mathbf { D }$ & 64 & 66 & 71 & 69 \\
\hline
$\mathbf { E }$ & 65 & 68 & 72 & 66 \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the five workers.\\
(a) Explain how the table should be modified to allow the Hungarian algorithm to be used, giving reasons for your answer.\\
(b) Reducing rows first, use the Hungarian algorithm to obtain the maximum possible total earnings. You should explain how any initial row and column reductions were made and how you determined if the table was optimal at each stage.\\
\hfill \mbox{\textit{Edexcel FD2 AS 2021 Q1 [9]}}