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
AQA D2 2014 June Q1
9 marks Moderate -0.8
1 A major project has been divided into a number of tasks, as shown in the table. The minimum time required to complete each task is also shown. \section*{Answer space for question 1}
\includegraphics[max width=\textwidth, alt={}]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-03_424_410_296_685}
AQA D2 2014 June Q2
5 marks Easy -1.2
2 Alex and Roberto play a zero-sum game. The game is represented by the following pay-off matrix for Alex. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Roberto}
\multirow{5}{*}{Alex Strategy}DEFG
A5- 4- 11
B4301
C- 30- 5- 2
\end{table}
  1. Show that this game has a stable solution and state the play-safe strategy for each player.
  2. List any saddle points.
AQA D2 2014 June Q3
9 marks Moderate -0.5
3 The diagram below shows a network of pipes with source \(A\) and \(\operatorname { sink } J\). The capacity of each pipe is given by the number on each edge. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-08_816_1280_443_386}
  1. Find the values of the cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
  2. Find by inspection a flow of 60 units, with flows of 25,10 and 25 along \(H J , G J\) and \(I J\) respectively. Illustrate your answer on Figure 1.
    1. On a certain day the section \(E H\) is blocked, as shown on Figure 2. Find, by inspection or otherwise, the maximum flow on this day and illustrate your answer on Figure 2.
    2. Show that the flow obtained in part (c)(i) is maximal. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_595_1065_376_475}
      \end{figure} (c) \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_617_1061_1142_477}
      \end{figure} Maximum flow = \(\_\_\_\_\)
AQA D2 2014 June Q4
11 marks Standard +0.3
4
  1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l c } \text { Maximise } & P = 3 x + 6 y + 2 z \\ \text { subject to } & x + 3 y + 2 z \leqslant 11 \\ & 3 x + 4 y + 2 z \leqslant 21 \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  2. The first pivot to be chosen is from the \(y\)-column. Perform one iteration of the Simplex method.
  3. Perform one further iteration.
  4. Interpret the tableau obtained in part (c) and state the values of your slack variables.
AQA D2 2014 June Q5
8 marks Standard +0.3
5 Mark and Owen play a zero-sum game. The game is represented by the following pay-off matrix for Mark.
Owen
\cline { 2 - 5 }\cline { 2 - 5 }StrategyDEF
A41- 1
\cline { 2 - 5 } MarkB3- 2- 2
\cline { 2 - 5 }C- 203
  1. Explain why Mark should never play strategy B.
  2. It is given that the value of the game is 0.6 . Find the optimal strategy for Owen.
    (You are not required to find the optimal mixed strategy for Mark.)
    [0pt] [7 marks]
AQA D2 2014 June Q6
12 marks Standard +0.3
6 The network below has 11 vertices and 16 edges connecting some pairs of vertices. The numbers on the edges are their weights. The weight of the edge \(D G\) is given in terms of \(x\). There are three routes from \(A\) to \(K\) that have the same minimum total weight. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-16_863_1444_552_299} Working backwards from \(\boldsymbol { K }\), use dynamic programming, to find:
  1. the minimum total weight from \(A\) to \(K\);
  2. the value of \(x\);
  3. the three routes corresponding to the minimum total weight. You must complete the table opposite as your solution.
    [0pt] [12 marks] \section*{Answer space for question 6}
    StageStateFromCalculationValue
    1IK
    \(J\)K
AQA D2 2014 June Q7
11 marks Standard +0.3
7 The table shows the times taken, in minutes, by four people, \(A , B , C\) and \(D\), to carry out the tasks \(W , X , Y\) and \(Z\). Some of the times are subject to the same delay of \(x\) minutes, where \(4 < x < 11\).
AQA D2 2014 June Q8
10 marks Moderate -0.8
8 An activity diagram for a project is shown below. The duration of each activity is given in weeks. The earliest start time and the latest finish time for each activity are shown on the diagram. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-22_640_1626_475_209}
  1. Find the values of \(x , y\) and \(z\).
  2. State the critical path.
  3. Some of the activities can be speeded up at an additional cost. The following table lists the activities that can be speeded up together with the minimum possible duration of these activities. The table also shows the additional cost of reducing the duration of each of these activities by one week.
AQA D2 2015 June Q1
14 marks Moderate -0.5
1 Figure 2, on the page opposite, shows an activity diagram for a project. Each activity requires one worker. The duration required for each activity is given in hours.
  1. On Figure 1 below, complete the precedence table.
  2. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 2.
  3. List the critical paths.
  4. Find the float time of activity \(E\).
  5. Using Figure 3 opposite, draw a Gantt diagram to illustrate how the project can be completed in the minimum time, assuming that each activity is to start as early as possible.
  6. Given that there is only one worker available for the project, find the minimum completion time for the project.
  7. Given that there are two workers available for the project, find the minimum completion time for the project. Show a suitable allocation of tasks to the two workers.
    [0pt] [2 marks] \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1}
    ActivityImmediate predecessor(s)
    A
    B
    C
    D
    E
    \(F\)
    G
    \(H\)
    I
    J
    \end{table} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-03_1071_1561_376_278}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-03_801_1301_1644_420}
    \end{figure}
AQA D2 2015 June Q2
8 marks Moderate -0.8
2 Stan and Christine play a zero-sum game. The game is represented by the following pay-off matrix for Stan. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Christine}
\multirow{5}{*}{Stan}StrategyDEF
A3- 3- 1
B- 1- 42
C10- 3
\cline { 2 - 5 }- 2
\end{table}
  1. Find the play-safe strategy for each player.
  2. Show that there is no stable solution.
  3. Explain why a suitable pay-off matrix for Christine is given by
AQA D2 2015 June Q3
11 marks Moderate -0.3
3 In the London 2012 Olympics, the Jamaican \(4 \times 100\) metres relay team set a world record time of 36.84 seconds. Athletes take different times to run each of the four legs.
The coach of a national athletics team has five athletes available for a major championship. The lowest times that the five athletes take to cover each of the four legs is given in the table below. The coach is to allocate a different athlete from the five available athletes, \(A , B , C , D\) and \(E\), to each of the four legs to produce the lowest total time.
Leg 1Leg 2Leg 3Leg 4
Athlete \(\boldsymbol { A }\)9.848.918.988.70
Athlete \(\boldsymbol { B }\)10.289.069.249.05
Athlete \(\boldsymbol { C }\)10.319.119.229.18
Athlete \(\boldsymbol { D }\)10.049.079.199.01
Athlete \(\boldsymbol { E }\)9.918.959.098.74
Use the Hungarian algorithm, by reducing the columns first, to assign an athlete to each leg so that the total time of the four athletes is minimised. State the allocation of the athletes to the four legs and the total time.
[0pt] [11 marks]
\includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-08_1200_1705_1507_155}
AQA D2 2015 June Q4
13 marks Standard +0.8
4
  1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l r } \text { Maximise } & P = 2 x + 3 y + 4 z \\ \text { subject to } & x + y + 2 z \leqslant 20 \\ & 3 x + 2 y + z \leqslant 30 \\ & 2 x + 3 y + z \leqslant 40 \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
    1. The first pivot to be chosen is from the \(z\)-column. Identify the pivot and explain why this particular value is chosen.
    2. Perform one iteration of the Simplex method.
    1. Perform one further iteration.
    2. Interpret your final tableau and state the values of your slack variables.
AQA D2 2015 June Q5
11 marks Moderate -0.5
5 Tom is going on a driving holiday and wishes to drive from \(A\) to \(K\).
The network below shows a system of roads. The number on each edge represents the maximum altitude of the road, in hundreds of metres above sea level. Tom wants to ensure that the maximum altitude of any road along the route from \(A\) to \(K\) is minimised. \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-14_1522_1363_660_342}
  1. Working backwards from \(\boldsymbol { K }\), use dynamic programming to find the optimal route when driving from \(A\) to \(K\). You must complete the table opposite as your solution.
  2. Tom finds that the road \(C F\) is blocked. Find Tom's new optimal route and the maximum altitude of any road on this route.
    [0pt] [2 marks] \section*{Answer space for question 5}
    StageStateFromValue
    1H\(K\)
    I\(K\)
    \(J\)\(K\)
    2
    1. Optimal route is \(\_\_\_\_\)
    2. Tom's route is \(\_\_\_\_\) Maximum altitude is \(\_\_\_\_\) Figure 4 below shows a network of pipes.
      The capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-18_1039_1623_561_191}
      \end{figure}
    3. Find the value of the initial flow.
      1. Use the initial flow and the labelling procedure on Figure 5 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
      2. State the value of the maximum flow and, on Figure 6, illustrate a possible flow along each edge corresponding to this maximum flow.
    5. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
    6. On a particular day, there is a restriction at vertex \(G\) which allows a maximum flow through \(G\) of 30 . Find, by inspection, the maximum flow through the network on this day.
    7. Initial flow \(=\) \(\_\_\_\_\)
      1. Figure 5 \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-19_2158_1559_543_296} \(7 \quad\) Arsene and Jose play a zero-sum game. The game is represented by the following pay-off matrix for Arsene, where \(x\) is a constant. The value of the game is 2.5 .
        Jose
        \cline { 2 - 4 }StrategyCD
        \cline { 2 - 4 } ArseneA\(x + 3\)1
        \cline { 2 - 4 }B\(x + 1\)3
        \cline { 2 - 4 }
        \cline { 2 - 4 }
    9. Find the optimal mixed strategy for Arsene.
    10. Find the value of \(x\).
      \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-22_1636_1707_1071_153}
      \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-24_2288_1705_221_155}
AQA D2 2016 June Q1
12 marks Moderate -0.5
1
Figure 1 below shows an activity diagram for a project. Each activity requires one worker. The duration required for each activity is given in hours.
  1. Find the earliest start time and the latest finish time for each activity and insert these values on Figure 1.
    1. Find the critical path.
    2. Find the float time of activity \(F\).
  3. Using Figure 2 on page 3, draw a resource histogram to illustrate how the project can be completed in the minimum time, assuming that each activity is to start as early as possible.
    1. Given that there are two workers available for the project, find the minimum completion time for the project.
    2. Write down an allocation of tasks to the two workers that corresponds to your answer in part (d)(i). \section*{Answer space for question 1} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-02_687_1655_1941_189}
      \end{figure} \section*{Answer space for question 1} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-03_1115_1575_434_283}
      \end{figure}
      \includegraphics[max width=\textwidth, alt={}]{34de3f03-a275-44fb-88b2-b88038bcec97-03_1024_1593_1683_267}
AQA D2 2016 June Q2
10 marks Standard +0.3
2 Alan, Beth, Callum, Diane and Ethan work for a restaurant chain. The costs, in pounds, for the five people to travel to each of five different restaurants are recorded in the table below. Alan cannot travel to restaurant 1 and Beth cannot travel to restaurants 3 and 5, as indicated by the asterisks in the table.
AQA D2 2016 June Q3
13 marks Standard +0.8
3
Maximise \(\quad P = 2 x - 3 y + 4 z\) subject to \(\quad x + 2 y + z \leqslant 20\) \(x - y + 3 z \leqslant 24\) \(3 x - 2 y + 2 z \leqslant 30\) and \(\quad x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
  1. Display the linear programming problem in a Simplex tableau.
    1. The first pivot to be chosen is from the \(z\)-column. Identify the pivot and explain why this particular value is chosen.
    2. Perform one iteration of the Simplex method.
    3. Perform one further iteration.
  3. Interpret your final tableau and state the values of your slack variables.
    [0pt] [3 marks]
AQA D2 2016 June Q4
15 marks Standard +0.8
4 Monica and Vladimir play a zero-sum game. The game is represented by the following pay-off matrix for Monica.
AQA D2 2016 June Q5
11 marks Moderate -0.5
5 Robert is planning to renovate four houses, \(A , B , C\) and \(D\), at the rate of one per month. The houses can be renovated in any order but the costs will vary because some of the materials left over from renovating one house can be used for the next one. The expected profits, in hundreds of pounds, are given in the table below.
AQA D2 2016 June Q6
14 marks Standard +0.3
6 The network shows a system of pipes with lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{34de3f03-a275-44fb-88b2-b88038bcec97-22_817_744_397_648}
    1. Find the value of the cut \(X\).
    2. Hence state what can be deduced about the maximum flow from \(A\) to \(H\).
  2. Figure 3 shows a partially completed diagram for a feasible flow of 28 litres per second from \(A\) to \(H\). Indicate, on Figure 3, the flows along the edges \(B D , B E\) and \(C D\).
    1. Using your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4.
    2. Use flow augmentation on Figure 4 to find the maximum flow from \(A\) to \(H\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
    3. State the maximum flow and indicate a maximum flow on Figure 5. \section*{Answer space for question 6} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-23_682_689_312_397}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-23_935_1477_1037_365}
      \end{figure} Figure 5
      \includegraphics[max width=\textwidth, alt={}]{34de3f03-a275-44fb-88b2-b88038bcec97-24_2032_1707_219_153}
Edexcel D2 Q1
Easy -1.2
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-002_675_1052_378_485}
\end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .
  1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
  2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
    (3)
  3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
    (1)
  4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
    (2)
Edexcel D2 Q3
Standard +0.3
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-004_764_1514_283_141}
\end{figure} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.
  1. Complete the table in the answer booklet.
    (8)
  2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route.
    (2)
Edexcel D2 Q8
Moderate -0.3
8. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1404_285_343}
\end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
  1. Write down the source vertices. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1402_1170_343}
    \end{figure} Figure 5 shows a feasible flow through the same network.
  2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
  3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
  4. Show the maximal flow on Diagram 2 and state its value.
  5. Prove that your flow is maximal.
Edexcel D2 Q11
Standard +0.3
11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-011_723_1172_476_337}
\end{figure}
  1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
    1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
    1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.
Edexcel D2 Q12
Moderate -0.5
12. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-012_618_1211_253_253}
\end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.
  1. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
  2. State the maximum flow along
    1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
    2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
  3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
  4. From your final flow pattern, determine the number of van loads passing through \(B\) each day.
Edexcel D2 2017 June Q1
7 marks Moderate -0.8
1.
ABCDEF
A-8375826997
B83-9410377109
C7594-97120115
D8210397-105125
E6977120105-88
F9710911512588-
The table above shows the least distances, in km , between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .
  1. Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
    1. the minimum spanning tree method,
    2. the nearest neighbour algorithm.
      (5) By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km . By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
  2. Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.
    (2)