AQA D2 (Decision Mathematics 2) 2007 June

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
The following diagram shows an activity diagram for a building project. The time needed for each activity is given in days.
\includegraphics[max width=\textwidth, alt={}, center]{0c40b693-72d3-459c-bbb7-b9584a108b8e-02_698_1321_767_354}

1. Complete the precedence table for the project on Figure 1.
2. Find the earliest start times and latest finish times for each activity and insert their values on Figure 2.
3. Find the critical path and state the minimum time for completion of the project.
4. Find the activity with the greatest float time and state the value of its float time.

2 The daily costs, in pounds, for five managers A, B, C, D and E to travel to five different centres are recorded in the table below. Using the Hungarian algorithm, each of the five managers is to be allocated to a different centre so that the overall total travel cost is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   3	6	3	6	0
   4	0	6	0	2
   6	4	3	6	0
   2	3	8	3	0
   0	2	0	0	2

2. Show that the zeros in the table in part (a) can be covered with three lines and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five managers to the five centres with the least possible total travel cost.
4. Find the value of this minimum daily total travel cost.

3 Two people, Rose and Callum, play a zero-sum game. The game is represented by the following pay-off matrix for Rose.

1. 1. State the play-safe strategy for Rose and give a reason for your answer.
   2. Show that there is no stable solution for this game.
2. Explain why Rose should never play strategy \(\mathbf { R } _ { \mathbf { 3 } }\).
3. Rose adopts a mixed strategy, choosing \(\mathbf { R } _ { \mathbf { 1 } }\) with probability \(p\) and \(\mathbf { R } _ { \mathbf { 2 } }\) with probability \(1 - p\).
   1. Find expressions for the expected gain for Rose when Callum chooses each of his three possible strategies. Simplify your expressions.
   2. Illustrate graphically these expected gains for \(0 \leqslant p \leqslant 1\).
   3. Hence determine the optimal mixed strategy for Rose.
   4. Find the value of the game.

4 A linear programming problem involving variables \(x\) and \(y\) is to be solved. The objective function to be maximised is \(P = 3 x + 5 y\). The initial Simplex tableau is given below.

1. In addition to \(x \geqslant 0 , y \geqslant 0\), write down three inequalities involving \(x\) and \(y\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Explain how you know that the optimal value has not been reached.
3. 1. Perform one further iteration.
   2. Interpret the final tableau and state the values of the slack variables.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A maker of exclusive furniture is planning to build three cabinets \(A , B\) and \(C\) at the rate of one per month. The order in which they are built is a matter of choice, but the costs will vary because of the materials available and suppliers' costs. The expected costs, in pounds, are given in the table.

1. Use dynamic programming, working backwards from month 3, to determine the order of manufacture that minimises the total cost. You may wish to use Figure 3 for your working.
2. It is discovered that the figures given were actually the profits, not the costs, for each item. Modify your solution to find the order of manufacture that maximises the total profit. You may wish to use the final column of Figure 3 for your working.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{0c40b693-72d3-459c-bbb7-b9584a108b8e-07_713_1456_539_294}

1. 1. Find the value of the cut \(C\).
   2. State what can be deduced about the maximum flow from \(S\) to \(T\).
2. Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 20 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(M P , P N , Q R\) and \(N R\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
   2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 6.