A2 June 2024 Q4
4. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.
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.
| P | Q | R | S | |
|---|---|---|---|---|
| A | 65 | 72 | 69 | 75 |
| B | 71 | – | 68 | 65 |
| C | 70 | 69 | 73 | 77 |
| D | 73 | 70 | – | 71 |
The Hungarian algorithm can be used to find the maximum total amount that would be earned by the four workers.
| Scheme | Marks | AO |
|---|---|---|
| (i) Subtracting each entry from a constant value e.g. \(\geqslant 77\) to convert from maximisation problem to minimisation | B1 | 3.5c |
| Add a sufficiently large number (\(> 12\)) to cells BQ and DR | B1 | 1.1b |
| (ii) e.g. \(\begin{bmatrix} 12 & 5 & 8 & 2 \\ 6 & 100 & 9 & 12 \\ 7 & 8 & 4 & 0 \\ 4 & 7 & 100 & 6 \end{bmatrix}\) | B1 | 1.1b |
| (3) |
Notes
B1: correct reasoning for how to convert from maximisation to minimisation
B1: adding a large number (at least 13) to cells BQ and DR
B1: CAO
| Scheme | Marks | AO |
|---|---|---|
| Let \(x_{ij}\) be 0 or 1 \(\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}\) | B1 | 3.3 |
| where \(i \in \{\text{A, B, C, D}\}\) and \(j \in \{\text{P, Q, R, S}\}\) | B1 | 2.5 |
| minimise \(12x_{\text{AP}} + 5x_{\text{AQ}} + 8x_{\text{AR}} + 2x_{\text{AS}} + 6x_{\text{BP}} + \text{‘100’}x_{\text{BQ}} + 9x_{\text{BR}} + 12x_{\text{BS}}\) \(\quad + 7x_{\text{CP}} + 8x_{\text{CQ}} + 4x_{\text{CR}} + 4x_{\text{DP}} + 7x_{\text{DQ}} + \text{‘100’}x_{\text{DR}} + 6x_{\text{DS}}\) | M1 A1 | 3.3 1.1b |
| Subject to \(\sum x_{\text{A}j} = 1,\ \sum x_{\text{B}j} = 1,\ \sum x_{\text{C}j} = 1,\ \sum x_{\text{D}j} = 1\) \(\sum x_{i\text{P}} = 1,\ \sum x_{i\text{Q}} = 1,\ \sum x_{i\text{R}} = 1,\ \sum x_{i\text{S}} = 1\) | M1 A1 | 3.3 1.1b |
| (6) | ||
| (9 marks) |
Notes
B1: defining \(x_{ij}\) correctly
B1: correct definition of the values that \(i\) and \(j\) can take
M1: Attempt at a 15 (or 16) term expression in terms of \(x\) (or their defined variable), coefficients ‘correct’, 2 ‘large’ values included, condone 2 slips. If more than 2 errors in (a) ft exactly their table for this mark only.
A1: CAO including ‘minimise’ (or equivalent 14 term expression with ‘maximise’)
M1: At least four equations, each in three or four variables, unit coefficients, equal to 1 Do not accept inequalities
A1: CAO (all eight equations)
Maximise \(65x_{AP} + 72x_{AQ} + 69x_{AR} + 75x_{AS}\)
\(\qquad + 71x_{BP} + 68x_{BR} + 65x_{BS}\)
\(\qquad + 70x_{CP} + 69x_{CQ} + 73x_{CR} + 77x_{CS}\)
\(\qquad + 73x_{DP} + 70x_{DQ} + 71x_{DS}\)
Note: if maximising they must not include a large number for BQ and DR, so only 14 terms