OCR D2 (Decision Mathematics 2) 2011 June

1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals. The table shows which family members like each of the cereals in the pack.

1. Draw a bipartite graph to represent this information. Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from 6 to \(A\) and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
4. Adam decides that he wants cornflakes. Construct an alternating path starting at \(A\), based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.

2 Granny is on holiday in Amsterdam and has bought some postcards. She wants to send one card to each member of her family. She has given each card a score to show how suitable it is for each family member. The higher the score the more suitable the card is. \begin{table}[h] \end{table} Granny adds two dummy columns, \(G\) and \(H\), both with score 0 for each postcard. She then modifies the resulting table so that she can use the Hungarian algorithm to find the matching for which the total score is maximised.

1. Explain why the dummy columns were needed, why they should not have positive scores and how the resulting table was modified.
2. Show that, after reducing rows and columns, Granny gets this reduced cost matrix.

   	A	B	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
   \(P\)	4	2	4	0	6	2	2	2
   \(Q\)	2	0	2	0	2	1	1	1
   \(R\)	2	1	2	2	2	0	4	4
   \(S\)	2	0	2	2	6	2	2	2
   \(T\)	4	5	4	1	5	0	1	1
   \(U\)	1	0	0	0	1	1	0	0
   \(V\)	0	2	0	1	0	2	3	3
   \(W\)	2	0	1	2	1	1	2	2

3. Complete the application of the Hungarian algorithm, showing your working clearly. Write down which family member is sent each postcard, and which postcards are not used, to maximise the score.

3 Basil runs a luxury hotel. He advertises summer breaks at the hotel in several different magazines. Last summer he won the opportunity to place a full-page colour advertisement in one of four magazines for the price of the usual smaller advertisement. The table shows the expected additional weekly income, in \(\pounds\), for each of the magazines for each possible type of weather. Basil wanted to maximise the additional income.

1. Explain carefully why no magazine choice can be rejected using a dominance argument.
2. Treating the choice of strategies as being a zero-sum game, find Basil's play-safe strategy and show that the game is unstable.
3. Calculate the expected additional weekly income for each magazine choice if the weather is rainy with probability 0.4 and sunny with probability 0.6 . Suppose that the weather is rainy with probability \(p\) and sunny with probability \(1 - p\).
4. Which magazine should Basil choose if the weather is certain to be sunny ( \(p = 0\) ), and which should he choose if the weather is certain to be rainy ( \(p = 1\) )?
5. Graph the expected additional weekly income against \(p\). Hence advise Basil on which magazine he should choose for the different possible ranges of values of \(p\).

4 Jamil is building a summerhouse in his garden. The activities involved, the duration, immediate predecessors and number of workers required for each activity are listed in the table.

1. Represent the project by an activity network, using activity on arc. 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 event times and late event times at the vertices of your network. State the minimum project completion time and list the critical activities.
3. Draw a resource histogram to show the number of workers required each hour when each activity begins at its earliest possible start time.
4. Describe how it is possible for the project to be completed in the minimum project completion time when only four workers are available.
5. Describe how two workers can complete the project as quickly as possible. Find the minimum time in which two workers can complete the project.

5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from \(S\) to \(T\). The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem.
\includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , G \}\) from \(\{ B , D , E , F , T \}\).
2. Explain why neither arc \(S A\) nor arc \(E T\) can be full to capacity. Also explain why the arcs \(A C\) and \(B C\) cannot simultaneously be full to capacity.
3. Show a flow of 3300 people per hour, and find a cut of capacity 3300 . The direction of flow in \(B C\) is reversed.
4. Show the excess capacities and potential backflows when there is no flow.
5. Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along \(S B E T\).
6. Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from \(S\) to \(T\).
7. Show the maximum flow and explain how you know that this flow is maximal.

6 Set up a dynamic programming tabulation to find the maximin route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network.
\includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-7_883_1323_390_411}