Edexcel D1 (Decision Mathematics 1) 2024 June

1.

1. Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14
2. The list of 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.
3. Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14
4. Explain why the number of bins used in part (c) is optimal.
5. Use the binary search algorithm to try to locate 3.0 in the list of numbers. Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.

2. \begin{figure}[h] \end{figure} [The sum of the durations of all the activities is 59 days.]
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, in days, of the corresponding activity is shown in brackets. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. 1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
   2. State the minimum completion time of the project.
2. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
3. Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.

3. \begin{figure}[h] \end{figure} Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route.
   (6)
2. Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer. You do not need to find the minimum spanning tree.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 494]
Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3. The number on each arc represents the lengths, in kilometres, of the corresponding road.
The table below shows the shortest distances, in kilometres, between the nine factories. \section*{Table of shortest distances}

1. Starting at A, use Prim's algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.
   (3)
2. State the weight of the minimum spanning tree.
   (1) A route is needed that minimises the total distance to traverse each road at least once. The route must start at E and finish at F .
3. Determine the length of this route. You must give a reason for your answer. It is now decided to start the route at C and finish the route at A . The route must include every road at least once and must still minimise the total distance travelled.
4. By considering the pairings of all relevant nodes, find the roads that need to be traversed twice. Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.
5. Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko's route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.
6. By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko's route.

5. The head of a Mathematics department needs to order three types of paper. The three types of paper are plain, lined and graph. All three types of paper are sold in reams. (A ream is 500 sheets of paper.)
Based on the last academic year the head of department formed the following constraints.

• At least half the paper must be lined
• No more than \(15 \%\) of the paper must be graph paper
• The ratio of plain paper to graph paper must be \(5 : 2\)

The cost of each ream of plain, lined and graph paper is \(\pounds 5 , \pounds 12\) and \(\pounds 15\) respectively. The head of department has at most \(\pounds 834\) to spend on paper. The head of department wants to maximise the total number of reams of paper ordered.
Let \(x , y\) and \(z\) represent the number of reams of plain paper, lined paper and graph paper ordered respectively.

1. Formulate this information as a linear programming problem in \(x\) and \(y\) only, stating the objective and listing the constraints as simplified inequalities with integer coefficients. The head of department decides to order exactly 42 reams of lined paper and still wishes to maximise the total number of reams of paper ordered.
2. Determine
   1. the total number of reams of paper to be ordered,
   2. the number of reams of graph paper to be ordered.

6.

1. Draw the activity network for the project described in the precedence table, using activity on arc and the minimum number of dummies. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-10_880_1154_1464_452} \captionsetup{labelformat=empty} \caption{Grid 1}
   \end{figure} A cascade chart for all the activities of the project, except activity \(\mathbf { L }\), is shown on Grid 1. The time taken to complete each activity is given in hours and each activity requires one worker. The project is to be completed in the minimum time using as few workers as possible.
2. State the critical activities of the project.
3. Use the 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.) The duration of activity L is \(x\) hours. Given that the total float of activity L is at most 7 hours,
4. determine the range of possible values for \(\chi\).