Questions D1 (899 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 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics Stats 1 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 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 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 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 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics 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
Edexcel D1 2024 January Q4
4.
ActivityImmediately preceding activities
A-
B-
CA, B
DA, B
EB
FC, D, E
GF
HB
IF
JF
KG
LG, H, I, J
MG, I
  1. Draw the activity network described in the precedence table, using activity on arc and the minimum number of dummies.
  2. Given that
    • the activity network contains only one critical path
    • activity E is on this critical path
      state
      1. which activities could never be critical,
      2. which activities must be critical.
Edexcel D1 2024 January Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4814ebd7-f48a-49cf-8ca2-045d84abd63c-6_883_986_219_552} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\). The unshaded area, including its boundaries, forms the feasible region, \(R\). The four vertices of \(R\) are \(A ( 6,8 ) , B ( 13,12 ) , C ( 9,22 )\) and \(D ( 5,18 )\).
An objective line has been drawn and labelled on the graph.
When the objective function, \(P\), is maximised, the value of \(P\) is 540
When the objective function, \(P\), is minimised, the value of \(P\) is \(k\)
Determine the value of \(k\). You must make your method and working clear.
(You may assume that the objective function, \(P\), takes the form \(a x + b y\) where \(a\) and \(b\) are constants.)
Edexcel D1 2024 January Q6
6. The twelve numbers in the list below are to be packed into bins of size \(n\), where \(n\) is a positive integer.
28315251635182211271513
When the first-fit bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 28315
Bin 2: 25161811
Bin 3: 352215
Bin 4: 2713
  1. Based on the packing shown above, determine the possible values of \(n\). You must give reasons for your answer.
  2. The original list of twelve numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. When the first-fit decreasing bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 35315
    Bin 2: 282716
    Bin 3: 252218
    Bin 4: 151311
  3. Determine the value of \(n\). You must give a reason for your answer.
Edexcel D1 2024 January Q7
7. A farmer has 100 acres of land available that can be used for planting three crops: A, B and C . It takes 2 hours to plant each acre of crop A, 1.5 hours to plant each acre of crop B and 45 minutes to plant each acre of crop C . The farmer has 138 hours available for planting. At least one quarter of the total crops planted must be crop A.
For every three acres of crop B planted, at most five acres of crop C will be planted.
The farmer expects a profit of \(\pounds 160\) for each acre of crop A planted, \(\pounds 75\) for each acre of crop B planted and \(\pounds 125\) for each acre of crop C planted. The farmer wishes to maximise the profit from planting these three crops.
Let \(x , y\) and \(z\) represent the number of acres of land used for planting crop A, crop B, and crop C respectively.
  1. Formulate this information as a linear programming problem. State the objective, and list the constraints as simplified inequalities with integer coefficients. The farmer decides that all 100 acres of available land will be used for planting the three crops.
  2. Explain why the maximum total profit is achieved when \(- 7 x + 10 y\) is minimised. The farmer's decision to use all 100 acres reduces the constraints of the problem to the following: $$\begin{aligned} x & \geqslant 25
    3 x + 8 y & \geqslant 300
    x + y & \leqslant 100
    5 x + 3 y & \leqslant 252
    y & \geqslant 0 \end{aligned}$$
  3. Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, \(R\).
    1. Determine the exact coordinates of each of the vertices of \(R\).
    2. Apply the vertex method to determine how the 100 acres should be used for planting the three crops.
    3. Hence find the corresponding maximum expected profit.
Edexcel D1 2014 June Q1
1. \begin{displayquote} McCANN
SMITH
QUAGLIA
CONGDON
EVES
PATEL
BUSH
FOX
OSBORNE
  1. Use a quick sort to produce a list of these names in alphabetical order. You must make your pivots clear.
  2. Use the binary search algorithm on your list to locate the name PATEL. State the number of iterations you use. \end{displayquote} The binary search algorithm is to be used to search for a name in an alphabetical list of 641 names.
  3. Find the maximum number of iterations needed, justifying your answer.
Edexcel D1 2014 June Q2
2. (a) (i) Define the term complete matching.
(ii) Explain the difference between a complete matching and a maximal matching.
(3) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_732_563_434_376} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_739_563_429_1117} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 1 shows the possible allocations of dancing partners for the Truly Come Ballroom dancing competition. Six women, Annie (A), Bella (B), Chloe (C), Danika (D), Ella (E) and Faith (F), are to be paired with six men, Kieran (K), Lucas (L), Michael (M), Nasir (N), Oliver (O) and Paul (P). Figure 2 shows an initial matching.
(b) Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and list your improved matching.
(3) After dance practice, it is decided that Bella could also be paired with Kieran, and Danika could also be paired with Nasir.
(c) Starting with your improved matching from part (b), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and list your final matching.
Edexcel D1 2014 June Q3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-4_591_1581_239_258} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows a network representing the time taken, in minutes, to travel by train between nine towns, A, B, C, D, E, F, G, H and T. A train is to travel from A to T without stopping.
  1. Use Dijkstra's algorithm to find the quickest route from A to T and the time taken.
    (6) At present, the train travels from A to T via F without stopping.
  2. Use your answer to (a) to find the quickest route from A to T via F and the time taken.
    (2) A train is to travel from A to T , stopping for 2 minutes at each town it passes through on its route.
  3. Explain how you would adapt the network so that you could use Dijkstra's algorithm to find the quickest route for this train. You do not need to find this route.
    (2)
Edexcel D1 2014 June Q4
4. (a) State three differences between Prim's algorithm and Kruskal's algorithm for finding a minimum spanning tree.
(3) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-5_864_1073_386_497} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} [The total weight of the network is 341]
(b) Use Prim's algorithm, starting at D , to find a minimum spanning tree for the network shown in Figure 4. You must list the arcs in the order in which you select them.
(3) Figure 4 models a network of school corridors. The number on each arc represents the length, in metres, of that corridor. The school caretaker needs to inspect each corridor in the school to check that the fire alarms are working correctly. He wants to find a route of minimum length that traverses each corridor at least once and starts and finishes at his office, D.
(c) Use the route inspection algorithm to find the corridors that will need to be traversed twice. You must make your method and working clear. The caretaker now decides to start his inspection at G. His route must still traverse each corridor at least once but he does not need to finish at G.
(d) Determine the finishing point so that the length of his route is minimised. You must give reasons for your answer and state the length of his route.
(3)
Edexcel D1 2014 June Q5
5. Michael and his team are making toys to give to children at a summer fair. They make two types of toy, a soft toy and a craft set. Let \(x\) be the number of soft toys they make and \(y\) be the number of craft sets they make.
Each soft toy costs \(\pounds 3\) to make and each craft set costs \(\pounds 5\) to make. Michael and his team have a budget of \(\pounds 1000\) to spend on making the toys for the summer fair.
  1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Two further constraints are: $$\begin{gathered} y \leqslant 2 x
    4 y - x \geqslant 210 \end{gathered}$$
  2. Add lines and shading to Diagram 1 in the answer book to represent all of these constraints. Hence determine the feasible region and label it R . Michael's objective is to make as many toys as possible.
  3. State the objective function.
  4. Determine the exact coordinates of each of the vertices of the feasible region, and hence use the vertex method to find the optimal number of soft toys and craft sets Michael and his team should make. You should make your method clear.
Edexcel D1 2014 June Q6
6. (a) Draw the activity network described in this precedence table, using activity on arc and dummies only where necessary.
ActivityImmediately preceding activities
A-
B-
C-
DB, C
EA
FC
GD, E
HD, E
I\(F , G\)
JC
K\(G , H\)
(b) Explain the possible reasons dummies may be needed in activity networks.
Edexcel D1 2014 June Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-8_499_1319_191_383} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} A company models a project by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.
  1. Add early and late event times to Diagram 1 in the answer book.
  2. State the critical path and its length.
  3. On Diagram 2 in the answer book, construct a cascade (Gantt) chart.
  4. By using your cascade chart, state which activities must be happening at
    1. time 7.5
    2. time 16.5 It is decided that the company may use up to 25 days to complete the project.
  5. On Diagram 3 in the answer book, construct a scheduling diagram to show how this project can be completed within 25 days using as few workers as possible.
Edexcel D1 2015 June Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-2_686_1408_342_333} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents a network of roads. The number on each arc gives the length, in km , of the corresponding road.
  1. Use Dijkstra's algorithm to find the shortest distance from S to G . State the shortest route.
  2. State both the shortest distance and the shortest route from S to H .
Edexcel D1 2015 June Q2
2. A list of \(n\) numbers needs to be sorted into descending order starting at the left-hand end of the list.
  1. Describe how to carry out the first pass of a bubble sort on the numbers in the list.
    1. State which number in the list is guaranteed to be in the correct final position after the first pass.
    2. Write down the maximum number of passes required to sort a list of \(n\) numbers.
  3. The numbers below are to be sorted into descending order. Use a bubble sort, starting at the left-hand end of the list, to obtain the sorted list. You need only give the state of the list after each pass. $$\begin{array} { l l l l l l l l l } 11 & 9 & 4 & 13 & 5 & 1 & 7 & 12 & 8 \end{array}$$
  4. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 21
Edexcel D1 2015 June Q3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_591_1365_239_360} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 2 shows a graph G.
  1. Write down an example of a cycle on G.
    (1)
  2. State, with a reason, whether or not \(\mathrm { P } - \mathrm { Q } - \mathrm { R } - \mathrm { T } - \mathrm { Q } - \mathrm { S }\) is an example of a path on G .
    (2) \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_618_1406_1336_340} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} The numbers on the \(14 \operatorname { arcs }\) in Figure 3 represent the distances, in km , between eight vertices, \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T } , \mathrm { U } , \mathrm { V }\) and W , in a network.
  3. Use Prim's algorithm, starting at P , to find the minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
  4. Use Kruskal's algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to the minimum spanning tree.
  5. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. The weight on arc RU is now increased to a value of \(x\). The minimum spanning tree for the network is still unique and includes the same arcs as those found in (e).
  6. Write down the smallest interval that must contain \(x\).
Edexcel D1 2015 June Q4
4. (a) Define the term 'alternating path'. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-6_469_647_315_708} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 shows the possible allocations of five people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , to five tasks, \(1,2,3,4\) and 5 An initial matching has three people allocated to three of the tasks.
Starting from this initial matching, one possible alternating path that starts at E is $$E - 2 = B - 3 = A - 4 = D - 1$$ (b) Use this information to
  1. deduce this initial matching,
  2. list the improved matching generated by the given alternating path.
    (c) Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
Edexcel D1 2015 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-7_778_1369_239_354} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} \section*{[The total weight of the network is 214]} Figure 5 models a network of canals that have to be inspected. The number on each arc represents the length, in km , of the corresponding canal. Priya needs to travel along each canal at least once and wishes to minimise the length of her inspection route. She must start and finish at A .
  1. Use the route inspection algorithm to find the length of her route. State the arcs that will need to be traversed twice. You should make your method and working clear.
    (6)
  2. State the number of times that vertex F would appear in Priya's route.
    (1) It is now decided to start the inspection route at H . The route must still travel along each canal at least once but may finish at any vertex.
  3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of the minimum route.
    (3)
Edexcel D1 2015 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-8_1180_1572_207_251} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} [The sum of the durations of all the activities is 142 days]
A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete the precedence table in the answer book.
  2. Complete Diagram 1 in the answer book to show the early event times and late event times.
  3. Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
  4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. Diagram 2 in the answer book shows a partly completed scheduling diagram for this project.
  5. Complete the scheduling diagram, using the minimum number of workers, so that the project is completed in the minimum time.
Edexcel D1 2015 June Q7
7. Ian plans to produce two types of book, hardbacks and paperbacks. He will use linear programming to determine the number of each type of book he should produce. Let \(x\) represent the number of hardbacks Ian will produce. Let \(y\) represent the number of paperbacks Ian will produce. Each hardback takes 1 hour to print and 15 minutes to bind.
Each paperback takes 35 minutes to print and 24 minutes to bind.
The printing machine must be used for at least 14 hours. The binding machine must be used for at most 8 hours.
    1. Show that the printing time restriction leads to the constraint \(12 x + 7 y \geqslant k\), where \(k\) is a constant to be determined.
    2. Write the binding time restriction in a similar simplified form. Ian decides to produce at most twice as many hardbacks as paperbacks.
  2. Write down an inequality to model this constraint in terms of \(x\) and \(y\).
  3. Add lines and shading to Diagram 1 in the answer book to represent the constraints found in (a) and (b). Hence determine, and label, the feasible region R. Ian wishes to maximise \(\mathrm { P } = 60 x + 36 y\), where P is the total profit in pounds.
    1. Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must draw and clearly label your objective line and the vertex V .
    2. Determine the exact coordinates of V. You must show your working.
  5. Given that P is Ian's expected total profit, in pounds, find the number of each type of book that he should produce and his maximum expected profit.
Edexcel D1 2016 June Q1
1. $$\begin{array} { l l l l l l l l l } 4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 2.7 \end{array}$$
  1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 7.8
  2. Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
  3. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
  4. Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree. A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
  5. Explain why Prim's algorithm could not be used to complete the tree.
Edexcel D1 2016 June Q2
2. Six film critics, Bronwen (B), Greg (G), Jean (J), Mick (M), Renee (R) and Susan (S), must see six films, \(1,2,3,4,5\) and 6 . Each critic must attend a different film and each critic needs to be allocated to exactly one film. The critics are asked which films they would prefer and their preferences are given in the table below.
CriticPreference
B\(2,3,6\)
G1
J\(2,5,6\)
M1,5
R\(2,4,6\)
S3,5
  1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of critics to their preferred films. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-03_616_524_1114_767} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} Figure 2 shows an initial matching.
  2. Starting from the given initial matching, apply the maximum matching algorithm to find an alternating path from G to 3 . Hence find an improved matching. You should list the alternating path that you use, and state your improved matching.
    (3)
  3. Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You should list the alternating path that you use, and state your complete matching.
Edexcel D1 2016 June Q3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-04_1684_1492_194_283} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The equations of two of the lines have been given.
  1. Determine the inequalities that define the feasible region.
  2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = k x + y\).
  3. For the case \(k = 2\), use point testing to find the optimal vertex of the feasible region.
  4. For the case \(k = 2.5\), find the set of points for which \(P\) takes its maximum value.
Edexcel D1 2016 June Q4
4. (a) Draw the activity network described in the precedence table below, using activity on arc and the minimum number of dummies.
ActivityImmediately preceding activities
A-
B-
C-
DA
EA
FA, B, C
GC
HE, F, G
IE, F, G
JH, I
KH, I
LD, J
A project is modelled by the activity network drawn in (a). Each activity requires one worker. The project is to be completed in the shortest possible time. The table below gives the time, in days, to complete some of the activities.
ActivityDuration (in days)
B7
F4
J4
L6
The critical activities for the project are B, F, I, J and L and the length of the critical path is 30 days.
(b) Calculate the duration of activity I.
(c) Find the range of possible values for the duration of activity K .
Edexcel D1 2016 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-06_899_1241_230_411} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 88]}
\end{figure}
  1. Explain what is meant by the term 'path'.
    (2) Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
  2. Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.
    (6) On a particular day, Tomek needs to travel from G to J via A.
  3. Find the shortest route from G to J via A , and find its length.
    (3) The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
  4. Use an appropriate algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
    (5)
  5. Write down a possible shortest inspection route.
    (1)
Edexcel D1 2016 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-07_773_1353_226_372} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} A project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.
  1. Complete Diagram 1 in the answer book to show the early event times and late event times.
  2. State the critical activities.
  3. Calculate the maximum number of days by which activity E could be delayed without lengthening the completion time of the project. You must make the numbers used in your calculation clear.
  4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
  5. Draw a cascade (Gantt) chart for this project on the grid provided in the answer book.
Edexcel D1 2016 June Q7
7. A theatre company is planning to sell two types of ticket, standard and premier. The theatre company has completed some market research and has used this to form the following constraints.
  • They will sell at most 450 tickets.
  • They will sell at least three times as many standard tickets as premier tickets.
  • At most \(85 \%\) of all the tickets sold will be standard.
The theatre wants to maximise its profit. The profit on each standard ticket sold is \(\pounds 5\) and the profit on each premier ticket sold is \(\pounds 8\)
Let \(x\) represent the number of standard tickets sold and \(y\) represent the number of premier tickets sold. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.
(Total 6 marks)