Edexcel D1 (Decision Mathematics 1) 2017 June

1. $$\begin{array} { l l l l l l l l l l l } 2.5 & 0.9 & 3.1 & 1.4 & 1.5 & 2.0 & 1.9 & 1.2 & 0.3 & 0.4 & 3.9 \end{array}$$ The numbers in the list are the lengths, in metres, of eleven pieces of wood. They are to be cut from planks of wood of length 5 metres. You should ignore wastage due to cutting.

1. Calculate a lower bound for the number of planks needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how these pieces could be cut from 5 metre planks.
3. Carry out a quick sort to produce a list of the lengths in descending order. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from 5 metre planks.

2. The table shows the costs, in pounds, of connecting seven computer terminals, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G, to a server, S.

1. Use Prim's algorithm, starting at S , to find the minimum spanning tree for this table of costs. You must clearly state the order in which you select the edges of your tree.
   (3)
2. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. State the minimum cost, in pounds, of connecting the seven computer terminals to the server.
3. Explain why it is not necessary to check for cycles when using Prim's algorithm.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Andrea (A), Baasim (B), Charlie (C), Deirdre (D), Ean (E) and Fen-Fang (F), to six tasks, 1, 2, 3, 4, 5 and 6.

1. Write down the technical name given to the type of graph shown in Figure 1.
   (1) Figure 2 shows an initial matching.
2. Starting from the initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path you used and state your complete matching.
3. State a different complete matching from the one found in (b).
4. By considering the workers who must be allocated to particular tasks, explain why there are exactly two different complete matchings.

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, 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 late event times.
2. Determine the critical activities and the length of the critical path.
3. Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
4. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
5. Use your 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 times and activities.

5. A school awards two types of prize, junior and senior. The school decides that it will award at least 25 junior prizes and at most 60 senior prizes.
Let \(x\) be the number of junior prizes that the school awards and let \(y\) be the number of senior prizes that the school awards.

1. Write down two inequalities to model these constraints.
   (2) Two further constraints are $$\begin{aligned} & 2 x + 5 y \geqslant 250
   & 5 x - 3 y \leqslant 150 \end{aligned}$$
2. Add lines and shading to Diagram 1 in the answer book to represent all four of these constraints. Hence determine the feasible region and label it \(R\). The cost of a senior prize is three times the cost of a junior prize. The school wishes to minimise the cost of the prizes.
3. State the objective function, giving your answer in terms of \(x\) and \(y\).
4. Determine the exact coordinates of the vertices of the feasible region. Hence use the vertex method to find the number of junior prizes and the number of senior prizes that the school should award. You should make your working clear.

6. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 223]} Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.

1. Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length. On a particular day, Pamela must include C in her route.
2. Find the shortest route from A to B that includes C , and state its length.
   (2) Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
3. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, and calculate its length. You must make your calculation clear. Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
5. State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).

7. Draw the activity network described in this precedence table, using activity on arc and dummies only where necessary.