- A company has five machines \(A , B , C , D\) and \(E\), which it can assign to four tasks \(1,2,3\) and 4 . Each task must be assigned to just one machine and each machine may only be assigned to just one task.
The profit, in \(\pounds 100\) s, of using each machine to do each task is given in the table below.
| 1 | 2 | 3 | 4 |
| \(A\) | 14 | 12 | 11 | 17 |
| \(B\) | 14 | 13 | 15 | 16 |
| \(C\) | 17 | 16 | 10 | 12 |
| \(D\) | 16 | 14 | 13 | 12 |
| \(E\) | 13 | 15 | 13 | 15 |
- Explain why it is necessary to add a dummy column to the table.
(2) - Use the Hungarian algorithm to allocate machines to tasks in order to maximise the total profit. You must make your method clear and show the state of the table after each iteration.
(7)
(Total 9 marks)