OCR D2 (Decision Mathematics 2) 2014 June

1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have. \begin{figure}[h] \end{figure} Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
3. By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.

2 The network models a cooling system in a factory. Coolant starts at \(A , B\) and \(C\) and flows through the system. The arcs model components of the cooling system and the weights show the maximum amount of coolant that can flow through each component of the system (measured in litres per second). The arrows show the direction of flow.
\includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-3_611_832_539_605}

1. Add a supersource, \(S\), and a supersink, \(T\), to the copy of the network in your answer book. Connect \(S\) and \(T\) to the network using appropriately weighted arcs.
2. (a) Find the capacity of the cut that separates \(A , B , C\) and \(E\) from \(D , F , G\) and \(H\).
   (b) Find the capacity of the cut that separates \(A , B , C , D , E\) and \(F\) from \(G\) and \(H\).
   (c) What can you deduce from this value about the maximum flow through the system?
3. Find the maximum possible flow through the system and prove that this is the maximum.
4. Describe what effect increasing the capacity of \(C E\) would have on the maximum flow.

3 Each of five jobs is to be allocated to one of five workers, and each worker will have one job. The table shows the cost, in \(\pounds\), of using each worker on each job. It is required to find the allocation for which the total cost is minimised. Worker \begin{table}[h] \end{table}

1. Construct a reduced cost matrix by first reducing rows and then reducing columns. Cross through the 0's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [Try to ensure that the values in your table can still be read.]
2. Augment your reduced cost matrix and hence find a minimum cost allocation. Write a list showing which job should be given to which worker for your minimum cost allocation, and calculate the total cost in this case. Gill decides that she does not like the job she has been allocated and increases her cost for this job by \(\pounds 100\). New minimum cost allocations can be found, each allocation costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii).
3. Use the grid in your answer book to show the positions of the 0 's and 1 's in the augmented reduced cost matrix from part (ii). Hence find three allocations, each costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii) and with Gill having a different job to the one allocated in part (ii). [5]

4 Ross and Collwen are playing a game in which each secretly chooses a magic spell. They then reveal their choices, and work out their scores using the tables below. Ross and Collwen are both trying to get as large a score as possible.

1. Explain how this can be rewritten as the following zero-sum game.

   		Collwen's choice
   		Fire	Ice	Gale
   \cline { 2 - 5 }	Fire	- 3	3	- 2
   \cline { 2 - 5 } Ross's choice	Ice	2	- 2	0
   \cline { 2 - 5 }	Gale	1	- 3	- 1
   \cline { 2 - 5 }

2. If Ross chooses Ice what is Collwen's best choice?
3. Find the play-safe strategy for Ross and the play-safe strategy for Collwen, showing your working. Explain how you know that the game is unstable.
4. Show that none of Collwen's strategies dominates any other.
5. Explain why Ross would never choose Gale, hence reduce the game to a \(2 \times 3\) zero-sum game, showing the pay-offs for Ross. Suppose that Ross uses random numbers to choose between Fire and Ice, choosing Fire with probability \(p\) and Ice with probability \(1 - p\).
6. Use a graphical method to find the optimal value of \(p\) for Ross.

5 Following a promotion at work, Khalid needs to clear out his office to move to a different building. The activities involved, their durations (in hours) and immediate predecessors are listed in the table below. You may assume that some of Khalid's friends will help him and that once an activity is started it will be continued until it is completed.

1. Represent this project using an activity network.
2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and late event time at each vertex of your network. State the minimum project completion time and list the critical activities.
3. How much longer could be spent on sorting the items from the desk and throwing out the rubbish (activity \(C\) ) without it affecting the overall completion time? Khalid says that he needs to do activities \(A , C , E\) and \(G\) himself. These activities take a total of 8.5 hours.
4. By considering what happens if Khalid does \(A\) first, and what happens if he does \(C\) first, show that the project will take more than 8.5 hours.
5. Draw up a schedule to show how just two people, Khalid and his friend Mia, can complete the project in 9 hours. Khalid must do \(A , C , E\) and \(G\) and activities cannot be shared between Khalid and Mia. [2]

6 The table below shows an incomplete dynamic programming tabulation to solve a maximin problem. Do not write your answer on this copy of the table.

1. Complete the working and suboptimal maximin columns on the copy of the table in your answer book.
2. Use your answer to part (i) to write down the maximin value and the corresponding route. Give your route using (stage; state) variables.
3. Draw the network that is represented in the table. The network represents a system of pipes and the arc weights show the capacities of the pipes, in litres per second.
4. What does the answer to part (ii) represent in this network? The weights of the arcs in the maximin route are each reduced by the maximin value and then a maximin is found for the resulting network. This is done until the maximin value is 0 . At this point the network is as shown below.
   \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-8_552_1474_438_274}
5. (a) Describe how this solves the maximum flow problem on the original network.
   (b) Draw this maximum flow and draw a cut with value equal to the value of the flow. \section*{END OF QUESTION PAPER} \section*{\(\mathrm { OCR } ^ { \text {勾 } }\)}