3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5 . Each worker must be assigned to only one task and each task must be done by only one worker.
The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is \(\pounds x\), where \(x > 38\)
| 1 | 2 | 3 | 4 | 5 |
| A | 25 | 31 | 27 | 29 | 35 |
| B | 29 | 33 | 40 | 35 | 37 |
| C | 28 | 29 | 35 | 36 | 37 |
| D | 34 | 35 | 36 | \(x\) | 41 |
| E | 36 | 35 | 32 | 31 | 33 |
The total cost is to be minimised.
- Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
(8) - Find the minimum total cost.
(1)
Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now \(\pounds 5\) more than the minimum cost found in (b). - Calculate the value of \(x\). You must show your working.
(2)