Edexcel D1 (Decision Mathematics 1) 2022 June

1. \(\quad \begin{array} { l l l l l l l l l l } 175 & 135 & 210 & 105 & 100 & 150 & 60 & 20 & 70 & 125 \end{array}\)

The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300 kg .

1. Calculate a lower bound for the number of trucks that will be needed to transport the crates.
2. Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each pass.
3. Use the first-fit decreasing bin packing algorithm to allocate the crates to the trucks.

2. \begin{figure}[h] \end{figure} 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 of the activity, in days, is shown in brackets. The early event times and late event times are to be shown at each vertex and some have been completed. Given that

• CHN is the critical path for the project
• the total float on activity B is twice the duration of the total float on activity I
  1. find the value of \(x\) and show that the value of \(y\) is 7
  2. Calculate the missing early event times and late event times and hence complete Diagram 1 in your answer book.

Each activity requires one worker, and the project must be completed in the shortest possible time.

Draw a cascade chart for this project on Grid 1 in your answer book, and use it 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.

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the distances, in miles, between ten towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { H }\), \(\mathrm { L } , \mathrm { M } , \mathrm { P } , \mathrm { S } , \mathrm { W }\) and Y .

1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
   (3)

   	A	B	C	H	L	M	P	S	W	Y
   A	-	6	18	15	54	29	16	26	29	74
   B	6	-	22	21	60	35	10	32	33	80
   C	18	22	-	17	59	31	12	44	11	80
   H	15	21	17	-	42	14	29	41	28	63
   L	54	60	59	42	-	40	70	28	61	21
   M	29	35	31	14	40	-	43	55	21	61
   P	16	10	12	29	70	43	-	42	23	90
   S	26	32	44	41	28	55	42	-	55	48
   W	29	33	11	28	61	21	23	55	-	82
   Y	74	80	80	63	21	61	90	48	82	-

   The table shows the shortest distances, in miles, between the ten towns.
2. Use Prim's algorithm on the table, starting at A, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
3. State the weight of the minimum spanning tree found in (b). Sharon needs to visit all of the towns, starting and finishing in the same town, and wishes to minimise the total distance she travels.
4. Use your answer to (c) to calculate an initial upper bound for the length of Sharon's route.
5. Use the nearest neighbour algorithm on the table, starting at W , to find an upper bound for the length of Sharon's route. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at Y , an upper bound of length 212 miles was found.
6. State the best upper bound that can be obtained by using this information and your answers from (d) and (e). Give the reason for your answer.
7. By deleting W and all of its arcs, find a lower bound for the length of Sharon's route. Sharon decides to take the route found in (e).
8. Interpret this route in terms of the actual towns visited.

4. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = - x + y\)
subject to $$\begin{gathered} x + 2 y + z \leqslant 15
3 x - 4 y + 2 z \geqslant 1
2 x + y + z = 14
x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$

1. 1. Eliminate \(z\) from the first two inequality constraints, simplifying your answers.
   2. Hence state the maximum possible value of \(P\) Given that \(P\) takes the maximum possible value found in (a)(ii),
2. 1. determine the maximum possible value of \(x\)
   2. Hence find a solution to the linear programming problem.

5. The precedence table shows the eleven activities required to complete a project.

1. Draw the activity network for the project, using activity on arc and the minimum number of dummies.
   (5) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-07_314_1385_1464_347} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 shows a schedule for the project. Each of the activities shown in the precedence table requires one worker. The time taken to complete each activity is in hours and the project is to be completed in the minimum possible time.
2. 1. State the minimum completion time for the project.
   2. State the critical activities.
   3. State the total float on activity G and the total float on activity K .
      (4)

6. \begin{figure}[h] \end{figure} [The total weight of the network is \(383 + x\) ]
Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\), H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible. The time taken to travel between towns G and J is unknown and is denoted by \(x\) minutes. Dijkstra's algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the "Order of labelling" and "Final value" at A and J, and the "Working values" at J , have already been completed.

1. Use Dijkstra's algorithm to find the fastest time to travel from A to H . State the quickest route. Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A . It is given that his route will take at least 440 minutes.
2. Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of \(x\).
3. Write down a possible route for Ezra. A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A . It is given that this inspection route takes exactly 488 minutes.
4. Determine the value of \(x\). You must give reasons for your answer.

7. \begin{figure}[h] \end{figure} Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The equations of two of the lines and the three intersection points, \(A\), \(B\) and \(C\), are shown. The coordinates of \(C\) are \(\left( \frac { 35 } { 4 } , \frac { 15 } { 4 } \right)\) The objective function is \(P = x + 3 y\)
When the objective is to maximise \(x + 3 y\), the value of \(P\) is 24
When the objective is to minimise \(x + 3 y\), the value of \(P\) is 10

1. 1. Find the coordinates of \(A\) and \(B\).
   2. Determine the inequalities that define \(R\). An additional constraint, \(y \geqslant k x\), where \(k\) is a positive constant, is added to the linear programming problem.
2. Determine the greatest value of \(k\) for which this additional constraint does not affect the feasible region.