OCR D2 (Decision Mathematics 2) 2010 January

1 Andy ( \(A\) ), Beth ( \(B\) ), Chelsey ( \(C\) ), Dean ( \(D\) ) and Elly ( \(E\) ) have formed a quiz team. They have entered a quiz in which, as well as team questions, each of them must answer individual questions on a specialist topic. The specialist topics could be any of: food \(( F )\), geography \(( G )\), history \(( H )\), politics ( \(P\) ), science ( \(S\) ) and television ( \(T\) ). The team members do not know which five specialist topics will arise in the quiz. Andy wants to answer questions on either food or television; Beth wants to answer questions on geography, history or science; Chelsey wants to answer questions on geography or television; Dean wants to answer questions on politics or television; and Elly wants to answer questions on history or television.

1. Draw a bipartite graph to show the possible pairings between the team members and the specialist topics. In the quiz, the first specialist topic is food, and Andy is chosen to answer the questions. The second specialist topic is geography, and Beth is chosen. The next specialist topic is history, and Elly is chosen. The fourth specialist topic is science. Beth has already answered questions so Dean offers to try this round. The final specialist topic is television, and Chelsey answers these questions.
2. Draw a second bipartite graph to show these pairings, apart from Dean answering the science questions. Write down an alternating path starting from Dean to show that there would have been a better way to choose who answered the questions had the topics been known in advance. Write down which team member would have been chosen for each specialist topic in this case.
3. In a practice, although the other team members were able to choose topics that they wanted, Beth had to answer the questions on television. Write down which topic each team member answered questions on, and which topic did not arise.

2 Dudley has three daughters who are all planning to get married next year. The girls are named April, May and June, after the months in which they were born. Each girl wants to get married on her own birthday. Dudley has already obtained costings from four different hotels. From past experience, Dudley knows that when his family get together they are likely to end up with everyone fighting one another, so he cannot use the same hotel twice. The table shows the costs, in \(\pounds 100\), for each hotel to host each daughter's wedding. Dudley wants to choose the three hotels to minimise the total cost.
Add a dummy row and then apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the hotels and Dudley's daughters. State how each table is formed and write out the final solution and its cost to Dudley.

3 The table lists the duration (in hours), immediate predecessors and number of workers required for each activity in a project.

1. Draw an activity network, using activity on arc, to represent the project. You should make your diagram quite large so that there is room for working.
2. Carry out a forward pass and a backward pass through the activity network, showing the early and late event times clearly at the vertices of your network. State the minimum project completion time and list the critical activities.
3. Using graph paper, draw a resource histogram to show the number of workers required each hour. Each activity begins at its earliest possible start time. Once an activity has started it runs for its duration without a break. A delay from the supplier means that the start of activity \(F\) is delayed.
4. By how much could the start of activity \(F\) be delayed without affecting the minimum project completion time? Suppose that only six workers are available after the first four hours of the project.
5. Explain carefully what delay this will cause on the completion of the project. What is the maximum possible delay on the start of activity \(F\), compared with its earliest possible start time in part (iii), without affecting the new minimum project completion time? Justify your answer.

4 The diagram represents a map of an army truck-driving course that includes several bridges. The start and a 'safe point' just after each bridge have been given (stage; state) labels. The number below each bridge shows its weight limit, in tonnes.
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-4_698_1413_438_365} An army cadet needs to drive a truck through the course from start to finish, crossing exactly three bridges.

1. Draw a network, using the (stage; state) labels given, to represent the routes through the course. The weights on the arcs should show the weight limits for the bridges. The cadet wants to find out the weight of the heaviest truck she can use.
2. Which network problem does she need to solve?
3. Set up a dynamic programming tabulation to solve the cadet's problem. Write down the weight of the heaviest truck she can use and write down the (stage; state) labels for the route she should take.

5 Robbie received a new computer game for Christmas. He has already worked through several levels of the game but is now stuck at one of the levels in which he is playing against a character called Conan. Robbie has played this particular level several times. Each time Robbie encounters Conan he can choose to be helped by a dwarf, an elf or a fairy. Conan chooses between being helped by a goblin, a hag or an imp. The players make their choices simultaneously, without knowing what the other has chosen. Robbie starts the level with ten gold coins. The table shows the number of gold coins that Conan must give Robbie in each encounter for each combination of helpers (a negative entry means that Robbie gives gold coins to Conan). If Robbie's total reaches twenty gold coins then he completes the level, but if it reaches zero the game ends. This means that each attempt can be regarded as a zero-sum game.

1. Find the play-safe choice for each player, showing your working. Which helper should Robbie choose if he thinks that Conan will play-safe?
2. How many gold coins can Robbie expect to win, with each choice of helper, if he thinks that Conan will choose randomly between his three choices (so that each has probability \(\frac { 1 } { 3 }\) )? Robbie decides to choose his helper by using random numbers to choose between the elf and the fairy, where the probability of choosing the elf is \(p\) and the probability of choosing the fairy is \(1 - p\).
3. Write down an expression for the expected number of gold coins won at each encounter by Robbie for each of Conan's choices. Calculate the optimal value of \(p\). Robbie's girlfriend thinks that he should have included the possibility of choosing the dwarf. She denotes the probability with which Robbie should choose the dwarf, the elf and the fairy as \(x , y\) and \(z\) respectively. She then models the problem of choosing between the three helpers as the following LP. $$\begin{aligned} \text { Maximise } & M = m - 4 ,
   \text { subject to } & m \leqslant 3 x + 7 y + 5 z
   & m \leqslant 5 y + 3 z
   & m \leqslant 6 x + 5 z
   & x + y + z \leqslant 1 ,
   \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{aligned}$$
4. Explain how the expression \(3 x + 7 y + 5 z\) was formed. Robbie's girlfriend uses the Simplex algorithm to solve the LP problem. Her solution has \(x = 0\) and \(y = \frac { 2 } { 7 }\).
5. Calculate the optimal value of \(M\).

6 The diagram represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows two cuts, \(\alpha\) and \(\beta\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-6_818_1285_434_429}

1. Calculate the capacities of the cuts \(\alpha\) and \(\beta\).
2. Explain why the arcs \(A C\) and \(A F\) cannot both be at their lower capacities.
3. Explain why the \(\operatorname { arcs } B C , B D , D E\) and \(D T\) must all be at their lower capacities.
4. Show that a flow of 10 litres per second is impossible. Deduce the minimum and maximum feasible flows, showing your working. Vertex \(E\) becomes blocked so that no fluid can flow through it.
5. Draw a copy of the network with this vertex restriction. You are advised to make your diagram quite large. Show a flow of 9 litres per second on your diagram.