P61640A 2 1. Three workers, A, B and C, are each to be assigned to one of four tasks, P, Q, R and S. Each worker must be assigned to at most one task, and each task must be done by at most one worker. The amount, in pounds, that each worker will earn while assigned to each task is shown in the table below. P Q R S A 32 40 37 42 B 29 32 35 41 C 37 33 39 40 The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the three workers. (a) Explain how the table should be modified. (2) (b) (i) Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings. (ii) Explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage. (7) (Total for Question 1 is 9 marks) 2. (a) Find the general solution of the recurrence relation un + 1 = 3un + 2n n . 1 (4) (b) Find the particular solution of this recurrence relation for which u1 = u2 (2) (Total for Question 2 is 6 marks) P61640A 3 Turn over 3. 14 A B C D E F G H J S T 18 4 6 7 24 2 7 2 3 0 11 5 3 0 5 19 14 7 26 0 2 6 5 6 12 0 12 2 6 0 4 5 17 21 4 0 7 Figure 1 Alexa is monitoring a system of pipes through which fluid can flow from the source, S, to the sink, T. Currently, fluid is flowing through the system from S to T. Alexa initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1. (a) State the value of the initial flow. (1) (b) Explain why arcs DF and DG can never both be full to capacity. (1) (c) Obtain the capacity of the cut that passes through the arcs AC, AD, BD, DE, EG and EJ. (1) (d) Use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (3) (e) Use your answers to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book. (1) (f) Prove that the answer to part (e) is optimal. (3) (Total for Question 3 is 10 marks)