Questions (33218 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 2010 June Q6
14 marks Standard +0.8
6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}
  1. Find the value of the cut \(Q\).
  2. Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(B T , D E\) and \(E T\).
    1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4 opposite.
    2. Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
    3. Illustrate the maximum flow on Figure 5 opposite.
  4. Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
    \end{figure} Figure 4 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
    \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}
AQA D2 2011 June Q1
13 marks Moderate -0.5
1 Figure 1 below shows an activity diagram for a cleaning project. The duration of each activity is given in days.
  1. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
  2. Find the critical paths and state the minimum time for completion of the project.
  3. Find the activity with the greatest float time and state the value of its float time.
  4. On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as late as possible.
    1. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-02_846_1488_1391_292}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1295_1714_219_150} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(d)} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1023_1584_1589_278}
      \end{figure}
AQA D2 2011 June Q2
9 marks Moderate -0.3
2 The times taken, in minutes, for five people, \(A , B , C , D\) and \(E\), to complete each of five different puzzles are recorded in the table below.
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)
Puzzle 11613151615
Puzzle 21416161418
Puzzle 31412181316
Puzzle 41515171214
Puzzle 51317161415
Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.
  1. By reducing the columns first and then the rows, show that the new table of values is
    31041
    0\(k\)013
    10312
    23200
    05121
    State the value of the constant \(k\).
    1. Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
    2. Use augmentation to produce a table where five lines are required to cover the zeros.
  3. Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
  4. Find the minimum total time for completing the five puzzles.
  5. Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.
AQA D2 2011 June Q3
15 marks Easy -1.8
3
  1. Two people, Tom and Jerry, play a zero-sum game. The game is represented by the following pay-off matrix for Tom.
    Jerry
    \cline { 2 - 5 }StrategyABC
    TomI- 45- 3
    \cline { 2 - 5 }II- 3- 28
    \cline { 2 - 5 }III- 76- 2
    Show that this game has a stable solution and state the play-safe strategy for each player.
  2. Rohan and Carla play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Rohan. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Carla} Rohan
    Strategy\(\mathbf { C } _ { \mathbf { 1 } }\)\(\mathbf { C } _ { \mathbf { 2 } }\)\(\mathbf { C } _ { \mathbf { 3 } }\)
    \(\mathbf { R } _ { \mathbf { 1 } }\)35- 1
    \(\mathbf { R } _ { \mathbf { 2 } }\)1- 24
    \end{table}
    1. Find the optimal mixed strategy for Rohan and show that the value of the game is \(\frac { 3 } { 2 }\).
    2. Carla plays strategy \(\mathrm { C } _ { 1 }\) with probability \(p\), and strategy \(\mathrm { C } _ { 2 }\) with probability \(q\). Find the values of \(p\) and \(q\) and hence find the optimal mixed strategy for Carla.
      (4 marks)
      \includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-10_2486_1714_221_153}
      \includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-11_2486_1714_221_153}
AQA D2 2011 June Q4
15 marks Moderate -0.8
4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 2 x + 6 y + k z\), where \(k\) is a constant. The initial Simplex tableau is given below.
\(\boldsymbol { P }\)\(x\)\(y\)\(\boldsymbol { Z }\)\(\boldsymbol { s }\)\(\boldsymbol { t }\)\(\boldsymbol { u }\)value
1-2-6\(- k\)0000
0531010015
076401028
043600112
  1. In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
    1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
    2. Given that the optimal value has not been reached, find the possible values of \(k\).
  3. In the case when \(k = 20\) :
    1. perform one further iteration;
    2. interpret the final tableau and state the values of the slack variables.
AQA D2 2011 June Q5
14 marks Moderate -0.5
5 The network shows the evacuation routes along corridors in a college, from two teaching areas to the exit, in case of a fire alarm sounding. \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-14_729_1013_434_497} The two teaching areas are at \(A\) and \(G\) and the exit is at \(X\). The number on each edge represents the maximum number of people that can travel along a particular corridor in one minute.
  1. Find the value of the cut shown on the diagram.
  2. Find the maximum flow along each of the routes \(A B D X , G F B X\) and \(G H E X\) and enter their values in the table on Figure 3 opposite.
    1. Taking your answers to part (b) as the initial flow, use the labelling procedure on Figure 3 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 4, illustrate a possible flow along each edge corresponding to this maximum flow.
  4. During one particular fire drill, there is an obstruction allowing no more than 45 people per minute to pass through vertex \(B\). State the maximum number of people that can move through the network per minute during this fire drill. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_905_1559_331_292}
    \end{figure} Figure 4 \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_689_851_1370_598} Maximum flow is \(\_\_\_\_\) people per minute.
AQA D2 2011 June Q6
9 marks Moderate -0.5
6 Bob is planning to build four garden sheds, \(A , B , C\) and \(D\), at the rate of one per day. The order in which they are built is a matter of choice, but the costs will vary because some of the materials left over from making one shed can be used for the next one. The expected profits, in pounds, are given in the table below.
\multirow{2}{*}{Day}\multirow{2}{*}{Already built}Expected profit (£)
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)
Monday-50657080
\multirow{4}{*}{Tuesday}A-728384
B60-8083
C5768-85
D627081-
\multirow{6}{*}{Wednesday}\(\boldsymbol { A }\) and \(\boldsymbol { B }\)--8488
\(\boldsymbol { A }\) and \(\boldsymbol { C }\)-71-82
\(A\) and \(D\)-7483-
\(\boldsymbol { B }\) and \(\boldsymbol { C }\)65--86
\(\boldsymbol { B }\) and \(\boldsymbol { D }\)69-85-
\(\boldsymbol { C }\) and \(\boldsymbol { D }\)6673--
\multirow{4}{*}{Thursday}\(\boldsymbol { A } , \boldsymbol { B }\) and \(\boldsymbol { C }\)---90
\(\boldsymbol { A } , \boldsymbol { B }\) and \(\boldsymbol { D }\)--87-
\(A , C\) and \(D\)-76--
\(\boldsymbol { B } , \boldsymbol { C }\) and \(\boldsymbol { D }\)70---
By completing the table of values opposite, or otherwise, use dynamic programming, working backwards from Thursday, to find the building schedule that maximises the total expected profit.
Stage (Day)State (Sheds already built)Action (Shed to build)CalculationProfit in pounds
Thursday\(A , B , C\)D90
\(A , B , D\)C87
A, C, DB76
B, C, DA70
WednesdayA, BC\(84 + 90\)174
D\(88 + 87\)175
A, \(C\)B\(71 + 90\)161
D\(82 + 76\)158
A, \(D\)B
C
\(B , C\)A
D
\(B , D\)A
C
\(C , D\)A
B
TuesdayAB\(72 + 175\)247
C\(83 + 161\)244
D
Monday
\section*{Schedule}
\cline { 2 - 5 } \multicolumn{1}{c|}{}MondayTuesdayWednesdayThursday
Shed to build
\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-18_2486_1714_221_153}
AQA D2 2013 June Q1
9 marks Moderate -0.8
1 Figure 1 opposite shows an activity diagram for a project. The duration required for each activity is given in hours. The project is to be completed in the minimum time.
  1. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
  2. Find the critical path.
  3. Find the float time of activity \(E\).
  4. Given that activities \(H\) and \(K\) will both overrun by 10 hours, find the new minimum completion time for the project.
    \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-02_1515_1709_1192_153}
    \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-03_1656_869_627_611}
    \end{figure}
AQA D2 2013 June Q2
8 marks Easy -1.2
2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}
  1. Write down the capacity of edge \(E F\).
  2. State the source vertex.
  3. State the sink vertex.
  4. Find the values of \(x , y\) and \(z\).
  5. Find the value of the initial flow.
  6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).
AQA D2 2013 June Q3
12 marks Moderate -0.3
3 The table shows the times taken, in minutes, by five people, \(A , B , C , D\) and \(E\), to carry out the tasks \(V , W , X , Y\) and \(Z\).
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)
Task \(\boldsymbol { V }\)10011011210295
Task \(\boldsymbol { W }\)125130110120115
Task \(\boldsymbol { X }\)105110101108120
Task \(\boldsymbol { Y }\)115115120135110
Task \(\boldsymbol { Z }\)1009899100102
Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.
  1. By reducing the columns first, and then the rows, show that the new table of values is
    0121320
    14210\(k\)9
    3100623
    026200
    00007
    and state the value of the constant \(k\).
  2. Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
  3. Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
  4. Find the minimum total time.
AQA D2 2013 June Q4
9 marks Standard +0.3
4 A haulage company, based in town \(A\), is to deliver a tall statue to town \(K\). The statue is being delivered on the back of a lorry. The network below shows a system of roads. The number on each edge represents the height, in feet, of the lowest bridge on that road. The company wants to ensure that the height of the lowest bridge along the route from \(A\) to \(K\) is maximised. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-10_869_1593_715_221} 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.
StageStateFromValue
1H\(K\)
I\(K\)
JK
2
Optimal route is
AQA D2 2013 June Q5
15 marks Easy -2.5
5 Romeo and Juliet play a zero-sum game. The game is represented by the following pay-off matrix for Romeo.
Juliet
\cline { 2 - 5 }StrategyDEF
A4- 40
\cline { 2 - 5 } RomeoB- 2- 53
\cline { 2 - 5 }C21- 2
\cline { 2 - 5 }
\cline { 2 - 5 }
  1. Find the play-safe strategy for each player.
  2. Show that there is no stable solution.
  3. Explain why Juliet should never play strategy D.
    1. Explain why the following is a suitable pay-off matrix for Juliet.
      45- 1
      0- 32
    2. Hence find the optimal strategy for Juliet.
    3. Find the value of the game for Juliet.
AQA D2 2013 June Q6
11 marks Standard +0.3
6
  1. Display the following linear programming problem in a Simplex tableau.
    Maximise \(\quad P = 4 x + 3 y + z\) subject to $$\begin{aligned} & 2 x + y + z \leqslant 25 \\ & x + 2 y + z \leqslant 40 \\ & x + y + 2 z \leqslant 30 \end{aligned}$$ and \(x \geqslant 0 , \quad y \geqslant 0 , \quad z \geqslant 0\).
  2. The first pivot to be chosen is from the \(x\)-column. 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 2013 June Q7
11 marks Moderate -0.5
7 Figure 2 shows a network of pipes. Water from two reservoirs, \(R _ { 1 }\) and \(R _ { 2 }\), is used to supply three towns, \(T _ { 1 } , T _ { 2 }\) and \(T _ { 3 }\).
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.
  1. Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
    1. Use the initial flow and the labelling procedure on Figure 3 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 4, illustrate a possible flow along each edge corresponding to this maximum flow.
  3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
    \end{figure}
    \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
    \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}
Edexcel D2 2006 January Q1
13 marks Moderate -0.8
  1. A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.
Hot dogs and beef burgers (H)Ice cream (I)Popcorn, candyfloss and drinks (P)Snacks and hot drinks (S)
Site A267272276261
Site B264271278263
Site C267273275263
Site D261269274257
Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.
(Total 13 marks)
Edexcel D2 2006 January Q2
12 marks Standard +0.8
2. An engineering firm makes motors. They can make up to five in any one month, but if they make more than four they have to hire additional premises at a cost of \(\pounds 500\) per month. They can store up to two motors for \(\pounds 100\) per motor per month. The overhead costs are \(\pounds 200\) in any month in which work is done.
Motors are delivered to buyers at the end of each month. There are no motors in stock at the beginning of May and there should be none in stock after the September delivery. The order book for motors is:
MonthMayJuneJulyAugustSeptember
Number of motors33754
Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided below.
Stage (month)State (Number in store at start of month)Action (Number made in month)Destinatio n (Number in store at end of month)Value (cost)
\section*{Production schedule}
MonthMayJuneJulyAugustSeptember
Number to be
made
Total cost: \(\_\_\_\_\)
Edexcel D2 2006 January Q3
8 marks Moderate -0.5
3. Three depots, F, G and H, supply petrol to three service stations, S, T and U. The table gives the cost, in pounds, of transporting 1000 litres of petrol from each depot to each service station. F, G and H have stocks of 540000,789000 and 673000 litres respectively.
S, T and U require 257000,348000 and 412000 litres respectively. The total cost of transporting the petrol is to be minimised.
STU
F233146
G353851
H415063
Formulate this problem as a linear programming problem. Make clear your decision variables, objective function and constraints.
Edexcel D2 2006 January Q4
16 marks Moderate -0.8
4. The following minimising transportation problem is to be solved.
JKSupply
A12159
B81713
C4912
Demand911
  1. Complete the table below.
    JKLSupply
    A12159
    B81713
    C4912
    Demand91134
  2. Explain why an extra demand column was added to the table above. A possible north-west corner solution is:
    JKL
    A90
    B112
    C12
  3. Explain why it was necessary to place a zero in the first row of the second column. After three iterations of the stepping-stone method the table becomes:
    JKL
    A81
    B13
    C93
  4. Taking the most negative improvement index as the entering square for the stepping stone method, solve the transportation problem. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.
Edexcel D2 2006 January Q5
13 marks Moderate -0.5
5. A two-person zero-sum game is represented by the following pay-off matrix for player A.
B plays 1B plays 2B plays 3B plays 4
A plays 1- 213- 1
A plays 2- 1321
A plays 3- 420- 1
A plays 41- 2- 13
  1. Verify that there is no stable solution to this game.
  2. Explain why the \(4 \times 4\) game above may be reduced to the following \(3 \times 3\) game.
  3. Formulate the \(3 \times 3\) game as a linear programming problem for player A. Write the
    - 213
    - 132
    1- 2- 1
    constraints as inequalities. Define your variables clearly.
Edexcel D2 2006 January Q6
13 marks Moderate -0.5
6. The network in the figure above, shows the distances in km , along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A . By deleting D, a lower bound for the length of the route was found to be 586 km .
By deleting F, a lower bound for the length of the route was found to be 590 km .
  1. By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer.
  2. By inspection complete the table of least distances. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(8)
    (8)
    (Total 13 marks)} \includegraphics[alt={},max width=\textwidth]{a5d69a77-c196-483c-a550-1a55363555af-3_780_889_1069_1078}
    \end{figure} (4) The table can now be taken to represent a complete network. The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km .
    Starting at F, an upper bound for the length of the route was found to be 707 km .
  3. Starting at C , use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the
    ABCDEFGH
    A-848513817314952
    B84-13077126213222136
    C85130-53888392
    D1387753-49190
    E1731268849-100180215
    F21383100-163115
    G14922292180163-97
    H5213619021511597-
    three, giving a reason for your answer.
    (4) (Total 13 marks)
Edexcel D2 2006 January Q7
11 marks Moderate -0.5
7.
  1. Define the terms
    1. cut,
    2. minimum cut, as applied to a directed network flow. \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299} The figure above shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
  2. State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\). Given that one of these two cuts is a minimum cut,
  3. find a maximum flow pattern by inspection, and show it on the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
  4. Find a second minimum cut for this network. In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
  5. State, with a reason, which of these arcs should be added, and the value of the increased flow.
Edexcel D2 2002 June Q1
8 marks Easy -1.2
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-01_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 2002 June Q2
8 marks Easy -1.8
2. A two-person zero-sum game is represented by the following pay-off matrix for player \(A\).
\(B\)
IIIIIIIV
\multirow{3}{*}{\(A\)}I- 4- 5- 24
II- 11- 12
III05- 2- 4
IV- 13- 11
  1. Determine the play-safe strategy for each player.
  2. Verify that there is a stable solution and determine the saddle points.
  3. State the value of the game to \(B\).
Edexcel D2 2002 June Q3
10 marks Standard +0.3
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-03_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 2002 June Q4
8 marks Moderate -0.5
4. Andrew ( \(A\) ) and Barbara ( \(B\) ) play a zero-sum game. This game is represented by the following payoff matrix for Andrew. $$A \left( \begin{array} { c c c } & B & \\ 3 & 5 & 4 \\ 1 & 4 & 2 \\ 6 & 3 & 7 \end{array} \right)$$
  1. Explain why this matrix may be reduced to $$\left( \begin{array} { l l } 3 & 5 \\ 6 & 3 \end{array} \right)$$
  2. Hence find the best strategy for each player and the value of the game.
    (8)