AQA D2 (Decision Mathematics 2) 2008 January

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
A group of workers is involved in a building project. The table shows the activities involved. Each worker can perform any of the given activities.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time and the latest finish time for each activity, inserting their values on Figure 1.
3. Find the critical path and state the minimum time for completion.
4. The number of workers required for each activity is given in the table above. Given that each activity starts as early as possible and assuming there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2, indicating clearly which activities take place at any given time.
5. It is later discovered that there are only 7 workers available at any time. Use resource levelling to explain why the project will overrun and indicate which activities need to be delayed so that the project can be completed with the minimum extra time. State the minimum extra time required.

2 The following table shows the times taken, in minutes, by five people, Ash, Bob, Col, Dan and Emma, to carry out the tasks 1, 2, 3 and 4 . Dan cannot do task 3. Each of the four tasks is to be given to a different one of the five people so that the overall time for the four tasks is minimised.

1. Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four people should be allocated to which task. State the minimum total time for the four tasks using this matching.
3. After special training, Dan is able to complete task 3 in 12 minutes. Determine, giving a reason, whether the minimum total time found in part (b) could be improved.
   (2 marks)

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

1. Explain what is meant by the term 'zero-sum game'.
2. Show that this game has no stable solution.
3. Explain why Rob should never play strategy \(R _ { 3 }\).
4. 1. Find the optimal mixed strategy for Rob.
   2. Find the value of the game.

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

1. In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. By choosing the first pivot from the \(z\)-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.]
The following network shows 11 vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown.
\includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-05_824_1504_559_278}

1. Working backwards from \(\boldsymbol { T }\), use dynamic programming to find the minimum cost of travelling from \(S\) to \(T\). You may wish to complete the table on Figure 3 as your solution.
2. State the minimum cost and the routes corresponding to this minimum cost.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
Water has to be transferred from two mountain lakes \(P\) and \(Q\) to three urban reservoirs \(U\), \(V\) and \(W\). There are pumping stations at \(X , Y\) and \(Z\). The possible routes with the capacities along each edge, in millions of litres per hour, are shown in the following diagram.
\includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-06_862_1316_662_338}

1. On Figure 4, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each of the edges you have added.
2. 1. Find the value of the cut \(C\).
   2. State what can be deduced about the maximum flow from \(S\) to \(T\).
3. On Figure 5, write down the maximum flows along the routes \(S Q Z W T\) and \(S P Y X Z V T\).
4. 1. On Figure 6, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SQZWT and SPYXZVT found in part (c) as the initial flow, indicate the potential increases and decreases of flow on each edge.
   2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths on Figure 5 and modify the potential increases and decreases of the flow on Figure 6.
5. State the value of the flow from \(Y\) to \(X\) in millions of litres per hour when the maximum flow is achieved.