3 P62675A Turn over 2. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S. Each worker must be assigned to one task, and each task must be done by exactly one worker. Worker C cannot be assigned to task Q. The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below. P Q R S A 72 98 59 84 B 67 87 68 86 C 70 – 62 79 D 78 93 64 81 The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the four workers. (a) Explain how the table should be modified so that the Hungarian algorithm may be applied. (2) (b) Modify the table so that the Hungarian algorithm may be applied. (1) (c) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You should explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage. (6) (Total for Question 2 is 9 marks)