Edexcel D1 (Decision Mathematics 1) 2014 June

1. The table shows the travelling times, in seconds, to walk between seven departments in a college.

1. Use Prim's algorithm, starting at Art, to find the minimum spanning tree for the network represented by the table. 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.
3. State the weight of the tree.

2. (a) Draw the activity network described in the precedence table below, using activity on arc and exactly two dummies. (b) Explain why each of the two dummies is necessary.

3. \begin{figure}[h] \end{figure} Figure 1 models a network of tracks in a forest that need to be inspected by a park ranger. The number on each arc is the length, in km, of that section of the forest track. Each track must be traversed at least once and the length of the inspection route must be minimised. The inspection route taken by the ranger must start and end at vertex A.

1. Use the route inspection algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
2. State the number of times that vertex J would appear in the inspection route. The landowner decides to build two huts, one hut at vertex K and the other hut at a different vertex. In future, the ranger will be able to start his inspection route at one hut and finish at the other. The inspection route must still traverse each track at least once.
3. Determine where the other hut should be built so that the length of the route is minimised. You must give reasons for your answer and state a possible route and its length.

4. Six pupils, Ashley (A), Fran (F), Jas (J), Ned (N), Peter (P) and Richard (R), each wish to learn a musical instrument. The school they attend has six spare instruments; a clarinet (C), a trumpet (T), a violin (V), a keyboard (K), a set of drums (D) and a guitar (G). The pupils are asked which instruments they would prefer and their preferences are given in the table above. It is decided that each pupil must learn a different instrument and each pupil needs to be allocated to exactly one of their preferred instruments.

1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of pupils to instruments. Initially Ashley, Fran, Jas and Richard are each allocated to their first preference.
2. Show this initial matching on Diagram 2 in the answer book.
3. Starting with the initial matching from (b), apply the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and give your improved matching.
4. Explain why a complete matching is not possible. Fran decides that as a third preference she would like to learn to play the guitar. Peter decides that as a second preference he would like to learn to play the drums.
5. Starting with the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.

5. \begin{figure}[h] \end{figure} Sharon is planning a road trip from Preston to York. Figure 2 shows the network of roads that she could take on her trip. The number on each arc is the length of the corresponding road in miles.

1. Use Dijkstra's algorithm to find the shortest route from Preston (P) to York (Y). State the shortest route and its length.
   (6) Sharon has a friend, John, who lives in Manchester (M). Sharon decides to travel from Preston to York via Manchester so she can visit John. She wishes to minimise the length of her route.
2. State the new shortest route. Hence calculate the additional distance she must travel to visit John on this trip. You must make clear the numbers you use in your calculation.
   (3)

6.
\(\begin{array} { l l l l l l l l l } 24 & 14 & 8 & x & 19 & 25 & 6 & 17 & 9 \end{array}\) The numbers in the list represent the exact weights, in kilograms, of 9 suitcases. One suitcase is weighed inaccurately and the only information known about the unknown weight, \(x \mathrm {~kg}\), of this suitcase is that \(19 < x \leqslant 23\). The suitcases are to be transported in containers that can hold a maximum of 50 kilograms.

1. Use the first-fit bin packing algorithm, on the list provided, to allocate the suitcases to containers.
2. Using the list provided, carry out a quick sort to produce a list of the weights in descending order. Show the result of each pass and identify your pivots clearly.
3. Apply the first-fit decreasing bin packing algorithm to the ordered list to determine the 2 possible allocations of suitcases to containers. After the first-fit decreasing bin packing algorithm has been applied to the ordered list, one of the containers is full.
4. Calculate the possible integer values of \(x\). You must show your working.

7. (a) In the context of critical path analysis, define the term 'total float'. \begin{figure}[h] \end{figure} Figure 3 is the activity network for a building project. 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.
(b) Complete Diagram 1 in the answer book to show the early event times and the late event times.
(c) State the critical activities.
(d) Calculate the maximum number of days by which activity G could be delayed without affecting the shortest possible completion time of the project. You must make the numbers used in your calculation clear.
(e) Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. The project is to be completed in the minimum time using as few workers as possible.
(f) Schedule the activities using Grid 1 in the answer book.

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

1. Write down the constraints represented on the graph.
   (2) The objective function, P , is given by $$\mathrm { P } = x + k y$$ where \(k\) is a positive constant. The minimum value of the function P is given by the coordinates of vertex A and the maximum value of the function P is given by the coordinates of vertex D .
2. Find the range of possible values for \(k\). You must make your method clear.
   (Total 8 marks)