Edexcel D1 (Decision Mathematics 1) 2018 Specimen

1. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.

Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

1. Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound.
2. Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Liz's route.
3. Starting by deleting F, and all of its arcs, find a lower bound for the length of Liz's route.
4. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.

3.
\(12.1 \quad 9.3\)
\(15.7 \quad 10.9\)
17.4
6.4
20.1
7.9
14.0

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass.
   2. Write down the total number of comparisons and the total number of swaps performed during your two passes.
3. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear.
4. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33
5. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer.

4. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 196]} Figure 1 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to K . State the quickest route. On a particular day Oliver must travel from B to K via A .
2. Find a route of minimal time from B to K that includes A , and state its length. Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.
3. Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear.

5. A linear programming problem in \(x\) and \(y\) is described as follows. $$\begin{array} { l l } \text { Maximise } & \mathrm { P } = 5 x + 3 y
\text { subject to: } & x \geqslant 3
& x + y \leqslant 9
& 15 x + 22 y \leqslant 165
& 26 x - 50 y \leqslant 325 \end{array}$$

1. Add lines and shading to Diagram 2 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
2. 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.
3. Calculate the exact coordinates of vertex V and hence calculate the corresponding value of P at V . The objective is now to minimise \(5 x + 3 y\), where \(x\) and \(y\) are integers.
4. Write down the minimum value of \(5 x + 3 y\) and the corresponding value of \(x\) and corresponding value of \(y\).

6. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time required, in hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.

1. Explain the significance of the dummy activity
   1. from event 5 to event 6
   2. from event 7 to event 9 .
2. Complete Diagram 3 in the answer book to show the early event times and the late event times.
3. State the minimum project completion time.
4. Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time. You must show your working.
5. On Grid 1 in your answer book, draw a cascade (Gantt) chart for this project.
6. On Grid 2 in your answer book, construct a scheduling diagram to show that this project can be completed with three workers in just one more hour than the minimum project completion time.