OCR D2 (Decision Mathematics 2) 2009 January

1 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

2 Answer this question on the insert provided. The diagram shows an activity network for a project. The figures in brackets show the durations of the activities in days.
\includegraphics[max width=\textwidth, alt={}, center]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-3_497_1230_493_459}

1. Complete the table in the insert to show the precedences for the activities.
2. Use the boxes on the diagram in the insert to carry out a forward pass and a backward pass. Show that the minimum project completion time is 28 days and list the critical activities. The resource histogram below shows the number of workers required each day when the activities each begin at their earliest possible start time. Once an activity has been started it runs for its duration without a break.
   \includegraphics[max width=\textwidth, alt={}, center]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-3_457_1543_1503_299}
3. By considering which activities are happening each day, complete the table in the insert to show the number of workers required for each activity. You are advised to start at day 28 and work back through the days towards day 1 . Only five workers are actually available, but they are all equally skilled at each of the activities. The project can still be completed in 28 days by delaying the start of activity \(E\).
4. Find the minimum possible delay and the maximum possible delay on activity \(E\) in this case.

3 Answer this question on the insert provided. \begin{figure}[h] \end{figure} Fig. 1 represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows a cut \(\alpha\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second.

1. Calculate the capacity of the cut \(\alpha\).
2. By considering vertex \(B\), explain why arc \(S B\) must be at its lower capacity. Then by considering vertex \(E\), explain why arc \(C E\) must be at its upper capacity, and hence explain why arc \(H T\) must be at its lower capacity.
3. On the diagram in the insert, show a flow through the network of 15 litres per second. Write down one flow augmenting route that allows another 1 litre per second to flow through the network. Show that the maximum flow is 16 litres per second by finding a cut of 16 litres per second. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_602_1086_1809_568} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure} Fig. 2 represents the same system, but with pipe \(E B\) installed the wrong way round.
4. Explain why there can be no feasible flow through this network.

4 Anya \(( A )\), Ben \(( B )\), Connie \(( C )\), Derek \(( D )\) and Emma \(( E )\) work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page \(( P )\), restaurant review \(( R )\), sports news \(( S )\), theatre review \(( T )\) and weather report \(( W )\). Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.

1. Draw a bipartite graph to show the possible pairings between the writers ( \(A , B , C , D\) and \(E\) ) and the articles ( \(P , R , S , T\) and \(W\) ). On your bipartite graph, show who has been given which article by the editor.
2. Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.

   \multirow{8}{*}{Sub-editor}	\multirow{2}{*}{}	Article
   		\(P\)	\(R\)	\(S\)	\(T\)	\(W\)
   	Jeremy ( \(J\) )	56	56	51	57	58
   	Kath ( \(K\) )	53	52	53	54	54
   	Laura ( \(L\) )	57	55	52	58	60
   	Mohammed ( \(M\) )	59	55	53	59	57
   	Natalie ( \(N\) )	57	57	53	59	60
   	Ollie ( \(O\) )	58	56	51	56	57

   The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.
3. Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs \(\pounds 0.25\), calculate the total cost of checking the articles each week.

5 The local rugby club has challenged the local cricket club to a chess match to raise money for charity. Each of the top three chess players from the rugby club has played 10 chess games against each of the top three chess players from the cricket club. There were no drawn games. The table shows, for each pairing, the number of games won by the player from the rugby club minus the number of games won by the player from the cricket club. This will be called the score; the scores make a zero-sum game.

1. How many of the 10 games between Sanjeev and Doug did Sanjeev win? How many of the 10 games between Sanjeev and Euan did Euan win? Each club must choose one person to play. They want to choose the person who will optimise the score.
2. Find the play-safe choice for each club, showing your working. Explain how you know that the game is not stable.
3. Which person should the cricket club choose if they know that the rugby club will play-safe and which person should the rugby club choose if they know that the cricket club will play-safe?
4. Explain why the rugby club should not choose Tom. Which player should the cricket club not choose, and why? The rugby club chooses its player by using random numbers to choose between Sanjeev and Ursula, where the probability of choosing Sanjeev is \(p\) and the probability of choosing Ursula is \(1 - p\).
5. Write down an expression for the expected score for the rugby club for each of the two remaining choices that can be made by the cricket club. Calculate the optimal value for \(p\). Doug is studying AS Mathematics. He removes the row representing Tom and then models the cricket club's problem as the following LP. $$\begin{array} { l l } \operatorname { maximise } & M = m - 4
   \text { subject to } & m \leqslant 4 x \quad + 6 z
   & m \leqslant 2 x + 10 y + 4 z
   & x + y + z \leqslant 1
   \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
6. Show how Doug used the values in the table to get the constraints \(m \leqslant 4 x + 6 z\) and \(m \leqslant 2 x + 10 y + 4 z\). Doug uses the Simplex algorithm to solve the LP problem. His solution has \(x = 0\) and \(y = \frac { 1 } { 6 }\).
7. Calculate the optimal value of \(M\).