Edexcel D1 (Decision Mathematics 1) 2019 June

1. The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.

1. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
2. Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
3. Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads between ten villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.

1. Use Dijkstra's algorithm to find the shortest route from A to J. State the route and its length. During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
2. Use Prim's algorithm, starting at A , to find a minimum connector for the five villages \(\mathrm { A } , \mathrm { B }\), C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
3. Use Kruskal's algorithm to find a minimum connector for the five villages \(\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.
4. Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.

3. Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below. $$\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}$$

1. Calculate a lower bound for the number of tour groups required. You must make your method clear.
2. Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups. The above list of numbers is to be sorted into descending order.
3. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
4. Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-04_712_1141_1363_463} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} [The total weight of the network is 227.2]
   Figure 2 represents the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum's entrance at A .
5. Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.
6. Write down a possible shortest route, giving its length. Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.
7. State the finishing vertex of Sally's new route and calculate the difference in length between this new route and the route found in (f).

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

1. Explain the significance of the dummy activity
   1. from event 2 to event 3
   2. from event 6 to event 7
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. State the minimum project completion time and list the critical activities. The duration of activity H changes to \(x\) hours.
4. Find, in terms of \(x\) where necessary,
   1. the possible new early event time for event 7
   2. the possible new late event time for event 7 Given that the duration of activity H is such that the minimum project completion time is four hours greater than the time found in (c),
5. determine the value of \(x\).

5. A clothing shop sells a particular brand of shirt, which comes in three different sizes, small, medium and large. Each month the manager of the shop orders \(x\) small shirts, \(y\) medium shirts and \(z\) large shirts.
The manager forms constraints on the number of each size of shirts he will have to order.
One constraint is that for every 3 medium shirts he will order at least 5 large shirts.

1. Write down an inequality, with integer coefficients, to model this constraint. Two further constraints are $$x + y + z \geqslant 250 \text { and } x \leqslant 0.2 ( x + y + z )$$
2. Use these two constraints to write down statements, in context, that describe the number of different sizes of shirt the manager will order. The cost of each small shirt is \(\pounds 6\), the cost of each medium shirt is \(\pounds 10\) and the cost of each large shirt is \(\pounds 15\) The manager must minimise the total cost of all the shirts he will order.
3. Write down the objective function. Initially, the manager decides to order exactly 150 large shirts.
4. 1. Rewrite the constraints, as simplified inequalities with integer coefficients, in terms of \(x\) and \(y\) only.
   2. Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region \(R\).
5. Use the objective line method to find the optimal vertex, \(V\), of the feasible region. You must make your objective line clear and label \(V\).
6. Write down the number of each size of shirt the manager should order. Calculate the total cost of this order. Later, the manager decides to order exactly 50 small shirts and exactly 75 medium shirts instead of 150 large shirts.
7. Find the minimum number of large shirts the manager should order and show that this leads to a lower cost than the cost found in (f).

6. 2. \begin{figure}[h] \end{figure} Shortest route: \(\_\_\_\_\) Length of shortest route: \(\_\_\_\_\) \begin{figure}[h] \end{figure} 3. \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\)
\begin{figure}[h] \end{figure} 4. \includegraphics[max width=\textwidth, alt={}, center]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-20_572_1454_1021_248} \section*{Key:} \section*{Diagram 1} 5. \section*{Diagram 1} 6.