Edexcel FD2 AS (Further Decision 2 AS) 2022 June

1. 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 and worker D 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 minimum total time for the four workers to complete the tasks.

1. Modify the table so that the Hungarian algorithm may be used.
2. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total time. You should explain how any initial row and column reductions are made and also how you determine if the table is optimal at each stage.

2. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent a feasible flow from S to T.

1. State the value of this flow.
2. List the eight saturated arcs.
3. Explain why arc EH can never be full to capacity.
4. Find the capacity of
   1. cut \(C _ { 1 }\)
   2. cut \(C _ { 2 }\)
5. Write down a flow-augmenting route that increases the flow by three units. Given that the flow through the network is increased by three units,
6. prove that this new flow is maximal.

3. Terry and June play a zero-sum game. The pay-off matrix shows the number of points that Terry scores for each combination of strategies.

1. Explain the meaning of 'zero-sum' game.
2. Verify that there is no stable solution to the game.
3. Write down the pay-off matrix for June.
4. 1. Find the best strategy for June, defining any variables you use.
   2. State the value of the game to Terry. Let Terry play option A with probability \(t\).
5. By writing down a linear equation in \(t\), find the best strategy for Terry.

4. A sequence \(\left\{ u _ { n } \right\}\), where \(n \geqslant 0\), satisfies the recurrence relation $$u _ { n + 1 } + 3 u _ { n } = n + k$$ where \(k\) is a non-zero constant.
Given that \(u _ { 0 } = 1\)

1. solve the recurrence relation, giving \(u _ { n }\) in terms of \(k\) and \(n\). Given that \(u _ { n }\) is a linear function of \(n\),
2. use your answer to part (a) to find the value of \(u _ { 100 }\) TOTAL FOR DECISION MATHEMATICS 2 IS 40 MARKS END