OCR D2 (Decision Mathematics 2) 2006 January

1 Answer this question on the insert provided. Mrs Price has bought six T shirts for her children. Each child is to have two shirts.
Amanda would like the green shirt, the pink shirt or the red shirt.
Ben would like the green shirt, the turquoise shirt, the white shirt or the yellow shirt.
Carrie would like the pink shirt, the white shirt or the yellow shirt.

1. On the first diagram in the insert, draw a bipartite graph to show which child would like which shirt. The children are represented as \(A 1 , A 2 , B 1 , B 2 , C 1\) and \(C 2\) and the shirts as \(G , P , R , T , W\) and \(Y\). Initially, Mrs Price puts aside the green shirt and the pink shirt for Amanda, the turquoise shirt and the white shirt for Ben and the yellow shirt for Carrie.
2. Show this incomplete matching on the second diagram in the insert.
3. Write down an alternating path consisting of three arcs to enable the matching to be improved. Use your alternating path to match the children to the shirts.
4. Amanda decides that she does not like the green shirt after all. Which shirts should each child have now?

2 Answer this question on the insert provided. The diagram shows a directed network of paths with vertices labelled with (stage; state) labels. The weights on the arcs represent distances in km . The shortest route from \(( 3 ; 0 )\) to \(( 0 ; 0 )\) is required. Complete the dynamic programming tabulation on the insert, working backwards from stage 1 , to find the shortest route through the network. Give the length of this shortest route. \begin{figure}[h] \end{figure}

3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

4 Four workers, \(A , B , C\) and \(D\), are to be allocated, one to each of the four jobs, \(W , X , Y\) and \(Z\). The table shows how much each worker would charge for each job.
\includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}

1. What is the total cost of the four jobs if \(A\) does \(W , B\) does \(X , C\) does \(Y\) and \(D\) does \(Z\) ?
2. Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.
3. What problem does the Hungarian algorithm solve?

5 Answer this question on the insert provided. The diagram shows an activity network for a project. The table lists the durations of the activities (in days).
\includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-4_652_867_429_393}

1. Explain why each of the dummy activities is needed.
2. Complete the blank column of the table in the insert to show the immediate predecessors for each activity.
3. Carry out a forward pass to find the early start times for the events. Record these at the eight vertices on the copy of the network on the insert. Also calculate the late start times for the events and record these at the vertices. Find the minimum completion time for the project and list the critical activities.
4. By how much would the duration of activity \(C\) need to increase for \(C\) to become a critical activity? Assume that each activity requires one worker and that each worker is able to do any of the activities. The activities may not be split. The duration of \(C\) is 4 days.
5. Draw a resource histogram, assuming that each activity starts at its earliest possible time. How many workers are needed with this schedule?
6. Describe how, by delaying the start of activity \(E\) (and other activities, to be determined), the project can be completed in the minimum time by just three workers.

6 Lucy and Maria repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Lucy, who is playing rows, for each combination of strategies.