OCR D2 (Decision Mathematics 2) 2007 January

1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked. The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.

1. Explain why the ratings could not be used as given in the table.
2. Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.

2 The table shows the activities involved in a project, their durations, precedences and the number of workers needed for each activity. The graph gives a schedule with each activity starting at its earliest possible time. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-03_473_1591_964_278}

1. Using the graph, find the minimum completion time for the project and state which activities are critical.
2. Draw a resource histogram, using graph paper, assuming that there are no delays and that every activity starts at its earliest possible time. Assume that only four workers are available but that they are equally skilled at all tasks. Assume also that once an activity has been started it continues until it is finished.
3. The critical activities are to start at their earliest possible times. List the start times for the non-critical activities for completion of the project in the minimum possible time. What is this minimum completion time?

3 Rebecca and Claire repeatedly play a zero-sum game in which they each have a choice of three strategies, \(X , Y\) and \(Z\). The table shows the number of points Rebecca scores for each pair of strategies. \begin{table}[h] \end{table}

1. If both players choose strategy \(X\), how many points will Claire score?
2. Show that row \(X\) does not dominate row \(Y\) and that column \(Y\) does not dominate column \(Z\).
3. Find the play-safe strategies. State which strategy is best for Claire if she knows that Rebecca will play safe.
4. Explain why decreasing the value ' 5 ' when both players choose strategy \(X\) cannot alter the playsafe strategies.

4 The table gives the pay-off matrix for a zero-sum game between two players, Rowan and Colin. \begin{table}[h] \end{table} Rowan makes a random choice between strategies \(P\) and \(Q\), choosing strategy \(P\) with probability \(p\) and strategy \(Q\) with probability \(1 - p\).

1. Write down and simplify an expression for the expected pay-off for Rowan when Colin chooses strategy \(X\).
2. Using graph paper, draw a graph to show Rowan's expected pay-off against \(p\) for each of Colin's choices of strategy.
3. Using your graph, find the optimal value of \(p\) for Rowan.
4. Rowan plays using the optimal value of \(p\). Explain why, in the long run, Colin cannot expect to win more than 0.25 per game.

5

1. Capacity = \(\_\_\_\_\)
2. 
   \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
3. Route: \(\_\_\_\_\) Flow \(=\) \(\_\_\_\_\)
4. Maximum flow = \(\_\_\_\_\)
   Cut: \(\mathrm { X } = \{\)
   \} \(\quad \mathrm { Y } = \{\)
5. 
   \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

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

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

7 Annie (A), Brigid (B), Carla (C) and Diane ( \(D\) ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( \(M\) ), pasting the paper ( \(P\) ), hanging and then trimming the top end of the paper ( \(H\) ) and smoothing out the air bubbles and then trimming the lower end of the paper ( \(S\) ). They will each do one of these tasks.

• Annie does not like climbing ladders but she is prepared to do tasks \(M , P\) or \(S\)
• Brigid gets into a mess with paste so she is only able to do tasks \(M\) or \(S\)
• Carla enjoys hanging the paper so she wants to do task \(H\) or task \(S\)
• Diane wants to do task \(H\)

Initially Annie chooses task \(M\), Brigid task \(S\) and Carla task \(H\).

1. Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
2. Maximin value \(=\) Route \(=\)