Edexcel FD2 AS (Further Decision 2 AS) 2019 June

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. The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the three workers.

1. Explain how the table should be modified.
   (2)
2. 1. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings.
   2. Explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.

2. (a) Find the general solution of the recurrence relation $$u _ { n + 1 } = 3 u _ { n } + 2 ^ { n } \quad n \geqslant 1$$ (b) Find the particular solution of this recurrence relation for which \(u _ { 1 } = u _ { 2 }\)

3. \begin{figure}[h] \end{figure} 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.

1. State the value of the initial flow.
2. Explain why arcs DF and DG can never both be full to capacity.
3. Obtain the capacity of the cut that passes through the \(\operatorname { arcs } \mathrm { AC } , \mathrm { AD } , \mathrm { BD } , \mathrm { DE } , \mathrm { EG }\) and EJ .
4. 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)
5. 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.
6. Prove that the answer to part (e) is optimal.

4. The table below gives the pay-off matrix for a zero-sum game between two players, Aljaz and Brendan. The values in the table show the pay-offs for Aljaz. You may not need to use all of these tables
You may not need to use all the rows and columns
\includegraphics[max width=\textwidth, alt={}, center]{bbdfa492-6578-484a-a0b5-fcdb78020b83-06_437_832_1201_139}