Questions — OCR D2 (141 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 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics Stats 1 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 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 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 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 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics 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
OCR D2 2011 June Q2
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
OCR D2 2014 June Q2
2 The network models a cooling system in a factory. Coolant starts at \(A , B\) and \(C\) and flows through the system. The arcs model components of the cooling system and the weights show the maximum amount of coolant that can flow through each component of the system (measured in litres per second). The arrows show the direction of flow.
\includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-3_611_832_539_605}
  1. Add a supersource, \(S\), and a supersink, \(T\), to the copy of the network in your answer book. Connect \(S\) and \(T\) to the network using appropriately weighted arcs.
  2. (a) Find the capacity of the cut that separates \(A , B , C\) and \(E\) from \(D , F , G\) and \(H\).
    (b) Find the capacity of the cut that separates \(A , B , C , D , E\) and \(F\) from \(G\) and \(H\).
    (c) What can you deduce from this value about the maximum flow through the system?
  3. Find the maximum possible flow through the system and prove that this is the maximum.
  4. Describe what effect increasing the capacity of \(C E\) would have on the maximum flow.
OCR D2 2014 June Q3
5 marks
3 Each of five jobs is to be allocated to one of five workers, and each worker will have one job. The table shows the cost, in \(\pounds\), of using each worker on each job. It is required to find the allocation for which the total cost is minimised. Worker \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Job}
PlasteringRewiringShelvingTilingUpholstery
Gill2550344025
Harry3642484445
Ivy2750454226
James4046284550
Kelly3448345040
\end{table}
  1. Construct a reduced cost matrix by first reducing rows and then reducing columns. Cross through the 0's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [Try to ensure that the values in your table can still be read.]
  2. Augment your reduced cost matrix and hence find a minimum cost allocation. Write a list showing which job should be given to which worker for your minimum cost allocation, and calculate the total cost in this case. Gill decides that she does not like the job she has been allocated and increases her cost for this job by \(\pounds 100\). New minimum cost allocations can be found, each allocation costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii).
  3. Use the grid in your answer book to show the positions of the 0 's and 1 's in the augmented reduced cost matrix from part (ii). Hence find three allocations, each costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii) and with Gill having a different job to the one allocated in part (ii). [5]
OCR D2 2014 June Q4
4 Ross and Collwen are playing a game in which each secretly chooses a magic spell. They then reveal their choices, and work out their scores using the tables below. Ross and Collwen are both trying to get as large a score as possible.
Collwen's choice
Score for
Ross
FireIceGale
\cline { 2 - 5 }Fire172
\cline { 2 - 5 }
Ross's
choice
Ice624
\cline { 2 - 5 }Gale513
\cline { 2 - 5 }
Collwen's choice
Score for
Collwen
FireIceGale
\cline { 2 - 5 }Fire716
\cline { 2 - 5 }
Ross's
choice
Ice264
\cline { 2 - 5 }Gale375
\cline { 2 - 5 }
  1. Explain how this can be rewritten as the following zero-sum game.
    Collwen's choice
    FireIceGale
    \cline { 2 - 5 }Fire- 33- 2
    \cline { 2 - 5 }
    Ross's
    choice
    		Ice2- 20
    \cline { 2 - 5 }Gale1- 3- 1
    \cline { 2 - 5 }
  2. If Ross chooses Ice what is Collwen's best choice?
  3. Find the play-safe strategy for Ross and the play-safe strategy for Collwen, showing your working. Explain how you know that the game is unstable.
  4. Show that none of Collwen's strategies dominates any other.
  5. Explain why Ross would never choose Gale, hence reduce the game to a \(2 \times 3\) zero-sum game, showing the pay-offs for Ross. Suppose that Ross uses random numbers to choose between Fire and Ice, choosing Fire with probability \(p\) and Ice with probability \(1 - p\).
  6. Use a graphical method to find the optimal value of \(p\) for Ross.
OCR D2 2014 June Q5
2 marks
5 Following a promotion at work, Khalid needs to clear out his office to move to a different building. The activities involved, their durations (in hours) and immediate predecessors are listed in the table below. You may assume that some of Khalid's friends will help him and that once an activity is started it will be continued until it is completed.
ActivityDuration (hours)Immediate predecessors
ASort through cupboard and throw out rubbish4-
BGet packing boxes1-
CSort out items from desk and throw out rubbish3-
DPack remaining items from cupboard in boxes2\(A\), \(B\)
EPut personal items from desk into briefcase0.5C
\(F\)Pack remaining items from desk in boxes1.5\(B , C\)
GTake certificates down and put into briefcase1-
HLabel boxes to be stored0.5D, F
  1. Represent this project using an activity network.
  2. 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 your network. State the minimum project completion time and list the critical activities.
  3. How much longer could be spent on sorting the items from the desk and throwing out the rubbish (activity \(C\) ) without it affecting the overall completion time? Khalid says that he needs to do activities \(A , C , E\) and \(G\) himself. These activities take a total of 8.5 hours.
  4. By considering what happens if Khalid does \(A\) first, and what happens if he does \(C\) first, show that the project will take more than 8.5 hours.
  5. Draw up a schedule to show how just two people, Khalid and his friend Mia, can complete the project in 9 hours. Khalid must do \(A , C , E\) and \(G\) and activities cannot be shared between Khalid and Mia. [2]
OCR D2 2014 June Q6
6 The table below shows an incomplete dynamic programming tabulation to solve a maximin problem. Do not write your answer on this copy of the table.
StageStateActionWorkingSuboptimal maximin
\multirow[t]{3}{*}{3}0066
1011
2033
\multirow[t]{5}{*}{2}00\(\min ( 3,6 ) = 3\)3
\multirow{3}{*}{1}0\(\min ( 1,6 ) = 1\)\multirow[b]{3}{*}{2}
1\(\min ( 1,1 ) = 1\)
2\(\min ( 2,3 ) = 2\)
22\(\min ( 1,3 ) = 1\)1
\multirow[t]{5}{*}{1}\multirow[t]{2}{*}{0}0\(\min ( 3\),\multirow{2}{*}{}
1\(\min ( 4\),
11\(\min ( 3\),
\multirow[t]{2}{*}{2}1\(\min ( 3\),\multirow{2}{*}{}
2\(\min ( 1\),
\multirow[t]{3}{*}{0}\multirow[t]{3}{*}{0}0\(\min ( 5\),\multirow{3}{*}{}
1\(\min ( 3\),
2\(\min ( 4\),
  1. Complete the working and suboptimal maximin columns on the copy of the table in your answer book.
  2. Use your answer to part (i) to write down the maximin value and the corresponding route. Give your route using (stage; state) variables.
  3. Draw the network that is represented in the table. The network represents a system of pipes and the arc weights show the capacities of the pipes, in litres per second.
  4. What does the answer to part (ii) represent in this network? The weights of the arcs in the maximin route are each reduced by the maximin value and then a maximin is found for the resulting network. This is done until the maximin value is 0 . At this point the network is as shown below.
    \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-8_552_1474_438_274}
  5. (a) Describe how this solves the maximum flow problem on the original network.
    (b) Draw this maximum flow and draw a cut with value equal to the value of the flow. \section*{END OF QUESTION PAPER} \section*{\(\mathrm { OCR } ^ { \text {勾 } }\)}
OCR D2 2015 June Q1
1 The infamous fictional detective Agatha Parrot is working on a case and decides to invite each of the four suspects to visit her for tea. She will invite one suspect to tea on Sunday (S), another on Monday (M), another on Tuesday (T) and the final suspect on Wednesday (W).
  • Beryl Batty (B) could come to tea on Sunday or Monday but she is away for a few days after that.
  • Colonel Chapman (C) could come to tea on Sunday or Tuesday, but is busy on the other days.
  • Dimitri Delacruz (D) could only come to tea on Monday or Wednesday.
  • Erina El-Sayed (E) could come to tea on Sunday, Monday or Tuesday, but will be away on Wednesday.
    1. Draw a bipartite graph to show which suspects could come to tea on which day.
Agatha initially intended to invite Beryl to tea on Sunday, Dimitri on Monday and Colonel Chapman on Tuesday. However this would mean that Erina would not be able to come to tea, as she will be away on Wednesday.
  • Draw a second bipartite graph to show this incomplete matching.
  • Working from this incomplete matching, find the shortest possible alternating path, starting at Erina, to achieve a breakthrough. Write down which suspect is invited on which day with this matching. Before issuing invitations, Agatha overhears Erina making arrangements to go to tea with the vicar one day. She knows that Erina will not want to accept two invitations to tea on the same day. Unfortunately, Agatha does not know which day Erina has arranged to go to tea with the vicar, other than that it was not Sunday. Agatha invites Erina to tea on Sunday and the others when she can. After having tea with all four suspects she considers what they have said and invites them all back on Friday. She then accuses the person who came to tea on Monday of being guilty.
  • Who does Agatha accuse of being guilty?
    •
    OCR D2 2015 June Q2
    2 The diagram below shows an activity network for a project. The figures in brackets show the durations of the activities, in hours.
    \includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-3_371_1429_367_319}
    1. Complete the table in your answer book to show the immediate predecessors for each activity.
    2. Carry out a forward pass and a backward pass on the copy of the network in your answer book, showing the early event times and late event times. State the minimum project completion time, in hours, and list the critical activities.
    3. How much longer could be spent on activity \(F\) without it affecting the overall completion time? Suppose that each activity requires one worker. Once an activity has been started it must continue until it is finished. Activities cannot be shared between workers.
    4. (a) State how many workers are needed at the busiest point in the project if each activity starts at its earliest possible start time.
      (b) Suppose that there are fewer workers available than given in your answer to part (iv)(a). Explain why the project cannot now be completed in the minimum project completion time from part (ii). Suppose that activity \(C\) is delayed so that it starts 2 hours after its earliest possible start time, but there is no restriction on the number of workers available.
    5. Describe what effect this will have on the critical activities and the minimum project completion time.
    OCR D2 2015 June Q3
    3 A team triathlon is a race involving swimming, cycling and running for teams of three people. The first person swims, then the second person cycles and finally the third person runs. The winning team is the team that completes all three stages of the triathlon in the shortest time. Four friends are training to enter as a team for the triathlon. They need to choose who to enter for each stage of the triathlon, and who to leave out (this person will be the reserve). The table shows the times, in minutes, for each of them to complete each stage in training.
    SwimCycleRun
    Fred307548
    Gary258245
    Helen457653
    Isobel407045
    1. Complete a dummy column in the table in your answer book. Apply the Hungarian algorithm, reducing columns first. Make sure that the values in your tables can all be seen. Write a list showing who should be chosen for each stage of the triathlon. What is the minimum total time in which the team can expect to complete the three stages of the triathlon? The day before the triathlon, the friend who had been chosen to swim is injured and cannot compete.
    2. If the reserve takes over the swim, how much longer can the team expect the triathlon to take?
    3. Remove the row corresponding to the injured swimmer to form a \(3 \times 3\) table. Apply the Hungarian algorithm to find who should be chosen for each stage to complete the triathlon in the minimum expected time. State the minimum expected time.
    OCR D2 2015 June Q4
    4 Jeremy is planning a long weekend break during which he wants to photograph as many different churches as he can. He will start from his home, \(J\), on Friday morning and return to his home on Monday evening. Table 1, below, summarises the routes he can take each day and the number of churches that he will pass on each route. You may assume that the 28 churches in the table are all different. \begin{table}[h]
    DayFromToNumber of churches
    FridayJKayton\(K\)4
    JLittle Elling\(L\)5
    SaturdayKMoreton EmcombeM2
    KNether Ensleigh\(N\)0
    LNether Ensleigh\(N\)0
    LPeacombe\(P\)4
    SundayMRiver Ardan\(R\)0
    NRiver Ardan\(R\)4
    PSeabury\(S\)3
    \(P\)Teebury\(T\)2
    Monday\(R\)Jeremy's home\(J\)4
    SJeremy's home\(J\)0
    \(T\)Jeremy's home\(J\)0
    \captionsetup{labelformat=empty} \caption{Table 1}
    \end{table}
    1. Represent the information in the table as a directed network in which the vertices represent the places. You may code the place names using the letters, as above. Jeremy wants to use dynamic programming to find the route on which he will pass the greatest number of churches. The (stage; state) variables will represent the places where he stays overnight. \(J\) will have (stage; state) variable ( \(0 ; 0\) ) at the start of the journey and ( \(4 ; 0\) ) at the end. Table 2 shows the (stage; state) variables for all the other places. \begin{table}[h]
      Place\(K\)\(L\)\(M\)\(N\)\(P\)\(R\)\(S\)\(T\)
      Stage variable11222333
      State variable01012012
      \captionsetup{labelformat=empty} \caption{Table 2}
      \end{table}
    2. Set up a dynamic programming tabulation, working backwards from Monday to Friday, to find the route that Jeremy should take to pass the greatest number of churches. Write down Jeremy's route. You may code the place names using the letters, as above. Write down the number of churches that he will be able to photograph on this route.
    OCR D2 2015 June Q5
    5 The diagram shows a flow through a network of directed arcs. The amount that can flow in each arc is limited by its upper capacity, and the lower capacity of each arc is 0 . The labelled arrows by the arcs show how much more (excess capacity) and how much less (potential backflow) could flow in each arc, in litres per second, and the objective is to find the maximum flow from \(S\) to \(T\).
    \includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-6_969_1363_459_351}
    1. How many litres per second are currently flowing along the route SACHT?
    2. How many litres per second are currently flowing from \(S\) to \(T\) ?
    3. What is the maximum by which the flow along the route SBGIT can be increased? Use the copy of the network in your answer book to show what happens to the labels on the arrows when the flow along this route is augmented by this amount.
    4. Find the maximum amount that can flow through the network. Explain, by using a cut, how you know that your flow is a maximum. The network had vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\). The single vertex \(E\) is replaced by the pair of vertices \(E _ { 1 }\) and \(E _ { 2 }\), together with the \(\operatorname { arc } E _ { 1 } E _ { 2 }\).
    5. What does the \(\operatorname { arc }\) joining \(E _ { 1 }\) and \(E _ { 2 }\) tell you about the flow at \(E\) ?
    6. Complete the diagram in your answer book to show the flow resulting after part (iii) on a directed network with vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\).