OCR D2 (Decision Mathematics 2) 2007 June

1 D aniel needs to clean four houses but only has one day in which to do it. He estimates that each house will take one day and so he has asked three professional cleaning companies to give him a quotation for cleaning each house. He intends to hire the three companies to clean one house each and he will clean the fourth house himself. The table below shows the quotations that Daniel was given by the three companies.

1. Copy the table and add a dummy row to represent D aniel.
2. A pply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working and say how each matrix was formed.
3. Which house should Daniel ask each company to clean? Find the total cost of hiring the three companies.

2 The table gives the pay-off matrix for a zero-sum game between two players, A my and Bea. The values in the table show the pay-offs for A my. A my makes a random choice between strategies \(\mathbf { P }\) and \(Q\), choosing strategy \(P\) with probability \(p\) and strategy Q with probability \(1 - \mathrm { p }\).

1. Write down and simplify an expression for the expected pay-off for Amy when Bea chooses strategy X . Write down similar expressions for the cases when B ea chooses strategy Y and when she chooses strategy \(Z\).
2. Using graph paper, draw a graph to show A my's expected pay-off against p for each of Bea's choices of strategy. Using your graph, find the optimal value of pfor A my. A my and Bea play the game many times. A my chooses randomly between her strategies using the optimal value for p.
3. Showing your working, calculate A my's minimum expected pay-off per game. W hy might A my gain more points than this, on average?
4. W hat is B ea's minimum expected loss per game? How should B ea play to minimise her expected loss?

3 The table shows the activities involved in a project, their durations and precedences, and the number of workers needed for each activity.

1. On the insert, complete the last two columns of the table.
2. State the minimax value and write down the minimax route.
3. Complete the diagram on the insert to show the network that is represented by the table.

4 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a minimax problem.

1. On the insert, complete the last two columns of the table.
2. State the minimax value and write down the minimax route.
3. Complete the diagram on the insert to show the network that is represented by the table.

5 Answer this question on the insert provided. The network represents a system of pipes through which fluid can flow from a source, S , to a sink, T .
\includegraphics[max width=\textwidth, alt={}, center]{09d4aacd-026b-4d81-a826-3d3f29f9c105-5_1310_1301_447_424} The arrows are labelled to show excess capacities and potential backflows (how much more and how much less could flow in each pipe). The excess capacities and potential backflows are measured in litres per second. Currently the flow is 6 litres per second, all flowing along a single route through the system.

1. Write down the route of the 6 litres per second that is flowing from \(S\) to \(T\).
2. What is the capacity of the pipe AG and in which direction can fluid flow along this pipe?
3. Calculate the capacity of the \(\operatorname { cut } \mathrm { X } = \{ \mathrm { S } , \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \} , \mathrm { Y } = \{ \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { I } , \mathrm { T } \}\).
4. Describe how a further 7 litres per second can flow from S to T and update the labels on the arrows to show your flow. Explain how you know that this is the maximum flow. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}