Questions - OCR D2 - A-Level Maths

Calculate the capacity of the cut with $\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}$.
Explain why the capacity of the cut $\alpha$, shown on the diagram, is only 21 litres per second.
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$.
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.

OCR D2 2006 January Q4

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}

What is the total cost of the four jobs if $A$ does $W , B$ does $X , C$ does $Y$ and $D$ does $Z$ ?
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.
What problem does the Hungarian algorithm solve?

OCR D2 2006 January Q6

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.


\cline { 2 - 5 }	$X$	$Y$	$Z$
$A$	2	- 3	4
\cline { 2 - 5 } Lucy's	$B$	- 3	5	1
\cline { 2 - 5 } strategyy	$C$	4	2	- 3

Show that strategy $A$ does not dominate strategy $B$ and also that strategy $B$ does not dominate strategy $A$.
Show that Maria will not choose strategy $Y$ if she plays safe.
Give a reason why Lucy might choose to play strategy $B$. Lucy decides to play strategy $A$ with probability $p _ { 1 }$, strategy $B$ with probability $p _ { 2 }$ and strategy $C$ with probability $p _ { 3 }$. She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 3 ,
\text { subject to } & m \leqslant 5 p _ { 1 } + 7 p _ { 3 } ,
& m \leqslant 8 p _ { 2 } + 5 p _ { 3 } ,
& m \leqslant 7 p _ { 1 } + 4 p _ { 2 } ,
& 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}$$ [You are not required to solve this problem.]
Explain why 3 has to be subtracted from $m$ in the objective row.
Explain how $5 p _ { 1 } + 7 p _ { 3 } , 8 p _ { 2 } + 5 p _ { 3 }$ and $7 p _ { 1 } + 4 p _ { 2 }$ were obtained.
Explain why $m$ has to be less than or equal to each of the expressions in part (v). Lucy discovers that Maria does not intend ever to choose strategy $Y$. Because of this she decides that she will never choose strategy $B$. This means that $p _ { 2 } = 0$.
Show that the expected number of points won by Lucy when Maria chooses strategy $X$ is $4 - 2 p _ { 1 }$ and find a similar expression for the number of points won by Lucy when Maria chooses strategy $Z$.
Set your two expressions from part (vii) equal to each other and solve for $p _ { 1 }$. Calculate the expected number of points won by Lucy with this value of $p _ { 1 }$ and also when $p _ { 1 } = 0$ and when $p _ { 1 } = 1$. Use these values to decide how Lucy should choose between strategies $A$ and $C$ to maximise the expected number of points that she wins.

OCR D2 2007 January Q1

1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked.

The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.

Explain why the ratings could not be used as given in the table.
Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.

OCR D2 2007 January Q2

2 The table shows the activities involved in a project, their durations, precedences and the number of workers needed for each activity. The graph gives a schedule with each activity starting at its earliest possible time.

Activity	Duration (hours)	Immediate predecessors	Number of workers
$A$	3	-	3
$B$	5	$A$	2
C	3	A	2
$D$	3	B	1
E	3	C	3
$F$	5	D, E	2
$G$	3	$B , E$	3

\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-03_473_1591_964_278}

Using the graph, find the minimum completion time for the project and state which activities are critical.
Draw a resource histogram, using graph paper, assuming that there are no delays and that every activity starts at its earliest possible time. Assume that only four workers are available but that they are equally skilled at all tasks. Assume also that once an activity has been started it continues until it is finished.
The critical activities are to start at their earliest possible times. List the start times for the non-critical activities for completion of the project in the minimum possible time. What is this minimum completion time?

OCR D2 2007 January Q3

3 Rebecca and Claire repeatedly play a zero-sum game in which they each have a choice of three strategies, $X , Y$ and $Z$. The table shows the number of points Rebecca scores for each pair of strategies. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Claire}

	$X$	$Y$	$Z$
\cline { 2 - 5 }	$X$	5	- 3	1
\cline { 2 - 5 } Rebecca	$Y$	3	2	- 2
\cline { 2 - 5 }	$Z$	- 1	1	3
\cline { 2 - 5 }
\cline { 2 - 5 }

\end{table}

If both players choose strategy $X$, how many points will Claire score?
Show that row $X$ does not dominate row $Y$ and that column $Y$ does not dominate column $Z$.
Find the play-safe strategies. State which strategy is best for Claire if she knows that Rebecca will play safe.
Explain why decreasing the value ' 5 ' when both players choose strategy $X$ cannot alter the playsafe strategies.

OCR D2 2007 January Q4

4 The table gives the pay-off matrix for a zero-sum game between two players, Rowan and Colin. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Colin}

\cline { 2 - 5 }		Strategy $X$	Strategy $Y$	Strategy $Z$
\cline { 2 - 5 } Rowan	Strategy $P$	5	- 3	- 2
\cline { 2 - 5 }	Strategy $Q$	- 4	3	1
\cline { 2 - 5 }
\cline { 2 - 5 }

\end{table} Rowan makes a random choice between strategies $P$ and $Q$, choosing strategy $P$ with probability $p$ and strategy $Q$ with probability $1 - p$.

Write down and simplify an expression for the expected pay-off for Rowan when Colin chooses strategy $X$.
Using graph paper, draw a graph to show Rowan's expected pay-off against $p$ for each of Colin's choices of strategy.
Using your graph, find the optimal value of $p$ for Rowan.
Rowan plays using the optimal value of $p$. Explain why, in the long run, Colin cannot expect to win more than 0.25 per game.

OCR D2 2007 January Q5

Capacity = $\_\_\_\_$
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
Route: $\_\_\_\_$ Flow $=$ $\_\_\_\_$
Maximum flow = $\_\_\_\_$
Cut: $\mathrm { X } = \{$
\} $\quad \mathrm { Y } = \{$
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

OCR D2 2007 January Q7

7 Annie (A), Brigid (B), Carla (C) and Diane ( $D$ ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( $M$ ), pasting the paper ( $P$ ), hanging and then trimming the top end of the paper ( $H$ ) and smoothing out the air bubbles and then trimming the lower end of the paper ( $S$ ). They will each do one of these tasks.

Annie does not like climbing ladders but she is prepared to do tasks $M , P$ or $S$
Brigid gets into a mess with paste so she is only able to do tasks $M$ or $S$
Carla enjoys hanging the paper so she wants to do task $H$ or task $S$
Diane wants to do task $H$

Initially Annie chooses task $M$, Brigid task $S$ and Carla task $H$.

Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
Maximin value $=$ Route $=$

OCR D2 2008 January Q1

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.

Room	Floor	Can be seen from road	Looks out onto garden	Has balcony
1	Ground	✓
2	Ground		✓
3	First		✓	✓
4	First	✓		✓
5	Second		✓	✓
6	Second	✓

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.
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.
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
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.

OCR D2 2008 January Q2

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.

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

OCR D2 2008 January Q3

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,

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

OCR D2 2008 January Q4

\includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}
$\_\_\_\_$
$\_\_\_\_$ = $\_\_\_\_$ gallons per hour
$\_\_\_\_$ = $\_\_\_\_$ 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

OCR D2 2009 January Q4

4 Anya $( A )$, Ben $( B )$, Connie $( C )$, Derek $( D )$ and Emma $( E )$ work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page $( P )$, restaurant review $( R )$, sports news $( S )$, theatre review $( T )$ and weather report $( W )$. Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.

Draw a bipartite graph to show the possible pairings between the writers ( $A , B , C , D$ and $E$ ) and the articles ( $P , R , S , T$ and $W$ ). On your bipartite graph, show who has been given which article by the editor.

Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.

\multirow{8}{*}{Sub-editor}	\multirow{2}{*}{}	Article
		$P$	$R$	$S$	$T$	$W$
	Jeremy ( $J$ )	56	56	51	57	58
	Kath ( $K$ )	53	52	53	54	54
	Laura ( $L$ )	57	55	52	58	60
	Mohammed ( $M$ )	59	55	53	59	57
	Natalie ( $N$ )	57	57	53	59	60
	Ollie ( $O$ )	58	56	51	56	57

The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.

Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs $\pounds 0.25$, calculate the total cost of checking the articles each week.

OCR D2 2009 January Q5

5 The local rugby club has challenged the local cricket club to a chess match to raise money for charity. Each of the top three chess players from the rugby club has played 10 chess games against each of the top three chess players from the cricket club. There were no drawn games. The table shows, for each pairing, the number of games won by the player from the rugby club minus the number of games won by the player from the cricket club. This will be called the score; the scores make a zero-sum game.

		Cricket club
\cline { 2 - 5 }\cline { 2 - 5 }		Doug	Euan	Fiona
\cline { 2 - 5 } Sanjeev	0	4	- 2
\cline { 2 - 5 } Rugby club	Tom	- 4	2	- 4
\cline { 2 - 5 }	Ursula	2	- 6	0
\cline { 2 - 5 }
\cline { 2 - 5 }

How many of the 10 games between Sanjeev and Doug did Sanjeev win? How many of the 10 games between Sanjeev and Euan did Euan win? Each club must choose one person to play. They want to choose the person who will optimise the score.
Find the play-safe choice for each club, showing your working. Explain how you know that the game is not stable.
Which person should the cricket club choose if they know that the rugby club will play-safe and which person should the rugby club choose if they know that the cricket club will play-safe?
Explain why the rugby club should not choose Tom. Which player should the cricket club not choose, and why? The rugby club chooses its player by using random numbers to choose between Sanjeev and Ursula, where the probability of choosing Sanjeev is $p$ and the probability of choosing Ursula is $1 - p$.
Write down an expression for the expected score for the rugby club for each of the two remaining choices that can be made by the cricket club. Calculate the optimal value for $p$. Doug is studying AS Mathematics. He removes the row representing Tom and then models the cricket club's problem as the following LP. $$\begin{array} { l l } \operatorname { maximise } & M = m - 4
\text { subject to } & m \leqslant 4 x \quad + 6 z
& m \leqslant 2 x + 10 y + 4 z
& x + y + z \leqslant 1
\text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
Show how Doug used the values in the table to get the constraints $m \leqslant 4 x + 6 z$ and $m \leqslant 2 x + 10 y + 4 z$. Doug uses the Simplex algorithm to solve the LP problem. His solution has $x = 0$ and $y = \frac { 1 } { 6 }$.
Calculate the optimal value of $M$.

OCR D2 2010 January Q1

1 Andy ( $A$ ), Beth ( $B$ ), Chelsey ( $C$ ), Dean ( $D$ ) and Elly ( $E$ ) have formed a quiz team. They have entered a quiz in which, as well as team questions, each of them must answer individual questions on a specialist topic. The specialist topics could be any of: food $( F )$, geography $( G )$, history $( H )$, politics ( $P$ ), science ( $S$ ) and television ( $T$ ). The team members do not know which five specialist topics will arise in the quiz. Andy wants to answer questions on either food or television; Beth wants to answer questions on geography, history or science; Chelsey wants to answer questions on geography or television; Dean wants to answer questions on politics or television; and Elly wants to answer questions on history or television.

Draw a bipartite graph to show the possible pairings between the team members and the specialist topics. In the quiz, the first specialist topic is food, and Andy is chosen to answer the questions. The second specialist topic is geography, and Beth is chosen. The next specialist topic is history, and Elly is chosen. The fourth specialist topic is science. Beth has already answered questions so Dean offers to try this round. The final specialist topic is television, and Chelsey answers these questions.
Draw a second bipartite graph to show these pairings, apart from Dean answering the science questions. Write down an alternating path starting from Dean to show that there would have been a better way to choose who answered the questions had the topics been known in advance. Write down which team member would have been chosen for each specialist topic in this case.
In a practice, although the other team members were able to choose topics that they wanted, Beth had to answer the questions on television. Write down which topic each team member answered questions on, and which topic did not arise.

OCR D2 2010 January Q2

2 Dudley has three daughters who are all planning to get married next year. The girls are named April, May and June, after the months in which they were born. Each girl wants to get married on her own birthday. Dudley has already obtained costings from four different hotels. From past experience, Dudley knows that when his family get together they are likely to end up with everyone fighting one another, so he cannot use the same hotel twice. The table shows the costs, in $\pounds 100$, for each hotel to host each daughter's wedding.

Hotel
\cline { 2 - 6 }		Palace	Regent	Sunnyside	Tall Trees
\cline { 2 - 6 }	April	30	28	32	25
\cline { 2 - 6 } Daughter	May	32	34	32	35
\cline { 2 - 6 }	June	40	40	39	38
\cline { 2 - 6 }
\cline { 2 - 6 }

Dudley wants to choose the three hotels to minimise the total cost.
Add a dummy row and then apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the hotels and Dudley's daughters. State how each table is formed and write out the final solution and its cost to Dudley.

OCR D2 2010 January Q3

3 The table lists the duration (in hours), immediate predecessors and number of workers required for each activity in a project.

Activity	Duration	Immediate predecessors	Number of workers
$A$	6	-	2
B	5	-	4
C	4	-	1
D	1	$A , B$	3
E	2	$B$	2
$F$	1	$B , C$	2
$G$	2	D, E	4
$H$	3	D, E, F	3

Draw an activity network, using activity on arc, to represent the project. You should make your diagram quite large so that there is room for working.
Carry out a forward pass and a backward pass through the activity network, showing the early and late event times clearly at the vertices of your network. State the minimum project completion time and list the critical activities.
Using graph paper, draw a resource histogram to show the number of workers required each hour. Each activity begins at its earliest possible start time. Once an activity has started it runs for its duration without a break. A delay from the supplier means that the start of activity $F$ is delayed.
By how much could the start of activity $F$ be delayed without affecting the minimum project completion time? Suppose that only six workers are available after the first four hours of the project.
Explain carefully what delay this will cause on the completion of the project. What is the maximum possible delay on the start of activity $F$, compared with its earliest possible start time in part (iii), without affecting the new minimum project completion time? Justify your answer.

OCR D2 2010 January Q4

4 The diagram represents a map of an army truck-driving course that includes several bridges. The start and a 'safe point' just after each bridge have been given (stage; state) labels. The number below each bridge shows its weight limit, in tonnes.
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-4_698_1413_438_365} An army cadet needs to drive a truck through the course from start to finish, crossing exactly three bridges.

Draw a network, using the (stage; state) labels given, to represent the routes through the course. The weights on the arcs should show the weight limits for the bridges. The cadet wants to find out the weight of the heaviest truck she can use.
Which network problem does she need to solve?
Set up a dynamic programming tabulation to solve the cadet's problem. Write down the weight of the heaviest truck she can use and write down the (stage; state) labels for the route she should take.

OCR D2 2010 January Q5

5 Robbie received a new computer game for Christmas. He has already worked through several levels of the game but is now stuck at one of the levels in which he is playing against a character called Conan. Robbie has played this particular level several times. Each time Robbie encounters Conan he can choose to be helped by a dwarf, an elf or a fairy. Conan chooses between being helped by a goblin, a hag or an imp. The players make their choices simultaneously, without knowing what the other has chosen. Robbie starts the level with ten gold coins. The table shows the number of gold coins that Conan must give Robbie in each encounter for each combination of helpers (a negative entry means that Robbie gives gold coins to Conan). If Robbie's total reaches twenty gold coins then he completes the level, but if it reaches zero the game ends. This means that each attempt can be regarded as a zero-sum game.

Conan
\cline { 2 - 5 }		Goblin	Hag	Imp
\cline { 2 - 5 }	Dwarf	- 1	- 4	2
\cline { 2 - 5 } Robbie	Elf	3	1	- 4
\cline { 2 - 5 }	Fairy	1	- 1	1
\cline { 2 - 5 }
\cline { 2 - 5 }

Find the play-safe choice for each player, showing your working. Which helper should Robbie choose if he thinks that Conan will play-safe?
How many gold coins can Robbie expect to win, with each choice of helper, if he thinks that Conan will choose randomly between his three choices (so that each has probability $\frac { 1 } { 3 }$ )? Robbie decides to choose his helper by using random numbers to choose between the elf and the fairy, where the probability of choosing the elf is $p$ and the probability of choosing the fairy is $1 - p$.
Write down an expression for the expected number of gold coins won at each encounter by Robbie for each of Conan's choices. Calculate the optimal value of $p$. Robbie's girlfriend thinks that he should have included the possibility of choosing the dwarf. She denotes the probability with which Robbie should choose the dwarf, the elf and the fairy as $x , y$ and $z$ respectively. She then models the problem of choosing between the three helpers as the following LP. $$\begin{aligned} \text { Maximise } & M = m - 4 ,
\text { subject to } & m \leqslant 3 x + 7 y + 5 z
& m \leqslant 5 y + 3 z
& m \leqslant 6 x + 5 z
& x + y + z \leqslant 1 ,
\text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{aligned}$$
Explain how the expression $3 x + 7 y + 5 z$ was formed. Robbie's girlfriend uses the Simplex algorithm to solve the LP problem. Her solution has $x = 0$ and $y = \frac { 2 } { 7 }$.
Calculate the optimal value of $M$.

OCR D2 2010 January Q6

6 The diagram represents a system of pipes through which fluid can flow from a source, $S$, to a sink, $T$. It also shows two cuts, $\alpha$ and $\beta$. The weights on the arcs show the lower and upper capacities of the pipes in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-6_818_1285_434_429}

Calculate the capacities of the cuts $\alpha$ and $\beta$.
Explain why the arcs $A C$ and $A F$ cannot both be at their lower capacities.
Explain why the $\operatorname { arcs } B C , B D , D E$ and $D T$ must all be at their lower capacities.
Show that a flow of 10 litres per second is impossible. Deduce the minimum and maximum feasible flows, showing your working. Vertex $E$ becomes blocked so that no fluid can flow through it.
Draw a copy of the network with this vertex restriction. You are advised to make your diagram quite large. Show a flow of 9 litres per second on your diagram.

OCR D2 2011 January Q1

1 Four friends, Amir (A), Bex (B), Cerys (C) and Duncan (D), are visiting a bird sanctuary. They have decided that they each will sponsor a different bird. The sanctuary is looking for sponsors for a kite $( K )$, a lark $( L )$, a moorhen $( M )$, a nightjar $( N )$, and an owl $( O )$. Amir wants to sponsor the kite, the nightjar or the owl; Bex wants to sponsor the lark, the moorhen or the owl; Cerys wants to sponsor the kite, the lark or the owl; and Duncan wants to sponsor either the lark or the owl.

Draw a bipartite graph to show which friend wants to sponsor which birds. Amir chooses to sponsor the kite and Bex chooses the lark. Cerys then chooses the owl and Duncan is left with no bird that he wants.
Write down the shortest possible alternating path starting from the nightjar, and hence write down one way in which all four friends could have chosen birds that they wanted to sponsor.
List a way in which all four friends could have chosen birds they wanted to sponsor, with the owl not being chosen.

OCR D2 2011 January Q2

2 Amir, Bex, Cerys and Duncan all have birthdays in January. To save money they have decided that they will each buy a present for just one of the others, so that each person buys one present and receives one present. Four slips of paper with their names on are put into a hat and each person chooses one of them. They do not tell the others whose name they have chosen and, fortunately, nobody chooses their own name. The table shows the cost, in $\pounds$, of the present that each person would buy for each of the others.

		To
\cline { 2 - 6 }		Amir	Bex	Cerys	Duncan
\multirow{4}{*}{From}	Amir	-	15	21	19
\cline { 2 - 6 }	Bex	20	-	16	14
\cline { 2 - 6 }	Cerys	25	12	-	16
\cline { 2 - 6 }	Duncan	24	10	18	-
\cline { 2 - 6 }
\cline { 2 - 6 }

As it happens, the names are chosen in such a way that the total cost of the presents is minimised.
Assign the cost $\pounds 25$ to each of the missing entries in the table and then apply the Hungarian algorithm, reducing rows first, to find which name each person chose.

OCR D2 2011 January Q3

3 The table lists the duration, immediate predecessors and number of workers required for each activity in a project.

Activity	Duration (hours)	Immediate predecessors	Number of workers
$A$	3	-	1
$B$	2	-	1
C	2	$A$	2
$D$	3	$A$, $B$	2
E	3	$C$	3
$F$	3	C, D	3
$G$	2	D	3
$H$	5	$E , F$	1
I	4	$F , G$	2

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.
Carry out a forward pass and a backward pass through the activity network, showing the early event times and late event times clearly at the vertices of your network. State the minimum project completion time and list the critical activities.
Draw a resource histogram to show the number of workers required each hour when each activity begins at its earliest possible start time.
Show how it is possible for the project to be completed in the minimum project completion time when only six workers are available.

OCR D2 2011 January Q4

4 Answer parts (v) and (vi) of this question on the insert provided. The diagram represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities of the pipes in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{33995efa-7ede-4e83-89d3-7b6c8be8d955-4_703_789_479_678}

Which vertex is the source and which vertex is the sink?
Cut $\alpha$ partitions the vertices into the sets $\{ A , B , C \} , \{ D , E , F , G , H , I \}$. Calculate the capacity of cut $\alpha$.
Explain why partitioning the vertices into sets $\{ A , D , G \} , \{ B , C , E , F , H , I \}$ does not give a cut.
(a) How many litres per second must flow along arc $D G$ ?
(b) Explain why the arc $A D$ must be at its upper capacity. Hence find the flow in $\operatorname { arc } B A$.
(c) Explain why at least 7 litres per second must flow along arc $B C$.
Use the diagrams in the insert to show a minimum feasible flow and a maximum feasible flow. The upper capacity of $B C$ is now increased from 8 to 18 .
(a) Use the diagram in the insert to show a flow of 19 litres per second.
(b) List the saturated arcs when 19 litres per second flows through the network. Hence, or otherwise, find a cut of capacity 19 .
Explain how your answers to part (vi) show that 19 litres per second is the maximum flow.

Questions — OCR D2 (141 questions)

Browse by module

Browse by board

OCR D2 2006 January Q3

OCR D2 2006 January Q4

OCR D2 2006 January Q6

OCR D2 2007 January Q1

OCR D2 2007 January Q2

OCR D2 2007 January Q3

OCR D2 2007 January Q4

OCR D2 2007 January Q5

OCR D2 2007 January Q7

OCR D2 2008 January Q1

OCR D2 2008 January Q2

OCR D2 2008 January Q3

OCR D2 2008 January Q4

OCR D2 2009 January Q4

OCR D2 2009 January Q5

OCR D2 2010 January Q1

OCR D2 2010 January Q2

OCR D2 2010 January Q3

OCR D2 2010 January Q4

OCR D2 2010 January Q5

OCR D2 2010 January Q6

OCR D2 2011 January Q1

OCR D2 2011 January Q2

OCR D2 2011 January Q3

OCR D2 2011 January Q4