OCR D2 (Decision Mathematics 2) 2016 June

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h] \end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. 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 (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
3. Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at \(S\) to a sink at \(T\). Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty. Fig. 3 shows a flow of 5 litres per second from \(S\) to \(T\). Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down the capacity of \(\operatorname { arc } F T\) and of \(\operatorname { arc } D T\). Find the value of the cut that separates the vertices \(S , A , B , C , D , E , F\) from the sink at \(T\).
2. (a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along \(S - C - B - F - T\).
   (b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time.
3. Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.

3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task. The theatre company wants to employ the three technicians for whom the total cost is least.
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.

1. Make the necessary modification to the table. Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]
2. Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company. Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.
3. Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly \(\pounds 1\) less than your answer from part (ii).

4 Rowan and Colin are playing a game of 'scissors-paper-rock'. In each round of this game, each player chooses one of scissors ( \(\$$ ), paper ( \)\square\( ) or rock ( \)\bullet$ ). The players reveal their choices simultaneously, using coded hand signals. Rowan and Colin will play a large number of rounds. At the end of the game the player with the greater total score is the winner. The rules of the game are that scissors wins over paper, paper wins over rock and rock wins over scissors. In this version of the game, if a player chooses scissors they will score \(+ 1,0\) or - 1 points, according to whether they win, draw or lose, but if they choose paper or rock they will score \(+ 2,0\) or - 2 points. This gives the following pay-off tables.
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_476_773_667_239}
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_478_780_667_1071}

1. Use an example to show that this is not a zero-sum game.
2. Write down the minimum number of points that Rowan can win using each strategy. Hence find the strategy that maximises the minimum number of points that Rowan can win. Rowan decides to use random numbers to choose between the three strategies, choosing scissors with probability \(p\), paper with probability \(q\) and rock with probability \(( 1 - p - q )\).
3. Find and simplify, in terms of \(p\) and \(q\), expressions for the expected number of points won by Rowan for each of Colin's possible choices. Rowan wants his expected winnings to be the same for all three of Colin's possible choices.
4. Calculate the probability with which Rowan should play each strategy.

5 The network below represents a project using activity on arc. The durations of the activities are not yet shown.
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-6_597_1257_340_386}

1. If \(C\) were to turn out to be a critical activity, which two other activities would be forced to be critical?
2. Complete the table, in the Answer Book, to show the immediate predecessor(s) for each activity. In fact, \(C\) is not a critical activity. Table 1 lists the activities and their durations, in minutes. \begin{table}[h]

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Duration	10	15	10	5	15	5	10	15	5	15

   \captionsetup{labelformat=empty} \caption{Table 1}
   \end{table}
3. 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 the network. State the minimum project completion time and list the critical activities. Each activity requires one person.
4. Draw a schedule to show how three people can complete the project in the minimum time, with each activity starting at its earliest possible time. Each box in the Answer Book represents 5 minutes. For each person, write the letter of the activity they are doing in each box, or leave the box blank if the person is resting for those 5 minutes.
5. Show how two people can complete the project in the minimum time. It is required to reduce the project completion time by 10 minutes. Table 2 lists those activities for which the duration could be reduced by 5 minutes, and the cost of making each reduction. \begin{table}[h]

   Activity	\(A\)	\(B\)	\(C\)	\(E\)	\(G\)	\(H\)	\(J\)
   Cost \(( \pounds )\)	200	400	100	600	100	500	500
   New duration	5	10	5	10	5	10	10

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
6. Explain why the cost of saving 5 minutes by reducing activity \(A\) is more than \(\pounds 200\). Find the cheapest way to complete the project in a time that is 10 minutes less than the original minimum project completion time. State which activities are reduced and the total cost of doing this.

6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.

1. Complete the working and suboptimal maximum columns on the copy of the table in your Answer Book. Write down the weight of the maximum path and the corresponding route. Give your route using (stage; state) variables. Ken has entered a cake-making competition. The actions in the dynamic programming tabulation above represent the different types of cake that Ken could make. Each competitor must make one cake in each stage of the competition. The rules of the competition mean that, for each competitor, the actions representing their four cakes must form a route from \(( 0 ; 0 )\) to \(( 4 ; 0 )\). The weights in the tabulation are the number of points that Ken can expect to get by making each of the cakes. Each cake is also judged for how well it has been decorated. The number of points that Ken expects to get for decorating each cake is shown below. Ken is not very good at decorating the cakes. He expects to get 0 points for decorating for the cakes that are not listed below.

   Cake	(0; 0) to (1; 0)	(1; 0) to (2; 1)	(1; 1) to (2; 0)	(2; 0) to (3; 0)	(2; 0) to (3; 1)	(2; 1) to (3; 0)	(2; 1) to (3; 1)
   Decorating points	1	1	2	1	1	1	1

2. Calculate the number of decorating points that Ken can expect if he makes the cakes given in the solution to part (i). When Ken meets the other competitors he realises that he is not good enough to win the competition, so he decides instead to try to win the judges' special award. For each cake, the absolute difference between the score for cake-making and the score for decorating is calculated. The award is given to the person whose biggest absolute difference is least. (Note: to find the absolute difference, calculate larger number-smaller number, or 0 if they are the same.)
3. Draw the graph that the dynamic programming tabulation represents. Label the vertices using (stage; state) labels with \(( 0 ; 0 )\) at the left hand side and \(( 4 ; 0 )\) at the right hand side. Make the graph into a network by weighting the arcs with the absolute differences.
4. Use a dynamic programming tabulation to find the minimax route for the absolute differences.