Questions - OCR D2 - A-Level Maths

	1	2	3
1	15	25	30
2	20	50	15
3	30	35	15

Thousands of soldiers remaining in $C$ 's army
$C$ 's choice
$R$ 's choice

	1	2	3
1	20	35	10
2	15	50	20
3	10	25	40

Construct a table to show the number of thousands of soldiers remaining in $R$ 's army minus the number of thousands of soldiers remaining in $C$ 's army (the excess for $R$ 's army) for each combination of strategies. The commander whose army has the greatest positive excess of soldiers remaining at the end of the game will be declared the winner.
Explain the meaning of the value in the top left cell of your table from part (i) (where each commander chooses strategy 1). Hence explain why this table may be regarded as representing a zero-sum game.
Find the play-safe strategy for $R$ and the play-safe strategy for $C$. If $C$ knows that $R$ will choose his play-safe strategy, which strategy should $C$ choose? One of the strategies is redundant for one of the commanders, because of dominance.
Draw a table for the reduced game, once the redundant strategy has been removed. Label the rows and columns to show how many divisions have been sent North. A mixed strategy is to be employed on the resulting reduced game. This leads to the following LP problem:
Maximise $\quad M = m - 25$
Subject to $\quad m \leqslant 15 x + 25 y + 35 z$
$m \leqslant 45 x + 20 y$
$x + y + z \leqslant 1$
and
Interpret what $x , y$ and $z$ represent and show how $m \leqslant 15 x + 25 y + 35 z$ was formed. A computer runs the Simplex algorithm to solve this problem. It gives $x = 0.5385 , y = 0$ and $z = 0.4615$.
Describe how this solution should be interpreted, in terms of how General Rose chooses where to send his troops. Calculate the optimal value for $M$ and explain its meaning. Elizabeth does not have access to a computer. She says that at the solution to the LP problem $15 x + 25 y + 35 z$ must equal $45 x + 20 y$ and $x + y + z$ must equal 1 . This simplifies to give $y + 7 z = 6 x$ and $x + y + z = 1$.
Explain why there can be no valid solution of $y + 7 z = 6 x$ and $x + y + z = 1$ with $x = 0$. Elizabeth tries $z = 0$ and gets the solution $x = \frac { 1 } { 7 }$ and $y = \frac { 6 } { 7 }$.
Explain why this is not a solution to the LP problem.

OCR D2 2016 June Q1

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_497_1246_488_415} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h]

Sailing ships	(1)			January/February
Seascape	(2)	• ◯	(MA)	March/April
Snow scene	(3)	\includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_54_381_1451_716}	(MJ)	May/June
Street scene		\includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_59_38_1536_712}	(JA)	July/August
Sunset	(5)		(SO)	September/October
Swans	(6)		(ND)	November/December

\captionsetup{labelformat=empty} \caption{Fig. 2}

\end{table}

Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

OCR D2 2016 June Q2

2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at $S$ to a sink at $T$. Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty. Fig. 3 shows a flow of 5 litres per second from $S$ to $T$. Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc). \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-3_524_876_717_141} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-3_524_878_717_1046} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure}

Write down the capacity of $\operatorname { arc } F T$ and of $\operatorname { arc } D T$. Find the value of the cut that separates the vertices $S , A , B , C , D , E , F$ from the sink at $T$.
(a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along $S - C - B - F - T$.
(b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time.
Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.

OCR D2 2016 June Q3

3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task.

\multirow{2}{*}{}		Task
		Lighting	Sound	Trapeze
\multirow{4}{*}{Technician}	Amir	86	88	90
	Bex	92	94	95
	Caz	88	92	94
	Dee	98	100	98

The theatre company wants to employ the three technicians for whom the total cost is least.
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.

Make the necessary modification to the table. Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]
Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company. Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.
Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly $\pounds 1$ less than your answer from part (ii).

OCR D2 2016 June Q4

4 Rowan and Colin are playing a game of 'scissors-paper-rock'. In each round of this game, each player chooses one of scissors ( $\$$ ), paper ( $\square$ ) or rock ( $\bullet$ ). The players reveal their choices simultaneously, using coded hand signals. Rowan and Colin will play a large number of rounds. At the end of the game the player with the greater total score is the winner. The rules of the game are that scissors wins over paper, paper wins over rock and rock wins over scissors. In this version of the game, if a player chooses scissors they will score $+ 1,0$ or - 1 points, according to whether they win, draw or lose, but if they choose paper or rock they will score $+ 2,0$ or - 2 points. This gives the following pay-off tables.
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_476_773_667_239}
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_478_780_667_1071}

Use an example to show that this is not a zero-sum game.
Write down the minimum number of points that Rowan can win using each strategy. Hence find the strategy that maximises the minimum number of points that Rowan can win. Rowan decides to use random numbers to choose between the three strategies, choosing scissors with probability $p$, paper with probability $q$ and rock with probability $( 1 - p - q )$.
Find and simplify, in terms of $p$ and $q$, expressions for the expected number of points won by Rowan for each of Colin's possible choices. Rowan wants his expected winnings to be the same for all three of Colin's possible choices.
Calculate the probability with which Rowan should play each strategy.

OCR D2 2016 June Q5

5 The network below represents a project using activity on arc. The durations of the activities are not yet shown.
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-6_597_1257_340_386}

If $C$ were to turn out to be a critical activity, which two other activities would be forced to be critical?
Complete the table, in the Answer Book, to show the immediate predecessor(s) for each activity. In fact, $C$ is not a critical activity. Table 1 lists the activities and their durations, in minutes. \begin{table}[h]
Activity $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$ $I$ $J$
Duration 10 15 10 5 15 5 10 15 5 15
\captionsetup{labelformat=empty} \caption{Table 1}
\end{table}
Carry out a forward pass and a backward pass through the activity network, showing the early event time and late event time at each vertex of the network. State the minimum project completion time and list the critical activities. Each activity requires one person.
Draw a schedule to show how three people can complete the project in the minimum time, with each activity starting at its earliest possible time. Each box in the Answer Book represents 5 minutes. For each person, write the letter of the activity they are doing in each box, or leave the box blank if the person is resting for those 5 minutes.
Show how two people can complete the project in the minimum time. It is required to reduce the project completion time by 10 minutes. Table 2 lists those activities for which the duration could be reduced by 5 minutes, and the cost of making each reduction. \begin{table}[h]
Activity $A$ $B$ $C$ $E$ $G$ $H$ $J$
Cost $( \pounds )$ 200 400 100 600 100 500 500
New duration 5 10 5 10 5 10 10
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table}
Explain why the cost of saving 5 minutes by reducing activity $A$ is more than $\pounds 200$. Find the cheapest way to complete the project in a time that is 10 minutes less than the original minimum project completion time. State which activities are reduced and the total cost of doing this.

OCR D2 2016 June Q6

6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.

Stage	State	Action	Working	Suboptimal maximum
\multirow[t]{2}{*}{3}	0	0	1	1
	1	0	2	2
\multirow[t]{4}{*}{2}	\multirow[t]{2}{*}{0}	0	$1 + 1 = 2$	\multirow[b]{2}{*}{3}
		1	$1 + 2 = 3$
	\multirow[t]{2}{*}{1}	0	$3 + 1 = 4$	\multirow[t]{2}{*}{4}
		1	$1 + 2 = 3$
\multirow[t]{4}{*}{1}	\multirow[t]{2}{*}{0}	0	$1 + =$	\multirow{4}{*}{}
		1	$0 + =$
	\multirow[t]{2}{*}{1}	0	$0 + =$
		1	$1 + =$
\multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	$2 + =$	\multirow{2}{*}{}
		1	$2 + =$

Complete the working and suboptimal maximum columns on the copy of the table in your Answer Book. Write down the weight of the maximum path and the corresponding route. Give your route using (stage; state) variables. Ken has entered a cake-making competition. The actions in the dynamic programming tabulation above represent the different types of cake that Ken could make. Each competitor must make one cake in each stage of the competition. The rules of the competition mean that, for each competitor, the actions representing their four cakes must form a route from $( 0 ; 0 )$ to $( 4 ; 0 )$. The weights in the tabulation are the number of points that Ken can expect to get by making each of the cakes. Each cake is also judged for how well it has been decorated. The number of points that Ken expects to get for decorating each cake is shown below. Ken is not very good at decorating the cakes. He expects to get 0 points for decorating for the cakes that are not listed below.
Cake (0; 0) to (1; 0) (1; 0) to (2; 1) (1; 1) to (2; 0) (2; 0) to (3; 0) (2; 0) to (3; 1) (2; 1) to (3; 0) (2; 1) to (3; 1)
Decorating points 1 1 2 1 1 1 1
Calculate the number of decorating points that Ken can expect if he makes the cakes given in the solution to part (i). When Ken meets the other competitors he realises that he is not good enough to win the competition, so he decides instead to try to win the judges' special award. For each cake, the absolute difference between the score for cake-making and the score for decorating is calculated. The award is given to the person whose biggest absolute difference is least. (Note: to find the absolute difference, calculate larger number-smaller number, or 0 if they are the same.)
Draw the graph that the dynamic programming tabulation represents. Label the vertices using (stage; state) labels with $( 0 ; 0 )$ at the left hand side and $( 4 ; 0 )$ at the right hand side. Make the graph into a network by weighting the arcs with the absolute differences.
Use a dynamic programming tabulation to find the minimax route for the absolute differences.

OCR D2 Specimen Q1

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

Arthur wants to use lavender, orange or tangerine.
Bridget wants to use lavender, mauve or pink.
Carlos wants to use pink or scarlet.
Davinder wants to use mauve or pink.
Eric wants to use lavender or orange.
Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

Draw a bipartite graph on the insert, showing which neighbours ( $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

OCR D2 Specimen Q2

2 A company has organised four regional training sessions to take place at the same time in four different cities. The company has to choose four of its five trainers, one to lead each session. The cost ( $\pounds 1000$ 's) of using each trainer in each city is given in the table.

\multirow{7}{*}{Trainer}	\multirow{2}{*}{}	City
		London	Glasgow	Manchester	Swansea
	Adam	4	3	2	4
	Betty	3	5	4	2
	Clive	3	6	3	3
	Dave	2	6	4	3
	Eleanor	2	5	3	4

Convert this into a square matrix and then apply the Hungarian algorithm, reducing rows first, to allocate the trainers to the cities at minimum cost.
Betty discovers that she is not available on the date set for the training. Find the new minimum cost allocation of trainers to cities.

OCR D2 Specimen Q3

3 [Answer this question on the insert provided.]
A flying doctor travels between islands using small planes. Each flight has a weight limit that restricts how much he can carry. A plague has broken out on Farr Island and the doctor needs to take several crates of medical supplies to the island. The crates must be carried on the same planes as the doctor. The diagram shows a network with (stage; state) variables at the vertices representing the islands, arcs representing flight routes that can be used, and weights on the arcs representing the number of crates that the doctor can carry on each flight. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-03_506_1084_671_477} \captionsetup{labelformat=empty} \caption{Stage 0}

\end{figure} Stage 1 Stage 2

It is required to find the route from ( $0 ; 0$ ) to ( $3 ; 0$ ) for which the minimum number of crates that can be carried on any stage is a maximum (the maximin route). The insert gives a dynamic programming tabulation showing stages, states and actions, together with columns for working out the route minimum at each stage and for indicating the current maximin. Complete the table on the insert sheet and hence find the maximin route and the maximum number of crates that can be carried.
It is later found that the number of crates that can be carried on the route from ( $2 ; 0$ ) to ( $3 ; 0$ ) has been recorded incorrectly and should be 15 instead of 5 . What is the maximin route now, and how many crates can be carried?

OCR D2 Specimen Q4

4 Henry is planning a surprise party for Lucinda. He has left the arrangements until the last moment, so he will hold the party at their home. The table below lists the activities involved, the expected durations, the immediate predecessors and the number of people needed for each activity. Henry has some friends who will help him, so more than one activity can be done at a time.

Activity	Duration (hours)	Preceded by	Number of people
A: Telephone other friends	2	-	3
$B$ : Buy food	1	A	2
C: Prepare food	4	B	5
D: Make decorations	3	A	3
$E$ : Put up decorations	1	D	3
$F$ : Guests arrive	1	C, E	1

Draw an activity network to represent these activities and the precedences. Carry out forward and reverse passes to determine the minimum completion time and the critical activities. If Lucinda is expected home at 7.00 p.m., what is the latest time that Henry or his friends can begin telephoning the other friends?
Draw a resource histogram showing time on the horizontal axis and number of people needed on the vertical axis, assuming that each activity starts at its earliest possible start time. What is the maximum number of people needed at any one time?
Now suppose that Henry’s friends can start buying the food and making the decorations as soon as the telephoning begins. Construct a timetable, with a column for 'time' and a column for each person, showing who should do which activity when, in order than the party can be organised in the minimum time using a total of only six people (Henry and five friends). When should the telephoning begin with this schedule?

OCR D2 Specimen Q5

5 [Answer this question on the insert provided.]
Fig. 1 shows a directed flow network. The weight on each arc shows the capacity in litres per second. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_620_1082_424_502} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Find the capacity of the cut $\mathscr { C }$ shown.
Deduce that there is no possible flow from $S$ to $T$ in which both arcs leading into $T$ are saturated. Explain your reasoning clearly. Fig. 2 shows a possible flow of 160 litres per second through the network. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_499_1084_1471_500} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure}
On the diagram in the insert, show the excess capacities and potential backflows for this flow.
Use the labelling procedure to augment the flow as much as possible. Show your working clearly, but do not obscure your answer to part (iii).
Show the final flow that results from part (iv). Explain clearly how you know that this flow is maximal.

OCR D2 Specimen Q6

6 Rose is playing a game against a computer. Rose aims a laser beam along a row, $A , B$ or $C$, and, at the same time, the computer aims a laser beam down a column, $X , Y$ or $Z$. The number of points won by Rose is determined by where the two laser beams cross. These values are given in the table. The computer loses whatever Rose wins.

	Computer
\cline { 2 - 5 }		$X$	$Y$	$Z$
\cline { 2 - 5 } Rose	$A$	1	3	4
$B$	4	3	2
$C$	3	2	1
\cline { 2 - 5 }

Find Rose's play-safe strategy and show that the computer's play-safe strategy is $Y$. How do you know that the game does not have a stable solution?
Explain why Rose should never choose row $C$ and hence reduce the game to a $2 \times 3$ pay-off matrix.
Rose intends to play the game a large number of times. She decides to use a standard six-sided die to choose between row $A$ and row $B$, so that row $A$ is chosen with probability $a$ and row $B$ is chosen with probability $1 - a$. Show that the expected pay-off for Rose when the computer chooses column $X$ is $4 - 3 a$, and find the corresponding expressions for when the computer chooses column $Y$ and when it chooses column $Z$. Sketch a graph showing the expected pay-offs against $a$, and hence decide on Rose's optimal choice for $a$. Describe how Rose could use the die to decide whether to play $A$ or $B$. The computer is to choose $X , Y$ and $Z$ with probabilities $x , y$ and $z$ respectively, where $x + y + z = 1$. Graham is an AS student studying the D1 module. He wants to find the optimal choices for $x , y$ and $z$ and starts off by producing a pay-off matrix for the computer.
Graham produces the following pay-off matrix.
3 1 0
0 1 2
Write down the pay-off matrix for the computer and explain what Graham did to its entries to get the values in his pay-off matrix.
Graham then sets up the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = p - 4 ,
\text { subject to } & p - 3 x - y \leqslant 0 ,
& p - y - 2 z \leqslant 0 ,
& x + y + z \leqslant 1 ,
\text { and } & p \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ The Simplex algorithm is applied to the problem and gives $x = 0.4$ and $y = 0$. Find the values of $z , p$ and $P$ and interpret the solution in the context of the game. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}

OCR D2 2007 January Q6

6 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

Stage	State	Action	Working	Maximin
\multirow{2}{*}{1}	0	0	4	4
	1	0	3	3
\multirow{6}{*}{2}	0	0	$\min ( 6,4 ) = 4$	\multirow{2}{*}{}
		1	$\min ( 2,3 ) = 2$
	\multirow{2}{*}{1}	0	$\min ( 2,4 ) =$	\multirow{2}{*}{}
		1	$\min ( 4,3 ) =$
	\multirow{2}{*}{2}	0	min(2,	\multirow{2}{*}{}
		1	min(3,
\multirow{3}{*}{3}	\multirow{3}{*}{0}	0	min(5,	\multirow{3}{*}{}
		1	$\min ( 5$,
		2	$\min ( 2$,

Complete the last two columns of the table in the insert.
State the maximin value and write down the maximin route.

OCR D2 2006 January Q1

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.

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.
Show this incomplete matching on the second diagram in the insert.
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.
Amanda decides that she does not like the green shirt after all. Which shirts should each child have now?

OCR D2 2006 January Q2

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]

\includegraphics[alt={},max width=\textwidth]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-2_501_1018_1741_575} \captionsetup{labelformat=empty} \caption{Stage 3 Stage 2 Stage 1}

\end{figure}

OCR D2 2006 January Q5

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}

Activity	Duration
$A$	5
$B$	3
$C$	4
$D$	2
$E$	1
$F$	3
$G$	5
$H$	2
$I$	4
$J$	3

Explain why each of the dummy activities is needed.
Complete the blank column of the table in the insert to show the immediate predecessors for each activity.
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.
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.
Draw a resource histogram, assuming that each activity starts at its earliest possible time. How many workers are needed with this schedule?
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.

OCR D2 2008 January Q5

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}

Complete the table in the insert to show the precedences for the activities.
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
On graph paper, draw a resource histogram for the project with each activity starting at its earliest possible time.
Describe how the project can be completed in 21 days using just six workers.

OCR D2 2009 January Q1

1 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

Stage	State	Action	Working	Maximin
\multirow{4}{*}{1}	0	0	10
	1	0	11
	2	0	14
	3	0	15
\multirow{10}{*}{2}	\multirow{2}{*}{0}	0	(12, ) =	\multirow{2}{*}{}
		2	$( 10 , \quad ) =$
	\multirow{3}{*}{1}	0	$( 13 , \quad ) =$	\multirow{3}{*}{}
		1	$( 10 , \quad ) =$
		2	(11, ) =
	\multirow{3}{*}{2}	1	( 9, ) =	\multirow{3}{*}{}
		2	(10, ) =
		3	( 7, ) =
	\multirow{2}{*}{3}	1	( 8, ) =	\multirow{2}{*}{}
		3	(12, ) =
\multirow{4}{*}{3}	\multirow{4}{*}{0}	0	$( 15 , \quad ) =$	\multirow{4}{*}{}
		1	$( 14 , \quad ) =$
		2	(16, ) =
		3	(13, ) =

Complete the last two columns of the table in the insert.
State the maximin value and write down the maximin route.

OCR D2 2009 January Q2

2 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]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-3_497_1230_493_459}

Complete the table in the insert to show the precedences for the activities.
Use the boxes on the diagram in the insert to carry out a forward pass and a backward pass. Show that the minimum project completion time is 28 days and list the critical activities. The resource histogram below shows the number of workers required each day when the activities each begin at their earliest possible start time. Once an activity has been started it runs for its duration without a break.
\includegraphics[max width=\textwidth, alt={}, center]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-3_457_1543_1503_299}
By considering which activities are happening each day, complete the table in the insert to show the number of workers required for each activity. You are advised to start at day 28 and work back through the days towards day 1 . Only five workers are actually available, but they are all equally skilled at each of the activities. The project can still be completed in 28 days by delaying the start of activity $E$.
Find the minimum possible delay and the maximum possible delay on activity $E$ in this case.

OCR D2 2009 January Q3

3 Answer this question on the insert provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_625_1100_358_520} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} Fig. 1 represents a system of pipes through which fluid can flow from a source, $S$, to a sink, $T$. It also shows a cut $\alpha$. The weights on the arcs show the lower and upper capacities of the pipes in litres per second.

Calculate the capacity of the cut $\alpha$.
By considering vertex $B$, explain why arc $S B$ must be at its lower capacity. Then by considering vertex $E$, explain why arc $C E$ must be at its upper capacity, and hence explain why arc $H T$ must be at its lower capacity.
On the diagram in the insert, show a flow through the network of 15 litres per second. Write down one flow augmenting route that allows another 1 litre per second to flow through the network. Show that the maximum flow is 16 litres per second by finding a cut of 16 litres per second. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_602_1086_1809_568} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Fig. 2 represents the same system, but with pipe $E B$ installed the wrong way round.
Explain why there can be no feasible flow through this network.

OCR D2 2011 January Q6

6 Answer this question on the insert provided. Four friends have decided to sponsor four birds at a bird sanctuary. They want to construct a route through the bird sanctuary, starting and ending at the entrance/exit, that enables them to visit the four birds in the shortest possible time. The table below shows the times, in minutes, that it takes to get between the different birds and the entrance/exit. The friends will spend the same amount of time with each bird, so this does not need to be included in the calculation.

	Entrance/exit	Kite	Lark	Moorhen	Nightjar
Entrance/exit	-	10	14	12	17
Kite	10	-	3	2	6
Lark	14	3	-	2	4
Moorhen	12	2	2	-	3
Nightjar	17	6	4	3	-

Let the stages be $0,1,2,3,4,5$. Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be $0,1,2,3,4$ representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$, or this in reverse, taking 27 minutes.
Explain why the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$ is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state $1 ( 234 )$ means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.

Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

$21 + 3 = 24 18 + 6 = 24$

OCR D2 2007 June Q4

4 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a minimax problem.

Stage	State	A ction	Working	M inimax
\multirow{3}{*}{1}	0	0	4	4
	1	0	3	3
	2	0	2	2
\multirow{9}{*}{2}	\multirow{3}{*}{0}	0	$\max ( 6,4 ) = 6$	\multirow{3}{*}{3}
		1	$\max ( 2,3 ) = 3$
		2	$\max ( 3,2 ) = 3$
	\multirow{3}{*}{1}	0	$\max ( 2,4 ) =$	\multirow{3}{*}{}
		1	$\max ( 4,3 ) =$
		2	$\max ( 5,2 ) =$
	\multirow{3}{*}{2}	0	max(2,	\multirow{3}{*}{}
		1	max(3,
		2	max(4,
\multirow{3}{*}{3}	\multirow{3}{*}{0}	0	max(5,	\multirow{3}{*}{}
		1	max(5,
		2	max(2,

On the insert, complete the last two columns of the table.
State the minimax value and write down the minimax route.
Complete the diagram on the insert to show the network that is represented by the table.

OCR D2 2007 June Q5

5 Answer this question on the insert provided. The network represents a system of pipes through which fluid can flow from a source, S , to a sink, T .
\includegraphics[max width=\textwidth, alt={}, center]{09d4aacd-026b-4d81-a826-3d3f29f9c105-5_1310_1301_447_424} The arrows are labelled to show excess capacities and potential backflows (how much more and how much less could flow in each pipe). The excess capacities and potential backflows are measured in litres per second. Currently the flow is 6 litres per second, all flowing along a single route through the system.

Write down the route of the 6 litres per second that is flowing from $S$ to $T$.
What is the capacity of the pipe AG and in which direction can fluid flow along this pipe?
Calculate the capacity of the $\operatorname { cut } \mathrm { X } = \{ \mathrm { S } , \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \} , \mathrm { Y } = \{ \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { I } , \mathrm { T } \}$.
Describe how a further 7 litres per second can flow from S to T and update the labels on the arrows to show your flow. Explain how you know that this is the maximum flow. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}

OCR D2 2006 June Q1

1 The network represents a system of pipes along which fluid can flow from $S$ to $T$. The values on the arcs are lower and upper capacities in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-02_696_1292_376_424}

Calculate the capacity of the cut with $\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}$.
Show that the capacity of the cut $\alpha$, shown on the diagram, is 12 litres per second and calculate the minimum flow across the cut $\alpha$, from $S$ to $T$, (without regard to the remainder of the diagram).
Explain why the arc SC must have at least 5 litres per second flowing through it. By considering the flow through $A$, explain why $A D$ cannot be full to capacity.
Show that it is possible for 11 litres per second to flow through the system.
From your previous answers, what can be deduced about the maximum flow through the system?

Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
Duration	10	15	10	5	15	5	10	15	5	15

	Computer
\cline { 2 - 5 }		\(X\)	\(Y\)	\(Z\)
\cline { 2 - 5 } Rose	\(A\)	1	3	4
\(B\)	4	3	2
\(C\)	3	2	1
\cline { 2 - 5 }

Activity	Duration
\(A\)	5
\(B\)	3
\(C\)	4
\(D\)	2
\(E\)	1
\(F\)	3
\(G\)	5
\(H\)	2
\(I\)	4
\(J\)	3

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

Cake	(0; 0) to (1; 0)	(1; 0) to (2; 1)	(1; 1) to (2; 0)	(2; 0) to (3; 0)	(2; 0) to (3; 1)	(2; 1) to (3; 0)	(2; 1) to (3; 1)
Decorating points	1	1	2	1	1	1	1

Activity	\(A\)	\(B\)	\(C\)	\(E\)	\(G\)	\(H\)	\(J\)
Cost \(( \pounds )\)	200	400	100	600	100	500	500
New duration	5	10	5	10	5	10	10

Stage	State	Action	Working	Suboptimal maximum
\multirow[t]{2}{*}{3}	0	0	1	1
	1	0	2	2
\multirow[t]{4}{*}{2}	\multirow[t]{2}{*}{0}	0	\(1 + 1 = 2\)	\multirow[b]{2}{*}{3}
		1	\(1 + 2 = 3\)
	\multirow[t]{2}{*}{1}	0	\(3 + 1 = 4\)	\multirow[t]{2}{*}{4}
		1	\(1 + 2 = 3\)
\multirow[t]{4}{*}{1}	\multirow[t]{2}{*}{0}	0	\(1 + =\)	\multirow{4}{*}{}
		1	\(0 + =\)
	\multirow[t]{2}{*}{1}	0	\(0 + =\)
		1	\(1 + =\)
\multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	\(2 + =\)	\multirow{2}{*}{}
		1	\(2 + =\)

Questions — OCR D2 (141 questions)

Browse by module

Browse by board

OCR D2 2015 June Q6

OCR D2 2016 June Q1

OCR D2 2016 June Q2

OCR D2 2016 June Q3

OCR D2 2016 June Q4

OCR D2 2016 June Q5

OCR D2 2016 June Q6

OCR D2 Specimen Q1

OCR D2 Specimen Q2

OCR D2 Specimen Q3

OCR D2 Specimen Q4

OCR D2 Specimen Q5

OCR D2 Specimen Q6

OCR D2 2007 January Q6

OCR D2 2006 January Q1

OCR D2 2006 January Q2

OCR D2 2006 January Q5

OCR D2 2008 January Q5

OCR D2 2009 January Q1

OCR D2 2009 January Q2

OCR D2 2009 January Q3

OCR D2 2011 January Q6

OCR D2 2007 June Q4

OCR D2 2007 June Q5

OCR D2 2006 June Q1