D2 June 2014 Q1
1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.
Worker A cannot do task 4 and worker B cannot do task 2.
The amount, in pounds, that each worker would earn if assigned to the tasks, is shown in the table below.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 19 | 16 | 23 | – |
| B | 24 | – | 30 | 23 |
| C | 18 | 17 | 25 | 18 |
| D | 24 | 24 | 26 | 24 |
Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage. (10)
| Scheme | Marks | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Since maximising, subtract all elements from some \(n \geqslant 30\) and insert large numbers in cells A4 and B2 e.g. \(\begin{bmatrix}21&24&17&100\\16&100&10&17\\22&23&15&22\\16&16&14&16\end{bmatrix}\) | M1 M1 | ||||||||||||
Reduce rows \(\begin{bmatrix}4&7&0&83\\6&90&0&7\\7&8&0&7\\2&2&0&2\end{bmatrix}\) then columns \(\begin{bmatrix}2&5&0&81\\4&88&0&5\\5&6&0&5\\0&0&0&0\end{bmatrix}\) | M1 A1 | ||||||||||||
| \(\begin{bmatrix}0&3&0&79\\2&86&0&3\\3&4&0&3\\0&0&2&0\end{bmatrix}\) | M1 A1ft | ||||||||||||
either \(\begin{bmatrix}0*&0&0&76\\2&83&0&0\\3&1&0&0\\3&0*&5&0\end{bmatrix}\) or \(\begin{bmatrix}0*&3&2&79\\0&84&0&1\\1&2&0&1\\0&0*&4&0\end{bmatrix}\) then \(\begin{bmatrix}0*&2&2&78\\0&83&0&0\\1&1&0&0\\1&0*&5&0\end{bmatrix}\) | M1 A1ft A1 | ||||||||||||
Two optimal allocations:
| A1 | ||||||||||||
| 10 marks |
Notes
1M1: Subtracting from some \(n \geqslant 30\), condone up to 2 errors.
2M1: Dealing with the A4 and B2 entries.
3M1: Reducing rows and then columns.
1A1: CAO
4M1: Double covered + e; one uncovered – e; and one single covered unchanged. 2 lines needed to 3 lines needed.
2A1ft: follow through on their previous table - no errors
5M1: One double covered + e; one uncovered – e; and one single covered unchanged. 3 lines needed to 4 lines needed (so getting to optimal table).
3A1ft: Follow through on their previous table - no errors.
4A1: CSO on final table.
5A1: CAO – either one – this mark is dependent on all M marks being awarded.
Special Cases: Minimising (can score a max. of 5)1M0 2M1 3M1 1A1 4M0 2A0 5M1 3A1ft 4A0 5A0
E.g.
Then either
Not dealing with the – (can score a max. of 6)
1M1 2M0 3M1 1A0 4M1 2A1ft 5M1 3A1ft 4A0 5A0