AQA D2 (Decision Mathematics 2) 2006 January

1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below. Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.

1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.

2 A manufacturing company is planning to build three new machines, \(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 profits will vary according to the number of workers available and the suppliers' costs. The expected profits in thousands of pounds are given in the table.

1. Draw a labelled network such that the most profitable order of manufacture corresponds to the longest path within that network.
2. Use dynamic programming to determine the order of manufacture that maximises the total profit, and state this maximum profit.

3 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A building project is to be undertaken. The table shows the activities involved.

1. Complete the activity network for the project on Figure 1.
2. Find the earliest start time for each activity.
3. Find the latest finish time for each activity.
4. Find the critical path and state the minimum time for completion.
5. State the float time for each non-critical activity.
6. Given that each activity starts as early as possible, draw a resource histogram for the project on Figure 2.
7. There are only 3 workers available at any time. Use resource levelling to explain why the project will overrun and state the minimum extra time required.

4 [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]{30a88efe-fe9e-4384-a3e3-da2a05326797-04_547_1214_555_404}

1. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(M N , P Q , N P\) and \(N T\).
2. 1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\).
   2. State the value of the maximum flow and illustrate this flow on Figure 5.
3. Find a cut with capacity equal to that of the maximum flow.

5

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l c } \text { Maximise } & P = 3 x + 2 y + 4 z
   \text { subject to } & x + 4 y + 2 z \leqslant 8
   & 2 x + 7 y + 3 z \leqslant 21
   & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(z\)-column as pivot.
3. 1. Perform one further iteration.
   2. State whether or not this is the optimal solution, and give a reason for your answer.

6 Sam is playing a computer game in which he is trying to drive a car in different road conditions. He chooses a car and the computer decides the road conditions. The points scored by Sam are shown in the table. Sam is trying to maximise his total points and the computer is trying to stop him.

1. Explain why Sam should never choose \(S _ { 1 }\) and why the computer should not choose \(C _ { 3 }\).
2. Find the play-safe strategies for the reduced 2 by 2 game for Sam and the computer, and hence show that this game does not have a stable solution.
3. Sam uses random numbers to choose \(S _ { 2 }\) with probability \(p\) and \(S _ { 3 }\) with probability \(1 - p\).
   1. Find expressions for the expected gain for Sam when the computer chooses each of its two remaining strategies.
   2. Calculate the value of \(p\) for Sam to maximise his total points.
   3. Hence find the expected points gain for Sam.

      Surname

      Other Names

      Centre Number

      Candidate Number

      Candidate Signature

      \section*{General Certificate of Education January 2006
      Advanced Level Examination} \section*{MATHEMATICS
      Unit Decision 2} MD02 \section*{Insert} Wednesday 18 January 20061.30 pm to 3.00 pm Insert for use in Questions 3 and 4.
      Fill in the boxes at the top of this page.
      Fasten this insert securely to your answer book.