| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2022 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Moderate -0.5 This is a standard Hungarian algorithm application with straightforward restrictions (handled by dashes in the table). The algorithm itself is mechanical once learned, requiring row/column reduction and covering lines. While it has multiple steps, it's a routine textbook exercise for FD2 students with no novel problem-solving required beyond following the algorithm procedure. |
| Spec | 7.03k Sorting: quick sort |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | P | Q | R | S |
| A | 54 | 48 | 51 | 52 |
| B | 55 | 51 | 53 | 58 |
| C | 52 | - | 53 | 54 |
| D | 67 | 63 | 68 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct cost matrix e.g. \(\begin{pmatrix} & P & Q & R & S \\ A & 54 & 48 & 51 & 52 \\ B & 55 & 51 & 53 & 58 \\ C & 52 & 100 & 53 & 54 \\ D & 67 & 63 & 68 & 100 \end{pmatrix}\) | B1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Reduce row A by 48, reduce row B by 51, reduce row C by 52, row D by 63 (or equivalent). No reduction for columns P and Q, reduce R by 1 and column S by 2 | B1 | 2.4 |
| Correct reduced matrix after row and column reductions, followed by correct second matrix after covering zeros with two lines — solution not optimal, augment by 1 | M1 | 1.1b |
| Correct matrix after second augmentation; three lines required to cover zeros — solution not optimal, augment by 1 | M1 | 1.1b |
| Correct matrix after third augmentation (two valid versions shown); four lines required to cover zeros — solution is optimal | M1, B1 | 1.1b, 2.4 |
| \(A-S,\ B-R,\ C-P,\ D-Q\) | A1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Replace blanks in cells CQ and DS with values \(> 68\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct statements regarding row and column reduction | B1 | |
| Simplifying initial matrix by reducing rows then columns | M1 | Allow 2 independent slips |
| Develop improved solution: one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 2 lines to 3 lines | M1 | |
| Develop improved solution: same process, 3 lines to 4 lines (reaching optimal table) | M1 | |
| Dependent on two augmentations (2→3 lines, 3→4 lines); correct statement on minimum lines to cover zeros at each stage or general statement covering all augmentations | B1 | Must mention 'zeros' at least once and use word 'optimal' |
| CSO on final table + deduction of correct allocation | A1 |
# Question 1:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct cost matrix e.g. $\begin{pmatrix} & P & Q & R & S \\ A & 54 & 48 & 51 & 52 \\ B & 55 & 51 & 53 & 58 \\ C & 52 & 100 & 53 & 54 \\ D & 67 & 63 & 68 & 100 \end{pmatrix}$ | B1 | 1.1b |
**(1 mark)**
---
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Reduce row A by 48, reduce row B by 51, reduce row C by 52, row D by 63 (or equivalent). No reduction for columns P and Q, reduce R by 1 and column S by 2 | B1 | 2.4 |
| Correct reduced matrix after row and column reductions, followed by correct second matrix after covering zeros with two lines — solution not optimal, augment by 1 | M1 | 1.1b |
| Correct matrix after second augmentation; three lines required to cover zeros — solution not optimal, augment by 1 | M1 | 1.1b |
| Correct matrix after third augmentation (two valid versions shown); four lines required to cover zeros — solution is optimal | M1, B1 | 1.1b, 2.4 |
| $A-S,\ B-R,\ C-P,\ D-Q$ | A1 | 2.2a |
**(6 marks)**
**Total: 7 marks**
# Question 1:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Replace blanks in cells CQ and DS with values $> 68$ | B1 | cao |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct statements regarding row and column reduction | B1 | |
| Simplifying initial matrix by reducing rows then columns | M1 | Allow 2 independent slips |
| Develop improved solution: one double covered $+e$; one uncovered $-e$; one single covered unchanged. 2 lines to 3 lines | M1 | |
| Develop improved solution: same process, 3 lines to 4 lines (reaching optimal table) | M1 | |
| Dependent on two augmentations (2→3 lines, 3→4 lines); correct statement on minimum lines to cover zeros at each stage **or** general statement covering all augmentations | B1 | Must mention 'zeros' at least once and use word 'optimal' |
| CSO on final table + deduction of correct allocation | A1 | |
---\begin{enumerate}
\item Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S.
\end{enumerate}
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 and worker D cannot be assigned to task S.\\
The time, in minutes, that each worker takes to complete 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 & 54 & 48 & 51 & 52 \\
\hline
B & 55 & 51 & 53 & 58 \\
\hline
C & 52 & - & 53 & 54 \\
\hline
D & 67 & 63 & 68 & - \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm is to be used to find the minimum total time for the four workers to complete the tasks.\\
(a) Modify the table so that the Hungarian algorithm may be used.\\
(b) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total time. You should explain how any initial row and column reductions are made and also how you determine if the table is optimal at each stage.\\
\hfill \mbox{\textit{Edexcel FD2 AS 2022 Q1 [7]}}