| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Session | Specimen |
| Marks | 13 |
| 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 for maximisation with clear instructions. Part (a) requires knowing to subtract from maximum (routine modification), part (b) is mechanical application of the algorithm to a small 4×4 matrix, and part (c) is standard LP formulation. While it requires knowledge of Further Maths content, the execution is straightforward with no novel problem-solving required. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | P | Q | R | S |
| A | 32 | 32 | 33 | 35 |
| B | 28 | 35 | 31 | 37 |
| C | 35 | 29 | 33 | 36 |
| D | 36 | 30 | 36 | 33 |
\begin{enumerate}
\item Four workers, A, B, C and D, are to be assigned to 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 just one worker.
The amount, in pounds, that each worker would 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 & 32 & 33 & 35 \\
\hline
B & 28 & 35 & 31 & 37 \\
\hline
C & 35 & 29 & 33 & 36 \\
\hline
D & 36 & 30 & 36 & 33 \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm is to be used to find the maximum total amount which may be earned by the four workers.\\
(a) Explain how the table should be modified.\\
(b) Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings, stating how each table was formed.\\
(c) Formulate the problem as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.\\
\hfill \mbox{\textit{Edexcel FD2 Q3 [13]}}