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, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

1. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
3. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you used and your complete matching.

2. The table shows the average journey time, in minutes, between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them.
2. Draw your tree using the vertices given in Diagram 1 in the answer book.
3. Find the weight of your minimum spanning tree. Kruskal's algorithm may also be used to find a minimum spanning tree.
4. State three differences between Prim's algorithm and Kruskal's algorithm.

3. \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 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 H. You must make the numbers you use in your calculation clear.
3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. Show your calculation. Diagram 2 in the answer book shows a partly completed scheduling diagram for this project.
4. Complete the scheduling diagram, using the minimum number of workers, so that the project is completed in the minimum time.

4.

1. Sam (S)
2. Janelle (J)
3. Haoyu (H)
4. Alfie (A)
5. Cyrus (C)
6. Komal (K)
7. Polly (P)
8. David (D)
9. Tom (T)
10. Lydia (L)

A binary search is to be performed on the names in the list above to locate the name Lydia.

1. Using an appropriate algorithm, rearrange the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
2. Use the binary search algorithm to locate the name Lydia in the list you obtained in (a). You must make your method clear.

5. \begin{figure}[h] \end{figure} Figure 4 represents a network of power cables that have to be inspected. The number on each arc represents the length, in km , of that cable. A route of minimum length that traverses each cable at least once and starts and finishes at A needs to be found.

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. It is now decided to start and finish the inspection route at two distinct vertices. The route must still traverse each cable at least once.
3. Determine possible starting and finishing points so that the length of the route is minimised. You must give reasons for your answer.

6.

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

7. \begin{figure}[h] \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\). A route of minimum length is required. It is decided to use Dijkstra's algorithm to find the shortest routes between \(\mathrm { C } _ { 1 }\) and J and between \(\mathrm { C } _ { 2 }\) and J .

1. Explain why J , rather than \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\), should be chosen as the starting vertex.
   (1)
2. Use Dijkstra's algorithm to find the shortest route needed to transport the crane. State your route and its length.
   (6)

8. \begin{figure}[h] \end{figure} A company makes two types of garden bench, the 'Rustic' and the 'Contemporary'. The company wishes to maximise its profit and decides to use linear programming. Let \(x\) be the number of 'Rustic' benches made each week and \(y\) be the number of 'Contemporary' benches made each week. The graph in Figure 6 is being used to solve this linear programming problem.
Two of the constraints have been drawn on the graph and the rejected region shaded out.

1. Write down the constraints shown on the graph giving your answers as inequalities in terms of \(x\) and \(y\). It takes 4 working hours to make one 'Rustic' bench and 3 working hours to make one 'Contemporary' bench. There are 120 working hours available in each week.
2. Write down an inequality to represent this information. Market research shows that 'Rustic' benches should be at most \(\frac { 3 } { 4 }\) of the total benches made each week.
3. Write down, and simplify, an inequality to represent this information. Your inequality must have integer coefficients.
4. Add two lines and shading to Diagram 1 in your answer book to represent the inequalities of (b) and (c). Hence determine and label the feasible region, R. The profit on each 'Rustic' bench and each 'Contemporary' bench is \(\pounds 45\) and \(\pounds 30\) respectively.
5. Write down the objective function, P , in terms of \(x\) and \(y\).
6. Determine the coordinates of each of the vertices of the feasible region and hence use the vertex method to determine the optimal point.
7. State the maximum weekly profit the company could make.
   (Total 16 marks)