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
Edexcel D2 Q6
14 marks Standard +0.3
6. The tableau below is the initial tableau for a maximising linear programming problem.
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)1624100350
\(s\)18- 26010480
\(t\)505001360
\(P\)- 18- 7- 200000
  1. Write down the four equations represented in the initial tableau.
  2. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the Simplex algorithm. State the row operations that you use.
  3. State whether or not your last tableau is optimal. Give a reason for your answer.
Edexcel D2 Q7
14 marks Challenging +1.8
7. D2 make industrial robots. They can make up to four in any one month, but if they make more than three they need to hire additional labour at a cost of \(\pounds 300\) per month. They can store up to three robots at a cost of \(\pounds 100\) per robot per month. The overhead costs are \(\pounds 500\) in any month in which work is done. The robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock at the end of May. The order book for January to May is:
MonthJanuaryFebruaryMarchAprilMay
Number of robots required32254
Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided in the answer book. State the minimum cost.
(Total 14 marks)
Edexcel D2 Specimen Q1
5 marks Easy -1.2
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{899a26d1-7599-4051-b1cf-596542624997-2_730_1534_285_264} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.
  1. Find the values of \(x , y\), and \(z\).
    (3)
  2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
    (2)
Edexcel D2 Specimen Q2
7 marks Moderate -0.8
2. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit \(P\). The following initial tableau was obtained.
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)Value
\(r\)2041080
\(s\)14201160
\(P\)- 2- 8- 20000
  1. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use.
  2. Write down the profit equation shown in tableau \(T\).
  3. State whether tableau \(T\) is optimal. Give a reason for your answer.
Edexcel D2 Specimen Q3
11 marks Moderate -0.5
3. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.
\cline { 2 - 5 } \multicolumn{1}{c|}{}\(D\)\(E\)\(F\)Available
\(A\)21241624
\(B\)18231732
\(C\)15192514
Required203020
\cline { 1 - 4 }
\cline { 1 - 4 }
  1. Use the north-west corner rule to find an initial solution.
  2. Obtain improvement indices for each unused route.
  3. Use the stepping-stone method once to obtain a better solution and state its cost.
Edexcel D2 Specimen Q4
11 marks Moderate -0.5
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{899a26d1-7599-4051-b1cf-596542624997-5_602_1255_196_406} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} The network in Figure 2 shows the distances, in km , of the cables between seven electricity relay stations \(A , B , C , D , E , F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station. By deleting C, a lower bound for the length of the route is found to be 129 km .
  1. Find another lower bound for the length of the route by deleting \(F\). State which is the best lower bound of the two.
  2. By inspection, complete the table of least distances. The table can now be taken to represent a complete network.
  3. Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route.
Edexcel D2 Specimen Q5
6 marks Moderate -0.5
5. Three warehouses \(W , X\) and \(Y\) supply televisions to three supermarkets \(J , K\) and \(L\). The table gives the cost, in pounds, of transporting a television from each warehouse to each supermarket. The warehouses have stocks of 34,57 and 25 televisions respectively, and the supermarkets require 20, 56 and 40 televisions respectively. The total cost of transporting the televisions is to be minimised.
\(J\)\(K\)\(L\)
\(W\)363
\(X\)584
\(Y\)257
Formulate this transportation problem as a linear programming problem. Make clear your decision variables, objective function and constraints.
Edexcel D2 Specimen Q6
9 marks Standard +0.3
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{899a26d1-7599-4051-b1cf-596542624997-6_705_1424_1034_338} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} A maximin route is to be found through the network shown in Figure 3.
Complete the table in the answer book, and hence find a maximin route.
Edexcel D2 Specimen Q7
15 marks Moderate -0.5
7. Four salespersons \(A , B , C\) and \(D\) are to be sent to visit four companies 1,2,3 and 4. Each salesperson will visit exactly one company, and all companies will be visited.
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.
\cline { 2 - 5 } \multicolumn{1}{c|}{}1234
Ann26303030
Brenda30232629
Connor30252724
Dave30272521
  1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
  2. State the value of the maximum sales.
  3. Show that there is a second allocation that maximises the sales.
Edexcel D2 Specimen Q8
11 marks Standard +0.8
8. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).
IIIIII
I523
II354
  1. Verify that there is no stable solution to this game.
  2. Find the best strategy for player \(A\) and the value of the game to her.
    (Total 11 marks)
OCR D2 2006 January Q3
12 marks Standard +0.3
3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}
  1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
  2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
  3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
  4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.
OCR D2 2006 January Q4
13 marks Moderate -0.8
4 Four workers, \(A , B , C\) and \(D\), are to be allocated, one to each of the four jobs, \(W , X , Y\) and \(Z\). The table shows how much each worker would charge for each job. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}
  1. What is the total cost of the four jobs if \(A\) does \(W , B\) does \(X , C\) does \(Y\) and \(D\) does \(Z\) ?
  2. Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.
  3. What problem does the Hungarian algorithm solve?
OCR D2 2006 January Q6
15 marks Moderate -1.0
6 Lucy and Maria repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Lucy, who is playing rows, for each combination of strategies.
\cline { 2 - 5 }\(X\)\(Y\)\(Z\)
\(A\)2- 34
\cline { 2 - 5 } Lucy's\(B\)- 351
\cline { 2 - 5 } strategyy\(C\)42- 3
  1. Show that strategy \(A\) does not dominate strategy \(B\) and also that strategy \(B\) does not dominate strategy \(A\).
  2. Show that Maria will not choose strategy \(Y\) if she plays safe.
  3. Give a reason why Lucy might choose to play strategy \(B\). Lucy decides to play strategy \(A\) with probability \(p _ { 1 }\), strategy \(B\) with probability \(p _ { 2 }\) and strategy \(C\) with probability \(p _ { 3 }\). She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 3 , \\ \text { subject to } & m \leqslant 5 p _ { 1 } + 7 p _ { 3 } , \\ & m \leqslant 8 p _ { 2 } + 5 p _ { 3 } , \\ & m \leqslant 7 p _ { 1 } + 4 p _ { 2 } , \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 , \\ \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$ [You are not required to solve this problem.]
  4. Explain why 3 has to be subtracted from \(m\) in the objective row.
  5. Explain how \(5 p _ { 1 } + 7 p _ { 3 } , 8 p _ { 2 } + 5 p _ { 3 }\) and \(7 p _ { 1 } + 4 p _ { 2 }\) were obtained.
  6. Explain why \(m\) has to be less than or equal to each of the expressions in part (v). Lucy discovers that Maria does not intend ever to choose strategy \(Y\). Because of this she decides that she will never choose strategy \(B\). This means that \(p _ { 2 } = 0\).
  7. Show that the expected number of points won by Lucy when Maria chooses strategy \(X\) is \(4 - 2 p _ { 1 }\) and find a similar expression for the number of points won by Lucy when Maria chooses strategy \(Z\).
  8. Set your two expressions from part (vii) equal to each other and solve for \(p _ { 1 }\). Calculate the expected number of points won by Lucy with this value of \(p _ { 1 }\) and also when \(p _ { 1 } = 0\) and when \(p _ { 1 } = 1\). Use these values to decide how Lucy should choose between strategies \(A\) and \(C\) to maximise the expected number of points that she wins.
OCR D2 2007 January Q1
8 marks Moderate -0.8
1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked.
Attic
room
Back
room
Downstairs
room
Front
room
Phil5104
Rob1612
Sam4223
Tim3500
The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.
  1. Explain why the ratings could not be used as given in the table.
  2. Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.
OCR D2 2007 January Q2
8 marks Moderate -0.8
2 The table shows the activities involved in a project, their durations, precedences and the number of workers needed for each activity. The graph gives a schedule with each activity starting at its earliest possible time.
ActivityDuration (hours)Immediate predecessorsNumber of workers
\(A\)3-3
\(B\)5\(A\)2
C3A2
\(D\)3B1
E3C3
\(F\)5D, E2
\(G\)3\(B , E\)3
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-03_473_1591_964_278}
  1. Using the graph, find the minimum completion time for the project and state which activities are critical.
  2. Draw a resource histogram, using graph paper, assuming that there are no delays and that every activity starts at its earliest possible time. Assume that only four workers are available but that they are equally skilled at all tasks. Assume also that once an activity has been started it continues until it is finished.
  3. The critical activities are to start at their earliest possible times. List the start times for the non-critical activities for completion of the project in the minimum possible time. What is this minimum completion time?
OCR D2 2007 January Q3
8 marks Easy -2.0
3 Rebecca and Claire repeatedly play a zero-sum game in which they each have a choice of three strategies, \(X , Y\) and \(Z\). The table shows the number of points Rebecca scores for each pair of strategies. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Claire}
\(X\)\(Y\)\(Z\)
\cline { 2 - 5 }\(X\)5- 31
\cline { 2 - 5 } Rebecca\(Y\)32- 2
\cline { 2 - 5 }\(Z\)- 113
\cline { 2 - 5 }
\cline { 2 - 5 }
\end{table}
  1. If both players choose strategy \(X\), how many points will Claire score?
  2. Show that row \(X\) does not dominate row \(Y\) and that column \(Y\) does not dominate column \(Z\).
  3. Find the play-safe strategies. State which strategy is best for Claire if she knows that Rebecca will play safe.
  4. Explain why decreasing the value ' 5 ' when both players choose strategy \(X\) cannot alter the playsafe strategies.
OCR D2 2007 January Q4
10 marks Standard +0.3
4 The table gives the pay-off matrix for a zero-sum game between two players, Rowan and Colin. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Colin}
\cline { 2 - 5 }Strategy \(X\)Strategy \(Y\)Strategy \(Z\)
\cline { 2 - 5 } RowanStrategy \(P\)5- 3- 2
\cline { 2 - 5 }Strategy \(Q\)- 431
\cline { 2 - 5 }
\cline { 2 - 5 }
\end{table} Rowan makes a random choice between strategies \(P\) and \(Q\), choosing strategy \(P\) with probability \(p\) and strategy \(Q\) with probability \(1 - p\).
  1. Write down and simplify an expression for the expected pay-off for Rowan when Colin chooses strategy \(X\).
  2. Using graph paper, draw a graph to show Rowan's expected pay-off against \(p\) for each of Colin's choices of strategy.
  3. Using your graph, find the optimal value of \(p\) for Rowan.
  4. Rowan plays using the optimal value of \(p\). Explain why, in the long run, Colin cannot expect to win more than 0.25 per game.
OCR D2 2007 January Q5
12 marks Moderate -0.5
5
  1. Capacity = \(\_\_\_\_\)
  2. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
  3. Route: \(\_\_\_\_\) Flow \(=\) \(\_\_\_\_\)
  4. Maximum flow = \(\_\_\_\_\) Cut: \(\mathrm { X } = \{\) \} \(\quad \mathrm { Y } = \{\)
  5. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}
OCR D2 2007 January Q7
14 marks Moderate -0.5
7 Annie (A), Brigid (B), Carla (C) and Diane ( \(D\) ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( \(M\) ), pasting the paper ( \(P\) ), hanging and then trimming the top end of the paper ( \(H\) ) and smoothing out the air bubbles and then trimming the lower end of the paper ( \(S\) ). They will each do one of these tasks.
  • Annie does not like climbing ladders but she is prepared to do tasks \(M , P\) or \(S\)
  • Brigid gets into a mess with paste so she is only able to do tasks \(M\) or \(S\)
  • Carla enjoys hanging the paper so she wants to do task \(H\) or task \(S\)
  • Diane wants to do task \(H\)
Initially Annie chooses task \(M\), Brigid task \(S\) and Carla task \(H\).
  1. Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
  2. Maximin value \(=\) Route \(=\)
OCR D2 2008 January Q1
14 marks Easy -1.8
1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements. Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road. The table below shows the features of each of the six rooms available.
RoomFloorCan be seen from roadLooks out onto gardenHas balcony
1Ground✓
2Ground✓
3First✓✓
4First✓✓
5Second✓✓
6Second✓
  1. Draw a bipartite graph to show the possible pairings between the stars ( \(A , B , C , D , E\) and \(F\) ) and the rooms ( \(1,2,3,4,5\) and 6 ). Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
  2. Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
  3. Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room. When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.
    \multirow{2}{*}{}Room
    123456
    Arnie (A)364152
    Brigitte ( \(B\) )532416
    Charles (C)213456
    Diana (D)541326
    Edward ( \(E\) )564321
    Faye (F)564132
  4. Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.
OCR D2 2008 January Q2
17 marks Easy -1.2
2 As part of a team-building exercise the reprographics technicians (Team R) and the computer network support staff (Team C) take part in a paintballing game. The game ends when a total of 10 'hits' have been scored. Each team has to choose a player to be its captain. The number of 'hits' expected by Team R for each pair of captains is shown below.
  1. Complete the last two columns of the table in the insert.
  2. State the minimax value and write down the minimax route.
  3. Draw the network represented by the table.
OCR D2 2008 January Q3
12 marks Moderate -0.5
3
  1. StageStateActionWorkingMinimax
    \multirow{3}{*}{1}001
    103
    202
    \multirow{6}{*}{2}\multirow{2}{*}{0}0(4,\multirow{2}{*}{}
    1(2,
    \multirow{2}{*}{1}1(3,\multirow{2}{*}{}
    2(5,
    \multirow{2}{*}{2}0(2,\multirow{2}{*}{}
    2(4,
    \multirow{3}{*}{3}\multirow{3}{*}{0}0(5,\multirow{3}{*}{}
    1(3,
    2(1,
  2. Minimax value = \(\_\_\_\_\) Minimax route = \(\_\_\_\_\)
  3. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-10_958_1527_1539_351}
OCR D2 2008 January Q4
14 marks Moderate -0.5
4
  1. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}
  2. \(\_\_\_\_\)
  3. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour
  4. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(v)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_671_729_1822_315}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(vi)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_735_1816_1171}
    \end{figure} Maximum flow = \(\_\_\_\_\) gallons per hour
OCR D2 2009 January Q4
16 marks Moderate -0.5
4 Anya \(( A )\), Ben \(( B )\), Connie \(( C )\), Derek \(( D )\) and Emma \(( E )\) work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page \(( P )\), restaurant review \(( R )\), sports news \(( S )\), theatre review \(( T )\) and weather report \(( W )\). Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.
  1. Draw a bipartite graph to show the possible pairings between the writers ( \(A , B , C , D\) and \(E\) ) and the articles ( \(P , R , S , T\) and \(W\) ). On your bipartite graph, show who has been given which article by the editor.
  2. Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.
    \multirow{8}{*}{Sub-editor}\multirow{2}{*}{}Article
    \(P\)\(R\)\(S\)\(T\)\(W\)
    Jeremy ( \(J\) )5656515758
    Kath ( \(K\) )5352535454
    Laura ( \(L\) )5755525860
    Mohammed ( \(M\) )5955535957
    Natalie ( \(N\) )5757535960
    Ollie ( \(O\) )5856515657
    The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.
  3. Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs \(\pounds 0.25\), calculate the total cost of checking the articles each week.
OCR D2 2009 January Q5
20 marks Moderate -0.5
5 The local rugby club has challenged the local cricket club to a chess match to raise money for charity. Each of the top three chess players from the rugby club has played 10 chess games against each of the top three chess players from the cricket club. There were no drawn games. The table shows, for each pairing, the number of games won by the player from the rugby club minus the number of games won by the player from the cricket club. This will be called the score; the scores make a zero-sum game.
Cricket club
\cline { 2 - 5 }\cline { 2 - 5 }DougEuanFiona
\cline { 2 - 5 } Sanjeev04- 2
\cline { 2 - 5 } Rugby clubTom- 42- 4
\cline { 2 - 5 }Ursula2- 60
\cline { 2 - 5 }
\cline { 2 - 5 }
  1. How many of the 10 games between Sanjeev and Doug did Sanjeev win? How many of the 10 games between Sanjeev and Euan did Euan win? Each club must choose one person to play. They want to choose the person who will optimise the score.
  2. Find the play-safe choice for each club, showing your working. Explain how you know that the game is not stable.
  3. Which person should the cricket club choose if they know that the rugby club will play-safe and which person should the rugby club choose if they know that the cricket club will play-safe?
  4. Explain why the rugby club should not choose Tom. Which player should the cricket club not choose, and why? The rugby club chooses its player by using random numbers to choose between Sanjeev and Ursula, where the probability of choosing Sanjeev is \(p\) and the probability of choosing Ursula is \(1 - p\).
  5. Write down an expression for the expected score for the rugby club for each of the two remaining choices that can be made by the cricket club. Calculate the optimal value for \(p\). Doug is studying AS Mathematics. He removes the row representing Tom and then models the cricket club's problem as the following LP. $$\begin{array} { l l } \operatorname { maximise } & M = m - 4 \\ \text { subject to } & m \leqslant 4 x \quad + 6 z \\ & m \leqslant 2 x + 10 y + 4 z \\ & x + y + z \leqslant 1 \\ \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
  6. Show how Doug used the values in the table to get the constraints \(m \leqslant 4 x + 6 z\) and \(m \leqslant 2 x + 10 y + 4 z\). Doug uses the Simplex algorithm to solve the LP problem. His solution has \(x = 0\) and \(y = \frac { 1 } { 6 }\).
  7. Calculate the optimal value of \(M\).