- Three workers, A, B and C, are each to be assigned to one of four tasks, P, Q, R and S.
Each worker must be assigned to at most one task, and each task must be done by at most one worker.
The amount, in pounds, that each worker will earn while assigned to each task is shown in the table below.
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | P | Q | R | S |
| A | 32 | 40 | 37 | 42 |
| B | 29 | 32 | 35 | 41 |
| C | 37 | 33 | 39 | 40 |
The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the three workers.
- Explain how the table should be modified.
(2) - Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings.
- Explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.