OCR D2 (Decision Mathematics 2) 2012 June

1 The six cadets in Red Team have been told to guard a building through the night, starting at 2200 hours and finishing at 0800 hours the next day. Each will be on duty for either one hour or three hours and will then hand over to the next cadet. The table shows which duty each cadet has offered to take. \begin{table}[h] \end{table}

1. Draw a bipartite graph to represent this information. Amir suggests that he should take the 2200 duty, hand over to Becca at 0100 , she can hand over to Chris at 0200 , and Dan can take the 0400 duty. However, this leaves Emma and Finn to cover the 0300 and 0500 duties, and neither of them wants either of these.
2. Write down the shortest possible alternating path starting at the 0500 duty and hence write down an improved but still incomplete matching between the cadets and the duties.
3. Augment this second incomplete matching by writing down a shortest possible alternating path, this time starting from one of the cadets, to form a complete matching between the cadets and the duties. Write down which cadet should take which duty.

2 The cadets in Blue Team have been set a task that requires them to get inside a guarded building. Every two hours one of them will attempt to get inside the building. Each cadet will have one attempt. The table shows a score for each cadet attempting to get inside the building at each time. The higher the score the more likely the cadet is to succeed. Time

1. Explain how to modify the table so that the Hungarian algorithm can be used to find the matching for which the total score is maximised.
2. Show that, after modifying the table and then reducing rows and then columns, the reduced cost matrix becomes:

   	2330	0130	0330	0530	0730
   \(G\)	0	6	0	3	4
   \(H\)	0	5	1	5	4
   \(I\)	0	4	0	3	2
   \(J\)	0	3	0	2	2
   \(K\)	0	0	0	0	0

3. Complete the application of the Hungarian algorithm, stating how each table was formed. Write down the order in which the cadets should attempt to get into the building to maximise the total score. If the cadets use this solution, which one is least likely to succeed?

3 Throughout this question all clock times are in Greenwich Mean Time (GMT).
An aeroplane needs to arrive at its destination at 3pm. The places it can pass through on its route are shown in the network, together with the flying times, in hours, between them.
\includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-4_609_1523_486_255} Use a dynamic programming tabulation, working backwards from 3pm at the destination, to find the latest time that the aeroplane could set off. If the aeroplane takes off at its latest time, which places does it pass through, and at what time does it reach each of these places?

4 A group of rowers have challenged some cyclists to see which team is fitter. There will be several rounds to the challenge. In each round, the rowers and the cyclists each choose a team member and these two compete in a series of gym exercises. The time by which the winner finishes ahead of the loser is converted into points. These points are added to the score for the winner's team and taken off the score for the loser's team. The table shows the expected number of points added to the score for the rowers for each combination of competitors. Rowers \begin{table}[h] \end{table}

1. Regarding this as a zero-sum game, find the play-safe strategy for the rowers and the play-safe strategy for the cyclists. Show that the game is stable. Unfortunately, Wendy and Kath are needed by their coaches and cannot compete.
2. Show that the resulting reduced game is unstable.
3. Suppose that the cyclists are equally likely to choose Chris or Jamie. Calculate the expected number of points added to the score for the rowers when they choose Andy and when they choose Zac. Suppose that the cyclists use random numbers to choose between Chris and Jamie, so that Chris is chosen with probability \(p\) and Jamie with probability \(1 - p\).
4. Showing all your working, calculate the optimum value of \(p\) for the cyclists.
5. The rowers use random numbers in a similar way to choose between Andy and Zac, so that Andy is chosen with probability \(q\) and Zac with probability \(1 - q\). Calculate the optimum value of \(q\).

5 The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the pipes, in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-6_577_1182_351_443}

1. Identify the source and explain how you know that the sink is at \(G\).
2. Calculate the capacity of the cut that separates \(\{ A , B , C , D , E , F \}\) from \(\{ G , H , I , J , K , L \}\).
3. Assuming that a feasible flow exists, explain why arc \(J G\) must be at its lower capacity. Write down the flows in arcs \(H K\) and \(I L\).
4. Assuming that a feasible flow exists, explain why arc HI must be at its upper capacity. Write down the flows in arcs \(E H\) and \(C B\).
5. Show a flow of 10 litres per second through the system.
6. Using your flows from part (v), label the arrows on the diagram to show the excess capacities and the potential backflows.
7. Write down a flow augmenting path from your diagram in part (vi), but do not update the excess capacities and the potential backflows. Hence show a maximum flow through the system, and state how you know that the flow is maximal.

6 Tariq wants to advertise his gardening services. The activities involved, their durations (in hours) and immediate predecessors are listed in the table.

1. Draw an activity network, using activity on arc, to represent the project.
2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities. Tariq does not have time to complete all the activities on his own, so he gets some help from his friend Sally.
   Sally can help Tariq with any of the activities apart from \(C , H\) and \(J\). If Tariq and Sally share an activity, the time it takes is reduced by 1 hour. Sally can also do any of \(F , G\) and \(I\) on her own.
3. Describe how Tariq and Sally should share the work so that activity \(D\) can start 5 hours after the start of the project.
4. Show that, if Sally does as much of the work as she can, she will be busy for 18 hours. In this case, for how many hours will Tariq be busy?
5. Explain why, if Sally is busy for 18 hours, she will not be able to finish until more than 18 hours from the start. How soon after the start can Sally finish when she is busy for 18 hours?
6. Describe how Tariq and Sally can complete the project together in 18 hours or less.