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 2014 June Q2
9 marks Moderate -0.3
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
13 marks Moderate -0.3
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
16 marks Standard +0.3
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
14 marks Moderate -0.8
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
14 marks Standard +0.3
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
5 marks Moderate -0.8
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
    12 marks Moderate -0.5
    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
    12 marks Moderate -0.3
    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
    13 marks Moderate -0.8
    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
    10 marks Moderate -0.3
    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\).
    OCR D2 2015 June Q6
    20 marks Easy -1.8
    6 At the final battle in a war game, the two opposing armies, led by General Rose, \(R\), and Colonel Cole, \(C\), are facing each other across a wide river. Each army consists of four divisions. The commander of each army needs to send some of his troops North and send the rest South. Each commander has to decide how many divisions (1,2 or 3) to send North. Intelligence information is available on the number of thousands of soldiers that each army can expect to have remaining with each combination of strategies. Thousands of soldiers remaining in \(R\) 's army \(C\) 's choice \(R\) 's choice
    123
    1152530
    2205015
    3303515
    Thousands of soldiers remaining in \(C\) 's army \(C\) 's choice \(R\) 's choice
    123
    1203510
    2155020
    3102540
    1. 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.
    2. 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.
    3. 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.
    4. 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
    5. 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\).
    6. 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\).
    7. 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 }\).
    8. Explain why this is not a solution to the LP problem.
    OCR D2 2016 June Q1
    7 marks Standard +0.3
    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}
    1. 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.
    2. 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.
    3. 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
    10 marks Moderate -0.8
    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}
    1. 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\).
    2. (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.
    3. 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
    13 marks Standard +0.8
    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
    LightingSoundTrapeze
    \multirow{4}{*}{Technician}Amir868890
    Bex929495
    Caz889294
    Dee9810098
    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.
    1. 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.]
    2. 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.
    3. 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
    10 marks Easy -1.2
    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}
    1. Use an example to show that this is not a zero-sum game.
    2. 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 )\).
    3. 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.
    4. Calculate the probability with which Rowan should play each strategy.
    OCR D2 2016 June Q5
    16 marks Standard +0.3
    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}
    1. If \(C\) were to turn out to be a critical activity, which two other activities would be forced to be critical?
    2. 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\)
      Duration10151051551015515
      \captionsetup{labelformat=empty} \caption{Table 1}
      \end{table}
    3. 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.
    4. 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.
    5. 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 )\)200400100600100500500
      New duration51051051010
      \captionsetup{labelformat=empty} \caption{Table 2}
      \end{table}
    6. 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
    16 marks Standard +0.3
    6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.
    StageStateActionWorkingSuboptimal maximum
    \multirow[t]{2}{*}{3}0011
    1022
    \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 + =\)
    1. 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 points1121111
    2. 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.)
    3. 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.
    4. Use a dynamic programming tabulation to find the minimax route for the absolute differences.
    OCR D2 Specimen Q1
    9 marks Moderate -0.8
    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.
    1. 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.
    2. By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
    3. 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
    9 marks Moderate -0.3
    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
    LondonGlasgowManchesterSwansea
    Adam4324
    Betty3542
    Clive3633
    Dave2643
    Eleanor2534
    1. 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.
    2. 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
    10 marks Standard +0.3
    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
    1. 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.
    2. 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
    13 marks Moderate -0.5
    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.
    ActivityDuration (hours)Preceded byNumber of people
    A: Telephone other friends2-3
    \(B\) : Buy food1A2
    C: Prepare food4B5
    D: Make decorations3A3
    \(E\) : Put up decorations1D3
    \(F\) : Guests arrive1C, E1
    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?
    2. 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?
    3. 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
    14 marks Standard +0.3
    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}
    1. Find the capacity of the cut \(\mathscr { C }\) shown.
    2. 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}
    3. On the diagram in the insert, show the excess capacities and potential backflows for this flow.
    4. 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).
    5. Show the final flow that results from part (iv). Explain clearly how you know that this flow is maximal.
    OCR D2 Specimen Q6
    17 marks Standard +0.8
    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\)134
    \(B\)432
    \(C\)321
    \cline { 2 - 5 }
    1. 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?
    2. Explain why Rose should never choose row \(C\) and hence reduce the game to a \(2 \times 3\) pay-off matrix.
    3. 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.
    4. Graham produces the following pay-off matrix.
      310
      012
      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.
    5. 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. {}
    OCR MEI D2 2005 June Q1
    16 marks Moderate -0.5
    1 The switching circuit in Fig. 1.1 shows switches, \(s\) for a car's sidelights, \(h\) for its dipped headlights and f for its high-intensity rear foglights. It also shows the three sets of lights. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_284_917_404_580} \captionsetup{labelformat=empty} \caption{Fig. 1.1}
    \end{figure} (Note: \(s\) and \(h\) are each "ganged" switches. A ganged switch consists of two connected switches sharing a single switch control, so that both are either on or off together.)
      1. Describe in words the conditions under which the foglights will come on. Fig. 1.2 shows a combinatorial circuit. \begin{figure}[h]
        \includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_367_1235_1183_431} \captionsetup{labelformat=empty} \caption{Fig. 1.2}
        \end{figure}
      2. Write the output in terms of a Boolean expression involving \(s , h\) and \(f\).
      3. Use a truth table to prove that \(\mathrm { s } \wedge \mathrm { h } \wedge \mathrm { f } = \sim ( \sim \mathrm { s } \vee \sim \mathrm { h } ) \wedge \mathrm { f }\).
    2. A car's first gear can be engaged ( g ) if either both the road speed is low ( r ) and the clutch is depressed ( d ), or if both the road speed is low ( r ) and the engine speed is the correct multiple of the road speed (m).
      1. Draw a switching circuit to represent the conditions under which first gear can be engaged. Use two ganged switches to represent \(r\), and single switches to represent each of \(\mathrm { d } , \mathrm { m }\) and g .
      2. Draw a combinatorial circuit to represent the Boolean expression \(\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g }\).
      3. Use Boolean algebra to prove that \(\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g } = ( ( \mathrm { r } \wedge \mathrm { d } ) \vee ( \mathrm { r } \wedge \mathrm { m } ) ) \wedge \mathrm { g }\).
      4. Draw another switching circuit to represent the conditions under which first gear can be selected, but without using a ganged switch.
    OCR MEI D2 2005 June Q2
    16 marks Moderate -0.5
    2 Karl is considering investing in a villa in Greece. It will cost him 56000 euros ( € 56000 ). His alternative is to invest his money, \(\pounds 35000\), in the United Kingdom. He is concerned with what will happen over the next 5 years. He estimates that there is a \(60 \%\) chance that a house currently worth \(€ 56000\) will appreciate to be worth \(€ 75000\) in that time, but that there is a \(40 \%\) chance that it will be worth only \(€ 55000\). If he invests in the United Kingdom then there is a \(50 \%\) chance that there will be \(20 \%\) growth over the 5 years, and a \(50 \%\) chance that there will be \(10 \%\) growth.
    1. Given that \(\pounds 1\) is worth \(€ 1.60\), draw a decision tree for Karl, and advise him what to do, using the EMV of his investment (in thousands of euros) as his criterion. In fact the \(\pounds / €\) exchange rate is not fixed. It is estimated that at the end of 5 years, if there has been \(20 \%\) growth in the UK then there is a \(70 \%\) chance that the exchange rate will stand at 1.70 euros per pound, and a \(30 \%\) chance that it will be 1.50 . If growth has been \(10 \%\) then there is a \(40 \%\) chance that the exchange rate will stand at 1.70 and a \(60 \%\) chance that it will be 1.50 .
    2. Produce a revised decision tree incorporating this information, and give appropriate advice. A financial analyst asks Karl a number of questions to determine his utility function. He estimates that for \(x\) in cash (in thousands of euros) Karl's utility is \(x ^ { 0.8 }\), and that for \(y\) in property (in thousands of euros), Karl's utility is \(y ^ { 0.75 }\).
    3. Repeat your computations from part (ii) using utility instead of the EMV of his investment. Does this change your advice?
    4. Using EMVs, find the exchange rate (number of euros per pound) which will make Karl indifferent between investing in the UK and investing in a villa in Greece.
    5. Show that, using Karl's utility function, the exchange rate would have to drop to 1.277 euros per pound to make Karl indifferent between investing in the UK and investing in a villa in Greece.