Edexcel D1 (Decision Mathematics 1) 2020 June

1. The table below shows the distances, in metres, between six vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , in a network.

1. Draw the weighted network using the vertices given in Diagram 1 in the answer book.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.
3. Draw the minimum spanning tree on Diagram 2 in the answer book and state its total weight.

2. (a) (i) Describe how to carry out the first pass of a bubble sort when it is used to sort a list of \(n\) numbers into ascending order.
(ii) Write down the circumstances under which a bubble sort stops. A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads
0.9
0.5
0.7
1.2
1.5
1.4
1.1
1.7
2.2
3.2
(b) Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.
(c) Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.
(d) Use the first-fit decreasing bin packing algorithm to determine how the ten numbers listed above can be packed into bins of size 4

3. The table below shows the least distances, in km, between six towns, A, B, C, D, E and F. Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.

1. Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei'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 Mei's route.
3. Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.

4. (a) Draw the activity network described by the precedence table below, using activity on arc. Use dummies only where necessary.
(5) Given that K is a critical activity,
(b) state which other activities must also be critical.
(1) Given instead that all activities shown in the precedence table have the same duration and K is not necessarily critical,
(c) state the critical path for the network.
(1)

5. \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 corresponding 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 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 on Grid 1 in the answer book using the minimum number of workers so that the project is completed in the minimum time. Additional resources become available, which can shorten the duration of one of activities D, G or P by one day.
4. Determine which of these three activities should be shortened to allow the project to be completed in the minimum time. You must give reasons for your answer.

6. \begin{figure}[h] \end{figure} The graph in Figure 2 is being used to solve a linear programming problem in \(x\) and \(y\). The three constraints have been drawn on the graph and the rejected regions have been shaded out. The three vertices of the feasible region \(R\) are labelled \(\mathrm { A } , \mathrm { B }\) and C .

1. Determine the inequalities that define \(R\).
   (2) The objective function, \(P\), is given by $$P = a x + b y$$ where \(a\) and \(b\) are positive constants.
   The minimum value of \(P\) is 8 and the maximum value of \(P\) occurs at C .
2. Find the range of possible values of \(a\). You must make your method clear.
   (5)

7. \begin{figure}[h] \end{figure} [The total weight of the network is \(205 + 3 x\) ] Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Malcolm wishes to minimise the time spent driving from his home at A to his office at H . The delays from roadworks on two of the roads leading in to H vary daily, and so the time taken to drive along these roads is expressed in terms of \(x\), where \(x\) is fixed for any given day and \(x > 0\)

1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H. State the length of each route, leaving your answer in terms of \(x\) where necessary. On Monday, Malcolm needs to check each road. He must travel along each road at least once. He must start and finish at H and minimise the total time taken for his inspection route. Malcolm finds that his minimum duration inspection route requires him to traverse exactly four roads twice and the total time it takes to complete his inspection route is 307 minutes.
2. Calculate the minimum time taken for Malcolm to travel from A to H on Monday. You must make your method and working clear.

8. A bakery makes three types of doughnut. These are ring, jam and custard. The bakery has the following constraints on the number of doughnuts it must make each day.

• The total number of doughnuts made must be at least 200
• They must make at least three times as many ring doughnuts as jam doughnuts
• At most \(70 \%\) of the doughnuts the bakery makes must be ring doughnuts
• At least a fifth of the doughnuts the bakery makes must be jam doughnuts

It costs 8 pence to make each ring doughnut, 10 pence to make each jam doughnut and 14 pence to make each custard doughnut. The bakery wants to minimise the total daily costs of making the required doughnuts. Let \(x\) represent the number of ring doughnuts, let \(y\) represent the number of jam doughnuts and let z represent the number of custard doughnuts the bakery makes each day.

1. Formulate this as a linear programming problem stating the objective and listing the constraints as simplified inequalities with integer coefficients. On a given day, instead of making at least 200 doughnuts, the bakery requires that exactly 200 doughnuts are made. Furthermore, the bakery decides to make the minimum number of jam doughnuts which satisfy all the remaining constraints. Given that the bakery still wants to minimise the total cost of making the required doughnuts, use algebra to
2. 1. calculate the number of each type of doughnut the bakery will make on that day,
   2. calculate the corresponding total cost of making all the doughnuts. \section*{END}