| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Session | Specimen |
| 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 straightforward application of the Hungarian algorithm with a standard unequal sets setup (6 workers, 5 tasks). The question explicitly tells students to reduce rows first and requires showing tables at each stage, making it a methodical bookwork exercise. While it requires careful arithmetic and systematic application of the algorithm through multiple stages, it involves no problem-solving insight or novel thinking—just following a learned procedure with clear instructions. |
| Spec | 7.03k Sorting: quick sort |
| P | Q | R | S | T | |
| A | 32 | 32 | 35 | 34 | 33 |
| B | 28 | 35 | 31 | 37 | 40 |
| C | 35 | 29 | 33 | 36 | 35 |
| D | 36 | 30 | 34 | 33 | 35 |
| E | 30 | 31 | 29 | 37 | 36 |
| F | 29 | 28 | 32 | 31 | 34 |
| Answer | Marks |
|---|---|
| B1 | 1.1b |
| Answer | Marks |
|---|---|
| M1 | 1.1b |
| Answer | Marks |
|---|---|
| A1 | 1.1b |
| Answer | Marks |
|---|---|
| M1 | 1.1b |
| Answer | Marks |
|---|---|
| A1ft | 1.1b |
| Answer | Marks |
|---|---|
| M1 | 1.1b |
| Answer | Marks |
|---|---|
| A1ft | 1.1b |
| Answer | Marks |
|---|---|
| A1 | 1.1b |
| Answer | Marks |
|---|---|
| A1 | 2.2a |
# Question 1
**B1** | 1.1b
Introducing a dummy task and appropriate value (cao)
**M1** | 1.1b
Simplifying the initial matrix by reducing rows and then columns
**A1** | 1.1b
Correct answer (cao)
**M1** | 1.1b
Develop an improved solution – need to see:
- Double covered $+e$
- One uncovered $-e$
- One single covered unchanged
- 4 lines to 5 lines needed
**A1ft** | 1.1b
Follow through on previous table – no errors
**M1** | 1.1b
Finding the optimal solution – need to see:
- One double covered $+e$
- One uncovered $-e$
- One single covered unchanged
- 5 lines needed to 6 lines needed (reaching optimal table)
**A1ft** | 1.1b
Follow through on previous table – no errors
**A1** | 1.1b
Correct solution only (cso on final table – must have scored all previous marks)
**A1** | 2.2a
Correct solution only – dependent on all M marks being awarded. Deduce the optimal allocation from the location of zeros in the table.
**(9 marks)**\begin{enumerate}
\item Six workers, A, B, C, D, E and F, are to be assigned to five tasks, P, Q, R, S and T.
\end{enumerate}
Each worker can be assigned to at most one task and each task must be done by just one worker. The time, in minutes, that each worker takes to complete each task is shown in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& P & Q & R & S & T \\
\hline
A & 32 & 32 & 35 & 34 & 33 \\
\hline
B & 28 & 35 & 31 & 37 & 40 \\
\hline
C & 35 & 29 & 33 & 36 & 35 \\
\hline
D & 36 & 30 & 34 & 33 & 35 \\
\hline
E & 30 & 31 & 29 & 37 & 36 \\
\hline
F & 29 & 28 & 32 & 31 & 34 \\
\hline
\end{tabular}
\end{center}
Reducing rows first, use the Hungarian algorithm to obtain an allocation which minimises the total time. You must explain your method and show the table after each stage.\\
\hfill \mbox{\textit{Edexcel FD2 AS Q1 [9]}}