June 2018: AS Paper 27: Decision Mathematics 1

40 marks · 13 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) 6 —
1(b) Algorithms, sorting, bin packing and graph theory 2 —
1(c) Algorithms, sorting, bin packing and graph theory 1 —
2(a) Algorithms, sorting, bin packing and graph theory 2 —
2(b)(i) Algorithms, sorting, bin packing and graph theory 3 —
2(c) Algorithms, sorting, bin packing and graph theory 5 —
3(a) Critical path analysis 3 —
3(b) Critical path analysis 3 —
3(c) Critical path analysis 1 —
3(d) Critical path analysis 3 —
4(a) Linear programming: formulation, graphs and the Simplex algorithm 1 —
4(b) Linear programming: formulation, graphs and the Simplex algorithm 2 —
4(c) Linear programming: formulation, graphs and the Simplex algorithm 8 —

The questions

1(a)1(b)1(c)2(a)2(b)(i)2(c)3(a)3(b)3(c)3(d)4(a)4(b)4(c)
June 2018 · AS Paper 2 (Decision 1) · Q1(a) 6 marks minimum spanning trees and shortest paths
1. B C A E A I G J H Figure 1 Figure 1 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. (a) (i) Use Dijkstra’s algorithm to find the shortest time needed to travel from A to H. (ii) State the quickest route. (6)
June 2018 · AS Paper 2 (Decision 1) · Q1(b) 2 marks algorithms and graph theory
For a network with n vertices, Dijkstra’s algorithm has order n? (b) If it takes 1.5 seconds to run the algorithm when n = 250, calculate approximately how long it will take, in seconds, to run the algorithm when 7 = 9500. You should make your method and working clear. (2)
June 2018 · AS Paper 2 (Decision 1) · Q1(c) 1 mark algorithms and graph theory
(c) Explain why your answer to part (b) is only an approximation. (1)
June 2018 · AS Paper 2 (Decision 1) · Q2(a) 2 marks algorithms and graph theory
2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. (a) Given that a simply connected graph has exactly four vertices, (i) write down the minimum number of arcs it can have, (ii) write down the maximum number of arcs it can have. (2)
June 2018 · AS Paper 2 (Decision 1) · Q2(b)(i) 3 marks algorithms and graph theory
(b) (i) Draw a simply connected graph that has exactly four vertices and exactly five arcs. (ii) State, with justification, whether your graph is Eulerian, semi-Eulerian or neither. (3)
June 2018 · AS Paper 2 (Decision 1) · Q2(c) 5 marks algorithms and graph theory
(c) By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs. (5)
June 2018 · AS Paper 2 (Decision 1) · Q3(a) 3 marks critical path analysis
3. Time taken (days) Immediately preceding activities PAS as a eeee ee ee ee eee a ee ee ee: The table above shows the activities required for the completion of a building project. For each activity, the table shows the time it takes, in days, and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time. A(5) F(3) H(5) I(7) B(8) C(4) Figure 2 Figure 2 showsa partially completed activity network used to model the project. The activities are represented by the arcs and the number in brackets on each arc is the time taken, in days, to complete the corresponding activity. (a) Add the missing activities and necessary dummies to Diagram 1 in the answer book. (3)
June 2018 · AS Paper 2 (Decision 1) · Q3(b) 3 marks critical path analysis
(b) Complete Diagram1 in the answer book to show the early event times and the late event times. (3)
June 2018 · AS Paper 2 (Decision 1) · Q3(c) 1 mark critical path analysis
(c) State the critical activities. (1)
June 2018 · AS Paper 2 (Decision 1) · Q3(d) 3 marks critical path analysis
At the beginning of the project it is decided that activity G is no longer required. (d) Explain what effect, if any, this will have on (i) the shortest completion time of the project if activity G is no longer required, (ii) the timing of the remaining activities. (3)
June 2018 · AS Paper 2 (Decision 1) · Q4(a) 1 mark linear programming
4. The manager of a factory is planning the production schedule for the next three weeks for a range of cabinets. The following constraints apply to the production schedule. ¢ The total number of cabinets produced in week 3 cannot be fewer than the total number produced in weeks | and 2 ¢ At most twice as many cabinets must be produced in week 3 as in week 2 ¢ The number of cabinets produced in weeks 2 and 3 must, in total, be at most 125 The production cost for each cabinet produced in weeks 1, 2 and 3 is £250, £275 and £200 respectively. The factory manager decides to formulate a linear programming problem to find a production schedule that minimises the total cost of production. The objective is to minimise 250x + 275y + 200z (a) Explain what the variables x, y and z represent. (1)
June 2018 · AS Paper 2 (Decision 1) · Q4(b) 2 marks linear programming
(b) Write down the constraints of the linear programming problem in terms of x, y and z. (2)
June 2018 · AS Paper 2 (Decision 1) · Q4(c) 8 marks linear programming
Due to demand, exactly 150 cabinets must be produced during these three weeks. This reduces the constraints to x+y <75 x + 3y > 150 x > 25 y20 which are shown in Diagram| in the answer book. Given that the manager does not want any cabinets left unfinished at the end of a week, (c) (i) use a graphical approach to solve the linear programming problem and hence determine the production schedule which minimises the cost of production. You should make your method and working clear. (ii) Find the minimum total cost of the production schedule. (8)

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.