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
Edexcel D1 Q3
8 marks Challenging +1.2
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-03_734_1353_196_317} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Figure 1 shows a graph in which \(y \geq 0\).
Given that the graph is a weighted network,
  1. find the range of values for the path of lowest weight from \(S\) to \(T\). Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
  2. find the range of values for the maximum flow from \(S\) to \(T\).
  3. Give an example of a practical problem which could be solved by using:
    1. the weighted network in part (a),
    2. the capacitated network in part (b).
Edexcel D1 Q4
11 marks Moderate -0.8
4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.
MinisterGovernment Position
\(P\)Chancellor ( \(C\) )
\(Q\)Foreign Secretary ( \(F\) ), Minister for Education ( \(E\) )
\(R\)Minister for Defence ( \(D\) ), Minister for Industry ( \(I\) )
SMinister for Defence ( \(D\) ), Home Secretary ( \(H\) )
\(T\)Home Secretary (H)
\(U\)Chancellor ( \(C\) ), Foreign Secretary ( \(F\) )
  1. Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
  2. Draw this initial matching.
  3. Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
  4. Explain why no complete matching is now possible.
    (2 marks)
Edexcel D1 Q5
11 marks Moderate -0.5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-05_863_1061_223_360} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} The network in Figure 2 represents the streets near Randolph Square in Newtown, Edinburgh. The weightings represent the average time, in seconds, taken to travel along each road in either direction. The large values for the roads \(C D\) and \(J L\) are due to traffic lights. In the course of his work, a van driver must travel along each road at least once each day. He starts and finishes at his depot, \(F\), and wishes to minimise the total time that this takes.
  1. Describe an appropriate algorithm that can be used to find this minimum time.
    (3 marks)
  2. Apply this algorithm to find a route that the driver can take and state the total time he can expect to spend on this journey each day.
    (5 marks)
    The section of road \(A B\) is to be turned into a pedestrian precinct.
  3. Assuming that the driver must still travel along all the other roads at least once each day, find the modified time he can expect to spend on his daily journey Comment on your answer.
    (3 marks)
Edexcel D1 Q6
16 marks Moderate -0.3
6. The table below shows the maximum flows possible within a system.
To From\(S\)\(A\)\(B\)\(C\)D\(T\)
S-353055--
A-----50
B-12-8-20
C----1530
D-----14
T------
For example, the maximum flow from \(B\) to \(A\) is 12 units.
  1. Draw a digraph to represent this information.
  2. Give the capacity of the cut \(\{ S , A , B , C \} \mid \{ D , T \}\).
  3. Find the minimum cut, stating its capacity, and expressing it in the form \(\{ \quad \} \mid \{ \quad \}\).
  4. Use the labelling procedure to find the maximum flow from \(S\) to \(T\). You should list each flow-augmenting route you find together with its flow.
  5. Explain how you know that you have found the maximum possible flow.
  6. Give an example of a practical situation that could be modelled by the original table.
Edexcel D1 Q7
16 marks Standard +0.8
7. A fitness centre runs introductory courses aimed at the following groups of customers: Pensioners, who will be charged \(\pounds 4\) for a 2 -hour session.
Other adults, who will be charged \(\pounds 10\) for a 4 -hour session.
Children, who will be charged \(\pounds 2\) for a 1 -hour session.
Let the number of pensioners, other adults, and children be \(x , y\) and \(z\) respectively.
Regulations state that the number of pensioners, \(x\), must be at most 5 more than the number of adults, \(y\). There must also be at least twice as many adults, \(y\), as there are children, \(z\). The centre is able to supervise up to 40 person-hours each day at the centre and wishes to maximise the revenue \(( \pounds R )\) that can be earned each day from these sessions. You may assume that the places on any courses that the centre runs will be filled.
  1. Modelling this situation as a linear programming problem, write down the constraints and objective function in terms of \(x , y\) and \(z\). Using the Simplex algorithm, the following initial tableau is obtained.
  2. \(\_\_\_\_\)
Edexcel D1 Q1
6 marks Easy -1.2
  1. Make plane drawings of each of the graphs shown in Figure 1. Graph 1 \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-02_1155_664_278_529} \captionsetup{labelformat=empty} \caption{Fig. 1}
    \end{figure}
  2. State the name given to Graph 1 and write down the features that identify it.
  3. State, with a reason, whether it is possible to add further arcs to Graph 2 such that it remains a simple connected graph. No further vertices may be added.
    (1 mark)
Edexcel D1 Q2
7 marks Moderate -0.8
2. This question should be answered on the sheet provided. A builder is going to put up houses on a plot of land of area \(12000 \mathrm {~m} ^ { 2 }\).
There are 5 designs to choose from and no more than one of each design can be built.
DesignKendalMilvertonArlingtonElfordGrosvenor
Plot area ('000 \(\mathrm { m } ^ { 2 }\) )3113510
Value ( \(\pounds ^ { \prime } 000 \mathrm {~s}\) )1001904080120
The builder needs to work out which houses he should build in order to maximise the total value of the site. He does this using a tree diagram and each "branch" on the tree is terminated when the total area of land on that branch exceeds \(12000 \mathrm {~m} ^ { 2 }\).
    1. Complete the tree diagram so that each branch is terminated or all choices have been considered.
    2. Hence, determine which designs the builder should use and the total value that the site will have when completed.
  2. Explain how this method could be altered if more than one of each design is allowed.
Edexcel D1 Q3
7 marks Easy -1.2
3. (a) Draw a graph with 6 vertices, each of degree 1 .
(b) Draw two graphs with 6 vertices, each of degree 2 such that:
  1. the graph is connected,
  2. the graph is not connected. A simple connected graph has 5 vertices each of degree \(x\).
    (c) Find the possible values of \(x\) and explain your answer.
    (d) For each value of \(x\) you found in part (c) draw a possible graph.
Edexcel D1 Q4
12 marks Standard +0.3
4. A company produces \(x _ { 1 }\) finished articles at the end of January, \(x _ { 2 }\) finished articles at the end of February, \(x _ { 3 }\) finished articles at the end of March, \(x _ { 4 }\) finished articles at the end of April. Other details for each month are as follows:
MonthJanuaryFebruaryMarchApril
Demand at end of month200350250200
Production costs per article£1000£1800£1600£1900
The cost of storing each finished but unsold article is \(\pounds 500\) per month. Thus, for example, any article unsold at the end of January would incur a \(\pounds 500\) charge if it is stored until the end of February or a \(\pounds 1000\) charge if it is stored until the end of March. There must be no unsold stock at the end of April.
The selling price of each article is \(\pounds 4000\) and the total profit ( \(\pounds P\) ) must be maximised.
  1. Rewrite \(x _ { 4 }\) in terms of the other 3 variables.
  2. Show that the total cost incurred \(( \pounds C )\) is given by: $$C = 600 x _ { 1 } + 900 x _ { 2 } + 200 x _ { 3 } + 1125000$$
  3. Hence, show that \(P = { } ^ { - } 600 x _ { 1 } - 900 x _ { 2 } - 200 x _ { 3 } + 2875000\).
  4. Three of the constraints operating can be expressed as \(x _ { 1 } \geq 200\), \(x _ { 2 } \geq 0\) and \(x _ { 3 } \geq 0\). Write down inequalities representing two further constraints.
    (2 marks)
  5. Explain why it is not appropriate to use a graphical method to solve this problem.
  6. An employee of the company wishes to use the Simplex algorithm to solve the problem. He tries to generate an initial tableau with \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) as the non-basic variables. Explain why this is not appropriate and explain what he should do instead. You are not required to generate an initial tableau or to solve the problem.
    (2 marks)
Edexcel D1 Q5
12 marks Moderate -0.5
5. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-05_956_1561_312_242} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.
  1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
    1. the order in which you labelled the vertices,
    2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
  2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
    (4 marks)
Edexcel D1 Q6
15 marks Standard +0.3
6. This question should be answered on the sheet provided. A town has adopted a one-way system to cope with recent problems associated with congestion in one area. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-06_670_1301_459_331} \captionsetup{labelformat=empty} \caption{Fig. 3}
\end{figure} Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.
  1. Find the capacity of the cut which passes through the \(\operatorname { arcs } A E , B F , B G\) and \(C D\).
    (2 marks) \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-07_659_1278_196_335} \captionsetup{labelformat=empty} \caption{Fig. 4}
    \end{figure} Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, \(S\), and a supersink, \(T\), have been used.
    1. Use the labelling procedure to find the maximum flow through this network. You must list each flow-augmenting route you use together with its flow.
    2. Show your maximum flow pattern and state its value.
  3. Prove that your flow is the maximum possible through the network.
  4. It is suggested that the maximum flow through the network could be increased by making road \(E F\) undirected, so that it has a capacity of 8 in either direction. Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.
    (2 marks)
  5. An alternative suggestion is to widen a single road in order to increase its capacity. Which road, on its own, could lead to the biggest improvement, and what would be the largest maximum flow this could achieve.
    (2 marks)
Edexcel D1 Q7
16 marks Moderate -0.8
7. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-09_2036_1555_349_248}
  1. \(\_\_\_\_\)
  2. \(\_\_\_\_\) \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking} Sheet for answering question 6
    NAME \section*{Please hand this sheet in for marking}
      1. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_666_1280_461_374}
      2. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_657_1276_1356_376} Maximum Flow = \(\_\_\_\_\)
    3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    4. \(\_\_\_\_\)
    5. \(\_\_\_\_\)
Edexcel D1 Q1
7 marks Easy -1.8
  1. Use the binary search algorithm to locate the name PENICUIK in the following list. \begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
  2. Use the same algorithm to attempt to locate PENDINE.
  3. Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}
Edexcel D1 Q2
7 marks Moderate -0.8
  1. The following lengths of cloth (in metres) are to be cut from standard 24 metre rolls.
$$\begin{array} { l l l l l l l l l l l l } 6 & 6 & 4 & 6 & 8 & 8 & 4 & 12 & 14 & 6 & 14 & 8 \end{array}$$
  1. Considering only the total amount, what is the least number of rolls that are needed?
  2. Using the first-fit decreasing algorithm, show that the lengths could be cut from 5 rolls.
  3. Using "full-bin" combinations show that it is possible to cut these lengths from the number of rolls found in part (a).
  4. Comment on this result.
Edexcel D1 Q3
11 marks Moderate -0.8
3. This question should be answered on the sheet provided. A firm of auditors is to place one trainee accountant at each of its five offices. These are situated in Dundee, Edinburgh, Glasgow and London. There are two offices in London, one of which is the company's Head Office. The table summarises the trainees' preferences.
TraineePreferences
\(P\)Dundee, London (either)
\(Q\)Dundee, Edinburgh, Glasgow
\(R\)Glasgow, London (Head Office only)
SEdinburgh
\(T\)Edinburgh
  1. Draw a bipartite graph to model this situation.
  2. Explain why no complete matching is possible. Trainee \(T\) is persuaded that either office in London would be just as good for her personal development as the Edinburgh office.
  3. Draw a second bipartite graph to model the changed situation. In an initial matching, trainee \(P\) is placed in the Dundee office, trainee \(R\) in the Glasgow office, and trainee \(S\) in the Edinburgh office.
  4. Draw this initial matching.
  5. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must indicate how the algorithm has been applied, stating clearly the alternating paths you use and the final matching.
    (7 marks)
Edexcel D1 Q4
11 marks Standard +0.3
4. The following matrix gives the capacities of the pipes in a system.
To FromS\(T\)A\(B\)\(C\)D
S--1626--
T------
A----135
B-16---11
C-11----
D-11----
  1. Represent this information as a digraph.
  2. Find the minimum cut, expressing it in the form \(\{ \} \mid \{ \}\), and state its value.
  3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow.
  4. Explain how you know that this flow is maximal.
Edexcel D1 Q5
11 marks Moderate -0.5
5. This question should be answered on the sheet provided. An algorithm is described by the flow chart shown in Figure 1 below. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-05_1337_937_388_404} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure}
  1. Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output.
  2. Explain what the algorithm achieves.
  3. Attempt to apply the algorithm again, with the initial value of \(a\), as specified in Box 2, changed to 5 . Explain what happens.
    (2 mark)
  4. Find the set of positive initial values of \(a\) for which the algorithm will work.
    (2 marks)
Edexcel D1 Q6
14 marks Moderate -0.5
6. The manager of a new leisure complex needs to maximise the Revenue \(( \pounds R )\) from providing the following two weekend programmes.
\(\frac { \text { Participants } } { \text { Children } }\)7 hours windsurfing, 2 hours sailing\(\frac { \text { Revenue } } { \pounds 50 }\)
Adults5 hours windsurfing, 6 hours sailing\(\pounds 100\)
The following restrictions apply to each weekend.
No more than 90 participants can be accommodated.
There must be at most 40 adults.
A maximum of 600 person-hours of windsurfing can be offered.
A maximum of 300 person-hours of sailing can be offered.
  1. Formulate the above information as a linear programming problem, listing the constraints as inequalities and stating the objective function \(R\).
  2. On graph paper, illustrate the constraints, indicating clearly the feasible region.
  3. Solve the problem graphically, stating how many adults and how many children should be accepted each weekend and what the revenue will be. The manager is considering buying more windsurfing equipment at a cost of \(\pounds 2000\). This would increase windsurfing provision by \(10 \%\).
  4. State, with a reason, whether such a purchase would be cost effective.
Edexcel D1 Q7
14 marks Standard +0.3
7. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-07_576_1360_331_278} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows an activity network modelling the tasks involved in widening a bridge over the B451. The arcs represent the tasks and the numbers in brackets gives the time, in days, to complete each task.
  1. Find the early and late times for each event.
  2. Determine those activities which lie on the critical path and list them in order.
  3. State the minimum length of time needed to widen the bridge. Each task needs a single worker.
  4. Show that two men would not be sufficient to widen the bridge in the shortest time.
    (2 marks)
  5. Draw up a schedule showing how 3 men could complete the project in the shortest time. \section*{Please hand this sheet in for marking}
    1. Complete matching:
      \(P\)\(\bullet\)\(\bullet\)\(D\)
      \(Q\)\(\bullet\)\(\bullet\)\(G\)
      \(R\)\(\bullet\)\(\bullet\)\(E\)
      \(S\)\(\bullet\)\(\bullet\)\(L ( H )\)
      \(T\)\(\bullet\)\(\bullet\)\(L\)
      \section*{Please hand this sheet in for marking}
    2. \(x\)\(a\)\(b\)\(( a - b ) < 0.01\) ?
      1005026No
      -2614.923No
      Final output
    3. \(\_\_\_\_\)
    4. \(x\)\(a\)\(b\)\(( a - b ) < 0.01 ?\)
      100
    5. \(\_\_\_\_\) \section*{Please hand this sheet in for marking}
    6. \includegraphics[max width=\textwidth, alt={}, center]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-11_768_1689_427_221}
    7. \(\_\_\_\_\)
    8. \(\_\_\_\_\)
    9. 051015202530354045505560
      Worker 1
      Worker 2
    10. 051015202530354045505560
      Worker 1
      Worker 2
      Worker 3
AQA D2 2010 January Q1
13 marks Moderate -0.8
1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
Figure 1 shows the activity network and the duration, in days, of each activity for a particular project.
  1. On Figure 1:
    1. find the earliest start time for each activity;
    2. find the latest finish time for each activity.
  2. Find the float for activity \(G\).
  3. Find the critical paths and state the minimum time for completion.
  4. The number of workers required for each activity is shown in the table.
    Activity\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)\(I\)\(J\)
    Number of workers required2232321352
    Given that each activity starts as late as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2, indicating clearly which activities take place at any given time.
AQA D2 2010 January Q2
11 marks Standard +0.3
2 The following table shows the times taken, in minutes, by five people, Ron, Sam, Tim, Vic and Zac, to carry out the tasks \(1,2,3\) and 4 . Sam takes \(x\) minutes, where \(8 \leqslant x \leqslant 12\), to do task 2.
RonSamTimVicZac
Task 1879108
Task 29\(x\)8711
Task 312109910
Task 411981111
Each of the four tasks is to be given to a different one of the five people so that the total time for the four tasks is minimised.
  1. Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
    1. Use the Hungarian algorithm, reducing columns first and then rows, to reduce the matrix to a form, in terms of \(x\), from which the optimum matching can be made.
    2. Hence find the possible way of allocating the four tasks so that the total time is minimised.
    3. Find the minimum total time.
  3. After special training, Sam is able to complete task 2 in 7 minutes and is assigned to task 2. Determine the possible ways of allocating the other three tasks so that the total time is minimised.
AQA D2 2010 January Q3
12 marks Easy -1.3
3
  1. Two people, Ann and Bill, play a zero-sum game. The game is represented by the following pay-off matrix for Ann.
    \multirow{5}{*}{Ann}Bill
    Strategy\(\mathbf { B } _ { \mathbf { 1 } }\)\(\mathbf { B } _ { \mathbf { 2 } }\)\(\mathbf { B } _ { \mathbf { 3 } }\)
    \(\mathbf { A } _ { \mathbf { 1 } }\)-10-2
    \(\mathbf { A } _ { \mathbf { 2 } }\)4-2-3
    \(\mathbf { A } _ { \mathbf { 3 } }\)-4-5-3
    Show that this game has a stable solution and state the play-safe strategies for Ann and Bill.
  2. Russ and Carlos play a different zero-sum game, which does not have a stable solution. The game is represented by the following pay-off matrix for Russ.
    Carlos
    \cline { 2 - 5 }Strategy\(\mathbf { C } _ { \mathbf { 1 } }\)\(\mathbf { C } _ { \mathbf { 2 } }\)\(\mathbf { C } _ { \mathbf { 3 } }\)
    \cline { 2 - 5 } Russ\(\mathbf { R } _ { \mathbf { 1 } }\)- 47- 3
    \cline { 2 - 5 }\(\mathbf { R } _ { \mathbf { 2 } }\)2- 11
    1. Find the optimal mixed strategy for Russ.
    2. Find the value of the game.
AQA D2 2010 January Q4
14 marks Standard +0.3
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 + 4 y + 3 z\). The initial Simplex tableau is given below.
\(\boldsymbol { P }\)\(\boldsymbol { x }\)\(\boldsymbol { y }\)\(\boldsymbol { Z }\)\(s\)\(t\)\(\boldsymbol { u }\)value
1-2-4-30000
022110014
0-1120106
044300129
    1. What name is given to the variables \(s , t\) and \(u\) ?
    2. Write down an equation involving \(x , y , z\) and \(s\) for this problem.
    1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
    2. Explain how you know that the optimal value has not been reached.
    1. Perform one further iteration.
    2. Interpret the final tableau, stating the values of \(P , x , y\) and \(z\).
AQA D2 2010 January Q5
10 marks Moderate -0.5
5 [Figure 3, printed on the insert, is provided for use in this question.]
A landscape gardener has three projects, \(A , B\) and \(C\), to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table.
\cline { 2 - 5 } \multicolumn{1}{c|}{}MayJuneJulyAugust
Project \(\boldsymbol { A }\)17161816
Project \(\boldsymbol { B }\)14131210
Project \(\boldsymbol { C }\)14171514
By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.
AQA D2 2010 January Q6
15 marks Moderate -0.5
6 [Figures 4, 5, 6 and 7, printed on the insert, are provided for use in this question.]
  1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity, in litres per minute, indicated on each edge. \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_350_878_532_591}
    1. Show that the value of the cut shown on the diagram is 97 .
    2. The cut shown on the diagram can be represented as \(\{ S , C \} , \{ A , B , T \}\). Complete the table on Figure 4, giving the value of each of the 8 possible cuts.
    3. State the value of the maximum flow through the network, giving a reason for your answer.
    4. Indicate on Figure 5 a possible flow along each edge corresponding to this maximum flow.
  2. Extra pipes, \(B D , C D\) and \(D T\), are added to form a new system, with the capacity, in litres per minute, indicated on each edge of the network below. \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_483_977_1724_520}
    1. Taking your values from Figure 5 as the initial flow, use the labelling procedure on Figure 6 to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
    2. State the value of the new maximum flow, and, on Figure 7, indicate a possible flow along each edge corresponding to this maximum flow.