OCR D2 (Decision Mathematics 2) 2013 January

1 A TV soap opera has five main characters, Alice ( \(A\) ), Bob ( \(B\) ), Charlie ( \(C\) ), Dylan ( \(D\) ) and Etty ( \(E\) ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( \(F\) ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( \(G\) ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( \(J\) ) does not star any of the main characters who were in the episodes about the fire or the house break-in.

1. Draw a bipartite graph to show which main characters ( \(A , B , C , D , E\) ) are in which of the next five episodes \(( F , G , H , I , J )\). The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.
2. Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.
3. From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.
4. By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

2 A project is represented by this activity network. The weights (in brackets) on the arcs represent activity durations, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-3_645_1235_356_415}

1. Complete the table in the answer book to show the immediate predecessors for each activity.
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. Suppose that the start of one activity is delayed by 2 minutes.
3. List each activity which could be delayed by 2 minutes with no change to the minimum project completion time.
4. Without altering your diagram from part (ii), state the effect that a delay of 2 minutes on activity \(A\) would have on the minimum project completion time. Name another activity which could be delayed by 2 minutes, instead of \(A\), and have the same effect on the minimum project completion time.
5. Without altering your diagram from part (ii), state what effect a delay of 2 minutes on activity \(C\) would have on the minimum project completion time.

3 Agatha Parrot is in her garden and overhears her neighbours talking about four new people who have moved into her village. Each of the new people has a different job, and Agatha's neighbours are guessing who has which job. Using the information she has overheard, Agatha counts how many times she heard it guessed that each person has each job. Agatha wants to find the allocation of people to jobs that maximises the total number of correct guesses. She intends to use the Hungarian algorithm to do this. She starts by subtracting each value in the table from 10.

1. Write down the table which Agatha gets after she has subtracted each value from 10. Explain why she did a subtraction.
2. Apply the Hungarian algorithm, reducing rows first, to find which job Agatha concludes each person has. State how each table of working was calculated from the previous one. Agatha later meets Liz Lomax and is surprised to find out that she is the radiographer.
3. Using this additional information, but without formally using the Hungarian algorithm, find which job Agatha should now conclude each person has. Explain how you know that there is no better solution in which Liz is the radiographer.

4 The diagram represents a system of pipes through which fluid can flow from two sources, \(S _ { 1 }\) and \(S _ { 2 }\), to a sink, \(T\). Most of the pipes have valves which restrict the flow to one direction only. However, the flow in arc \(D E\) can be in either direction. The weights on the arcs show the lower capacities and the upper capacities of the pipes in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-5_565_1130_447_463}

1. Add a supersource, \(S\), to the copy of the diagram in the answer book, and weight the arcs attached to it with appropriate lower and upper capacities.
2. The cut \(\alpha\) partitions the vertices into the sets \(\left\{ S , S _ { 1 } , S _ { 2 } , A , C \right\} , \{ B , D , E , T \}\). By considering the cut arcs only, calculate the maximum and minimum capacities of cut \(\alpha\).
3. Show that the maximum capacity of the cut \(\left\{ S , S _ { 1 } , S _ { 2 } , A , E \right\} , \{ B , C , D , T \}\) is 47 litres per second. A flow is set up in which the arcs \(S _ { 1 } A , S _ { 1 } B , S _ { 2 } C , A E , C E\) and \(D T\) are all at their lower capacities.
4. Show the flow in each arc on the diagram in the answer book, indicating the direction of the flow in \(\operatorname { arc } D E\).
5. What is the maximum amount, in litres per second, by which the flow can be augmented using the routes \(S _ { 1 } A D T\) and \(S _ { 2 } C E T\) ?
6. Find the maximum possible flow through the system, explaining how you know both that this is feasible and that it cannot be exceeded.

5 Rose and Colin are playing a game in which they each have four cards. Each player chooses a card from those in their hand, and simultaneously they show each other the cards they have chosen. The table below shows how many points Rose wins for each combination of cards. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rose and Colin are trying to win as many points as possible.

1. What is the greatest number of points that Colin can win when Rose chooses and which card does Colin need to choose to achieve this?
2. Explain why Rose should never choose and find the card that Colin should never choose. 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 and show whether or not the game is stable. Rose makes a random choice between her cards, choosing with probability \(x\) with probability \(y\), and with probability \(z\). She formulates the following LP problem to be solved using the Simplex algorithm:
   maximise \(\quad M = m - 6\),
   subject to \(\quad m \leqslant 4 x + 10 y\),
   \(n \leqslant 9 x + 3 y + 11 z\),
   \(n \leqslant 2 x + 10 y + z\),
   \(x + y + z \leqslant 1\),
   and
   \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0 , m \geqslant 0\).
   (You are not required to solve this problem.)
4. Explain how \(9 x + 3 y + 11 z\) was obtained. The Simplex algorithm is used to solve the LP problem. The solution has \(x = \frac { 7 } { 48 } , y = \frac { 27 } { 48 } , z = \frac { 14 } { 48 }\).
5. Calculate the optimal value of \(M\).

6 Simon makes playhouses which he sells through an agent. Each Sunday the agent orders the number of playhouses she will need Simon to deliver at the end of each day. The table below shows the order for the coming week. Simon can make up to 3 houses each day, except for Wednesday when he can make at most 2 houses. Because of limited storage space, Simon can store at most 2 houses overnight from one day to the next, although the number in store does not restrict how many houses Simon can make the next day. The process is modelled by letting the stages be the days and the states be the numbers of houses stored overnight. Simon starts the week, on Monday morning, with no houses in storage. This means that the start of Monday morning has (stage; state) label ( \(0 ; 0\) ). Simon wants to end the week on Friday afternoon with no houses in storage, so the start of Saturday morning will have (stage; state) label ( \(5 ; 0\) ).

1. Explain why the (stage; state) label ( \(4 ; 0\) ) is not needed. Simon wants to draw up a production plan showing how many houses he needs to make each day. He prefers not to have to make several houses on the same day so he assigns a 'cost' that is the square of the number of houses made that day, apart from Monday when the 'cost' is the cube of the number of houses made. So, for example, if he makes 3 houses one day the cost is 9 units, unless it is Monday when the cost is 27 units.
2. Complete the diagram in the answer book to show all the possible production plans and weight the arcs with the costs. Simon wants to find a production plan that minimises the sum of the costs.
3. Set up a dynamic programming tabulation, working backwards from ( \(5 ; 0\) ), to find a production plan that solves Simon's problem.
4. Write down the number of houses that he should make each day with this plan.