Edexcel D1 (Decision Mathematics 1) 2023 June

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 days, to complete the activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. Calculate the maximum number of days by which activity H could be delayed without lengthening the completion time of the project. You must make the numbers used in your calculation clear.
3. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
4. Schedule the activities on Grid 1 in the answer book, using the minimum number of workers, so that the project is completed in the minimum time.

2. A list of eleven numbers is to be sorted into descending order. After one pass, the quick sort algorithm produces the following list $$\begin{array} { l l l l l l l l l l l } 17 & 33 & 14 & 25 & 23 & 28 & 21 & 13 & 9 & 6 & 10 \end{array}$$

1. State, with a reason, which number was used as a pivot for the first pass.
2. Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85

3. In this question, the function \(\operatorname { INT } ( X )\) is the largest integer less than or equal to \(X\). For example, $$\begin{aligned} \mathrm { INT } ( 5.7 ) & = 5
\mathrm { INT } ( 8 ) & = 8
\mathrm { INT } ( - 2.3 ) & = - 3 \end{aligned}$$ Consider the following algorithm.
Step 1 Input \(N\)
Step 2 Calculate \(A = N \div 10\)
Step 3 Let \(B = \operatorname { INT } ( A )\)
Step 4 Calculate \(C = B \times 10\)
Step 5 Calculate \(D = N - C\)
Step 6 Output \(D\)
Step \(7 \quad\) Replace \(N\) by \(B\)
Step 8 If \(N = 0\) then STOP, otherwise go back to Step 2

1. Complete the table in the answer book, using \(N = 4217\), to show the results obtained at each step of the algorithm.
2. Explain how the output values of the algorithm relate to the original input \(N\), where \(N\) is any positive integer.

4. \begin{figure}[h] \end{figure} Figure 2 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 are shown on the graph.

1. Determine the inequalities that define the feasible region.
2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = 2 x + k y\)
3. For the case \(k = 3\), use the point testing method to find the optimal vertex of the feasible region and state the corresponding value of \(P\).
4. Determine the range of values for \(k\) for which the optimal vertex found in (c) is still optimal.

5.

1. Draw the activity network described in the precedence table above, using activity on arc and the minimum number of dummies. A project is modelled by the activity network drawn in (a). Each activity requires exactly one worker. The project is to be completed in the shortest possible time. The table below gives the time, in hours, to complete three of the activities.

   Activity	Duration (in hours)
   A	10
   E	7
   F	8

   The length of the critical path AEFK is 33 hours.
2. Determine the range of possible values for the duration of activity J. You must make your method and working clear.

6. \begin{figure}[h] \end{figure} [The total weight of the network is 315]
Figure 3 represents a network of roads between nine parks, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in miles, 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 parks need to be inspected. Robin must travel along each road at least once. Robin wishes to minimise the length of the inspection route. Robin will start the inspection route at C and finish at E .
2. By considering the pairings of all relevant nodes, find the length of Robin's route.
3. State the number of times Robin will pass through G . It is now decided to start and finish the inspection route at A. Robin must still minimise the length of the route and travel along each road at least once.
4. Calculate the difference between the lengths of the two inspection routes.
5. State the edges that need to be traversed twice in the route that starts and finishes at A , but do not need to be traversed twice in the route that starts at C and finishes at E .

7. The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H. A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is \(x \mathrm {~km}\) where \(32 \leqslant x \leqslant 35\)

1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
2. Use your answer to (a) to determine an initial upper bound for the length of the tourist's route.
3. Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist's route. Write down the route that gives this upper bound. The nearest neighbour algorithm starting at E gives a route of $$\mathrm { E } - \mathrm { H } - \mathrm { A } - \mathrm { D } - \mathrm { G } - \mathrm { C } - \mathrm { B } - \mathrm { F } - \mathrm { E }$$
4. State which of these two nearest neighbour routes gives the better upper bound. Give reasons for your answer. Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
5. Determine the smallest interval that must contain the optimal length of the tourist's route. You must make your method and working clear.

8. A headteacher is deciding how to allocate prizes to the students who are leaving at the end of the school year. There are three categories of prize: academic, sport, and leadership.

• Each academic prize costs \(\pounds 14\), each sport prize costs \(\pounds 8\), and each leadership prize costs \(\pounds 12\). The total amount available to spend on all prizes is \(\pounds 976\)
• For every 5 academic prizes there must be at least 2 leadership prizes
• At least half the prizes must be academic
• \(20 \%\) of the prizes must be for sport

The headteacher wishes to maximise the total number of prizes.
Let \(x , y\) and \(z\) represent the number of academic, sport and leadership prizes respectively.

1. Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective and listing the constraints as simplified inequalities with integer coefficients. Given that the headteacher awards 16 sport prizes,
2. calculate the corresponding number of leadership prizes that the headteacher awards. You must show your working.