AQA D2 (Decision Mathematics 2) 2009 June

1 [Figure 1, printed on the insert, is provided for use in this question.]
A decorating project is to be undertaken. The table shows the activities involved.

1. Complete an activity network for the project on Figure 1.
2. On Figure 1, indicate:
   1. the earliest start time for each activity;
   2. the latest finish time for each activity.
3. State the minimum completion time for the decorating project and identify the critical path.
4. Activity \(F\) takes 4 days longer than first expected.
   1. Determine the new earliest start time for activities \(H\) and \(I\).
   2. State the minimum delay in completing the project.

2 Two people, Rowena and Colin, play a zero-sum game.
The game is represented by the following pay-off matrix for Rowena.

1. Explain what is meant by the term 'zero-sum game'.
2. Determine the play-safe strategy for Colin, giving a reason for your answer.
3. Explain why Rowena should never play strategy \(R _ { 3 }\).
4. Find the optimal mixed strategy for Rowena.

3 Five lecturers were given the following scores when matched against criteria for teaching five courses in a college. Each lecturer is to be allocated to exactly one of the courses so as to maximise the total score of the five lecturers.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(17 - x\).
2. Form a new table by subtracting each number in the table above from 17. Hence show that, by reducing rows first and then columns, the resulting table of values is as below.

   0	0	3	3	0
   4	3	4	0	2
   0	6	7	2	2
   5	2	3	0	6
   3	1	0	2	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of courses to the five lecturers so that the total score is maximised.
5. State the value of the maximum total score.

4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 4 x + y + k z\), where \(k\) is a constant. The initial Simplex tableau is given below.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), write down two inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. The first pivot is chosen from the \(\boldsymbol { x }\)-column. Identify the pivot and perform one iteration of the Simplex method.
   2. Given that the optimal value of \(P\) has not been reached after this first iteration, find the possible values of \(k\).
3. Given that \(k = 10\) :
   1. perform one further iteration of the Simplex method;
   2. interpret the final tableau.

5 [Figure 2, printed on the insert, is provided for use in this question.]
A company has a number of stores. The following network shows the possible actions and profits over the next five years. The number on each edge is the expected profit, in millions of pounds. A negative number indicates a loss due to investment in new stores.
\includegraphics[max width=\textwidth, alt={}, center]{1bf0d8b7-9f91-437a-bc18-3bfe5ca12223-06_1006_1583_591_223}

1. Working backwards from \(\boldsymbol { T }\), use dynamic programming to maximise the expected profits over the five years. You may wish to complete the table on Figure 2 as your solution.
2. State the maximum expected profit and the sequence of vertices from \(S\) to \(T\) in order to achieve this.
   (2 marks)

6 [Figures 3, 4 and 5, 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]{1bf0d8b7-9f91-437a-bc18-3bfe5ca12223-07_849_1363_518_326}

1. Find the value of the cut \(C\).
2. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 40 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(A E , E F\) and \(F G\).
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 4.
   2. Use flow augmentation on Figure 4 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.
4. Illustrate the maximum flow on Figure 5.
5. Find a cut with value equal to that of the maximum flow.