Edexcel D1 (Decision Mathematics 1) 2004 June

The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise. Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2]
2. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use. [3]
3. Explain why it is not possible to find a complete matching. [2]

\includegraphics{figure_1} Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from \(S\) to \(T\) as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time to travel from \(S\) to \(T\). [4]
2. Find a route for Avinash to travel from \(S\) to \(T\) in the shortest time. State, with a reason, whether this route is a unique solution. [2]

On a particular day Avinash must include \(C\) in his route.

1. Find a route of minimal time from \(S\) to \(T\) that includes \(C\), and state its time. [2]

\includegraphics{figure_2}

1. Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm. [1]
2. Use the route inspection algorithm to find which paths, if any, need to be traversed twice. [4]
3. State whether your answer to part (b) is unique. Give a reason for your answer. [1]
4. Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. [1]

Given that it is permitted to start and finish the inspection at two distinct vertices,

1. find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer. [2]

1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth

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

1. Explain why a binary search cannot be performed with the list in its present form. [1]
2. Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use. [4]
3. Use the binary search algorithm on your new list to locate the name Newcastle. [4]

\includegraphics{figure_3} Figure 3 shows a capacitated directed network. The number on each arc is its capacity. \includegraphics{figure_4} Figure 4 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\). [2]
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
3. Use this initial flow and the labelling procedure on Diagram 1 in this answer book to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. [5]
4. Show your maximal flow pattern on Diagram 2. [2]
5. Prove that your flow is maximal. [2]

The Young Enterprise Company "Decide", is going to produce badges to sell to decision maths students. It will produce two types of badges. Badge 1 reads "I made the decision to do maths" and Badge 2 reads "Maths is the right decision". "Decide" must produce at least 200 badges and has enough material for 500 badges. Market research suggests that the number produced of Badge 1 should be between 20% and 40% of the total number of badges made. The company makes a profit of 30p on each Badge 1 sold and 40p on each Badge 2. It will sell all that it produced, and wishes to maximise its profit. Let \(x\) be the number produced of Badge 1 and \(y\) be the number of Badge 2.

1. Formulate this situation as a linear programming problem, simplifying your inequalities so that all the coefficients are integers. [6]
2. On the grid provided in the answer book, construct and clearly label the feasible region. [5]
3. Using your graph, advise the company on the number of each badge it should produce. State the maximum profit "Decide" will make. [3]

\includegraphics{figure_5} A project is modelled by the activity network shown in Fig. 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the activity. The numbers in circles give the event numbers. Each activity requires one worker.

1. Explain the purpose of the dotted line from event 4 to event 5. [1]
2. Calculate the early time and the late time for each event. Write these in the boxes in the answer book. [4]
3. Determine the critical activities. [1]
4. Obtain the total float for each of the non-critical activities. [3]
5. On the grid in the answer book, draw a cascade (Gantt) chart, showing the answers to parts (c) and (d). [4]
6. Determine the minimum number of workers needed to complete the project in the minimum time. Make your reasoning clear. [2]