Edexcel FD2 AS (Further Decision 2 AS) 2023 June

1. Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

Each worker can only be assigned to at most one task, and each task must be done by at most one worker. Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below. The Hungarian algorithm is to be used to find the least total time to complete all four tasks.

1. Explain how the table should be modified so that the Hungarian algorithm can be applied.
2. 1. Use the Hungarian algorithm to obtain an allocation that minimises the total time.
   2. Explain how you determined if the table was optimal at each stage.
3. Calculate the least total time to complete all four tasks.

2. \begin{figure}[h] \end{figure} An engineer monitors a system of pipes through which a fluid flows from the source, S , to the sink, T . The engineer 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. Obtain the capacity of the cut that passes through the arcs \(\mathrm { SA } , \mathrm { SB } , \mathrm { CE } , \mathrm { FE }\) and FJ .
3. 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.
4. Use your answer to (c) to draw a maximum flow pattern on Diagram 1 in the answer book.
5. Prove that the answer to (d) is optimal.

3. A two-person zero-sum game is represented by the following pay-off matrix for player \(A\).

1. 1. Show that this game is stable.
   2. State the value of this game to player \(B\). Option S is removed from player A's choices and the reduced game, with option S removed, is no longer stable.
2. Write down the reduced pay-off matrix for player \(B\). Let \(B\) play option X with probability \(p\) and option Y with probability \(1 - p\).
3. Use a graphical method to find the optimal value of \(p\) and hence find the best strategy for player \(B\) in the reduced game.
4. 1. Find the value of the reduced game to player \(A\).
   2. State which option player \(A\) should never play in the reduced game.
   3. Hence find the best strategy for player \(A\) in the reduced game.

4. A sequence \(\left\{ u _ { n } \right\}\), where \(n \geqslant 0\), satisfies the recurrence relation $$u _ { n + 1 } = \frac { 3 } { 2 } u _ { n } - 2 n ^ { 2 } - 4 \quad u _ { 0 } = k$$ where \(k\) is an integer.

1. Determine an expression for \(u _ { n }\) in terms of \(n\) and \(k\).
   (6) Given that \(u _ { 10 } > 5000\)
2. determine the minimum possible value of \(k\).
   (2)