OCR D2 (Decision Mathematics 2) 2009 June

1

1. A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( \(F\) ), his mother Gwen ( \(G\) ), his wife Helen ( \(H\) ), his son Jack ( \(J\) ) and Mr King ( \(K\) ). The table shows who likes which rolls.

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Avocado and bacon	\(( A )\)	\(\checkmark\)		\(\checkmark\)
   Beef and horseradish	\(( B )\)		\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
   Chicken and stuffing	\(( C )\)		\(\checkmark\)		\(\checkmark\)
   Duck and plum sauce	\(( D )\)			\(\checkmark\)		\(\checkmark\)
   Egg and tomato	\(( E )\)	\(\checkmark\)

   1. Draw a bipartite graph to represent this information. Put the fillings ( \(A , B , C , D\) and \(E\) ) on the left-hand side and the members of the family ( \(F , G , H , J\) and \(K\) ) on the right-hand side. Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
   2. Draw a second bipartite graph to show this incomplete matching.
   3. Construct the shortest possible alternating path from \(E\) to \(K\) and hence find a complete matching. State which roll each family member has with this complete matching.
   4. Find a different complete matching.
2. Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Family member}

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Lemon	\(L\)	8	8	8	8	1
   Mandarin	\(M\)	4	8	6	4	2
   Nectarine	\(N\)	9	9	9	7	1
   Orange	\(O\)	4	6	5	4	3
   Peach	\(P\)	6	9	7	5	0

   \end{table} The smaller entries in each column correspond to fruits that the family members liked most.
   Mr King buys one of each of these five fruits. Each family member is to be given a fruit.
   Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?

2

1. Set up a dynamic programming tabulation to find the maximum weight route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network.
   \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
2. The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.

   Activity	Duration	Immediate predecessors
   \(A\)	8	-
   \(B\)	9	-
   C	7	-
   D	5	\(A\)
   E	6	\(A\)
   \(F\)	4	\(B\)
   \(G\)	5	B
   \(H\)	6	\(B\)
   \(I\)	10	C
   \(J\)	9	\(C\)
   \(K\)	6	\(C\)
   \(L\)	7	D, F, I
   \(M\)	6	\(E , G , J\)
   \(N\)	8	\(H\), \(K\)

   Make a large copy of the network with the activities \(A\) to \(N\) labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
3. Compare the solutions to parts (i) and (ii).

3 The 'Rovers' and the 'Collies' are two teams of dog owners who compete in weekly dog shows. The top three dogs owned by members of the Rovers are Prince, Queenie and Rex. The top four dogs owned by the Collies are Woof, Xena, Yappie and Zulu. In a show the Rovers choose one of their dogs to compete against one of the dogs owned by the Collies. There are 10 points available in total. Each of the 10 points is awarded either to the dog owned by the Rovers or to the dog owned by the Collies. There are no tied points. At the end of the competition, 5 points are subtracted from the number of points won by each dog to give the score for that dog. The table shows the score for the dog owned by the Rovers for each combination of dogs.

1. Explain why calculating the score by subtracting 5 from the number of points for each dog makes this a zero-sum game.
2. If the Rovers choose Prince and the Collies choose Woof, what score does Woof get, and how many points do Prince and Woof each get in the competition?
3. Show that column \(W\) is dominated by one of the other columns, and state which column this is.
4. Delete the column for \(W\) and find the play-safe strategy for the Rovers and the play-safe strategy for the Collies on the table that remains. Queenie is ill one week, so the Rovers make a random choice between Prince and Rex, choosing Prince with probability \(p\) and Rex with probability \(1 - p\).
5. Write down and simplify an expression for the expected score for the Rovers when the Collies choose Xena. Write down and simplify the corresponding expressions for when the Collies choose Yappie and for when they choose Zulu.
6. Using graph paper, draw a graph to show the expected score for the Rovers against \(p\) for each of the choices that the Collies can make. Using your graph, find the optimal value of \(p\) for the Rovers. If Queenie had not been ill, the Rovers would have made a random choice between Prince, Queenie and Rex, choosing Prince with probability \(p _ { 1 }\), Queenie with probability \(p _ { 2 }\) and Rex with probability \(p _ { 3 }\). The problem of choosing the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) can be formulated as the following linear programming problem: $$\begin{array} { l l } \operatorname { maximise } & M = m - 4
   \text { subject to } & m \leqslant 6 p _ { 1 } + 5 p _ { 2 } ,
   & m \leqslant 3 p _ { 1 } + p _ { 2 } + 5 p _ { 3 } ,
   & m \leqslant 7 p _ { 1 } + 3 p _ { 2 } + 4 p _ { 3 } ,
   & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1
   \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$
7. Explain how the expressions \(6 p _ { 1 } + 5 p _ { 2 } , 3 p _ { 1 } + p _ { 2 } + 5 p _ { 3 }\) and \(7 p _ { 1 } + 3 p _ { 2 } + 4 p _ { 3 }\) were obtained. Also explain how the linear programming formulation tells you that \(M\) is a maximin solution. The Simplex algorithm is used to find the optimal values of the probabilities. The optimal value of \(p _ { 1 }\) is \(\frac { 5 } { 8 }\) and the optimal value of \(p _ { 2 }\) is 0 .
8. Calculate the optimal value of \(p _ { 3 }\) and the corresponding value of \(M\).

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute.
\includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-6_599_1580_402_280}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the arcs \(A C\) and \(A D\) cannot both be full to capacity and why the arcs \(D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.