Edexcel FD2 (Further Decision 2) 2020 June

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4 . Each worker must be assigned to exactly one task and each task must be done by exactly one worker.

Worker A cannot do task 3 and worker B cannot do task 4 The table below shows the profit, in pounds, that each worker would earn if assigned to each of the tasks.

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.

2. Jenny can choose one of three options, A, B or C, when playing a game. The profit, in pounds, associated with each outcome and their corresponding probabilities are shown on the decision tree in Figure 1. \begin{figure}[h] \end{figure}

1. Calculate the optimal EMV to determine Jenny's best course of action. You must make your working clear. For a profit of \(\pounds x\), Jenny's utility is given by \(1 - \mathrm { e } ^ { - \frac { x } { 400 } }\)
2. Using expected utility as the criterion for the best course of action, determine what Jenny should do now to maximise her profit. You must make your working clear.

3. 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 three sales points, \(\mathrm { P } , \mathrm { Q }\) and R . 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. \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 AR 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
   • shadow costs
   • improvement indices
   • route
   • entering cell and exiting cell.
   • Determine whether the solution obtained from this second iteration is optimal, giving the reason for your answer.
   • Formulate this situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
   • Explain why the Simplex algorithm cannot be used to solve transportation linear programming problems such as that formulated in (d).

1. The complementary function for the second order recurrence relation

$$u _ { n + 2 } + \alpha u _ { n + 1 } + \beta u _ { n } = 20 ( - 3 ) ^ { n } \quad n \geqslant 0$$ is given by $$u _ { n } = A ( 2 ) ^ { n } + B ( - 1 ) ^ { n }$$ where \(A\) and \(B\) are arbitrary non-zero constants.

1. Find the value of \(\alpha\) and the value of \(\beta\). Given that \(2 u _ { 0 } = u _ { 1 }\) and \(u _ { 4 } = 164\)
2. find the solution of this second order recurrence relation to obtain an expression for \(u _ { n }\) in terms of \(n\).
   (6)

5. \begin{figure}[h] \end{figure} Figure 2 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 capacities and upper capacities for the corresponding pipes, in litres per second.

1. State the source node.
2. Explain why the sink node must be G.
3. Calculate the capacity of the cut \(C _ { 1 }\)
4. Assuming that a feasible flow exists,
   1. explain why arc JH must be at its upper capacity,
   2. explain why arcs AD and CD must be at their lower capacities.
5. Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system.
6. Prove that the answer to (e) is the maximum flow through the system.

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

1. Explain, with justification, why this matrix may be reduced to a \(3 \times 3\) matrix by removing option S from player A's choices.
2. Verify that there is no stable solution to the reduced game. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and T , choosing option Q with probability \(p _ { 1 }\), option R 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 linear programme, writing the constraints as inequalities. Maximise \(P = V\), where \(V =\) the value of original game + 3 $$\begin{aligned} \text { subject to } & V \leqslant 4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 }
   & V \leqslant 8 p _ { 1 } + p _ { 3 }
   & V \leqslant 6 p _ { 1 } + 4 p _ { 2 } + 3 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}$$
3. Explain why \(V\) cannot exceed any of the following expressions $$4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \quad 8 p _ { 1 } + p _ { 3 } \quad 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 }$$
4. Explain why it is necessary to use the constraint \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\) The Simplex algorithm is used to solve the linear programming problem.
   Given that the optimal value of \(p _ { 1 } = \frac { 7 } { 11 }\) and the optimal value of \(p _ { 3 } = 0\)
5. calculate the value of the game to player A .
   (3) Player B 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 }\)
6. Determine the optimal strategy for player B, making your working clear.

7. A manufacturer can export five batches of footwear each year. Each exported batch contains just one type of footwear. The types of footwear are trainers, sandals or high heels. The table below shows the profit, in \(\pounds 1000\) s, for the number of batches of each type of footwear. 2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} 3. \begin{table}[h] \end{table} 4. .
5. \begin{figure}[h] \end{figure} 6. Player A \begin{table}[h] \end{table} 7.