| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2019 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm with clear instructions to reduce rows first. The table is small (3×4), the modification for maximisation is routine (subtract from maximum), and the algorithm follows a mechanical procedure taught in the syllabus. It requires careful execution but no problem-solving insight or novel thinking. |
| Spec | 7.03k Sorting: quick sort |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | P | Q | R | S |
| A | 32 | 40 | 37 | 42 |
| B | 29 | 32 | 35 | 41 |
| C | 37 | 33 | 39 | 40 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Subtract each entry from a constant (e.g. 42) to convert from maximisation problem to minimisation | B1 | AO 1.1a |
| Add an additional dummy row with equal values (e.g. 42, 0, etc.) to create a square array | B1 | AO 3.5c |
| Total: (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct initial reduced matrix, e.g. \(\begin{pmatrix} & P & Q & R & S \\ A & 10 & 2 & 5 & 0 \\ B & 13 & 10 & 7 & 1 \\ C & 5 & 9 & 3 & 2 \\ X & 42 & 42 & 42 & 42 \end{pmatrix}\) | B1 | AO 1.1b |
| No reduction for row A, reduce row B by 1, reduce row C by 2 and row X by 42 (or equivalent). No reduction of columns | B1 | AO 2.4 |
| Reducing rows and columns gives \(\begin{pmatrix} & P & Q & R & S \\ A & 10 & 2 & 5 & 0 \\ B & 12 & 9 & 6 & 0 \\ C & 3 & 7 & 1 & 0 \\ X & 0 & 0 & 0 & 0 \end{pmatrix}\) Two lines required to cover zeros, solution not optimal (augment by 1) | M1 | AO 1.1b |
| \(\begin{pmatrix} & P & Q & R & S \\ A & 9 & 1 & 4 & 0 \\ B & 11 & 8 & 5 & 0 \\ C & 2 & 6 & 0 & 0 \\ X & 0 & 0 & 0 & 1 \end{pmatrix}\) Three lines required to cover zeros, solution not optimal (augment by 1) | M1 | AO 1.1b |
| \(\begin{pmatrix} & P & Q & R & S \\ A & 8 & 0 & 3 & 0 \\ B & 10 & 7 & 4 & 0 \\ C & 2 & 6 & 0 & 1 \\ X & 0 & 0 & 0 & 2 \end{pmatrix}\) or \(\begin{pmatrix} & P & Q & R & S \\ A & 8 & 0 & 4 & 0 \\ B & 10 & 7 & 5 & 0 \\ C & 1 & 5 & 0 & 0 \\ X & 0 & 0 & 1 & 2 \end{pmatrix}\) Four lines required to cover zeros, solution is optimal | M1 | AO 1.1b |
| Four lines required to cover the zeros hence solution is optimal | B1 | AO 2.4 |
| \(A-Q,\ B-S,\ C-R,\ (X-P)\) | A1 | AO 2.2a |
| Total: (7) |
# Question 1:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Subtract each entry from a constant (e.g. 42) to convert from maximisation problem to minimisation | B1 | AO 1.1a |
| Add an additional dummy row with equal values (e.g. 42, 0, etc.) to create a square array | B1 | AO 3.5c |
| **Total: (2)** | | |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct initial reduced matrix, e.g. $\begin{pmatrix} & P & Q & R & S \\ A & 10 & 2 & 5 & 0 \\ B & 13 & 10 & 7 & 1 \\ C & 5 & 9 & 3 & 2 \\ X & 42 & 42 & 42 & 42 \end{pmatrix}$ | B1 | AO 1.1b |
| No reduction for row A, reduce row B by 1, reduce row C by 2 and row X by 42 (or equivalent). No reduction of columns | B1 | AO 2.4 |
| Reducing rows and columns gives $\begin{pmatrix} & P & Q & R & S \\ A & 10 & 2 & 5 & 0 \\ B & 12 & 9 & 6 & 0 \\ C & 3 & 7 & 1 & 0 \\ X & 0 & 0 & 0 & 0 \end{pmatrix}$ Two lines required to cover zeros, solution not optimal (augment by 1) | M1 | AO 1.1b |
| $\begin{pmatrix} & P & Q & R & S \\ A & 9 & 1 & 4 & 0 \\ B & 11 & 8 & 5 & 0 \\ C & 2 & 6 & 0 & 0 \\ X & 0 & 0 & 0 & 1 \end{pmatrix}$ Three lines required to cover zeros, solution not optimal (augment by 1) | M1 | AO 1.1b |
| $\begin{pmatrix} & P & Q & R & S \\ A & 8 & 0 & 3 & 0 \\ B & 10 & 7 & 4 & 0 \\ C & 2 & 6 & 0 & 1 \\ X & 0 & 0 & 0 & 2 \end{pmatrix}$ or $\begin{pmatrix} & P & Q & R & S \\ A & 8 & 0 & 4 & 0 \\ B & 10 & 7 & 5 & 0 \\ C & 1 & 5 & 0 & 0 \\ X & 0 & 0 & 1 & 2 \end{pmatrix}$ Four lines required to cover zeros, solution is optimal | M1 | AO 1.1b |
| Four lines required to cover the zeros hence solution is optimal | B1 | AO 2.4 |
| $A-Q,\ B-S,\ C-R,\ (X-P)$ | A1 | AO 2.2a |
| **Total: (7)** | | |
**(9 marks total)**\begin{enumerate}
\item Three workers, A, B and C, are each to be assigned to one of four tasks, P, Q, R and S.
\end{enumerate}
Each worker must be assigned to at most one task, and each task must be done by at most one worker.\\
The amount, in pounds, that each worker will earn while 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|}{} & P & Q & R & S \\
\hline
A & 32 & 40 & 37 & 42 \\
\hline
B & 29 & 32 & 35 & 41 \\
\hline
C & 37 & 33 & 39 & 40 \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the three workers.\\
(a) Explain how the table should be modified.\\
(2)\\
(b) (i) Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings.\\
(ii) Explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.\\
\hfill \mbox{\textit{Edexcel FD2 AS 2019 Q1 [9]}}