AQA D2 (Decision Mathematics 2) 2006 June

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A construction 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.
5. State the float time for each non-critical activity.
6. On Figure 2, draw a cascade diagram (Gantt chart) for the project, assuming each activity starts as late as possible.

2 Four of the five students Phil, Quin, Ros, Sue and Tim are to be chosen to make up a team for a mathematical relay race. The team will be asked four questions, one each on the topics A, B, C and D. A different member of the team will answer each question. Each member has to give the correct answer to the question before the next question is asked. The team with the least overall time wins.
The average times, in seconds, for each student in some practice questions are given below.

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 students should be chosen for the team. State which student should be allocated to each topic and state the total time for the four students on the practice questions using this matching.

3 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows eight 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]{587bccdf-abd7-4a08-a76e-61374f322e2e-03_595_1234_1866_386}

1. Use dynamic programming to find the minimum cost of travelling from \(A\) to \(H\). You may use Figure 3 for your working.
2. State the minimum cost and the possible routes corresponding to this minimum cost.

4 [Figures 4 and 5, printed on the insert, are provided for use in this question.]
The network shows the routes along corridors from the playgrounds \(A\) and \(G\) to the assembly hall in a school. The number on each edge represents the maximum number of pupils that can travel along the corridor in one minute.
\includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-04_1043_1573_559_228}

1. State the vertex that represents the assembly hall.
2. Find the value of the cut shown on the diagram.
3. State the maximum flow along the routes \(A B D\) and \(G E D\).
4. 1. Taking your answers to part (c) as the initial flow, use a labelling procedure on Figure 4 to find the maximum flow through the network.
   2. State the value of the maximum flow and, on Figure 5, illustrate a possible flow along each edge corresponding to this maximum flow.
   3. Verify that your flow is a maximum flow by finding a cut of the same value.
5. On a particular day, there is an obstruction allowing no more than 15 pupils per minute to pass through vertex \(E\). State the maximum number of pupils that can move through the network per minute on this particular day.

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

1. Write down the three inequalities in \(x\) and \(y\) represented by this tableau.
2. The Simplex method is to be used to solve this linear programming problem by initially choosing a value in the \(x\)-column as the pivot.
   1. Explain why the initial pivot has value 1.
   2. Perform two iterations using the Simplex method.
   3. Comment on how you know that the optimum solution has been achieved and state your final values of \(P , x\) and \(y\).

6 Two people, Rowan and Colleen, play a zero-sum game. The game is represented by the following pay-off matrix for Rowan. Colleen

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

      Surname

      Other Names

      Centre Number

      Candidate Number

      Candidate Signature

      \section*{MATHEMATICS
      Unit Decision 2} \section*{Insert} Thursday 8 June 2006 9.00 am to 10.30 am Insert for use in Questions 1, 3 and 4.
      Fill in the boxes at the top of this page.
      Fasten this insert securely to your answer book.