AQA D2 (Decision Mathematics 2) 2010 January

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
Figure 1 shows the activity network and the duration, in days, of each activity for a particular project.

1. On Figure 1:
   1. find the earliest start time for each activity;
   2. find the latest finish time for each activity.
2. Find the float for activity \(G\).
3. Find the critical paths and state the minimum time for completion.
4. The number of workers required for each activity is shown in the table.

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Number of workers required	2	2	3	2	3	2	1	3	5	2

   Given that each activity starts as late as possible and assuming that 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.

2 The following table shows the times taken, in minutes, by five people, Ron, Sam, Tim, Vic and Zac, to carry out the tasks \(1,2,3\) and 4 . Sam takes \(x\) minutes, where \(8 \leqslant x \leqslant 12\), to do task 2. Each of the four tasks is to be given to a different one of the five people so that the total 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. 1. Use the Hungarian algorithm, reducing columns first and then rows, to reduce the matrix to a form, in terms of \(x\), from which the optimum matching can be made.
   2. Hence find the possible way of allocating the four tasks so that the total time is minimised.
   3. Find the minimum total time.
3. After special training, Sam is able to complete task 2 in 7 minutes and is assigned to task 2. Determine the possible ways of allocating the other three tasks so that the total time is minimised.

3

1. Two people, Ann and Bill, play a zero-sum game. The game is represented by the following pay-off matrix for Ann.

   \multirow{5}{*}{Ann}	Bill
   	Strategy	\(\mathbf { B } _ { \mathbf { 1 } }\)	\(\mathbf { B } _ { \mathbf { 2 } }\)	\(\mathbf { B } _ { \mathbf { 3 } }\)
   	\(\mathbf { A } _ { \mathbf { 1 } }\)	-1	0	-2
   	\(\mathbf { A } _ { \mathbf { 2 } }\)	4	-2	-3
   	\(\mathbf { A } _ { \mathbf { 3 } }\)	-4	-5	-3

   Show that this game has a stable solution and state the play-safe strategies for Ann and Bill.
2. Russ and Carlos play a different zero-sum game, which does not have a stable solution. The game is represented by the following pay-off matrix for Russ.

   	Carlos
   \cline { 2 - 5 }	Strategy	\(\mathbf { C } _ { \mathbf { 1 } }\)	\(\mathbf { C } _ { \mathbf { 2 } }\)	\(\mathbf { C } _ { \mathbf { 3 } }\)
   \cline { 2 - 5 } Russ	\(\mathbf { R } _ { \mathbf { 1 } }\)	- 4	7	- 3
   \cline { 2 - 5 }	\(\mathbf { R } _ { \mathbf { 2 } }\)	2	- 1	1

   1. Find the optimal mixed strategy for Russ.
   2. Find the value of the game.

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

1. 1. What name is given to the variables \(s , t\) and \(u\) ?
   2. Write down an equation involving \(x , y , z\) and \(s\) 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, stating the values of \(P , x , y\) and \(z\).

5 [Figure 3, printed on the insert, is provided for use in this question.]
A landscape gardener has three projects, \(A , B\) and \(C\), to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.

6 [Figures 4, 5, 6 and 7, printed on the insert, are provided for use in this question.]

1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity, in litres per minute, indicated on each edge.
   \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_350_878_532_591}
   1. Show that the value of the cut shown on the diagram is 97 .
   2. The cut shown on the diagram can be represented as \(\{ S , C \} , \{ A , B , T \}\). Complete the table on Figure 4, giving the value of each of the 8 possible cuts.
   3. State the value of the maximum flow through the network, giving a reason for your answer.
   4. Indicate on Figure 5 a possible flow along each edge corresponding to this maximum flow.
2. Extra pipes, \(B D , C D\) and \(D T\), are added to form a new system, with the capacity, in litres per minute, indicated on each edge of the network below.
   \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_483_977_1724_520}
   1. Taking your values from Figure 5 as the initial flow, use the labelling procedure on Figure 6 to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the new maximum flow, and, on Figure 7, indicate a possible flow along each edge corresponding to this maximum flow.