2 The times taken, in minutes, for five people, \(A , B , C , D\) and \(E\), to complete each of five different puzzles are recorded in the table below.
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) |
| Puzzle 1 | 16 | 13 | 15 | 16 | 15 |
| Puzzle 2 | 14 | 16 | 16 | 14 | 18 |
| Puzzle 3 | 14 | 12 | 18 | 13 | 16 |
| Puzzle 4 | 15 | 15 | 17 | 12 | 14 |
| Puzzle 5 | 13 | 17 | 16 | 14 | 15 |
Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.
- By reducing the columns first and then the rows, show that the new table of values is
| 3 | 1 | 0 | 4 | 1 |
| 0 | \(k\) | 0 | 1 | 3 |
| 1 | 0 | 3 | 1 | 2 |
| 2 | 3 | 2 | 0 | 0 |
| 0 | 5 | 1 | 2 | 1 |
- Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
- Use augmentation to produce a table where five lines are required to cover the zeros.
- Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
- Find the minimum total time for completing the five puzzles.
- Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.