Edexcel D1 (Decision Mathematics 1) 2001 January

This question should be answered on the sheet provided in the answer booklet. A school wishes to link 6 computers. One is in the school office and one in each of rooms \(A\), \(B\), \(C\), \(D\) and \(E\). Cables need to be laid to connect the computers. The school wishes to use a minimum total length of cable. The table shows the shortest distances, in metres, between the various sites.

1. Starting at the school office, use Prim's algorithm to find a minimum spanning tree. Indicate the order in which you select the edges and draw your final tree. [5 marks]
2. Using your answer to part (a), calculate the minimum total length of cable required. [1 mark]

1. Use the binary search algorithm to locate the name HUSSAIN in the following alphabetical list. Explain each step of the algorithm. 1. ALLEN 2. BALL 3. COOPER 4. EVANS 5. HUSSAIN 6. JONES 7. MICHAEL 8. PATEL 9. RICHARDS 10. TINDALL 11. WU [6 marks]
2. State the maximum number of comparisons that need to be made to locate a name in an alphabetical list of 11 names. [1 mark]

\includegraphics{figure_1}

1. Using an appropriate algorithm, obtain a suitable route starting and finishing at A. [5 marks]
2. Calculate the total length of this route. [2 marks]

This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed (A) -- Monday and Wednesday; Miss Brown (B) -- Monday, Wednesday and Friday; Ms. Clough (C) -- Monday; Mr. Dingle (D) -- Tuesday, Wednesday and Thursday; Mrs. Evans (E) -- Wednesday and Thursday. The manager initially suggests that A might work on Monday, B on Wednesday and D on Thursday.

1. Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion. [2 marks]
2. Obtain an alternating path, starting at C, and use this to improve the initial matching. [3 marks]
3. Find another alternating path and hence obtain a complete matching. [3 marks]

This question should be answered on the sheet provided in the answer booklet. \includegraphics{figure_2} Figure 2 shows the activity network used to model a small building project. The activities are represented by the edges and the number in brackets on each edge represents the time, in hours, taken to complete that activity.

1. Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet. [6 marks]
2. Hence determine the critical activities and the length of the critical path. [2 marks]

Each activity requires one worker. The project is to be completed in the minimum time.

1. Schedule the activities for the minimum number of workers using the time line on the answer sheet. Ensure that you make clear the order in which each worker undertakes his activities. [5 marks]

This question should be answered on the sheet provided in the answer booklet. \includegraphics{figure_3} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. State the maximum flow along
   1. SAET,
   2. SBDT,
   3. SCFT.
   [3 marks]
2. Show these maximum flows on Diagram 1 on the answer sheet. [1 mark]
3. Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from S to T. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow. [6 marks]
4. Indicate a maximum flow on Diagram 3. [2 marks]
5. Prove that your flow is maximal. [2 marks]

A tailor makes two types of garment, A and B. He has available 70 m² of cotton fabric and 90 m² of woollen fabric. Garment A requires 1 m² of cotton fabric and 3 m² of woollen fabric. Garment B requires 2 m² of each fabric. The tailor makes \(x\) garments of type A and \(y\) garments of type B.

1. Explain why this can be modelled by the inequalities $$x + 2y \leq 70,$$ $$3x + 2y \leq 90,$$ $$x \geq 0, y \geq 0.$$ [2 marks]

The tailor sells type A for £30 and type B for £40. All garments made are sold. The tailor wishes to maximise his total income.

1. Set up an initial Simplex tableau for this problem. [3 marks]
2. Solve the problem using the Simplex algorithm. [8 marks]

Figure 4 shows a graphical representation of the feasible region for this problem. \includegraphics{figure_4}

1. Obtain the coordinates of the points A, C and D. [4 marks]
2. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. [3 marks]