Edexcel FD2 (Further Decision 2) 2021 June

1. Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3 . Each task must be assigned to just one worker and each worker can do one task only.

Worker A cannot do task 2 and worker D cannot do task 3
The cost of assigning each worker to each task is shown in the table below.
The total cost is to be minimised. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
(6) \section*{(Total for Question 1 is 6 marks)}

1. Alka is considering paying \(\pounds 5\) to play a game. The game involves rolling two fair six-sided dice. If the sum of the numbers on the two dice is at least 8 , she receives \(\pounds 10\), otherwise she loses and receives nothing.

If Alka loses, she can pay a further \(\pounds 5\) to roll the dice again. If both dice show the same number then she receives \(\pounds 35\), otherwise she loses and receives nothing.

1. Draw a decision tree to model Alka’s possible decisions and the possible outcomes.
2. Determine Alka’s optimal EMV and state the optimal strategy indicated by the decision tree.

3. The table below 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 four sales points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
2. Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
3. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and stating the
   • shadow costs
   • improvement indices
   • entering cell and exiting cell
   • 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. Sequences \(\left\{ x _ { n } \right\}\) and \(\left\{ y _ { n } \right\}\) for \(n \in \mathbb { N }\), are defined by

$$\begin{gathered} x _ { n + 1 } = 2 y _ { n } + 3 \quad \text { and } \quad y _ { n + 1 } = 3 x _ { n + 1 } - 4 x _ { n }
x _ { 1 } = 1 \quad \text { and } \quad y _ { 1 } = a \end{gathered}$$ where \(a\) is a constant.

1. Show that \(x _ { n + 2 } - 6 x _ { n + 1 } + 8 x _ { n } = 3\)
2. Solve the second-order recurrence relation given in (a) to obtain an expression for \(x _ { n }\) in terms of \(a\) and \(n\). Given that \(x _ { 7 } = 28225\)
3. find the value of \(a\).

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the corresponding pipes, in litres per second.

1. Calculate the capacity of
   1. cut \(C _ { 1 }\)
   2. cut \(C _ { 2 }\)
2. Using only the capacities of cuts \(C _ { 1 }\) and \(C _ { 2 }\), state what can be deduced about the maximum flow through the system. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{262aa0e6-479f-447a-94db-aeb901b3c6fe-6_775_1516_169_278} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 2 shows an initial flow through the same network.
3. State the value of the initial flow.
4. By entering values along \(B C , C F\) and \(D T\), complete the labelling procedure on Diagram 1 in the answer book.
5. 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.
6. Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 in the answer book.
7. Prove that the answer to (f) is optimal. A vertex restriction is now applied to \(B\) so that no more than 16 litres per second can flow through it.
8. 1. Complete Diagram 3 in the answer book to show this restriction.
   2. State the value of the maximum flow with this restriction.

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, \(S , A , B , C , D , E , F , G , H , I , J\) and \(T\). The number on each arc shows the distance between these towns, in miles. Bradley is planning a four-day cycle ride from \(S\) to \(T\).
He plans to leave his home at \(S\). On the first night he will stay at \(A , B\) or \(C\), on the second night he will stay at \(D , E , F\) or \(G\), on the third night he will stay at \(H , I\) or \(J\), and he will arrive at his friend's house at \(T\) on the fourth day. Bradley decides that the maximum distance he will cycle on any one day should be as small as possible.

1. Write down the type of dynamic programming problem that Bradley needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence write down the possible routes that Bradley could take.

7. Alexis and Becky are playing a zero-sum game. Alexis has two options, Q and R . Becky has three options, \(\mathrm { X } , \mathrm { Y }\) and Z .
Alexis intends to make a random choice between options Q and R , choosing option Q with probability \(p _ { 1 }\) and option R with probability \(p _ { 2 }\) Alexis wants to find the optimal values of \(p _ { 1 }\) and \(p _ { 2 }\) and formulates the following linear programme, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V
& \text { where } V = 3 + \text { the value of the gan }
& \text { subject to } V \leqslant 6 p _ { 1 } + p _ { 2 }
& \qquad \begin{aligned} & V \leqslant 8 p _ { 2 }
& V \leqslant 4 p _ { 1 } + 2 p _ { 2 }
& p _ { 1 } + p _ { 2 } \leqslant 1
& p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , V \geqslant 0 \end{aligned} \end{aligned}$$

1. Complete the pay-off matrix for Alexis in the answer book.
2. Use a graphical method to find the best strategy for Alexis.
3. Calculate the value of the game to Alexis. Becky intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z , choosing option X with probability \(q _ { 1 }\), option Y with probability \(q _ { 2 }\) and option Z with probability \(q _ { 3 }\)
4. Determine the best strategy for Becky, making your method and working clear.