| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2024 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Standard +0.8 This is a Further Maths Decision 2 question requiring the Hungarian algorithm with restrictions (forbidden assignments). Students must understand how to convert a maximization problem to minimization, handle constraints by blocking cells, apply the algorithm, and formulate as an LP with binary variables. While the algorithm itself is mechanical, the setup and LP formulation require solid understanding of the method and constraint handling, making it moderately challenging for Further Maths students. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations |
| P | Q | R | S | |
| A | 65 | 72 | 69 | 75 |
| B | 71 | - | 68 | 65 |
| C | 70 | 69 | 73 | 77 |
| D | 73 | 70 | - | 71 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Subtracting each entry from a constant value e.g. \(\geq 77\) to convert from maximisation problem to minimisation | B1 | Correct reasoning for converting maximisation to minimisation |
| Add a sufficiently large number (\(> 12\)) to cells BQ and DR | B1 | Adding a large number (at least 13) to cells BQ and DR; CAO |
| e.g. \(\begin{bmatrix} 12 & 5 & 8 & 2 \\ 6 & 100 & 9 & 12 \\ 7 & 8 & 4 & 0 \\ 4 & 7 & 100 & 6 \end{bmatrix}\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Let \(x_{ij}\) be 0 or 1; \(\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}\) | B1 | Defining \(x_{ij}\) correctly |
| where \(i \in \{A,B,C,D\}\) and \(j \in \{P,Q,R,S\}\) | B1 | Correct definition of values \(i\) and \(j\) can take |
| minimise \(12x_{AP} + 5x_{AQ} + 8x_{AR} + 2x_{AS} + 6x_{BP} + {'}100{'}x_{BQ} + 9x_{BR} + 12x_{BS} + 7x_{CP} + 8x_{CQ} + 4x_{CR} + 4x_{DP} + 7x_{DQ} + {'}100{'}x_{DR} + 6x_{DS}\) | M1 | Attempt at 15 (or 16) term expression; coefficients 'correct'; 2 'large' values included; condone 2 slips. If more than 2 errors in (a) ft exactly their table |
| (as above, with 'minimise') | A1 | CAO including 'minimise' (or equivalent 14 term expression with 'maximise') |
| Subject to \(\sum x_{Aj}=1,\ \sum x_{Bj}=1,\ \sum x_{Cj}=1,\ \sum x_{Dj}=1\) \(\sum x_{iP}=1,\ \sum x_{iQ}=1,\ \sum x_{iR}=1,\ \sum x_{iS}=1\) | M1 | At least four equations, each in three or four variables, unit coefficients, equal to 1. Do not accept inequalities |
| (all eight equations as above) | A1 | CAO (all eight equations) |
# Question 4:
## Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Subtracting each entry from a constant value e.g. $\geq 77$ to convert from maximisation problem to minimisation | B1 | Correct reasoning for converting maximisation to minimisation |
| Add a sufficiently large number ($> 12$) to cells BQ and DR | B1 | Adding a large number (at least 13) to cells BQ and DR; CAO |
| e.g. $\begin{bmatrix} 12 & 5 & 8 & 2 \\ 6 & 100 & 9 & 12 \\ 7 & 8 & 4 & 0 \\ 4 & 7 & 100 & 6 \end{bmatrix}$ | B1 | CAO |
## Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Let $x_{ij}$ be 0 or 1; $\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}$ | B1 | Defining $x_{ij}$ correctly |
| where $i \in \{A,B,C,D\}$ and $j \in \{P,Q,R,S\}$ | B1 | Correct definition of values $i$ and $j$ can take |
| minimise $12x_{AP} + 5x_{AQ} + 8x_{AR} + 2x_{AS} + 6x_{BP} + {'}100{'}x_{BQ} + 9x_{BR} + 12x_{BS} + 7x_{CP} + 8x_{CQ} + 4x_{CR} + 4x_{DP} + 7x_{DQ} + {'}100{'}x_{DR} + 6x_{DS}$ | M1 | Attempt at 15 (or 16) term expression; coefficients 'correct'; 2 'large' values included; condone 2 slips. If more than 2 errors in (a) ft exactly their table |
| (as above, with 'minimise') | A1 | CAO including 'minimise' (or equivalent 14 term expression with 'maximise') |
| Subject to $\sum x_{Aj}=1,\ \sum x_{Bj}=1,\ \sum x_{Cj}=1,\ \sum x_{Dj}=1$ $\sum x_{iP}=1,\ \sum x_{iQ}=1,\ \sum x_{iR}=1,\ \sum x_{iS}=1$ | M1 | At least four equations, each in three or four variables, unit coefficients, equal to 1. Do not accept inequalities |
| (all eight equations as above) | A1 | CAO (all eight equations) |
---\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 task must be assigned to just one worker and each worker can do only one task.\\
Worker B cannot be assigned to task Q and worker D cannot be assigned to task R.\\
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 | }
\hline
& P & Q & R & S \\
\hline
A & 65 & 72 & 69 & 75 \\
\hline
B & 71 & - & 68 & 65 \\
\hline
C & 70 & 69 & 73 & 77 \\
\hline
D & 73 & 70 & - & 71 \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm can be used to find the maximum total amount that would be earned by the four workers.\\
(a) (i) Explain how to modify the table so that the Hungarian algorithm could be applied.\\
(ii) Modify the table as described in (a)(i).\\
(b) Formulate the above situation as a linear programming problem. You must define the decision variables and make the objective function and constraints clear.\\
\hfill \mbox{\textit{Edexcel FD2 2024 Q4 [9]}}