WDM01 01 Que 20190621
WDM01 01 Que 20190621
WDM01 01 Que 20190621
Mathematics
International Advanced Subsidiary/Advanced Level
Decision Mathematics D1
P56387A
©2019 Pearson Education Ltd.
1/1/1/
*P56387A*
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 workers, A, B, C, D, E and F, to six tasks, 1, 2, 3, 4,
5 and 6. Each task must be assigned to exactly one worker and each worker must be assigned to
exactly one task.
(a) Write down the technical name given to the type of graph shown in Figure 1.
(1)
(b) Starting from the given initial matching, use the maximum matching algorithm to find an
alternating path from C to 1. Hence find an improved matching. You should list the alternating
path you use, and state your improved matching.
(3)
(d) Starting from the improved matching found in (b) use the maximum matching algorithm to find
a complete matching. You should list the alternating path you use, and state your complete
matching.
(3)
(Total 8 marks)
P56387A 2
2. B 9 D
3
4 21 8
A
8
E
C 15
21
42 G 5
J F
30 10 7
6
22
K
H
31
Figure 3
(a) Use Dijkstra’s algorithm to find the shortest route from A to J. State the route and its length.
(6)
During the winter, the council needs to ensure that all ten villages are accessible by road even if
there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
(b) Use Prim’s algorithm, starting at A, to find a minimum connector for the five villages A, B,
C, D and E. You must clearly state the order in which you select the edges of your minimum
connector.
(2)
(c) Use Kruskal’s algorithm to find a minimum connector for the five villages F, G, H, J and K.
You must clearly show the order in which you consider the edges. For each edge, state whether
or not you are including it in your minimum connector.
(2)
(d) Calculate the total length of road that the council must keep clear of snow to ensure that all ten
villages are accessible.
(1)
(Total 11 marks)
8 17 9 14 18 12 22 10 15 7
(a) Calculate a lower bound for the number of tour groups required. You must make your method
clear.
(2)
(b) Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from
each school to tour groups.
(2)
(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) Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a
second allocation of pupils to tour groups.
(2)
F B
G 15.2 10.3
11.1 14.5
22.1
D 21.3 C
Figure 4
[The total weight of the network is 227.2]
Figure 4 represents the corridors in the museum. The number on each arc is the length, in metres,
of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each
corridor at least once during each tour. Sally wishes to minimise the length of her route. She must
start and finish at the museum’s entrance at A.
(e) Use an appropriate algorithm to find the corridors that Sally will need to traverse twice.
You should make your method and working clear.
(4)
P56387A 4
(f) Write down a possible shortest route, giving its length.
(2)
Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum
length that includes each corridor at least once needs to be found.
(g) State the finishing vertex of Sally’s new route and calculate the difference in length between
this new route and the route found in (f).
(2)
(Total 18 marks)
4 6
K(2)
Figure 5
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 required, in hours, to complete the
corresponding activity. The numbers in circles are the event numbers.
(b) Complete Diagram 1 in the answer book to show the early event times and the late event times.
(4)
(c) State the minimum project completion time and list the critical activities.
(2)
Given that the duration of activity H is such that the minimum project completion time is four hours
greater than the time found in (c),
P56387A 6
5. A clothing shop sells a particular brand of shirt, which comes in three different sizes, small, medium
and large.
Each month the manager of the shop orders x small shirts, y medium shirts and z large shirts.
The manager forms constraints on the number of each size of shirts he will have to order.
One constraint is that for every 3 medium shirts he will order at least 5 large shirts.
(a) Write down an inequality, with integer coefficients, to model this constraint.
(2)
(b) Use these two constraints to write down statements, in context, that describe the number of
different sizes of shirt the manager will order.
(3)
The cost of each small shirt is £6, the cost of each medium shirt is £10 and the cost of each large
shirt is £15
The manager must minimise the total cost of all the shirts he will order.
(d) (i) Rewrite the constraints, as simplified inequalities with integer coefficients, in terms of
x and y only.
(ii) Represent these constraints on Diagram 1 in the answer book. Hence determine, and label,
the feasible region R.
(6)
(e) Use the objective line method to find the optimal vertex, V, of the feasible region. You must
make your objective line clear and label V.
(2)
(f) Write down the number of each size of shirt the manager should order. Calculate the total cost
of this order.
(2)
Later, the manager decides to order exactly 50 small shirts and exactly 75 medium shirts instead of
150 large shirts.
(g) Find the minimum number of large shirts the manager should order and show that this leads to
a lower cost than the cost found in (f).
(2)
(Total 18 marks)
(a) Draw the activity network described in the precedence table, using activity on arc and exactly
four dummies.
(5)
Given that there is a unique critical path for the network and that K is a critical activity,
Given instead that all the activities shown in the precedence table have the same duration and K is
not necessarily critical,
(c) state all the possible critical paths for the network.
(2)
(Total 8 marks)
TOTAL FOR PAPER: 75 MARKS
END
P56387A 8
Please check the examination details below before entering your candidate information
Candidate surname Other names
Mathematics
International Advanced Subsidiary/Advanced Level
Decision Mathematics D1
Turn over
P56387A
©2019 Pearson Education Ltd.
1/1/1/
*P56387A0120*
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
*P56387A0220*
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 8 marks)
3
*P56387A0320* Turn over
Leave
blank
2.
B 9 D
8 C E
15
21
J 42 G 5 F
30 7
K 22 H
31
Key:
Order of Final
Vertex
labelling value
Working values
DO NOT WRITE IN THIS AREA
4
*P56387A0420*
Leave
blank
Question 2 continued
DO NOT WRITE IN THIS AREA
B 9 D
3
4 21 8
A
8
E
C 15
21
42 G 5
J F
30 10 7
6
22
K
H
DO NOT WRITE IN THIS AREA
31
Figure 3
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
5
*P56387A0520* Turn over
Leave
blank
Question 2 continued
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
6
*P56387A0620*
Leave
blank
Question 2 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q2
(Total 11 marks)
7
*P56387A0720* Turn over
Leave
blank
3.
8 17 9 14 18 12 22 10 15 7
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
8
*P56387A0820*
Leave
blank
Question 3 continued
8 17 9 14 18 12 22 10 15 7
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
9
*P56387A0920* Turn over
Leave
blank
Question 3 continued
11.1 14.5
22.1
D 21.3 C
Figure 4
[The total weight of the network is 227.2]
10
*P56387A01020*
Leave
blank
Question 3 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q3
(Total 18 marks)
11
*P56387A01120* Turn over
Leave
blank
4.
_______________________________________________________________________
D(4) I(11)
B(4) F(6)
N(10)
G(3) J(1)
Key:
C(10)
Early
event
K(2)
time
Late
event
time
Diagram 1
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
12
*P56387A01220*
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 12 marks)
13
*P56387A01320* Turn over
Leave
blank
5.
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
14
*P56387A01420*
Leave
blank
Question 5 continued
y
DO NOT WRITE IN THIS AREA
120
100
80
60
40
20
0
0 10 20 30 40 50 60 70 80 90 100 110 120 x
DO NOT WRITE IN THIS AREA
Diagram 1
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
15
*P56387A01520* Turn over
Leave
blank
Question 5 continued
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
16
*P56387A01620*
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 18 marks)
17
*P56387A01720* Turn over
DO NOT WRITE IN THIS AREA DO NOT WRITE IN THIS AREA DO NOT WRITE IN THIS AREA
Leave
blank
*P56387A01820*
18
6.
Leave
blank
Question 6 continued
DO NOT WRITE IN THIS AREA
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
19
*P56387A01920* Turn over
Leave
blank
Question 6 continued
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q6
(Total 8 marks)
20
*P56387A02020*