| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2020 |
| Session | June |
| Marks | 9 |
| 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 one restriction (C cannot do Q). Part (a) tests understanding that the algorithm solves minimization problems (requiring negation/subtraction from maximum), part (b) is routine table modification, and part (c) is mechanical execution of the algorithm. The restriction is handled trivially by leaving a cell blank. This is slightly easier than average because it's a direct application of a taught algorithm with clear steps, though the maximization-to-minimization conversion and systematic execution require care. |
| Spec | 7.03k Sorting: quick sort |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | P | Q | R | S |
| A | 72 | 98 | 59 | 84 |
| B | 67 | 87 | 68 | 86 |
| C | 70 | - | 62 | 79 |
| D | 78 | 93 | 64 | 81 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Subtract each entry from a constant (e.g. 98) to convert from maximisation to minimisation | B1 | |
| Add an appropriate large value to cell CQ (e.g. twice the largest value) to make CQ unattractive | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Reduced matrix e.g. \(\begin{pmatrix} & P & Q & R & S \\ A & 26 & 0 & 39 & 14 \\ B & 31 & 11 & 30 & 12 \\ C & 28 & 78 & 36 & 19 \\ D & 20 & 5 & 34 & 17 \end{pmatrix}\) | B1 | Cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| No reduction for row A; reduce row B by 11, row C by 19, row D by 5; reduce column P by 9 and column R by 17, no reduction in columns Q and S | B1 | |
| Row and column reduction giving correct intermediate matrices | M1 | |
| Augment by 1; giving correct matrix | M1 | |
| Augment by 5; giving correct matrix | M1 | |
| Four lines required to cover zeros; solution is optimal | B1 | |
| \(A-Q,\ B-S,\ C-R,\ D-P\) | A1 |
## Question 2:
### Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Subtract each entry from a constant (e.g. 98) to convert from maximisation to minimisation | B1 | |
| Add an appropriate large value to cell CQ (e.g. twice the largest value) to make CQ unattractive | B1 | |
### Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Reduced matrix e.g. $\begin{pmatrix} & P & Q & R & S \\ A & 26 & 0 & 39 & 14 \\ B & 31 & 11 & 30 & 12 \\ C & 28 & 78 & 36 & 19 \\ D & 20 & 5 & 34 & 17 \end{pmatrix}$ | B1 | Cao |
### Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| No reduction for row A; reduce row B by 11, row C by 19, row D by 5; reduce column P by 9 and column R by 17, no reduction in columns Q and S | B1 | |
| Row and column reduction giving correct intermediate matrices | M1 | |
| Augment by 1; giving correct matrix | M1 | |
| Augment by 5; giving correct matrix | M1 | |
| Four lines required to cover zeros; solution is optimal | B1 | |
| $A-Q,\ B-S,\ C-R,\ D-P$ | A1 | |2. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S.
Each worker must be assigned to one task, and each task must be done by exactly one worker.
Worker C cannot be assigned to task Q.
The amount, in pounds, that each worker would earn when 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 & 72 & 98 & 59 & 84 \\
\hline
B & 67 & 87 & 68 & 86 \\
\hline
C & 70 & - & 62 & 79 \\
\hline
D & 78 & 93 & 64 & 81 \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the four workers.
\begin{enumerate}[label=(\alph*)]
\item Explain how the table should be modified so that the Hungarian algorithm may be applied.
\item Modify the table so that the Hungarian algorithm may be applied.
\item Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You should explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2020 Q2 [9]}}