Edexcel D1 (Decision Mathematics 1) 2008 January

1. (a) Define the terms
   1. alternating path,
   2. matching.
   \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-2_568_621_689_344} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-2_554_540_701_1171} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} At a school fair, five teachers, \(A , B , C , D\) and \(E\), are to supervise five stalls, \(1,2,3,4\) and 5 .
   A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.
   (b) Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use.

2. (a)
\(\begin{array} { l l l l l l l l l l l } 18 & 20 & 11 & 7 & 17 & 15 & 14 & 21 & 23 & 16 & 9 \end{array}\) The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear. \begin{figure}[h] \end{figure} Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.
(b) Using your answer to part (a) and Kruskal's algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree.
(c) Find the total weight of the minimum spanning tree.

3. \begin{figure}[h] \end{figure} Figure 4 models a network of roads in a housing estate. The number on each arc represents the length, in km , of the road. The total weight of the network is 11 km .
A council worker needs to travel along each road once to inspect the road surface. He will start and finish at A and wishes to minimise the length of his route.

1. Use an appropriate algorithm to find a route for the council worker. You should make your method and working clear. State your route and its length.
   (6) A postal worker needs to walk along each road twice, once on each side of the road. She must start and finish at A . The length of her route is to be minimised. You should ignore the width of the road.
2. 1. Explain how this differs from the standard route inspection problem.
      (1)
   2. Find the length of the shortest route for the postal worker.
      (2)

4. \begin{figure}[h] \end{figure} 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 hours, to complete the activity. Some of the early and late times for each event are shown.

1. Calculate the missing early and late times and hence complete Diagram 1 in your answer book.
2. Calculate the total float on activities D, G and I. You must make your calculations clear.
3. List the critical activities. Each activity requires one worker.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time.
   (2)

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

6. (a) Define the term 'cut' as it applies to a directed network.
(2) \begin{figure}[h] \end{figure} Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
(b) Complete the labelling procedure on Diagram 2 in your answer book by entering values along CE, EG, HT and GT.
(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
(d) Show a maximal flow pattern on Diagram 3 in your answer book.
(e) State the value of the maximum flow through the network.
(f) Prove that your flow is maximal.

7. \begin{figure}[h] \end{figure}

1. Phil sells boxed lunches to travellers at railway stations. Customers can select either the vegetarian box or the non-vegetarian box.

Phil decides to use graphical linear programming to help him optimise the numbers of each type of box he should produce each day. Each day Phil produces \(x\) vegetarian boxes and \(y\) non-vegetarian boxes.
One of the constraints limiting the number of boxes is $$x + y \geqslant 70$$ This, together with \(x \geqslant 0 , y \geqslant 0\) and a fourth constraint, has been represented in Figure 7. The rejected region has been shaded.

1. Write down the inequality represented by the fourth constraint. Two further constraints are: $$\begin{aligned} & x + 2 y \leqslant 160
   & \text { and } y > 60 \end{aligned}$$
2. Add two lines and shading to Diagram 4 in your answer book to represent these inequalities.
3. Hence determine and label the feasible region, R .
4. Use your graph to determine the minimum total number of boxes he needs to prepare each day. Make your method clear. Phil makes a profit of \(\pounds 1.20\) on each vegetarian box and \(\pounds 1.40\) on each non-vegetarian box. He wishes to maximise his profit.
5. Write down the objective function.
6. Use your graph to obtain the optimal number of vegetarian and non-vegetarian boxes he should produce each day. You must make your method clear.
7. Find Phil's maximum daily profit.