Edexcel D2 (Decision Mathematics 2) 2010 June

1. The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
   (2)
2. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
   (1)
3. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
4. State the best upper bound from your answers to (b) and (c).
5. Starting by deleting A , and all of its arcs, find a lower bound for the route length.

2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker. Jess cannot be assigned to task 4.
The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total amount earned by the team. You must make your method clear and show the table after each stage.
2. State who should be assigned to each task and the total amount earned by the team.

3. The table below shows the cost of transporting one block of staging from each of two supply points, X and Y , to each of four concert venues, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . It also shows the number of blocks held at each supply point and the number of blocks required at each concert venue. A minimal cost solution is required.

1. Use the north-west corner method to obtain a possible solution.
   (1)
2. Taking the most negative improvement index to indicate the entering square, use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
3. Is your current solution optimal? Give a reason for your answer.
   (1)

4. \begin{figure}[h] \end{figure} Figure 1 represents the maintenance choices a council can make and their costs, in \(\pounds 1000\) s, over the next four years. The council wishes to minimise the greatest annual cost of maintenance.

1. Use dynamic programming to find a minimax route from S to T .
   (9)
2. State your route and the greatest annual cost incurred by the council.
   (2)
3. Calculate the average annual cost to the council.
   (2)

5. \begin{figure}[h] \end{figure} Figure 2 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.
   (1)
2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
   (2)
3. By entering values along DH, FH, FI and IT, complete the labelling procedure on Diagram 1 in the answer book.
   (2)
4. Using Diagram 1, increase the flow by a further 4 units. You must list each flow-augmenting route you use, together with its flow.
   (3)
5. Prove that the flow is now maximal.
   (2)

6. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Write down the profit equation represented in the initial tableau.
   (1)
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, 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 of each variable.
   (3)

7. A two person zero-sum game is represented by the following pay-off matrix for player A. Formulate the game as a linear programming problem for player A. Write the constraints as inequalities and define your variables.