AQA D2 (Decision Mathematics 2) 2010 June

1 Figure 1 below shows an activity diagram for a construction project. The time needed for each activity is given in days.

1. Find the earliest start time and latest finish time for each activity and insert their values on Figure 1.
2. Find the critical paths and state the minimum time for completion of the project.
3. On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as early as possible.
4. A delay in supplies means that Activity \(I\) takes 9 days instead of 2 .
   1. Determine the effect on the earliest possible starting times for activities \(K\) and \(L\).
   2. State the number of days by which the completion of the project is now delayed.
      (1 mark) \section*{Figure 1}
5. 
   \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-02_815_1337_1573_395}
6. Critical paths are \(\_\_\_\_\)
   Minimum completion time is \(\_\_\_\_\) days. QUESTION PART REFERENCE
7. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-03_978_1207_354_461}
   \end{figure}

2 Five students attempted five different games, and penalty points were given for any mistakes that they made. The table shows the penalty points incurred by the students. Using the Hungarian algorithm, each of the five students is to be allocated to a different game so that the total number of penalty points is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   2	4	0	2	3
   4	2	0	1	1
   5	0	1	\(k\)	0
   1	1	0	4	2
   0	2	0	0	3

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with three lines, and use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five students to the five games with the minimum total of penalty points.
4. Find the minimum possible total of penalty points.
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-05_2484_1709_223_153}

3

1. Given that \(k\) is a constant, display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 6 x + 5 y + 3 z
   \text { subject to } & x + 2 y + k z \leqslant 8
   & 2 x + 10 y + z \leqslant 17
   & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. 1. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(x\)-column as pivot.
   2. Given that the maximum value of \(P\) has not been achieved after this first iteration, find the range of possible values of \(k\).
3. In the case where \(k = - 1\), perform one further iteration and interpret your final tableau.
   
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-07_2484_1707_223_155}

4 Two people, Roger and Corrie, play a zero-sum game.
The game is represented by the following pay-off matrix for Roger.

1. 1. Find the optimal mixed strategy for Roger.
   2. Show that the value of the game is \(\frac { 7 } { 13 }\).
2. Given that the value of the game is \(\frac { 7 } { 13 }\), find the optimal mixed strategy for Corrie.
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-09_2484_1709_223_153}

5 A three-day journey is to be made from \(P\) to \(V\), with overnight stops at the end of the first day at one of the locations \(Q\) or \(R\), and at the end of the second day at \(S , T\) or \(U\). The network shows the journey times, in hours, for each day of the journey.
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-10_737_1280_447_388} The optimal route, known as the minimax route, is that in which the longest day's journey is as small as possible.

1. Explain why the route \(P Q S V\) is better than the route \(P Q T V\).
2. By completing the table opposite, or otherwise, use dynamic programming, working backwards from \(\boldsymbol { V }\), to find the optimal (minimax) route from \(P\) to \(V\). You should indicate the calculations as well as the values at stages 2 and 3.
   (8 marks)

   \(\ldots . . .\).

   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-11_1000_114_1710_159}

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute.
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}

1. Find the value of the cut \(Q\).
2. Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(B T , D E\) and \(E T\).
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 opposite.
   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.
   3. Illustrate the maximum flow on Figure 5 opposite.
4. Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
   \end{figure} Figure 4 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153}
   \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}