OCR D2 (Decision Mathematics 2) 2008 January

1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements. Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road. The table below shows the features of each of the six rooms available.

1. Draw a bipartite graph to show the possible pairings between the stars ( \(A , B , C , D , E\) and \(F\) ) and the rooms ( \(1,2,3,4,5\) and 6 ). Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
2. Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
3. Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room. When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.

   \multirow{2}{*}{}	Room
   	1	2	3	4	5	6
   Arnie (A)	3	6	4	1	5	2
   Brigitte ( \(B\) )	5	3	2	4	1	6
   Charles (C)	2	1	3	4	5	6
   Diana (D)	5	4	1	3	2	6
   Edward ( \(E\) )	5	6	4	3	2	1
   Faye (F)	5	6	4	1	3	2

4. Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.

2 As part of a team-building exercise the reprographics technicians (Team R) and the computer network support staff (Team C) take part in a paintballing game. The game ends when a total of 10 'hits' have been scored. Each team has to choose a player to be its captain. The number of 'hits' expected by Team R for each pair of captains is shown below.

1. Complete the last two columns of the table in the insert.
2. State the minimax value and write down the minimax route.
3. Draw the network represented by the table.

3

1. Stage	State	Action	Working	Minimax
   \multirow{3}{*}{1}	0	0	1
   	1	0	3
   	2	0	2
   \multirow{6}{*}{2}	\multirow{2}{*}{0}	0	(4,	\multirow{2}{*}{}
   		1	(2,
   	\multirow{2}{*}{1}	1	(3,	\multirow{2}{*}{}
   		2	(5,
   	\multirow{2}{*}{2}	0	(2,	\multirow{2}{*}{}
   		2	(4,
   \multirow{3}{*}{3}	\multirow{3}{*}{0}	0	(5,	\multirow{3}{*}{}
   		1	(3,
   		2	(1,

2. Minimax value = \(\_\_\_\_\) Minimax route = \(\_\_\_\_\)
3. 
   \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-10_958_1527_1539_351}

4

1. 
   \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}
2. \(\_\_\_\_\)
3. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour
4. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(v)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_671_729_1822_315}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(vi)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_735_1816_1171}
   \end{figure} Maximum flow = \(\_\_\_\_\) gallons per hour

5 Answer this question on the insert provided. The diagram shows an activity network for a project. The figures in brackets show the durations of the activities in days.
\includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-06_956_921_495_612}

1. Complete the table in the insert to show the precedences for the activities.
2. Use the boxes on the diagram in the insert to carry out a forward pass and a backward pass. Find the minimum project duration and list the critical activities. The number of people required for each activity is shown in the table below. The workers are all equally skilled at all of the activities.

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Number of workers	4	1	2	2	3	2	3	3	1	2

3. On graph paper, draw a resource histogram for the project with each activity starting at its earliest possible time.
4. Describe how the project can be completed in 21 days using just six workers.