Edexcel D2 (Decision Mathematics 2) 2015 June

1. 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. Perform one iteration of the Simplex algorithm to obtain a new tableau, \(T\). State the row operations you use.
   (5)
2. Write down the profit equation given by \(T\) and state the current values of the slack variables.

2. Rani and Greg play a zero-sum game. The pay-off matrix shows the number of points that Rani scores for each combination of strategies.

1. Explain what the term 'zero-sum game' means.
2. State the number of points that Greg scores if he plays his strategy 3 and Rani plays her strategy 3.
3. Verify that there is no stable solution to this game.
4. Reduce the game so that Greg has only two possible strategies. Write down the reduced pay-off matrix for Greg.
5. Find the best strategy for Greg and the value of the game to him.

3. The network represented by the table shows the least distances, in km, between seven theatres, A, \(\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G . Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is \(x \mathrm {~km}\), where \(21 < x < 27\)

1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You should list the arcs in the order in which you consider them.
2. Use your answer to (a) to determine an initial upper bound for the length of Jasmine's route.
3. Use the nearest neighbour algorithm, starting at A , to find a second upper bound for the length of the route. The nearest neighbour algorithm starting at F gives a route of \(\mathrm { F } - \mathrm { E } - \mathrm { B } - \mathrm { A } - \mathrm { G } - \mathrm { D } - \mathrm { C } - \mathrm { F }\).
4. State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer. Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.
5. Find \(x\), making your method clear.
6. Write down the smallest interval that you can be confident contains the optimal length of Jasmine's route. Give your answer as an inequality.

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown.

1. Find the capacity of each of the two cuts. Given that one of these two cuts is a minimum cut,
2. write down the maximum possible flow through the network. Given that the network now has a maximal flow from S to T ,
3. determine the flow along arc SB.
4. Explain why arcs GF and GT cannot both be saturated. Given that arcs EC, AD and DF are saturated and that there is no flow along arc GF,
5. 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 to determine the maximum flow.

5. 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 sales points, \(\mathrm { P } , \mathrm { Q }\) and R . It also shows the stock held at each supply point and the amount required at each sales point. A minimum cost solution is required. The north-west corner method gives the following initial solution.

1. Taking AQ as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.
2. 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.
3. Determine whether your current solution is optimal. Justify your answer.
4. State the cost of the solution you found in (b).
5. Formulate this problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, \(\mathrm { S } , \mathrm { A }\), B, C, D, E, F, G, H, J and T. The number on each arc shows the weight limit, in tonnes, for the corresponding road. Janet needs to drive a truck from S to T, passing through exactly three other towns. She needs to find the maximum weight of the truck that she can use.

1. Write down the type of dynamic programming problem that Janet needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence find the maximum weight of the truck Janet can use.
4. Write down the route that Janet should take. Janet intends to ask for the weight limit to be increased on one of the three roads leading directly into T. Janet wishes to maximise the weight of her truck.
5. 1. Determine which of the three roads she should choose and its new minimum weight limit.
   2. Write down the maximum weight of the truck she would be able to use and the new route she would take.