WDM01 01 Que 20180118
WDM01 01 Que 20180118
WDM01 01 Que 20180118
Decision Mathematics D1
Advanced/Advanced Subsidiary
Instructions
•• Use black ink or ball-point pen.
If pencil is used for diagrams/sketches/graphs it must be dark (HB or B).
Coloured pencils and highlighter pens must not be used.
• centre
Fill in the boxes on the top of the answer book with your name,
number and candidate number.
• clearly labelled.
Answer all questions and ensure that your answers to parts of questions are
Advice
•• Read each question carefully before you start to answer it.
Try to answer every question.
• Check your answers if you have time at the end. Turn over
P51509A
©2018 Pearson Education Ltd.
1/1/1/1/
*P51509A*
Write your answers in the D1 answer book for this paper.
1.
A 1 A 1
B 2 B 2
C 3 C 3
D 4 D 4
E 5 E 5
F 6 F 6
Figure 1 Figure 2
Figure 1 shows the possible allocations of six people, A, B, C, D, E and F, to six activities, 1, 2, 3,
4, 5 and 6
(b) Starting from this initial matching, use the maximum matching algorithm to find a complete
matching. You should list the alternating path that you use, and state your complete matching.
(3)
(Total 5 marks)
P51509A 2
2.
Key:
5 D(3) 18
Early
event
5 w
time
Late
event
A(5) K(5)
E(7) time
F(x)
0 y 20 27
H(4) M(7)
C(6) J(4)
6 16 27
6 I(10) 16 N(3) 27
Figure 3
The network in Figure 3 shows the activities that need to be undertaken by a company to complete
a project. Each activity is represented by an arc and the duration of the activity, in days, is shown
in brackets. Each activity requires exactly one worker. The early event times and late event times
are shown at each vertex.
Given that the total float on activity B is 2 days and the total float on activity F is also 2 days,
(b) Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
(4)
(c) Use your cascade chart to determine the minimum number of workers needed to complete the
project in the shortest possible time. You must make specific reference to time and activities.
(You do not need to provide a schedule of the activities.)
(2)
(Total 10 marks)
10
G
18 24 10
33
20 11 A 35
27 D
14
24 F 20
H 12 E
34
31
8
J
26
Figure 4
Figure 4 represents a network of train tracks. The number on each edge represents the length, in
kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise
the distance she travels.
(a) Use Dijkstra’s algorithm to find the shortest path from A to J. State the path and its length.
(6)
(b) Find a route of minimal length that goes from D to H via A and state its length.
(2)
(c) Use Prim’s algorithm, starting at E, to find a minimum spanning tree for the network. You must
clearly state the order in which you select the edges of your tree.
(3)
(Total 12 marks)
P51509A 4
4.
y
5
R
1
O x
1 2 3
Figure 5
Figure 5 shows the constraints of a linear programming problem in x and y, where R is the feasible
region.
(b) Find the exact coordinates of the vertices of the feasible region.
(3)
(c) Use point testing at each vertex to find the optimal vertex, V, of the feasible region and state
the corresponding value of P at V.
(3)
(d) Find the range of values of k for which the vertex identified in (c) is still optimal.
(2)
(Total 11 marks)
H 27 E
17
K
Figure 6
[The total weight of the network is 601]
Figure 6 represents a network of footpaths in a park. The number on each arc is the length, in
metres, of the corresponding footpath. An inspection route of minimum length that traverses each
footpath at least once needs to be found.
(a) Write down the nodes at which the route will start and finish.
(1)
It is now decided to start the inspection route at B and finish the inspection route at D. A route of
minimum length that traverses each footpath at least once needs to be found.
(b) By considering the pairings of all relevant nodes find the arcs that will need to be traversed
twice. You must make your method and working clear.
(4)
(c) Write down a possible shortest inspection route, giving its length.
(2)
(Total 7 marks)
P51509A 6
6.
30 11 21 53 50 39 16 4 60 43
The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The
wire is sold in one metre lengths.
(a) Use the first-fit bin packing algorithm to determine how these pieces could be cut from
one metre lengths. You should ignore wastage due to cutting.
(3)
Starting at the left-hand end of the list, after three passes of the bubble sort, the list is
11 21 30 16 4 39 43 50 53 60
(b) (i) Write down the list that results at the end of the fourth pass.
(ii) Write down the number of comparisons and swaps performed during the fourth pass.
(3)
(c) Perform a quick sort to obtain the sorted list. You should show the result of each pass and
identify your pivots clearly.
(4)
(d) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut
from one metre lengths. You should ignore wastage due to cutting.
(3)
(Total 13 marks)
Emily has completed some market research and has used this to form the following constraints on
the number of milkshakes that she will sell each week.
• She will sell fewer than 200 non-vanilla milkshakes in total.
• She will sell at most 2.5 times as many strawberry milkshakes as vanilla milkshakes.
• At most, 75% of the milkshakes that she will sell will be vanilla.
The profit on each strawberry milkshake sold is £0.75, the profit on each vanilla milkshake sold is
£1.20 and the profit on each chocolate milkshake sold is £1.45
Let x represent the number of strawberry milkshakes sold, let y represent the number of vanilla
milkshakes sold and let z represent the number of chocolate milkshakes sold.
(a) Formulate this as a linear programming problem, stating the objective and listing the constraints
as simplified inequalities with integer coefficients.
(6)
(b) Calculate the maximum possible profit and minimum possible profit, in pounds, for the sale of
all milkshakes in week 1. You must show your working.
(3)
(Total 9 marks)
P51509A 8
8.
Activity Immediately preceding activities
A –
B –
C A
D A
E B
F B
G B, D
H B, D
I E, H
J C, G, I
K E, F, H
(a) Draw the activity network described in the precedence table, using activity on arc. Your
activity network must contain only the minimum number of dummies.
(5)
The earliest start time for activity G is 12 and the latest finish time for activity E is 25
(c) State whether the path ADHIJ is a critical path. Justify your answer.
(2)
(Total 8 marks)
TOTAL FOR PAPER: 75 MARKS
END
P51509A 9
BLANK PAGE
P51509A 10
BLANK PAGE
P51509A 11
BLANK PAGE
P51509A 12
Write your name here
Surname Other names
Decision Mathematics D1
Advanced/Advanced Subsidiary
Turn over
P51509A
©2018 Pearson Education Ltd.
1/1/1/1/
*P51509A0120*
Leave
blank
1.
A 1 A 1
C 3 C 3
D 4 D 4
E 5 E 5
F 6 F 6
Figure 1 Figure 2
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
2
*P51509A0220*
Leave
blank
Question 1 continued
A 1 A 1
DO NOT WRITE IN THIS AREA
B 2 B 2
C 3 C 3
D 4 D 4
E 5 E 5
F 6 F 6
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q1
(Total 5 marks)
3
*P51509A0320* Turn over
Leave
blank
2.
Key:
0 y 20 27
H(4) M(7)
C(6) J(4)
6 16 27
Figure 3
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
4
*P51509A0420*
Leave
blank
Question 2 continued
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
DO NOT WRITE IN THIS AREA
DO NOT WRITE IN THIS AREA
DO NOT WRITE IN THIS AREA
Grid 1
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q2
(Total 10 marks)
5
*P51509A0520* Turn over
Leave
blank
3.
B 4 C
10
11 27 35
14
H 24 F E D
20
12 20
34
8
Working values
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
6
*P51509A0620*
Leave
blank
Question 3 continued C
4
B
DO NOT WRITE IN THIS AREA
10
G
18 24 10
33
20 11 A 35
27 D
14
24 F 20
H 12 E
34
8 31
J
26
Figure 4
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
Q3
_______________________________________________________________________
(Total 12 marks)
7
*P51509A0720* Turn over
Leave
blank
4.
y
R
1
Figure 5
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
8
*P51509A0820*
Leave
blank
Question 4 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
9
*P51509A0920* Turn over
Question 4 continued
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
10
*P51509A01020*
Leave
blank
Question 4 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q4
(Total 11 marks)
11
*P51509A01120* Turn over
Leave
blank
5. C
81
H 27
17 E
K
Figure 6
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
12
*P51509A01220*
Leave
blank
Question 5 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q5
(Total 7 marks)
13
*P51509A01320* Turn over
Leave
blank
6.
30 11 21 53 50 39 16 4 60 43
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
14
*P51509A01420*
Leave
blank
Question 6 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
15
*P51509A01520* Turn over
Leave
blank
Question 6 continued
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
16
*P51509A01620*
Leave
blank
Question 6 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q6
(Total 13 marks)
17
*P51509A01720* Turn over
Leave
blank
7.
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
18
*P51509A01820*
Leave
blank
Question 7 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q7
(Total 9 marks)
19
*P51509A01920* Turn over
Leave
blank
8.
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q8
(Total 8 marks)
TOTAL FOR PAPER: 75 MARKS
END
20
*P51509A02020*