Questions D2 (553 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
OCR D2 2005 June Q3
14 marks Standard +0.3
3 The table lists the activities involved in preparing for a cycle ride, their expected durations and their immediate predecessors.
ActivityDuration (minutes)Preceded by
A: Check weather8-
B: Get maps out4-
C: Make sandwiches12-
D: Check bikes over20\(A\)
E: Plan route12A, B
\(F\) : Pack bike bags4A, B, \(C\)
G: Get bikes out ready2\(D , E , F\)
\(H\) : Change into suitable clothes12E, F
  1. Draw an activity network to represent the information in the table. Show the activities on the arcs and indicate the direction of each activity and dummy activity. You are advised to make your network quite large.
  2. Carry out a forward pass and a backward pass to determine the minimum completion time for preparing for the ride. List the critical activities.
  3. Construct a cascade chart, showing each activity starting at its earliest possible time. Two people, John and Kerry, are intending to go on the cycle ride. Activities \(A , B , F\) and \(G\) will each be done by just one person (either John or Kerry), but both are needed (at the same time) for activities \(C , D\) and \(E\). Also, each of John and Kerry must carry out activity \(H\), although not necessarily at the same time. All timings and precedences in the original table still apply.
  4. Draw up a schedule showing which activities are done by each person at which times in order to complete preparing for the ride in the shortest time possible. The schedule should have three columns, the first showing times in 4-minute intervals, the second showing which activities John does and the third showing which activities Kerry does.
OCR D2 2005 June Q4
15 marks Moderate -0.5
4 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit. Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( \(5 ; 0\) ) and the exit as ( \(0 ; 0\) ). He then counted the numbers of plants along paths. These numbers are shown below.
Stage 5(5;0) to (4;0): 6 plants (5;0) to (4;1): 8 plants
Stage 4(4;0) to (3;0): 5 plants (4;0) to (3;1): 8 plants(4;1) to (3;0): 7 plants (4;1) to (3;2): 5 plants
Stage 3( \(3 ; 0\) ) to ( \(2 ; 1\) ): 8 plants (3;0) to (2;3): 6 plants(3;1) to (2;0): 7 plants \(( 3 ; 1 )\) to (2;2): 6 plants(3;2) to (2;0): 7 plants (3;2) to (2;2): 6 plants ( \(3 ; 2\) ) to ( \(2 ; 3\) ): 8 plants
Stage 2(2; 0) to (1; 0): 4 plants ( \(2 ; 0\) ) to ( \(1 ; 1\) ): 5 plants(2; 1) to (1; 0): 6 plants(2;2) to (1;1): 7 plants(2;3) to (1;0): 5 plants (2;3) to (1;1): 6 plants
Stage 1(1;0) to (0;0): 4 plants(1; 1) to (0;0): 4 plants
  1. Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route? Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.
  2. Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 . You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.
OCR D2 2007 June Q1
13 marks Moderate -0.8
1 D aniel needs to clean four houses but only has one day in which to do it. He estimates that each house will take one day and so he has asked three professional cleaning companies to give him a quotation for cleaning each house. He intends to hire the three companies to clean one house each and he will clean the fourth house himself. The table below shows the quotations that Daniel was given by the three companies.
House 1House 2House 3House 4
Allclean\(\pounds 500\)\(\pounds 400\)\(\pounds 700\)\(\pounds 600\)
Brightenupp\(\pounds 300\)\(\pounds 200\)\(\pounds 400\)\(\pounds 350\)
Clean4U\(\pounds 500\)\(\pounds 300\)\(\pounds 750\)\(\pounds 680\)
  1. Copy the table and add a dummy row to represent D aniel.
  2. A pply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working and say how each matrix was formed.
  3. Which house should Daniel ask each company to clean? Find the total cost of hiring the three companies.
OCR D2 2007 June Q2
15 marks Moderate -0.8
2 The table gives the pay-off matrix for a zero-sum game between two players, A my and Bea. The values in the table show the pay-offs for A my.
Bea
\cline { 3 - 5 }Strategy XStrategy YStrategy Z
\cline { 2 - 5 }Strategy P4- 20
\cline { 2 - 5 } A myStrategy Q- 154
\cline { 2 - 5 }
\cline { 2 - 5 }
A my makes a random choice between strategies \(\mathbf { P }\) and \(Q\), choosing strategy \(P\) with probability \(p\) and strategy Q with probability \(1 - \mathrm { p }\).
  1. Write down and simplify an expression for the expected pay-off for Amy when Bea chooses strategy X . Write down similar expressions for the cases when B ea chooses strategy Y and when she chooses strategy \(Z\).
  2. Using graph paper, draw a graph to show A my's expected pay-off against p for each of Bea's choices of strategy. Using your graph, find the optimal value of pfor A my. A my and Bea play the game many times. A my chooses randomly between her strategies using the optimal value for p.
  3. Showing your working, calculate A my's minimum expected pay-off per game. W hy might A my gain more points than this, on average?
  4. W hat is B ea's minimum expected loss per game? How should B ea play to minimise her expected loss?
OCR D2 2007 June Q3
15 marks Moderate -0.8
3 The table shows the activities involved in a project, their durations and precedences, and the number of workers needed for each activity.
  1. On the insert, complete the last two columns of the table.
  2. State the minimax value and write down the minimax route.
  3. Complete the diagram on the insert to show the network that is represented by the table.
OCR D2 2009 June Q1
13 marks Moderate -0.8
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\)88881
    Mandarin\(M\)48642
    Nectarine\(N\)99971
    Orange\(O\)46543
    Peach\(P\)69750
    \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?
OCR D2 2009 June Q2
20 marks Standard +0.3
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.
    ActivityDurationImmediate predecessors
    \(A\)8-
    \(B\)9-
    C7-
    D5\(A\)
    E6\(A\)
    \(F\)4\(B\)
    \(G\)5B
    \(H\)6\(B\)
    \(I\)10C
    \(J\)9\(C\)
    \(K\)6\(C\)
    \(L\)7D, 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).
OCR D2 2009 June Q3
19 marks Easy -1.2
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.
Collies
\cline { 2 - 6 }\(W\)\(X\)\(Y\)\(Z\)
\cline { 2 - 6 }\(P\)12- 13
\cline { 2 - 6 }\(Q\)- 21- 3- 1
\cline { 2 - 6 } \(R\)2- 410
\cline { 2 - 6 }
\cline { 2 - 6 }
  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\).
OCR D2 2009 June Q4
20 marks Challenging +1.8
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.
OCR D2 2011 June Q1
6 marks Moderate -0.3
1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals. The table shows which family members like each of the cereals in the pack.
\multirow{8}{*}{Cereal}\multirow{2}{*}{}Family member
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)
Cornflakes (1)✓✓✓
Rice pips (2)✓✓
Wheat biscs (3)✓✓
Oatie bits (4)✓✓
Choco pips (5)✓✓✓
Honey footballs (6)✓
  1. Draw a bipartite graph to represent this information. Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, which is not a possible pairing.
  2. Draw a second bipartite graph to show this incomplete matching.
  3. Construct the shortest possible alternating path from 6 to \(A\) and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
  4. Adam decides that he wants cornflakes. Construct an alternating path starting at \(A\), based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.
OCR D2 2011 June Q2
12 marks Moderate -0.5
2 Granny is on holiday in Amsterdam and has bought some postcards. She wants to send one card to each member of her family. She has given each card a score to show how suitable it is for each family member. The higher the score the more suitable the card is. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Family member}
\multirow{9}{*}{Postcard}AdamBarbaraCharlieDonnaEdwardFiona
Painted barges\(P\)242604
Quaint houses\(Q\)353534
Reichsmuseum\(R\)676668
Scenic view\(S\)464404
Tulips\(T\)101405
University\(U\)344433
View from air\(V\)757675
Windmills\(W\)465455
\end{table} Granny adds two dummy columns, \(G\) and \(H\), both with score 0 for each postcard. She then modifies the resulting table so that she can use the Hungarian algorithm to find the matching for which the total score is maximised.
  1. Explain why the dummy columns were needed, why they should not have positive scores and how the resulting table was modified.
  2. Show that, after reducing rows and columns, Granny gets this reduced cost matrix.
    AB\(C\)D\(E\)\(F\)\(G\)\(H\)
    \(P\)42406222
    \(Q\)20202111
    \(R\)21222044
    \(S\)20226222
    \(T\)45415011
    \(U\)10001100
    \(V\)02010233
    \(W\)20121122
  3. Complete the application of the Hungarian algorithm, showing your working clearly. Write down which family member is sent each postcard, and which postcards are not used, to maximise the score.
OCR D2 2011 June Q3
12 marks Easy -1.2
3 Basil runs a luxury hotel. He advertises summer breaks at the hotel in several different magazines. Last summer he won the opportunity to place a full-page colour advertisement in one of four magazines for the price of the usual smaller advertisement. The table shows the expected additional weekly income, in \(\pounds\), for each of the magazines for each possible type of weather. Basil wanted to maximise the additional income.
Weather
RainySunny
\cline { 2 - 4 }Activity holidays40005000
\cline { 2 - 4 } MagazineBritish beaches10007000
\cline { 2 - 4 }Country retreats30006000
\cline { 2 - 4 }Dining experiences50003000
\cline { 2 - 4 }
  1. Explain carefully why no magazine choice can be rejected using a dominance argument.
  2. Treating the choice of strategies as being a zero-sum game, find Basil's play-safe strategy and show that the game is unstable.
  3. Calculate the expected additional weekly income for each magazine choice if the weather is rainy with probability 0.4 and sunny with probability 0.6 . Suppose that the weather is rainy with probability \(p\) and sunny with probability \(1 - p\).
  4. Which magazine should Basil choose if the weather is certain to be sunny ( \(p = 0\) ), and which should he choose if the weather is certain to be rainy ( \(p = 1\) )?
  5. Graph the expected additional weekly income against \(p\). Hence advise Basil on which magazine he should choose for the different possible ranges of values of \(p\).
OCR D2 2011 June Q4
14 marks Moderate -0.3
4 Jamil is building a summerhouse in his garden. The activities involved, the duration, immediate predecessors and number of workers required for each activity are listed in the table.
ActivityDuration (hours)Immediate predecessorsNumber of workers
\(A\) : Choose summerhouse2-2
\(B\) : Buy slabs for base1-2
\(C\) : Take goods home2\(A , B\)2
\(D\) : Level ground3-1
E: Lay slabs2\(C , D\)2
\(F\) : Treat wood3C1
\(G\) : Install floor, walls and roof4\(E , F\)2
\(H\) : Fit windows and door2\(G\)1
\(I\) : Fit patio rail1\(G\)1
\(J\) : Fit shelving1\(G\)1
  1. 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.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event times and late event times at the vertices of your network. State the minimum project completion time and list the critical activities.
  3. Draw a resource histogram to show the number of workers required each hour when each activity begins at its earliest possible start time.
  4. Describe how it is possible for the project to be completed in the minimum project completion time when only four workers are available.
  5. Describe how two workers can complete the project as quickly as possible. Find the minimum time in which two workers can complete the project.
OCR D2 2011 June Q5
19 marks Standard +0.3
5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from \(S\) to \(T\). The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}
  1. Calculate the capacity of the cut that separates \(\{ S , A , C , G \}\) from \(\{ B , D , E , F , T \}\).
  2. Explain why neither arc \(S A\) nor arc \(E T\) can be full to capacity. Also explain why the arcs \(A C\) and \(B C\) cannot simultaneously be full to capacity.
  3. Show a flow of 3300 people per hour, and find a cut of capacity 3300 . The direction of flow in \(B C\) is reversed.
  4. Show the excess capacities and potential backflows when there is no flow.
  5. Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along \(S B E T\).
  6. Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from \(S\) to \(T\).
  7. Show the maximum flow and explain how you know that this flow is maximal.
OCR D2 2011 June Q6
9 marks Standard +0.3
6 Set up a dynamic programming tabulation to find the maximin route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-7_883_1323_390_411}
OCR D2 2012 June Q1
5 marks Moderate -0.5
1 The six cadets in Red Team have been told to guard a building through the night, starting at 2200 hours and finishing at 0800 hours the next day. Each will be on duty for either one hour or three hours and will then hand over to the next cadet. The table shows which duty each cadet has offered to take. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Duty start time (24 hour clock time)}
220001000200030004000500
Amir (A)✓✓
Becca (B)✓✓
Chris (C)✓✓✓
Dan (D)✓✓
Emma (E)✓✓
Finn \(( F )\)✓
\end{table}
  1. Draw a bipartite graph to represent this information. Amir suggests that he should take the 2200 duty, hand over to Becca at 0100 , she can hand over to Chris at 0200 , and Dan can take the 0400 duty. However, this leaves Emma and Finn to cover the 0300 and 0500 duties, and neither of them wants either of these.
  2. Write down the shortest possible alternating path starting at the 0500 duty and hence write down an improved but still incomplete matching between the cadets and the duties.
  3. Augment this second incomplete matching by writing down a shortest possible alternating path, this time starting from one of the cadets, to form a complete matching between the cadets and the duties. Write down which cadet should take which duty.
OCR D2 2012 June Q2
8 marks Standard +0.3
2 The cadets in Blue Team have been set a task that requires them to get inside a guarded building. Every two hours one of them will attempt to get inside the building. Each cadet will have one attempt. The table shows a score for each cadet attempting to get inside the building at each time. The higher the score the more likely the cadet is to succeed. Time
\multirow{6}{*}{Cadet}\multirow[b]{3}{*}{
Gary
Hilary
}		23300130033005300730
\(G\)80711
H92702
IeuanI104935
Jenni\(J\)72612
Ken\(K\)108967
  1. Explain how to modify the table so that the Hungarian algorithm can be used to find the matching for which the total score is maximised.
  2. Show that, after modifying the table and then reducing rows and then columns, the reduced cost matrix becomes:
    23300130033005300730
    \(G\)06034
    \(H\)05154
    \(I\)04032
    \(J\)03022
    \(K\)00000
  3. Complete the application of the Hungarian algorithm, stating how each table was formed. Write down the order in which the cadets should attempt to get into the building to maximise the total score. If the cadets use this solution, which one is least likely to succeed?
OCR D2 2012 June Q3
9 marks Moderate -0.5
3 Throughout this question all clock times are in Greenwich Mean Time (GMT).
An aeroplane needs to arrive at its destination at 3pm. The places it can pass through on its route are shown in the network, together with the flying times, in hours, between them. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-4_609_1523_486_255} Use a dynamic programming tabulation, working backwards from 3pm at the destination, to find the latest time that the aeroplane could set off. If the aeroplane takes off at its latest time, which places does it pass through, and at what time does it reach each of these places?
OCR D2 2012 June Q4
15 marks Challenging +1.8
4 A group of rowers have challenged some cyclists to see which team is fitter. There will be several rounds to the challenge. In each round, the rowers and the cyclists each choose a team member and these two compete in a series of gym exercises. The time by which the winner finishes ahead of the loser is converted into points. These points are added to the score for the winner's team and taken off the score for the loser's team. The table shows the expected number of points added to the score for the rowers for each combination of competitors. Rowers \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Cyclists}
ChrisJamieWendy
Andy- 32- 4
Kath54- 6
Zac1- 4- 5
\end{table}
  1. Regarding this as a zero-sum game, find the play-safe strategy for the rowers and the play-safe strategy for the cyclists. Show that the game is stable. Unfortunately, Wendy and Kath are needed by their coaches and cannot compete.
  2. Show that the resulting reduced game is unstable.
  3. Suppose that the cyclists are equally likely to choose Chris or Jamie. Calculate the expected number of points added to the score for the rowers when they choose Andy and when they choose Zac. Suppose that the cyclists use random numbers to choose between Chris and Jamie, so that Chris is chosen with probability \(p\) and Jamie with probability \(1 - p\).
  4. Showing all your working, calculate the optimum value of \(p\) for the cyclists.
  5. The rowers use random numbers in a similar way to choose between Andy and Zac, so that Andy is chosen with probability \(q\) and Zac with probability \(1 - q\). Calculate the optimum value of \(q\).
OCR D2 2012 June Q5
18 marks Challenging +1.2
5 The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the pipes, in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-6_577_1182_351_443}
  1. Identify the source and explain how you know that the sink is at \(G\).
  2. Calculate the capacity of the cut that separates \(\{ A , B , C , D , E , F \}\) from \(\{ G , H , I , J , K , L \}\).
  3. Assuming that a feasible flow exists, explain why arc \(J G\) must be at its lower capacity. Write down the flows in arcs \(H K\) and \(I L\).
  4. Assuming that a feasible flow exists, explain why arc HI must be at its upper capacity. Write down the flows in arcs \(E H\) and \(C B\).
  5. Show a flow of 10 litres per second through the system.
  6. Using your flows from part (v), label the arrows on the diagram to show the excess capacities and the potential backflows.
  7. Write down a flow augmenting path from your diagram in part (vi), but do not update the excess capacities and the potential backflows. Hence show a maximum flow through the system, and state how you know that the flow is maximal.
OCR D2 2012 June Q6
17 marks Standard +0.3
6 Tariq wants to advertise his gardening services. The activities involved, their durations (in hours) and immediate predecessors are listed in the table.
ActivityDuration (hours)Immediate predecessors
AChoose a name for the gardening service2-
BThink about what the text needs to say3-
CArrange a photo shoot2B
DVisit a leaflet designer3A, \(C\)
EDesign website5A, \(C\)
\(F\)Get business cards printed3D
GIdentify places to publicise services2A, \(C\)
HArrange to go on local radio3B
IDistribute leaflets4D, G
JGet name put on van1E
  1. Draw an activity network, using activity on arc, to represent the project.
  2. Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities. Tariq does not have time to complete all the activities on his own, so he gets some help from his friend Sally.
    Sally can help Tariq with any of the activities apart from \(C , H\) and \(J\). If Tariq and Sally share an activity, the time it takes is reduced by 1 hour. Sally can also do any of \(F , G\) and \(I\) on her own.
  3. Describe how Tariq and Sally should share the work so that activity \(D\) can start 5 hours after the start of the project.
  4. Show that, if Sally does as much of the work as she can, she will be busy for 18 hours. In this case, for how many hours will Tariq be busy?
  5. Explain why, if Sally is busy for 18 hours, she will not be able to finish until more than 18 hours from the start. How soon after the start can Sally finish when she is busy for 18 hours?
  6. Describe how Tariq and Sally can complete the project together in 18 hours or less.
OCR D2 2013 June Q2
20 marks Standard +0.3
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]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-3_595_1054_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.
    ActivityDurationImmediate predecessors
    \(A\)8-
    \(B\)9-
    C7-
    D5\(A\)
    E6\(A\)
    \(F\)4\(B\)
    \(G\)5B
    \(H\)6\(B\)
    \(I\)10C
    \(J\)9\(C\)
    \(K\)6\(C\)
    \(L\)7D, 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).
OCR D2 2013 June Q3
19 marks Moderate -1.0
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.
Collies
\cline { 2 - 6 }\(W\)\(X\)\(Y\)\(Z\)
\cline { 2 - 6 }\(P\)12- 13
\cline { 2 - 6 }\(Q\)- 21- 3- 1
\(R\)2- 410
\cline { 2 - 6 }
\cline { 2 - 6 }
  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\).
OCR D2 2013 June Q4
20 marks Standard +0.8
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]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-6_597_1577_404_283}
  1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
  2. Explain why the \(\operatorname { arcs } A C\) and \(A D\) cannot both be full to capacity and why the \(\operatorname { 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.
OCR D2 2014 June Q1
6 marks Moderate -0.5
1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_522_976_351_525} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below. \begin{table}[h]
Adele(A)\includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_47_43_1210_750}(B)Battleship
Ezra(E)『(F)Flat iron
Jonah(J)\includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1389_759}(O)Old boot
Lily(L)\includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1486_759}(R)Racing car
Molly(M)\includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_44_377_1583_759}(S)Scottie dog
Noah(N)\includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_40_29_1684_764}(T)Top hat
\captionsetup{labelformat=empty} \caption{Fig. 2}
\end{table}
  1. Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
  2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
  3. By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.