OCR D2 (Decision Mathematics 2) 2006 June

1 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are lower and upper capacities in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-02_696_1292_376_424}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Show that the capacity of the cut \(\alpha\), shown on the diagram, is 12 litres per second and calculate the minimum flow across the cut \(\alpha\), from \(S\) to \(T\), (without regard to the remainder of the diagram).
3. Explain why the arc SC must have at least 5 litres per second flowing through it. By considering the flow through \(A\), explain why \(A D\) cannot be full to capacity.
4. Show that it is possible for 11 litres per second to flow through the system.
5. From your previous answers, what can be deduced about the maximum flow through the system?

2 A delivery company needs to transport heavy loads from its warehouse to a ferry port. Each of the roads that it can use has a bridge with a maximum weight limit. The directed network below represents the roads that can be used to get from the warehouse to the ferry port. Road junctions are labelled with (stage; state) labels. The weights on the arcs represent weight limits in tonnes.
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-03_896_1561_468_292}

1. Explain what a maximin route is.
2. Set up a dynamic programming tabulation, working backwards from stage 1, to find the two maximin routes through the network. What is the maximum load that can be transported in one journey from the warehouse to the ferry port?
3. A new road is opened connecting ( \(2 ; 0\) ) and ( \(2 ; 1\) ). There is no bridge on this road so it does not restrict the weight of the load that can be carried. Using the new road, what is the maximum load that can be transported in one journey from the warehouse to the ferry port? State the route that the delivery company should use. (Do not attempt to apply dynamic programming in this part.)

3 Rose and Colin repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Rose for each combination of strategies.

1. What is the greatest number of points that Colin can win when Rose plays strategy \(A\) and which strategy does Colin need to play to achieve this?
2. Show that strategy \(B\) dominates strategy \(C\) and also that strategy \(Y\) dominates strategy \(Z\). Hence reduce the game to a \(3 \times 3\) pay-off matrix.
3. Find the play-safe strategy for each player on the reduced game. Is the game stable? Rose makes a random choice between the strategies, choosing strategy \(A\) with probability \(p _ { 1 }\), strategy \(B\) with probability \(p _ { 2 }\) and strategy \(D\) with probability \(p _ { 3 }\). She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 5 ,
   \text { subject to } & m \leqslant 4 p _ { 1 } + 10 p _ { 2 } ,
   & m \leqslant 9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 } ,
   & m \leqslant 2 p _ { 1 } + 10 p _ { 2 } + p _ { 3 } ,
   & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 ,
   \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$ (You are not required to solve this problem.)
4. Explain how \(9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 }\) was obtained. A computer gives the solution to the LP problem as \(p _ { 1 } = \frac { 7 } { 48 } , p _ { 2 } = \frac { 27 } { 48 } , p _ { 3 } = \frac { 14 } { 48 }\).
5. Calculate the value of \(M\) at this solution.

4 Answer this question on the insert provided. The diagram shows an activity network for a project. The table lists the durations of the activities (in hours).
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-05_680_1125_424_244} (ii) Key: \begin{figure}[h] \end{figure} Minimum completion time = \(\_\_\_\_\) hours Critical activities: \(\_\_\_\_\)
(iii) \(\_\_\_\_\)
(iv)
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-11_513_1189_543_520} Number of workers required = \(\_\_\_\_\) (ii) \(\_\_\_\_\)
(iii) Answer part (iv) in your answer booklet.