Edexcel FD2 (Further Decision 2) 2024 June

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

1. 1. State the value of \(x\)
   2. State the value of \(y\)
2. State the value of the initial flow.
3. State the capacity of cut \(C _ { 1 }\)
4. Find, by inspection, a flow-augmenting route to increase the flow by four units. You must state your route. The flow-augmenting route from (d) is used to increase the flow from S to T .
5. Prove that the flow is now maximal. A vertex restriction is now applied so that no more than 12 litres per second can flow through E.
6. 1. Complete Diagram 1 in the answer book to show this restriction.
   2. State the value of the maximum flow through the network with this restriction.

2. The general solution of the first order recurrence relation $$u _ { n + 1 } + a u _ { n } = b n ^ { 2 } + c n + d \quad n \geqslant 0$$ is given by $$u _ { n } = A ( 3 ) ^ { n } + 5 n ^ { 2 } + 1$$ where \(A\) is an arbitrary non-zero constant.
By considering expressions for \(u _ { n + 1 }\) and \(u _ { n }\), find the values of the constants \(a , b , c\) and \(d\).

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , to three sales points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the amount required at each sales point.
A minimum cost solution is required.

1. Explain why it is necessary to add a dummy demand point.
2. On Table 1 in the answer book, insert appropriate values in the dummy demand column, D. After finding an initial feasible solution and applying one iteration of the stepping-stone method, the table becomes

   	\(A\)	\(B\)	\(C\)	\(D\)
   \(E\)	21
   \(F\)	19	13
   \(G\)		6	23
   \(H\)	5			18

3. Starting with GD as the next entering cell, perform two further iterations of the stepping-stone method to obtain an improved solution. You must make your method clear by showing your routes and stating the
   • shadow costs
   • improvement indices
   • entering and exiting cells
   • State the cost of the solution found in (c).
   • Determine whether the solution obtained in (c) is optimal, giving a reason for your answer.

1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.

Each task must be assigned to just one worker and each worker can do only one task.
Worker B cannot be assigned to task Q and worker D cannot be assigned to task R.
The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below. The Hungarian algorithm can be used to find the maximum total amount that would be earned by the four workers.

1. 1. Explain how to modify the table so that the Hungarian algorithm could be applied.
   2. Modify the table as described in (a)(i).
2. Formulate the above situation as a linear programming problem. You must define the decision variables and make the objective function and constraints clear.

5. Sebastien needs to make a journey. He can choose between travelling by plane, by train or by coach. Sebastien knows the exact costs of all three travel options, but he also wants to account for his travel time, including any possible delays. The cost of Sebastien's time is \(\pounds 50\) per hour.
The table below shows the costs, the journey times (without delays), and the corresponding probabilities of delays, for each travel option.

1. By drawing a decision tree, evaluate the EMV of the total cost of Sebastien's journey for each node of your tree.
2. Hence state the travel option that minimises the EMV of the total cost of Sebastien's journey.
3. A cube root utility function is applied to the total costs of each option. Determine the travel option with the best expected utility and state the corresponding value.

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns. Elena plans to drive from S to T . She must arrive at T by 9 pm .

1. By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm .
2. Hence write down the route that Elena should take.

7. 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 { R } , \mathrm { S }\) and T , choosing option R with probability \(p _ { 1 }\), option S with probability \(p _ { 2 }\) and option T 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 objective function for the corresponding linear programme. $$\text { Maximise } P = V \quad \text { where } V = \text { the value of the game } + 3$$
2. Determine an initial Simplex tableau, making your variables and working clear. After several iterations of the Simplex algorithm, a possible final tableau is

   b.v.	\(V\)	\(p _ { 1 }\)	\(p _ { 2 }\)	\(p _ { 3 }\)	r	\(s\)	\(t\)	\(u\)	Value
   \(p _ { 3 }\)	0	0	0	1	\(\frac { 1 } { 10 }\)	\(- \frac { 3 } { 80 }\)	\(- \frac { 1 } { 16 }\)	\(\frac { 33 } { 80 }\)	\(\frac { 33 } { 80 }\)
   \(p _ { 2 }\)	0	0	1	0	\(- \frac { 1 } { 10 }\)	\(\frac { 13 } { 80 }\)	\(- \frac { 1 } { 16 }\)	\(\frac { 17 } { 80 }\)	\(\frac { 17 } { 80 }\)
   V	1	0	0	0	\(\frac { 1 } { 2 }\)	\(\frac { 5 } { 16 }\)	\(\frac { 3 } { 16 }\)	\(\frac { 73 } { 16 }\)	\(\frac { 73 } { 16 }\)
   \(p _ { 1 }\)	0	1	0	0	0	\(- \frac { 1 } { 8 }\)	\(\frac { 1 } { 8 }\)	\(\frac { 3 } { 8 }\)	\(\frac { 3 } { 8 }\)
   \(P\)	0	0	0	0	\(\frac { 1 } { 2 }\)	\(\frac { 5 } { 16 }\)	\(\frac { 3 } { 16 }\)	\(\frac { 73 } { 16 }\)	\(\frac { 73 } { 16 }\)

3. 1. State the best strategy for player A.
   2. Calculate the value of the game for player B. Player B intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z .
4. Determine the best strategy for player B, making your method and working clear.
   (3)

8. A sequence \(\left\{ u _ { n } \right\}\), where \(n \geqslant 0\), satisfies the recurrence relation $$2 u _ { n + 2 } + 5 u _ { n + 1 } = 3 u _ { n } + 8 n + 2$$

1. Find the general solution of this recurrence relation.
   (5) A particular solution of this recurrence relation has \(u _ { 0 } = 1\) and \(u _ { 1 } = k\), where \(k\) is a positive constant. All terms of the sequence are positive.
2. Determine the value of \(k\).
   (3)