- Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:
- strip the wallpaper,
- paint the woodwork and ceiling,
- hang the new wallpaper,
- replace the fittings and tidy up.
The table below shows the time, in hours, that each of the friends is likely to take to complete each job.
| Alice | Bhavin | Carl | Dieter |
| Strip wallpaper | 5 | 3 | 5 | 4 |
| Paint | 7 | 5 | 6 | 4 |
| Hang wallpaper | 8 | 4 | 7 | 6 |
| Replace fittings | 5 | 3 | 2 | 3 |
As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.
- Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
- Hence find the minimum time in which the friends can redecorate the lounge.