Oct 2020: A level Paper 3D: Decision Mathematics 1

75 marks · 24 question parts · Question paper, mark scheme and examiner's report on Pearson's site

Question by question

QTopicMarksDifficulty
1(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 2 —
1(b) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 3 —
1(c) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 1 —
2(a) Critical path analysis 2 —
2(b) Critical path analysis 2 —
2(c) Critical path analysis 6 —
2(d) Critical path analysis 3 —
2(e) Critical path analysis 2 —
3(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 2 —
3(b) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 4 —
3(c) Route inspection and the travelling salesman problem 3 —
4(a) Linear programming: formulation, graphs and the Simplex algorithm 2 —
4(b) Linear programming: formulation, graphs and the Simplex algorithm 4 —
4(c) Linear programming: formulation, graphs and the Simplex algorithm 4 —
5(a) Algorithms, sorting, bin packing and graph theory 3 —
5(b) Algorithms, sorting, bin packing and graph theory 2 —
5(c) Algorithms, sorting, bin packing and graph theory 2 —
6(a) Algorithms, sorting, bin packing and graph theory 2 —
6(b) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd), Route inspection and the travelling salesman problem 9 —
7(a) Linear programming: formulation, graphs and the Simplex algorithm 4 —
7(b) Linear programming: formulation, graphs and the Simplex algorithm 2 —
7(c) Linear programming: formulation, graphs and the Simplex algorithm 3 —
7(d) Linear programming: formulation, graphs and the Simplex algorithm 5 —
7(e) Linear programming: formulation, graphs and the Simplex algorithm 3 —

The questions

1(a)1(b)1(c)2(a)2(b)2(c)2(d)2(e)3(a)3(b)3(c)4(a)4(b)4(c)5(a)5(b)5(c)6(a)6(b)7(a)7(b)7(c)7(d)7(e)
Oct 2020 · Paper 3D (Decision 1) · Q1(a) 2 marks minimum spanning trees and shortest paths
1. The table below shows the lengths, in km, of the roads in a network connecting seven towns, A, B, C, D, E, F and G. A B C E F G A – – – – B – – – – C – – – – – E – – – F – – – G – – – – (a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book. (2)
Oct 2020 · Paper 3D (Decision 1) · Q1(b) 3 marks minimum spanning trees and shortest paths
(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)
Oct 2020 · Paper 3D (Decision 1) · Q1(c) 1 mark minimum spanning trees and shortest paths
(c) State the weight of the minimum spanning tree. (1)
Oct 2020 · Paper 3D (Decision 1) · Q2(a) 2 marks critical path analysis
2. K(5) D(4) E(5) L(6) A(6) I(4) B(7) F(3) G(4) C(5) J(6) H(3) Figure 1 The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets. (a) Explain why each of the dummy activities is required. (2)
Oct 2020 · Paper 3D (Decision 1) · Q2(b) 2 marks critical path analysis
(b) Complete the table in the answer book to show the immediately preceding activities for each activity. (2)
Oct 2020 · Paper 3D (Decision 1) · Q2(c) 6 marks critical path analysis
(c) (i) Complete Diagram 1 in the answer book to show the early event times and the late event times. (ii) State the minimum completion time for the project. (iii) State the critical activities. (6)
Oct 2020 · Paper 3D (Decision 1) · Q2(d) 3 marks critical path analysis
Each activity requires one worker. Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption. (d) On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time. (3)
Oct 2020 · Paper 3D (Decision 1) · Q2(e) 2 marks critical path analysis
(e) Determine whether or not the project can be completed in the minimum possible time using fewer workers than the number indicated by the resource histogram in (d). You must justify your answer with reference to the resource histogram and the completed Diagram 1. (2)
Oct 2020 · Paper 3D (Decision 1) · Q3(a) 2 marks minimum spanning trees and shortest paths
3. A B C E Figure 2 Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages. (a) Set up initial time and route matrices. (2)
Oct 2020 · Paper 3D (Decision 1) · Q3(b) 4 marks minimum spanning trees and shortest paths
The matrices after two iterations of Floyd’s algorithm are shown below. Time matrix Route matrix A B C E A B C E A A – A B C B B – B A B C A E C – C A B C A E – A A C E E – E B B C E (b) Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration. (4)
Oct 2020 · Paper 3D (Decision 1) · Q3(c) 3 marks route inspection and travelling salesman
The final time matrix after completion of Floyd’s algorithm is shown below. Final time matrix A B C E A – B – C – – E – (c) (i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times. (ii) Find the time taken for this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (3)
Oct 2020 · Paper 3D (Decision 1) · Q4(a) 2 marks linear programming
4. y 2y = 5x 7 – y = x + 1 6 – 5 – 4 – R 3 – 2 – 1 – – – – – – – – x 6x + 5y = 30 Figure 3 Figure 3 shows the constraints of a linear programming problem in x and y, where R is the feasible region. (a) Write down the inequalities that define R. (2)
Oct 2020 · Paper 3D (Decision 1) · Q4(b) 4 marks linear programming
The objective is to maximise P, where P = 3x + y (b) Obtain the exact value of P at each of the three vertices of R and hence find the optimal vertex, V. (4)
Oct 2020 · Paper 3D (Decision 1) · Q4(c) 4 marks linear programming
The objective is changed to maximise Q, where Q = 3x + ay. Given that a is a constant and the optimal vertex is still V, (c) find the range of possible values of a. (4)
Oct 2020 · Paper 3D (Decision 1) · Q5(a) 3 marks algorithms and graph theory
5. The nine distinct numbers in the following list are to be packed into bins of size 50 23 17 19 x 24 8 18 10 21 When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23 17 8 Bin 2: 19 x 10 Bin 3: 24 18 Bin 4: 21 (a) Explain why 13 < x < 21 (3)
Oct 2020 · Paper 3D (Decision 1) · Q5(b) 2 marks algorithms and graph theory
The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is 23 19 17 24 x 18 10 21 8 (b) Using this information, write down the smallest interval that must contain x, giving your answer as an inequality. (2)
Oct 2020 · Paper 3D (Decision 1) · Q5(c) 2 marks algorithms and graph theory
When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 24 23 Bin 2: 21 19 10 Bin 3: 18 17 x Bin 4: 8 Given that only one of the bins is full and that x is an integer, (c) calculate the value of x. You must give reasons for your answer. (2)
Oct 2020 · Paper 3D (Decision 1) · Q6(a) 2 marks algorithms and graph theory
6. E B x F A C y G Figure 4 [The total weight of the network is 320 + x + y] (a) State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. (2)
The weights on the arcs in Figure 4 represent distances. The weight on arc EF is x where 12 < x < 26 and the weight on arc DG is y where 0 < y < 10 An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409 It is also given that the length of the shortest route from F to G via A is 140 (b) Using appropriate algorithms, find the value of x and the value of y. (9)
Oct 2020 · Paper 3D (Decision 1) · Q7(a) 4 marks linear programming
7. A maximisation linear programming problem in x, y and z is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below. Basic x y z s1 s2 s3 a1 a2 Value variable s1 a1 –1 a2 –1 –1 P –2 –1 –3 A (a) Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities. (4)
Oct 2020 · Paper 3D (Decision 1) · Q7(b) 2 marks linear programming
(b) Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. (2)
Oct 2020 · Paper 3D (Decision 1) · Q7(c) 3 marks linear programming
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method. Basic x y z s1 s2 s3 a1 a2 Value variable -7 -3 s1 -1 x -1 -1 z -11 -3 P A (c) (i) Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem. (ii) Write down the basic feasible solution for the second stage. (3)
Oct 2020 · Paper 3D (Decision 1) · Q7(d) 5 marks linear programming
(d) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (5)
Oct 2020 · Paper 3D (Decision 1) · Q7(e) 3 marks linear programming
(e) (i) Explain, using T, whether or not an optimal solution to the original linear programming problem has been found. (ii) Write down the value of the objective function. (iii) State the values of the basic variables. (3)

Find an Edexcel Further Maths tutor

Want this paper marked and gone through with a Further Maths tutor? Message us.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.