3 Each of five jobs is to be allocated to one of five workers, and each worker will have one job. The table shows the cost, in \(\pounds\), of using each worker on each job. It is required to find the allocation for which the total cost is minimised.
Worker
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Job}
| Plastering | Rewiring | Shelving | Tiling | Upholstery |
| Gill | 25 | 50 | 34 | 40 | 25 |
| Harry | 36 | 42 | 48 | 44 | 45 |
| Ivy | 27 | 50 | 45 | 42 | 26 |
| James | 40 | 46 | 28 | 45 | 50 |
| Kelly | 34 | 48 | 34 | 50 | 40 |
\end{table}
- Construct a reduced cost matrix by first reducing rows and then reducing columns. Cross through the 0's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [Try to ensure that the values in your table can still be read.]
- Augment your reduced cost matrix and hence find a minimum cost allocation. Write a list showing which job should be given to which worker for your minimum cost allocation, and calculate the total cost in this case.
Gill decides that she does not like the job she has been allocated and increases her cost for this job by \(\pounds 100\). New minimum cost allocations can be found, each allocation costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii).
- Use the grid in your answer book to show the positions of the 0 's and 1 's in the augmented reduced cost matrix from part (ii). Hence find three allocations, each costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii) and with Gill having a different job to the one allocated in part (ii). [5]