Edexcel D1 (Decision Mathematics 1) 2024 January

1. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 1. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time using as few workers as possible.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. Calculate the total float for activity D. You must make the numbers used in your calculation clear.
3. Calculate a lower bound for the minimum number of workers required to complete the project in the shortest possible time. You must show your working.
4. Draw a cascade chart for this project on Grid 1 in the answer book.
5. 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. \begin{table}[h] \end{table} Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
2. State the weight of the minimum spanning tree. \begin{table}[h]

   \cline { 2 - 9 } \multicolumn{1}{c|}{}	A	B	C	D	E	F	G	H
   J	33	37	41	35	\(x\)	40	28	42

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H .
   The journey time between towns E and J is \(x\) minutes where \(x > 28\)
   A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.
3. Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound. Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.
4. State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer. Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.
5. Determine the value of \(x\). You must make your method and working clear.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 458] Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to J.
   2. State the length of the shortest path from A to J . The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
2. By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice. If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
3. Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.

4.

1. Draw the activity network described in the precedence table, using activity on arc and the minimum number of dummies.
2. Given that
   • the activity network contains only one critical path
   • activity E is on this critical path
     state
     1. which activities could never be critical,
     2. which activities must be critical.

5. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\). The unshaded area, including its boundaries, forms the feasible region, \(R\). The four vertices of \(R\) are \(A ( 6,8 ) , B ( 13,12 ) , C ( 9,22 )\) and \(D ( 5,18 )\).
An objective line has been drawn and labelled on the graph.
When the objective function, \(P\), is maximised, the value of \(P\) is 540
When the objective function, \(P\), is minimised, the value of \(P\) is \(k\)
Determine the value of \(k\). You must make your method and working clear.
(You may assume that the objective function, \(P\), takes the form \(a x + b y\) where \(a\) and \(b\) are constants.)

6. The twelve numbers in the list below are to be packed into bins of size \(n\), where \(n\) is a positive integer. When the first-fit bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 28315
Bin 2: 25161811
Bin 3: 352215
Bin 4: 2713

1. Based on the packing shown above, determine the possible values of \(n\). You must give reasons for your answer.
2. The original list of twelve numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. When the first-fit decreasing bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 35315
   Bin 2: 282716
   Bin 3: 252218
   Bin 4: 151311
3. Determine the value of \(n\). You must give a reason for your answer.

7. A farmer has 100 acres of land available that can be used for planting three crops: A, B and C . It takes 2 hours to plant each acre of crop A, 1.5 hours to plant each acre of crop B and 45 minutes to plant each acre of crop C . The farmer has 138 hours available for planting. At least one quarter of the total crops planted must be crop A.
For every three acres of crop B planted, at most five acres of crop C will be planted.
The farmer expects a profit of \(\pounds 160\) for each acre of crop A planted, \(\pounds 75\) for each acre of crop B planted and \(\pounds 125\) for each acre of crop C planted. The farmer wishes to maximise the profit from planting these three crops.
Let \(x , y\) and \(z\) represent the number of acres of land used for planting crop A, crop B, and crop C respectively.

1. Formulate this information as a linear programming problem. State the objective, and list the constraints as simplified inequalities with integer coefficients. The farmer decides that all 100 acres of available land will be used for planting the three crops.
2. Explain why the maximum total profit is achieved when \(- 7 x + 10 y\) is minimised. The farmer's decision to use all 100 acres reduces the constraints of the problem to the following: $$\begin{aligned} x & \geqslant 25
   3 x + 8 y & \geqslant 300
   x + y & \leqslant 100
   5 x + 3 y & \leqslant 252
   y & \geqslant 0 \end{aligned}$$
3. Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, \(R\).
4. 1. Determine the exact coordinates of each of the vertices of \(R\).
   2. Apply the vertex method to determine how the 100 acres should be used for planting the three crops.
   3. Hence find the corresponding maximum expected profit.