| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2018 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm with a small 4×4 matrix and straightforward decimal values. While it requires careful execution of multiple steps (row reduction, column reduction, covering zeros, improving), the algorithm is entirely procedural with no problem-solving or insight required. It's slightly easier than average because the matrix is small and the method is prescribed. |
| Spec | 7.03k Sorting: quick sort |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | P | Q | R | S |
| A | 7.5 | 3.5 | 8 | 9.5 |
| B | 5 | 2 | 7 | 7.5 |
| C | 4 | 3.5 | 3.5 | 8 |
| D | 6 | 5 | 3.5 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Reducing rows and columns: \(\begin{pmatrix} & P & Q & R & S \\ A & 3.5 & 0 & 4.5 & 5.5 \\ B & 2.5 & 0 & 5 & 5 \\ C & 0 & 0 & 0 & 4 \\ D & 2 & 1.5 & 0 & 0 \end{pmatrix}\) | M1 | Simplifying the initial matrix by reducing rows and then columns |
| Correct reduced matrix | A1 | cao |
| Augment by 2.5: \(\begin{pmatrix} & P & Q & R & S \\ A & 1 & 0 & 2 & 3 \\ B & 0 & 0 & 2.5 & 2.5 \\ C & 0 & 2.5 & 0 & 4 \\ D & 2 & 4 & 0 & 0 \end{pmatrix}\) | M1 | Develop improved solution — need to see one double covered \(+e\); one uncovered \(-e\); and one single covered unchanged. 3 lines to 4 lines needed |
| Correct augmented matrix | A1ft | Allow follow through from one numerical slip only during row/column reduction |
| \(A-Q,\ B-P,\ C-R,\ D-S\) | A1ft | Dependent on all previous M marks and one A mark — deduce optimal allocation from location of zeros in the table |
# Question 1:
| Answer/Working | Marks | Guidance |
|---|---|---|
| Reducing rows and columns: $\begin{pmatrix} & P & Q & R & S \\ A & 3.5 & 0 & 4.5 & 5.5 \\ B & 2.5 & 0 & 5 & 5 \\ C & 0 & 0 & 0 & 4 \\ D & 2 & 1.5 & 0 & 0 \end{pmatrix}$ | M1 | Simplifying the initial matrix by reducing rows and then columns |
| Correct reduced matrix | A1 | cao |
| Augment by 2.5: $\begin{pmatrix} & P & Q & R & S \\ A & 1 & 0 & 2 & 3 \\ B & 0 & 0 & 2.5 & 2.5 \\ C & 0 & 2.5 & 0 & 4 \\ D & 2 & 4 & 0 & 0 \end{pmatrix}$ | M1 | Develop improved solution — need to see one double covered $+e$; one uncovered $-e$; and one single covered unchanged. 3 lines to 4 lines needed |
| Correct augmented matrix | A1ft | Allow follow through from one numerical slip only during row/column reduction |
| $A-Q,\ B-P,\ C-R,\ D-S$ | A1ft | Dependent on all previous M marks and one A mark — deduce optimal allocation from location of zeros in the table |
---\begin{enumerate}
\item Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker must be assigned to exactly one task and each task must be done by only one worker. The time, in hours, that each worker takes to complete each task is shown in the table below.
\end{enumerate}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & P & Q & R & S \\
\hline
A & 7.5 & 3.5 & 8 & 9.5 \\
\hline
B & 5 & 2 & 7 & 7.5 \\
\hline
C & 4 & 3.5 & 3.5 & 8 \\
\hline
D & 6 & 5 & 3.5 & 4 \\
\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 2018 Q1 [5]}}