Edexcel D2 (Decision Mathematics 2) 2013 June

1. The table shows the least distances, in km, between five hiding places, A, B, C, D and E.
Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.

1. Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
2. Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
3. Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
4. State the better upper bound from your answers to (b) and (c).
5. Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
6. Consider your answers to (d) and (e) and hence state an optimal route.

2. The table 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 each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking D1 as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.
   (2)
3. Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

3. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
2. State the capacity of cut \(\mathrm { C } _ { 1 }\). The labelling procedure has been used and the result drawn on Diagram 1 in the answer book.
3. Use Diagram 1 to find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
   (4)
4. Draw a maximum flow pattern on Diagram 2 in your answer book.
   (2)
5. Prove that the flow shown in (d) is maximal.
   (2)

4. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Reduce the game so that player B has only two possible actions.
2. Write down the reduced pay-off matrix for player B.
3. Find the best strategy for player B and the value of the game to him.

5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. Solve this linear programming problem. Make your method clear by stating the row operations you use.
3. State the final value of the objective function and the final values of each variable.

6. Three workers, Harriet, Jason and Katherine, are to be assigned to three tasks, 1, 2 and 3. Each worker must be assigned to just one task and each task must be done by just one worker. The amount each person would earn, in pounds, while assigned to each task is shown in the table below. The total income is to be maximised.

1. Modify the table so it can be used to find the maximum income.
2. Formulate the above situation as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.

7. Nigel has a business renting out his fleet of bicycles to tourists. At the start of each year Nigel must decide on one of two actions:

• Keep his fleet of bicycles, incurring maintenance costs.
• Replace his fleet of bicycles.

The cost of keeping the fleet of bicycles, the cost of replacing the fleet of bicycles and the annual income are dependent on the age of the fleet of bicycles.
Table 1 shows these amounts, in \(\pounds 1000\) s. \begin{table}[h] \end{table} Nigel has a new fleet of bicycles now and wishes to maximise his total profit over the next four years. He is planning to sell his business at the end of the fourth year.
The amount Nigel will receive will depend on the age of his fleet of bicycles.
These amounts, in £1000s, are shown in Table 2. \begin{table}[h] \end{table} Complete the table in the answer book to determine Nigel's best strategy to maximise his total profit over the next four years. You must state the action he should take each year (keep or replace) and his total profit.
(Total 13 marks)