3 The table shows the times taken, in minutes, by five people, \(A , B , C , D\) and \(E\), to carry out the tasks \(V , W , X , Y\) and \(Z\).
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) |
| Task \(\boldsymbol { V }\) | 100 | 110 | 112 | 102 | 95 |
| Task \(\boldsymbol { W }\) | 125 | 130 | 110 | 120 | 115 |
| Task \(\boldsymbol { X }\) | 105 | 110 | 101 | 108 | 120 |
| Task \(\boldsymbol { Y }\) | 115 | 115 | 120 | 135 | 110 |
| Task \(\boldsymbol { Z }\) | 100 | 98 | 99 | 100 | 102 |
Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.
- By reducing the columns first, and then the rows, show that the new table of values is
| 0 | 12 | 13 | 2 | 0 |
| 14 | 21 | 0 | \(k\) | 9 |
| 3 | 10 | 0 | 6 | 23 |
| 0 | 2 | 6 | 20 | 0 |
| 0 | 0 | 0 | 0 | 7 |
- Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
- Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
- Find the minimum total time.