OCR D2 (Decision Mathematics 2) 2015 June

1 The infamous fictional detective Agatha Parrot is working on a case and decides to invite each of the four suspects to visit her for tea. She will invite one suspect to tea on Sunday (S), another on Monday (M), another on Tuesday (T) and the final suspect on Wednesday (W).

• Beryl Batty (B) could come to tea on Sunday or Monday but she is away for a few days after that.
• Colonel Chapman (C) could come to tea on Sunday or Tuesday, but is busy on the other days.
• Dimitri Delacruz (D) could only come to tea on Monday or Wednesday.
• Erina El-Sayed (E) could come to tea on Sunday, Monday or Tuesday, but will be away on Wednesday.
  1. Draw a bipartite graph to show which suspects could come to tea on which day.

Agatha initially intended to invite Beryl to tea on Sunday, Dimitri on Monday and Colonel Chapman on Tuesday. However this would mean that Erina would not be able to come to tea, as she will be away on Wednesday.

Draw a second bipartite graph to show this incomplete matching.

Working from this incomplete matching, find the shortest possible alternating path, starting at Erina, to achieve a breakthrough. Write down which suspect is invited on which day with this matching. Before issuing invitations, Agatha overhears Erina making arrangements to go to tea with the vicar one day. She knows that Erina will not want to accept two invitations to tea on the same day. Unfortunately, Agatha does not know which day Erina has arranged to go to tea with the vicar, other than that it was not Sunday. Agatha invites Erina to tea on Sunday and the others when she can. After having tea with all four suspects she considers what they have said and invites them all back on Friday. She then accuses the person who came to tea on Monday of being guilty.

Who does Agatha accuse of being guilty?

2 The diagram below shows an activity network for a project. The figures in brackets show the durations of the activities, in hours.
\includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-3_371_1429_367_319}

1. Complete the table in your answer book to show the immediate predecessors for each activity.
2. Carry out a forward pass and a backward pass on the copy of the network in your answer book, showing the early event times and late event times. State the minimum project completion time, in hours, and list the critical activities.
3. How much longer could be spent on activity \(F\) without it affecting the overall completion time? Suppose that each activity requires one worker. Once an activity has been started it must continue until it is finished. Activities cannot be shared between workers.
4. (a) State how many workers are needed at the busiest point in the project if each activity starts at its earliest possible start time.
   (b) Suppose that there are fewer workers available than given in your answer to part (iv)(a). Explain why the project cannot now be completed in the minimum project completion time from part (ii). Suppose that activity \(C\) is delayed so that it starts 2 hours after its earliest possible start time, but there is no restriction on the number of workers available.
5. Describe what effect this will have on the critical activities and the minimum project completion time.

3 A team triathlon is a race involving swimming, cycling and running for teams of three people. The first person swims, then the second person cycles and finally the third person runs. The winning team is the team that completes all three stages of the triathlon in the shortest time. Four friends are training to enter as a team for the triathlon. They need to choose who to enter for each stage of the triathlon, and who to leave out (this person will be the reserve). The table shows the times, in minutes, for each of them to complete each stage in training.

1. Complete a dummy column in the table in your answer book. Apply the Hungarian algorithm, reducing columns first. Make sure that the values in your tables can all be seen. Write a list showing who should be chosen for each stage of the triathlon. What is the minimum total time in which the team can expect to complete the three stages of the triathlon? The day before the triathlon, the friend who had been chosen to swim is injured and cannot compete.
2. If the reserve takes over the swim, how much longer can the team expect the triathlon to take?
3. Remove the row corresponding to the injured swimmer to form a \(3 \times 3\) table. Apply the Hungarian algorithm to find who should be chosen for each stage to complete the triathlon in the minimum expected time. State the minimum expected time.

4 Jeremy is planning a long weekend break during which he wants to photograph as many different churches as he can. He will start from his home, \(J\), on Friday morning and return to his home on Monday evening. Table 1, below, summarises the routes he can take each day and the number of churches that he will pass on each route. You may assume that the 28 churches in the table are all different. \begin{table}[h] \end{table}

1. Represent the information in the table as a directed network in which the vertices represent the places. You may code the place names using the letters, as above. Jeremy wants to use dynamic programming to find the route on which he will pass the greatest number of churches. The (stage; state) variables will represent the places where he stays overnight. \(J\) will have (stage; state) variable ( \(0 ; 0\) ) at the start of the journey and ( \(4 ; 0\) ) at the end. Table 2 shows the (stage; state) variables for all the other places. \begin{table}[h]

   Place	\(K\)	\(L\)	\(M\)	\(N\)	\(P\)	\(R\)	\(S\)	\(T\)
   Stage variable	1	1	2	2	2	3	3	3
   State variable	0	1	0	1	2	0	1	2

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Set up a dynamic programming tabulation, working backwards from Monday to Friday, to find the route that Jeremy should take to pass the greatest number of churches. Write down Jeremy's route. You may code the place names using the letters, as above. Write down the number of churches that he will be able to photograph on this route.

5 The diagram shows a flow through a network of directed arcs. The amount that can flow in each arc is limited by its upper capacity, and the lower capacity of each arc is 0 . The labelled arrows by the arcs show how much more (excess capacity) and how much less (potential backflow) could flow in each arc, in litres per second, and the objective is to find the maximum flow from \(S\) to \(T\).
\includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-6_969_1363_459_351}

1. How many litres per second are currently flowing along the route SACHT?
2. How many litres per second are currently flowing from \(S\) to \(T\) ?
3. What is the maximum by which the flow along the route SBGIT can be increased? Use the copy of the network in your answer book to show what happens to the labels on the arrows when the flow along this route is augmented by this amount.
4. Find the maximum amount that can flow through the network. Explain, by using a cut, how you know that your flow is a maximum. The network had vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\). The single vertex \(E\) is replaced by the pair of vertices \(E _ { 1 }\) and \(E _ { 2 }\), together with the \(\operatorname { arc } E _ { 1 } E _ { 2 }\).
5. What does the \(\operatorname { arc }\) joining \(E _ { 1 }\) and \(E _ { 2 }\) tell you about the flow at \(E\) ?
6. Complete the diagram in your answer book to show the flow resulting after part (iii) on a directed network with vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\).

6 At the final battle in a war game, the two opposing armies, led by General Rose, \(R\), and Colonel Cole, \(C\), are facing each other across a wide river. Each army consists of four divisions. The commander of each army needs to send some of his troops North and send the rest South. Each commander has to decide how many divisions (1,2 or 3) to send North. Intelligence information is available on the number of thousands of soldiers that each army can expect to have remaining with each combination of strategies. Thousands of soldiers remaining in \(R\) 's army \(C\) 's choice
\(R\) 's choice Thousands of soldiers remaining in \(C\) 's army
\(C\) 's choice
\(R\) 's choice

1. Construct a table to show the number of thousands of soldiers remaining in \(R\) 's army minus the number of thousands of soldiers remaining in \(C\) 's army (the excess for \(R\) 's army) for each combination of strategies. The commander whose army has the greatest positive excess of soldiers remaining at the end of the game will be declared the winner.
2. Explain the meaning of the value in the top left cell of your table from part (i) (where each commander chooses strategy 1). Hence explain why this table may be regarded as representing a zero-sum game.
3. Find the play-safe strategy for \(R\) and the play-safe strategy for \(C\). If \(C\) knows that \(R\) will choose his play-safe strategy, which strategy should \(C\) choose? One of the strategies is redundant for one of the commanders, because of dominance.
4. Draw a table for the reduced game, once the redundant strategy has been removed. Label the rows and columns to show how many divisions have been sent North. A mixed strategy is to be employed on the resulting reduced game. This leads to the following LP problem:
   Maximise \(\quad M = m - 25\)
   Subject to \(\quad m \leqslant 15 x + 25 y + 35 z\)
   \(m \leqslant 45 x + 20 y\)
   \(x + y + z \leqslant 1\)
   and
5. Interpret what \(x , y\) and \(z\) represent and show how \(m \leqslant 15 x + 25 y + 35 z\) was formed. A computer runs the Simplex algorithm to solve this problem. It gives \(x = 0.5385 , y = 0\) and \(z = 0.4615\).
6. Describe how this solution should be interpreted, in terms of how General Rose chooses where to send his troops. Calculate the optimal value for \(M\) and explain its meaning. Elizabeth does not have access to a computer. She says that at the solution to the LP problem \(15 x + 25 y + 35 z\) must equal \(45 x + 20 y\) and \(x + y + z\) must equal 1 . This simplifies to give \(y + 7 z = 6 x\) and \(x + y + z = 1\).
7. Explain why there can be no valid solution of \(y + 7 z = 6 x\) and \(x + y + z = 1\) with \(x = 0\). Elizabeth tries \(z = 0\) and gets the solution \(x = \frac { 1 } { 7 }\) and \(y = \frac { 6 } { 7 }\).
8. Explain why this is not a solution to the LP problem.