Edexcel D1 (Decision Mathematics 1) 2021 October

1. (a) Explain what is meant by the term 'path'.
   (2)

\begin{figure}[h] \end{figure} Figure 1 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Piatrice wishes to travel from A to J.
(b) Use Dijkstra's algorithm to find the shortest path Piatrice could take from A to J. State your path and its length.
(6) Piatrice needs to return from J to A via G.
(c) Find the shortest path Piatrice could take from J to A via G and state its length.

2. Chris has been asked to design a badge in the shape of a triangle XYZ subject to the following constraints.

• Angle \(Y\) should be at least three times the size of angle \(X\)
• Angle \(Z\) should be at least \(50 ^ { \circ }\) larger than angle \(X\)
• Angle \(Y\) must be at most \(120 ^ { \circ }\)

Chris has been asked to maximise the sum of the angles \(X\) and \(Y\).
Let \(x\) be the size of angle \(X\) in degrees.
Let \(y\) be the size of angle \(Y\) in degrees.
Let z be the size of angle \(Z\) in degrees.
Formulate this information as a linear programming problem in \(x\) and \(y\) only. State the objective and list the constraints as simplified inequalities with integer coefficients. You are not required to solve this problem.

3. The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H. Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.
2. State the weight of the minimum spanning tree.
3. Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy’s route.
4. Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
5. State the best upper bound that can be obtained by using your answers to (c) and (d).
6. Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route. You must make your method and working clear.
7. Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy's route.

4. \begin{figure}[h] \end{figure} The network in Figure 2 shows the activities that need to be carried out by a company to complete a project. Each activity is represented by an arc, and the duration, in days, is shown in brackets. Each activity requires one worker. The early event times and the late event times are shown at each vertex.

1. Complete the precedence table in the answer book.
   (2) A cascade chart for this project is shown on Grid 1.
   \includegraphics[max width=\textwidth, alt={}, center]{d409aaae-811d-4eca-b118-efc927885f97-07_885_1358_276_356} \section*{Grid 1}
2. Use Figure 2 and Grid 1 to find the values of \(v , w , x , y\) and \(z\). The project is to be completed in the minimum time using as few workers as possible.
3. Calculate a lower bound for the minimum number of workers required. You must show your working.
4. On Grid 2 in your answer book, construct a scheduling diagram for this project. Before the project begins it is found that activity F will require an additional 5 hours to complete. The durations of all other activities are unchanged. The project is still to be completed in the shortest possible time using as few workers as possible.
5. State the new minimum project completion time and state the new critical path.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 166] Figure 3 models a network of cycle lanes that must be inspected. The number on each arc represents the length, in km, of the corresponding cycle lane. Lance needs to cycle along each lane at least once and wishes to minimise the length of his inspection route. He must start and finish at A.

1. Use an appropriate algorithm to find the length of the route. State the cycle lanes that Lance will need to traverse twice. You should make your method and working clear.
   (6)
2. State the number of times that vertex C appears in Lance's route.
   (1) It is now decided that the inspection route may finish at any vertex. Lance will still start at A and must cycle along each lane at least once.
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 this new minimum route.
   (3)

6. A linear programming problem in \(x\) and \(y\) is described as follows. Maximise \(P = k x + y\), where \(k\) is a constant
subject to: \(\quad 3 y \geqslant x\) $$\begin{aligned} x + 2 y & \leqslant 130
4 x + y & \geqslant 100
4 x + 3 y & \leqslant 300 \end{aligned}$$

1. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it \(R\).
2. For the case when \(k = 0.8\)
   1. use the objective line method to find the optimal vertex, \(V\), of the feasible region. You must draw and label your objective line and label vertex \(V\) clearly.
   2. calculate the coordinates of \(V\) and hence calculate the corresponding value of \(P\) at \(V\). Given that for a different value of \(k , V\) is not the optimal vertex of \(R\),
3. determine the range of possible values for \(k\). You must make your method and working clear.

7. The numbers listed below are to be packed into bins of size \(n\), where \(n\) is a positive integer.
14
20
23
17
15
22
19
25

20
23
17
15
22
19
25
13
28
32 A lower bound for the number of bins required is 4

1. Determine the range of possible values of \(n\). You must make your method clear.
   (3)
2. Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
   (4) When the first-fit bin packing algorithm is applied to the original list of numbers, the following allocation is achieved. \end{table}
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-14_1193_1586_1270_185}
   Shortest path from A to J: \(\_\_\_\_\)
   Length of shortest path from A to J: \(\_\_\_\_\) \section*{2.
   \(\_\_\_\_\)} \section*{3.}

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-22_755_1157_246_404} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}

3. Activity	Immediately preceding activities
   A
   B
   C
   D
   E

   Activity	Immediately preceding activities
   F
   G
   H
   I
   J

   Activity	Immediately preceding activities
   K
   L
   M

   $$v = \ldots \quad x = \ldots \quad y = \ldots$$ \includegraphics[max width=\textwidth, alt={}, center]{d409aaae-811d-4eca-b118-efc927885f97-23_2255_56_315_37}
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-23_1153_1338_303_310}
   \section*{Grid 2} 5. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-24_591_1433_255_260} \captionsetup{labelformat=empty} \caption{Figure 3
   [0pt] [The total weight of the network is 166]}
   \end{figure} 6.
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-26_1287_1645_301_162}
   \section*{Diagram 1} 7. \(\begin{array} { l l l l l l l l l l l } 14 & 20 & 23 & 17 & 15 & 22 & 19 & 25 & 13 & 28 & 32 \end{array}\)