Edexcel FD2 (Further Decision 2) Specimen

1. (a) Find the general solution of the recurrence relation

$$u _ { n + 2 } = u _ { n + 1 } + u _ { n } , \quad n \geqslant 1$$ Given that \(u _ { 1 } = 1\) and \(u _ { 2 } = 1\)
(b) find the particular solution of the recurrence relation.

2. A company has three factories, \(\mathrm { A } , \mathrm { B }\) and C . It supplies mattresses to three shops, \(\mathrm { D } , \mathrm { E }\) and F . The table shows the transportation cost, in pounds, of moving one mattress from each factory to each shop. It also shows the number of mattresses available at each factory and the number of mattresses required at each shop. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
2. Show how the transportation algorithm is used to solve this problem. You must state, at each appropriate step, the
   • shadow costs,
   • improvement indices,
   • route,
   • entering cell and exiting cell,
     and explain clearly how you know that your final solution is optimal.

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

Each worker must be assigned to at most one task and each task must be done by just one worker. The amount, in pounds, that each worker would earn while assigned to each task is shown in the table below. The Hungarian algorithm is to be used to find the maximum total amount which may be earned by the four workers.

1. Explain how the table should be modified.
2. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings, stating how each table was formed.
3. Formulate the problem as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.

4. A game uses a standard pack of 52 playing cards. A player gives 5 tokens to play and then picks a card. If they pick a \(2,3,4,5\) or 6 then they gain 15 tokens. If any other card is picked they lose. If they lose, the card is replaced and they can choose to pick again for another 5 tokens. This time if they pick either an ace or a king they gain 40 tokens. If any other card is picked they lose. Daniel is deciding whether to play this game.

1. Draw a decision tree to model Daniel's possible decisions and the possible outcomes.
2. Calculate Daniel's optimal EMV and state the optimal strategy indicated by the decision tree.

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

1. Explain, with justification, how this matrix may be reduced to a \(3 \times 3\) matrix.
2. Find the play-safe strategy for each player and verify that there is no stable solution to this game. The game is formulated as a linear programming problem for player A .
   The objective is to maximise \(P = V\), where \(V\) is the value of the game to player A.
   One of the constraints is that \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\), where \(p _ { 1 } , p _ { 2 } , p _ { 3 }\) are the probabilities that player A plays 1, 2, 3 respectively.
3. Formulate the remaining constraints for this problem. Write these constraints as inequalities. The Simplex algorithm is used to solve the linear programming problem.
   The solution obtained is \(p _ { 1 } = 0 , p _ { 2 } = \frac { 3 } { 7 } , p _ { 3 } = \frac { 4 } { 7 }\)
4. Calculate the value of the game to player A.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc \(( x , y )\) represents the lower \(( x )\) capacity and upper \(( y )\) capacity of that arc.

1. Calculate the value of the cut \(C _ { 1 }\) and cut \(C _ { 2 }\)
2. Explain why the flow through the network must be at least 12 and at most 16
3. Explain why arcs DG, AG, EG and FG must all be at their lower capacities.
4. Determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure.
5. 1. State the value of the maximum flow through the network.
   2. Explain why the value of the maximum flow is equal to the value of the minimum flow through the network. Node E becomes blocked and no flow can pass through it. To maintain the maximum flow through the network the upper capacity of exactly one arc is increased.
6. Explain how it is possible to maintain the maximum flow found in (d).

7. A company assembles boats. They can assemble up to five boats in any one month, but if they assemble more than three they will have to hire additional space at a cost of \(\pounds 800\) per month. The company can store up to two boats at a cost of \(\pounds 350\) each per month.
The overhead costs are \(\pounds 1500\) in any month in which work is done.
Boats are delivered at the end of each month. There are no boats in stock at the beginning of January and there must be none in stock at the end of May. The order book for boats is Use dynamic programming to determine the production schedule which minimises the costs to the company. Show your working in the table provided in the answer book and state the minimum production cost.