Edexcel D1 (Decision Mathematics 1) 2013 June

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, \(1,2,3,4,5\) and 6.

1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
2. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.
   (6)

2.
0.6
0.2
0.4
0.5
0.7
0.1
0.9
0.3
1.5
1.6

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.
   (3)
2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.
3. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2 .
4. Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

3. The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.

1. Use Prim's algorithm, starting at A , to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them.
2. Draw your minimum connector using the vertices given in Diagram 1 in the answer book.
3. Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table.
4. Use Kruskal's algorithm to find the minimum connector. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum connector.
5. State the minimum time needed, in days, to reconnect the six towns.

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Liz wishes to travel from S to T .

1. Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length. On a particular day, Liz must include F in her route.
2. Find the shortest path from S to T that includes F , and state its length.

5. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 344 miles]} Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway. Sophie needs to travel along each section to check that it is in good condition.
She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.

1. Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
2. Write down a possible shortest inspection route, giving its length. Sophie now decides to start the inspection route at E. The route must still traverse each arc at least once but may finish at any vertex.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.

6. Harry wants to rent out boats at his local park. He can use linear programming to determine the number of each type of boat he should buy. Let \(x\) be the number of 2 -seater boats and \(y\) be the number of 4 -seater boats.
One of the constraints is $$x + y \geqslant 90$$

1. Explain what this constraint means in the context of the question. Another constraint is $$2 x \leqslant 3 y$$
2. Explain what this constraint means in the context of the question. A third constraint is $$y \leqslant x + 30$$
3. Represent these three constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R . Each 2 -seater boat costs \(\pounds 100\) and each 4 -seater boat costs \(\pounds 300\) to buy. Harry wishes to minimise the total cost of buying the boats.
4. Write down the objective function, C , in terms of \(x\) and \(y\).
5. Determine the number of each type of boat that Harry should buy. You must make your method clear and state the minimum cost.

7. \begin{figure}[h] \end{figure} \section*{[The sum of the duration of all activities is 172 days]} A project is modelled by the activity network shown in Figure 5. 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 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. Calculate the total float for activity M. You must make the numbers you use in your calculation clear.
3. For each of the situations below, explain the effect that the delay would have on the project completion date.
   1. A 2 day delay on the early start of activity P.
   2. A 2 day delay on the early start of activity Q .
4. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. Diagram 2 in the answer book shows a partly completed cascade chart for this project.
5. Complete the cascade chart.
6. Use your cascade chart to determine a second lower bound on the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities.
7. State which of the two lower bounds found in (d) and (f) is better. Give a reason for your answer.
   (Total 17 marks)