AQA D2 (Decision Mathematics 2) 2007 January

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

1. Complete an 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. State the minimum completion time for the building project and identify the critical paths.

2 Five successful applicants received the following scores when matched against suitability criteria for five jobs in a company. It is intended to allocate each applicant to a different job so as to maximise the total score of the five applicants.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(15 - x\).
2. Form a new table by subtracting each number in the table from 15. Use the Hungarian algorithm to allocate the jobs to the applicants so that the total score is maximised.
3. It is later discovered that Bill has already been allocated to Job 4. Decide how to alter the allocation of the other jobs so as to maximise the score now possible.

3

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 5 x + 8 y + 7 z
   \text { subject to } & 3 x + 2 y + z \leqslant 12
   & 2 x + 4 y + 5 z \leqslant 16
   & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. The Simplex method is to be used by initially choosing a value in the \(y\)-column as a pivot.
   1. Explain why the initial pivot is 4 .
   2. Perform two iterations of your tableau from part (a) using the Simplex method.
   3. State the values of \(P , x , y\) and \(z\) after your second iteration.
   4. State, giving a reason, whether the maximum value of \(P\) has been achieved.

4

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

   \multirow{2}{*}{}	\multirow[b]{2}{*}{Strategy}	Col
   		X	Y	Z
   \multirow{3}{*}{Ros}	I	-4	-3	0
   	II	5	-2	2
   	III	1	-1	3

   1. Show that this game has a stable solution.
   2. Find the play-safe strategy for each player and state the value of the game.
2. Ros and Col play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Ros.

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Col
   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Strategy	\(\mathbf { C } _ { \mathbf { 1 } }\)	\(\mathbf { C } _ { \mathbf { 2 } }\)	\(\mathbf { C } _ { \mathbf { 3 } }\)
   \multirow{2}{*}{Ros}	\(\mathbf { R } _ { \mathbf { 1 } }\)	3	2	1
   \cline { 2 - 5 }	\(\mathbf { R } _ { \mathbf { 2 } }\)	- 2	- 1	2

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

5 A three-day journey is to be made from \(S\) to \(T\), with overnight stops at the end of the first day at either \(A\) or \(B\) and at the end of the second day at one of the locations \(C , D\) or \(E\). The network shows the number of hours of sunshine forecast for each day of the journey.
\includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-05_753_1284_479_386} The optimal route, known as the maximin route, is that for which the least number of hours of sunshine during a day's journey is as large as possible.

1. Explain why the three-day route \(S A E T\) is better than \(S A C T\).
2. Use dynamic programming to find the optimal (maximin) three-day route from \(S\) to \(T\). (8 marks)

6 [Figures 2 and 3, printed on the insert, are provided for use in this question.]
The diagram shows a network of pipelines through which oil can travel. The oil field is at \(S\), the refinery is at \(T\) and the other vertices are intermediate stations. The weights on the edges show the capacities in millions of barrels per hour that can flow through each pipeline.
\includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-06_956_1470_593_283}

1. 1. Find the value of the cut marked \(C\) on the diagram.
   2. Hence make a deduction about the maximum flow of oil through the network.
2. State the maximum possible flows along the routes \(S A B T , S D E T\) and \(S F T\).
3. 1. Taking your answer to part (b) as the initial flow, use a labelling procedure on Figure 2 to find the maximum flow from \(S\) to \(T\). Record your routes and flows in the table provided and show the augmented flows on the network diagram. (6 marks)
   2. State the value of the maximum flow, and, on Figure 3, illustrate a possible flow along each edge corresponding to this maximum flow.
   3. Prove that your flow in part (c)(ii) is a maximum.

      Surname

      Other Names

      Centre Number

      Candidate Number

      Candidate Signature

      \section*{General Certificate of Education
      January 2007
      Advanced Level Examination} \section*{MATHEMATICS
      Unit Decision 2} MD02 \section*{Insert} Insert for use in Questions 1 and 6.
      Fill in the boxes at the top of this page.
      Fasten this insert securely to your answer book.