Edexcel FD2 (Further Decision 2) 2023 June

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

1. State the value of the feasible flow.
   (1)
2. Find the capacity of cut \(\mathrm { C } _ { 1 }\) and the capacity of cut \(\mathrm { C } _ { 2 }\)
   (2)
3. By inspection, find a flow-augmenting route to increase the flow by two units. You must state your route.
   (1)
4. Prove that, once the flow-augmenting route found in (c) has been applied, the flow is now maximal.
   (3)

2. An outdoor theatre is holding a summer gala performance. The theatre owner must decide whether to take out insurance against rain for this performance. The theatre owner estimates that

• on a fine day, the total profit will be \(\pounds 15000\)
• on a wet day, the total loss will be \(\pounds 20000\)

Insurance against rain costs \(\pounds 2000\). If the performance must be cancelled due to rain, then the theatre owner will receive \(\pounds 16000\) from the insurer. If the performance is not cancelled due to rain, then the theatre owner will receive nothing from the insurer. The probability of rain on the day of the gala performance is 0.2
Draw a decision tree and hence determine whether the theatre owner should take out the insurance against rain for this performance.

3. The table below shows the stock held at each supply point and the stock required at each demand point in a standard transportation problem. The table also shows the cost, in pounds, of transporting the stock from each supply point to each demand point. The problem is partially described by the linear programming formulation below.
Let \(x _ { i j }\) be the number of units transported from i to j $$\begin{aligned} & \text { where } \quad i \in \{ A , B , C , D \}
& \quad j \in \{ Q , R , S \} \text { and } x _ { i j } \geqslant 0
& \text { Minimise } P = 23 x _ { A Q } + 18 x _ { A R } + 12 x _ { A S } + 8 x _ { B Q } + 10 x _ { B R } + 14 x _ { B S }
& \quad + 11 x _ { C Q } + 14 x _ { C R } + 21 x _ { C S } + 19 x _ { D Q } + 15 x _ { D R } + 11 x _ { D S } \end{aligned}$$

1. Write down, as inequalities, the constraints of the linear program.
2. Use the north-west corner method to obtain an initial solution to this transportation problem.
3. Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
4. 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 the
   • shadow costs
   • improvement indices
   • entering cell and exiting cell

1. Four students, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , are to be allocated to four rounds, \(1,2,3\) and 4 , in a competition. Each student is to take part in exactly one round and no two students may play in the same round.

Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below.

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

5. A sequence \(\left\{ u _ { n } \right\}\), where \(\mathrm { n } \geqslant 0\), satisfies the second order recurrence relation $$u _ { n + 2 } = \frac { 1 } { 2 } \left( u _ { n + 1 } + u _ { n } \right) + 3 \text { where } u _ { 0 } = 15 \quad u _ { 1 } = 20$$

1. By considering the sequence \(\left\{ v _ { n } \right\}\), where \(u _ { n } = v _ { n } + 2 n\) for \(\mathrm { n } \geqslant 0\), determine an expression for \(u _ { n }\) as a function of n .
2. Describe the long-term behaviour of \(u _ { n }\)

6. Polly is a motivational speaker who is planning her engagements for the next four weeks. Polly will

• visit four different countries in these four weeks
• visit just one country each week
• leave from her home, S , and return there only after visiting the four countries
• travel directly from one country to the next

Polly wishes to determine a schedule of four countries to visit.
Table 1 shows the countries Polly could visit each week. \begin{table}[h] \end{table} Table 2 shows the speaker fee, in \(\pounds 100\) s, Polly would expect to earn in each country. \begin{table}[h] \end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the countries. \begin{table}[h] \end{table} Polly's expected income is the value of the speaker fee minus the cost of travel.
She wants to find a schedule that maximises her total expected income for the four weeks. Use dynamic programming to determine the optimal schedule. Complete the table provided in the answer book and state the maximum expected income.
(13)

7. Martina decides to open a bank account to help her to save for a holiday. Each month she puts \(\pounds \mathrm { k }\) into the account and allows herself to spend one quarter of what was in the account at the end of the previous month. Let \(u _ { n }\) (where \(\mathrm { n } \geqslant 1\) ) represent the amount in the account at the end of month n .
Martina has \(\pounds \mathrm {~K}\) in the account at the end of the first month.

1. By setting up a first order recurrence relation for \(u _ { n + 1 }\) in terms of \(u _ { n }\), determine an expression for \(u _ { n }\) in terms of n and k At the end of the 8th month, Martina needs to have at least \(\pounds 1750\) in the account to pay for her holiday.
2. Determine, to the nearest penny, the minimum amount of money that Martina should put into the account each month.

8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below. \section*{Player B} Player A

1. Verify that there is no stable solution to this game.
2. Explain why player A should never play option T. You must make your reasoning clear. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and S , choosing option \(Q\) with probability \(p _ { 1 }\), option \(R\) with probability \(p _ { 2 }\) and option \(S\) with probability \(p _ { 3 }\) Player A wants to calculate the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
3. 1. Formulate the game as a linear programming problem for player A. You should write the constraints as equations.
   2. Write down an initial Simplex tableau for this linear programming problem, making your variables clear. The linear programming problem is solved using the Simplex algorithm. The optimal value of \(p _ { 1 }\) is \(\frac { 6 } { 11 }\) and the optimal value of \(p _ { 2 }\) is 0
4. Find the best strategy for player B, defining any variables you use.