Edexcel FD2 (Further Decision 2) 2019 June

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking DQ as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
2. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating the
   • shadow costs
   • improvement indices
   • route
   • entering cell and exiting cell.
   • Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer.
   • State the cost of the solution found in (b).

1. Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
2. Determine the resulting total profit.

3. \begin{figure}[h] \end{figure} In Figure 1 the weight of \(\operatorname { arc } \mathrm { SB }\) is denoted by \(x\) where \(x \geqslant 0\)

1. Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.
   (1) It is given that the minimum weight route from S to T passes through B .
2. Use dynamic programming to find
   1. the range of possible values of \(x\)
   2. the minimum weight route from S to T .
      (12)

4. A two person zero-sum game is represented by the pay-off matrix for player A shown above.

1. Verify that there is no stable solution to this game. Player A intends to make a random choice between options \(\mathrm { P } , \mathrm { Q }\) and R , choosing option P with probability \(p _ { 1 }\), option Q with probability \(p _ { 2 }\) and option R with probability \(p _ { 3 }\) Player A wants to find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm. Player A formulates the following linear programming problem for the game, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V
   & \text { subject to } V \geqslant 3 p _ { 1 } - 4 p _ { 2 } + p _ { 3 }
   &
   & V \geqslant - 2 p _ { 1 } + 4 p _ { 2 } + 2 p _ { 3 }
   & V \geqslant - 2 p _ { 2 } - p _ { 3 }
   & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1
   & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , V \geqslant 0 \end{aligned}$$
2. Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer.
3. Write down an initial Simplex tableau for the corrected linear programming problem. The Simplex algorithm is used to solve the corrected linear programming problem. The optimal values are \(p _ { 1 } = 0.6 , p _ { 2 } = 0\) and \(p _ { 3 } = 0.4\)
4. Calculate the value of the game to player A.
5. Determine the optimal strategy for player B, making your reasoning clear.

5. An increasing sequence \(\left\{ u _ { n } \right\}\) for \(n \in \mathbb { N }\) is such that the difference between the \(n\)th term of \(\left\{ u _ { n } \right\}\) and the mean of the previous two terms of \(\left\{ u _ { n } \right\}\) is always 6

1. Show that, for \(n \geqslant 3\) $$2 u _ { n } - u _ { n - 1 } - u _ { n - 2 } = 12$$ Given that \(u _ { 1 } = 2\) and \(u _ { 2 } = 8\)
2. find the solution of this second order recurrence relation to obtain an expression for \(u _ { n }\) in terms of \(n\).
3. Show that as \(n \rightarrow \infty , u _ { n } \rightarrow k n\) where \(k\) is a constant to be determined. You must give reasons for your answer.

6. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid flows from a source, S , to a sink, T . The numbers ( \(l , u\) ) on each arc represent, in litres per second, the lower capacity, \(l\), and the upper capacity, \(u\), of the corresponding pipe. Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown.

1. Find the capacity of
   1. \(\operatorname { cut } C _ { 1 }\)
   2. \(\operatorname { cut } C _ { 2 }\)
2. Explain why the arcs AE and CE cannot be at their upper capacities simultaneously.
3. Explain why a flow of 31 litres per second through the system is not possible.
4. Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams in the answer book and give reasons to justify your answer. You should not apply the labelling procedure to find these flows.