Edexcel D1 (Decision Mathematics 1) 2003 June

Six workers \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\) are to be matched to six tasks 1, 2, 3, 4, 5 and 6. The table below shows the tasks that each worker is able to do.

Worker	Tasks
A	2, 3, 5
B	1, 3, 4, 5
C	2
D	3, 6
E	2, 4, 5
F	1

A bipartite graph showing this information is drawn in the answer booklet. Initially, \(A\), \(B\), \(D\) and \(E\) are allocated to tasks 2, 1, 3 and 5 respectively. Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly. [5]

1. Explain why it is impossible to draw a network with exactly three odd vertices. [2]

\includegraphics{figure_1} The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100.

1. Determine the value of \(x\), showing your working clearly. [4]

1. Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network.

\includegraphics{figure_2}

1. Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
   1. Prim's algorithm,
   2. Kruskal's algorithm.
   [4]

The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper \((R)\), Palmer \((P)\), Boase \((B)\), Young \((Y)\), Thomas \((T)\), Kenney \((K)\), Morris \((M)\), Halliwell \((H)\), Wicker \((W)\), Garesalingam \((G)\).

1. Use the quick sort algorithm to sort the names above into alphabetical order. [5]
2. Use the binary search algorithm to locate the name Kenney. [4]

\includegraphics{figure_3} The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity.

1. Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet. [4]
2. Hence determine the critical activities. [2]
3. Calculate the total float time for \(D\). [2]

Each activity requires only one person.

1. Find a lower bound for the number of workers needed to complete the process in the minimum time. [2]

Given that there are only three workers available, and that workers may not share an activity,

1. schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time. [5]

A company produces two types of self-assembly wooden bedroom suites, the 'Oxford' and the 'York'. After the pieces of wood have been cut and finished, all the materials have to be packaged. The table below shows the time, in hours, needed to complete each stage of the process and the profit made, in pounds, on each type of suite.

	Oxford	York
Cutting	4	6
Finishing	3.5	4
Packaging	2	4
Profit (£)	300	500

The times available each week for cutting, finishing and packaging are 66, 56 and 40 hours respectively. The company wishes to maximise its profit. Let \(x\) be the number of Oxford, and \(y\) be the number of York suites made each week.

1. Write down the objective function. [1]
2. In addition to $$2x + 3y \leq 33,$$ $$x \geq 0,$$ $$y \geq 0,$$ find two further inequalities to model the company's situation. [2]
3. On the grid in the answer booklet, illustrate all the inequalities, indicating clearly the feasible region. [4]
4. Explain how you would locate the optimal point. [2]
5. Determine the number of Oxford and York suites that should be made each week and the maximum profit gained. [3]

It is noticed that when the optimal solution is adopted, the time needed for one of the three stages of the process is less than that available.

1. Identify this stage and state by how many hours the time may be reduced. [3]

\includegraphics{figure_4} Figure 4 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.

1. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 2 in the answer booklet. [2]
2. Find the values of \(x\) and \(y\), explaining your method briefly. [2]
3. Find the value of cuts \(C_1\) and \(C_2\). [3]

Starting with the given feasible flow of 68,

1. use the labelling procedure on Diagram 3 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. [6]
2. Show your maximal flow on Diagram 4 and state its value. [3]
3. Prove that your flow is maximal. [2]