OCR D2 (Decision Mathematics 2) 2012 January

1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film. Jack \(( J )\) wants to review a horror movie; Karen \(( K )\) wants to review an animated film; Lee \(( L )\) wants to review a film that is suitable for family viewing; Mark ( \(M\) ) wants to review an action adventure film and Nikki ( \(N\) ) wants to review anything that is in 3D. The film "Somewhere" ( \(S\) ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( \(T\) ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" \(( U )\) is an animated action adventure film; "Vampires" ( \(V\) ) is an animated horror movie that is suitable for family viewing and "World" ( \(W\) ) is an animated film.

1. Draw a bipartite graph to show which student ( \(J , K , L , M , N\) ) wants to review which films ( \(S , T , U\), \(V , W\) ). Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.
2. Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.
3. From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.
4. Show that this is the only possible complete matching between the students and the films.

2 The table lists the durations (in minutes), immediate predecessors and number of workers required for each activity in a project to decorate a room.

1. Draw an activity network, using activity on arc, to represent the project. Your network will require a dummy 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.
3. Draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time. Suppose that there is only one worker available at the start of the project, but another two workers are available later.
4. Find the latest possible time for the other workers to start and still have the project completed on time. Which activities could happen at the same time as painting the ceiling if the other two workers arrive at this latest possible time?
   [0pt] [Do not change your resource histogram from part (iii).]

3 The famous fictional detective Agatha Parrot has been called in to investigate the theft of some jewels. Each thief is known to have taken just one item of jewellery. Agatha has invented a scoring system based on motive, opportunity and past experience. The table shows the score for each of four suspects with each of three items of jewellery. The higher the score the more likely the suspect is to have stolen that item of jewellery. Suspect

1. Assuming that three of these four suspects are the thieves, find who is most likely to have stolen each item of jewellery for the total score to be maximised. State how each table of working was calculated. Write down the two possible solutions for who should be suspected of stealing each item of jewellery and who should be thought to be innocent. Further evidence shows that the butler stole the sapphire bracelet.
2. Using this additional information, find out which suspect should be thought to be innocent. Explain your reasoning.

4 The diagram represents a system of roads through which traffic flows from a source, \(S\), to a sink, \(T\). The weights on the arcs show the capacities of the roads in cars per minute.
\includegraphics[max width=\textwidth, alt={}, center]{3a47bac8-0067-4acb-a3c7-7d8512403cca-5_414_1080_349_488}

1. (a) The cut \(\alpha\) partitions the vertices into the sets \(\{ S , A , B , C \} , \{ D , E , F , T \}\). Calculate the capacity of cut \(\alpha\).
   (b) The cut \(\beta\) partitions the vertices into the sets \(\{ S , A , B , D \} , \{ C , E , F , T \}\). Calculate the capacity of cut \(\beta\).
   (c) Using only the capacities of cuts \(\alpha\) and \(\beta\), what can you deduce about the maximum possible flow through the system?
2. Explain why partitioning the vertices into sets \(\{ S , A , D , T \} , \{ B , C , E , F \}\) does not give a cut.
3. What do the double arcs between \(D\) and \(E\) and between \(E\) and \(F\) represent?
4. Explain why the maximum possible flow along \(C F\) must be less than 45 cars per minute.
5. (a) Show how a flow of 60 cars per minute along \(F T\) can be achieved.
   (b) Show that 60 cars per minute is the maximum possible flow through the system. An extra road is opened linking \(S\) to \(C\). Let the capacity of this road be \(x\) cars per minute.
6. Find the maximum possible flow through the new system, in terms of \(x\) where necessary, for the different possible values of \(x\).

5 Henry is doing a sponsored cycle ride for charity. He needs to finish at noon on Sunday. He can ride up to 50 miles each day, except Sunday when he can ride at most 20 miles if he is to finish on time. The total length of the ride is 95 miles so Henry has allowed 3 days for the ride. Henry will start his ride at \(A\) and travel through \(B , C , D\) and \(E\), in that order, and finish on Sunday at \(F\). He will stay overnight on Friday and Saturday at two of the places \(B , C , D\) and \(E\). The distances between the places along the route are: $$A - B = 30 \text { miles } , \quad B - C = 15 \text { miles } , \quad C - D = 35 \text { miles } , \quad D - E = 12 \text { miles } , \quad E - F = 3 \text { miles. }$$ To reach \(F\) on Sunday he must have reached at least \(D\) by Saturday night (since the distance from \(D\) to \(F\) is less than 20 miles but \(C\) to \(F\) is more than 20 miles.) Henry wants to use dynamic programming to minimise the maximum distance that he cycles on any day.
The stages will be the days. The places where Henry stays overnight will be the states. Henry starts on Friday morning at \(A\) which has the (stage; state) label ( \(0 ; 0\) ). On Friday night he can either stay at \(B ( 1 ; 0 )\) or at \(C ( 1 ; 1 )\). Depending on where he stays on Friday night, he can spend Saturday night at \(D ( 2 ; 0 )\) or \(E ( 2 ; 1 )\). On Sunday he arrives at \(F ( 3 ; 0 )\).
[0pt]

1. Use this information and the table below to draw a network, labelled with stages and states, to show the possible transitions between states. The arc weights should be the distances between the states. [2] Henry uses dynamic programming, working backwards from stage 3, to find where he should stay overnight to give the route for which the maximum on any day is a minimum. His tabulation is shown below.

   Stage	State	Action	Working	Suboptimal minimax
   \multirow[t]{2}{*}{2}	0	0	15	15
   	1	0	3	3
   \multirow{3}{*}{1}	0	0	\(\max ( 50,15 )\)	50
   	\multirow[t]{2}{*}{1}	0	\(\max ( 35,15 )\)	\multirow[t]{2}{*}{35}
   		1	\(\max ( 47,3 )\)
   \multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	\(\max ( 30,50 )\)	\multirow[b]{2}{*}{45}
   		1	max(45, 35)

2. (a) In the last row of the table, the action value is 1 . Explain what this tells you.
3. (b) In the last row of the table, the working column is \(\max ( 45,35 )\). Explain where each of the values 45 and 35 comes from and how they relate to the (stage; state) values for this row and for a row from the next stage.
4. Use the table to deduce where Henry should make his overnight stops to minimise the maximum distance that he cycles on any day. Explain how you obtained this solution from the table. Henry is so pleased with his ride that he decides to do a longer ride. Again he will cycle up to 50 miles each day, except the last day when he will cycle at most 20 miles. He wants to complete the ride in five days, and he wants to minimise the maximum distance that he rides on any one day. He will start at \(A\) and travel through \(B , C , D , E , F , G , H , I , J\) and \(K\), in that order, and finish at \(L\).
   He will stay overnight on Wednesday, Thursday, Friday and Saturday at four of \(B , C , D , E , F , G , H , I , J\) and \(K\). The distances between the places along the route are:

   \(A - B = 30\) miles,	\(B - C = 15\) miles,	\(C - D = 35\) miles,	\(D - E = 12\) miles,
   \(E - F = 3\) miles,	\(F - G = 30\) miles,	\(G - H = 10\) miles,	\(H - I = 25\) miles,
   \(I - J = 10\) miles,	\(J - K = 10\) miles,	\(K - L = 5\) miles.

5. (a) Which is the furthest place from \(L\) that Henry must reach by Saturday night if he is to finish on time?
   (b) Work backwards to deduce the furthest place from \(L\) that Henry must reach by Friday night, Thursday night and Wednesday night.
6. Find out where Henry could stay each night, and hence define appropriate states for each of stages 1, 2, 3 and 4 . (Note that not every place need correspond to a (stage; state) label.)
7. Set up a dynamic programming tabulation, working backwards from stage 5, to minimise the maximum distance that Henry must ride on any one day. Where should he make his overnight stops?

6 Rowena and Colin play a game in which each chooses a letter. The table shows how many points Rowena wins for each combination of letters. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rowena and Colin are trying to win as many points as possible. Colin's letter \begin{table}[h] \end{table}

1. Write down Colin's play-safe strategy, showing your working. What is the maximum number of points that Colin can win if he plays safe?
2. Explain why Rowena would never choose the letter \(W\). Rowena uses random numbers to choose between her three remaining options, so that she chooses \(X , Y\) and \(Z\) with probabilities \(x , y\) and \(z\), respectively. Rowena then models the problem of which letter she should choose as the following LP. $$\begin{array} { c l } \text { Maximise } & M = m - 1
   \text { subject to } & m \leqslant 2 x + 6 y + z ,
   & m \leqslant 4 x + 2 y ,
   & m \leqslant 3 y + 2 z ,
   & m \leqslant 2 x + 2 z ,
   & x + y + z \leqslant 1
   \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
3. Show how the expression \(2 x + 6 y + z\) was formed. The Simplex algorithm is used to solve the LP problem. The solution has \(x = 0.3 , y = 0.2\) and \(z = 0.5\).
4. Show that the optimal value of \(M\) is 0.6 . Colin then models the problem of which letter he should choose in a similar way. When Rowena plays using her optimal solution, from above, Colin finds that he should never choose the letter \(N\). Letting \(p , q\) and \(t\) denote the probabilities that he chooses \(P , Q\) and \(T\), respectively, Colin obtains the following equations. $$- 3 p + q - t = - 0.6 \quad - p - 2 q + t = - 0.6 \quad p - q - t = - 0.6 \quad p + q + t = 1$$
5. Explain how the equation \(- 3 p + q - t = - 0.6\) is obtained.
6. Use the third and fourth equations to find the value of \(p\). Hence find the values of \(q\) and \(t\).