Edexcel D1 (Decision Mathematics 1) 2001 June

1. The precedence table for activities involved in a small project is shown below

Draw an activity network, using activity on edge and without using dummies, to model this project.
(5)

2. \begin{figure}[h] \end{figure} Figure 1 shows 7 locations \(A , B , C , D , E , F\) and \(G\) which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.

1. Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
   (4)
2. Draw your minimum spanning tree and find the least cost of the pipelines.
   (3)

3. \begin{figure}[h] \end{figure} Figure 2 shows a new small business park. The vertices \(A , B , C , D , E , F\) and \(G\) represent the various buildings and the arcs represent footpaths. The number on an arc gives the length, in metres, of the path. The management wishes to inspect each path to make sure it is fit for use. Starting and finishing at \(A\), solve the Route Inspection (Chinese Postman) problem for the network shown in Fig. 2 and hence determine the minimum distance thet needs to be walked in carrying out this inspection. Make your method and working clear and give a possible route of minimum length.

4. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} The weighted network shown in Fig. 3 models the area in which Bill lives. Each vertex represents a town. The edges represent the roads between the towns. The weights are the lengths, in km , of the roads.

1. Use Dijkstra's algorithm to find the shortest route from Bill's home at \(S\) to \(T\). Complete all the boxes on the answer sheet and explain clearly how you determined the path of least weight from your labelling. Bill decides that on the way to \(T\) he must visit a shop in town \(E\).
2. Obtain his shortest route now, giving its length and explaining your method clearly.

5. $$90,50,55,40,20,35,30,25,45$$

1. Use the bubble sort algorithm to sort the list of numbers above into descending order showing the rearranged order after each pass. Jessica wants to record a number of television programmes onto video tapes. Each tape is 2 hours long. The lengths, in minutes, of the programmes she wishes to record are: $$\text { 55, 45, 20, 30, 30, 40, 20, 90, 25, 50, } 35 \text { and } 35 .$$
2. Find the total length of programmes to be recorded and hence determine a lower bound for the number of tapes required.
3. Use the first fit decreasing algorithm to fit the programmes onto her 2-hour tapes. Jessica's friend Amy says she can fit all the programmes onto 4 tapes.
4. Show how this is possible.

6. This question is to be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.

1. Explain why it is not possible to achieve a flow of 30 through the network from \(S\) to \(T\).
2. State the maximum flow along
   1. \(S A B T\)
   2. SCET.
3. Show these flows on Diagram 1 of the answer sheet.
4. Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from \(S\) to \(T\). Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
5. Indicate a maximum flow on Diagram 3.
6. Prove that your flow is maximal.

7. This question is to be answered on the sheet provided in the answer booklet. A chemical company makes 3 products \(X , Y\) and \(Z\). It wishes to maximise its profit \(\pounds P\). The manager considers the limitations on the raw materials available and models the situation with the following Linear Programming problem. Maximise $$\begin{gathered} P = 3 x + 6 y + 4 z
x \quad + \quad z \leq 4
x + 4 y + 2 z \leq 6
x + y + 2 z \leq 12
x \geq 0 , \quad y \geq 0 , \quad z \geq 0 \end{gathered}$$ subject to
where \(x , y\) and \(z\) are the weights, in kg , of products \(X , Y\) and \(Z\) respectively.
A possible initial tableau is

1. Explain
   1. the purpose of the variables \(r , s\) and \(t\),
   2. the final row of the tableau.
2. Solve this Linear Programming problem by using the Simplex alogorithm. Increase \(y\) for your first iteration and than increase \(x\) for your second iteration.
3. Interpret your solution.