1 The times taken in minutes for five people, \(\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }\) and T , to complete each of five different tasks are recorded in the table.
| P | Q | R | S | T |
| Task 1 | 17 | 20 | 19 | 17 | 17 |
| Task 2 | 19 | 18 | 18 | 18 | 15 |
| Task 3 | 13 | 16 | 16 | 14 | 12 |
| Task 4 | 13 | 13 | 15 | 13 | 13 |
| Task 5 | 10 | 11 | 12 | 14 | 13 |
Using the Hungarian algorithm, each of the five people is to be allocated to a different task so that the total time for completing the five tasks is minimised.
- By reducing the columns first and then the rows, show that the new table of values is as follows.
| 3 | 5 | 3 | 0 | 1 |
| 6 | 4 | 3 | 2 | 0 |
| 3 | 5 | 4 | 1 | 0 |
| 3 | 2 | 3 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
- Show that the zeros in the table in part (a) can be covered with three lines, and use adjustments to produce a table where five lines are required to cover the zeros.
- Hence find the two possible ways of allocating the five people to the five tasks so that the total completion time is minimised.
- Find the minimum total time for completing the five tasks.