Edexcel D1 (Decision Mathematics 1) 2002 January

Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs 1, 2, 3, 4 or 5. The table shows each member's preferences for the jobs. Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.

1. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs. [2]
2. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path. [3]
3. Find a second alternating path from the initial allocation. [1]

1. Use the binary search algorithm to try to locate the name \(SABINE\) in the following alphabetical list. Explain each step of the algorithm. \begin{align} 1. &\quad ABLE
   2. &\quad BROWN
   3. &\quad COOKE
   4. &\quad DANIEL
   5. &\quad DOUBLE
   6. &\quad FEW
   7. &\quad OSBORNE
   8. &\quad PAUL
   9. &\quad SWIFT
   10. &\quad TURNER \end{align} [5]
2. Find the maximum number of iterations of the binary search algorithm needed to locate a name in a list of 1000 names. [2]

1. 	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
   \(A\)	--	10	12	13	20	9
   \(B\)	10	--	7	15	11	7
   \(C\)	12	7	--	11	18	3
   \(D\)	13	15	11	--	27	8
   \(E\)	20	11	18	27	--	18
   \(F\)	9	7	3	8	18	--

   The table shows the distances, in metres, between six nodes \(A\), \(B\), \(C\), \(D\), \(E\), and \(F\) of a network.
   1. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. Explain your method and indicate the order in which you selected the edges. [4]
   2. Draw your minimum spanning tree and find its total length. [2]
   3. State whether your minimum spanning tree is unique. Justify your answer. [1]
2. A connected network \(N\) has seven vertices.
   1. State the number of edges in a minimum spanning tree for \(N\). [1]
   A minimum spanning tree for a connected network has \(n\) edges.
   1. State the number of vertices in the network. [1]

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

1. Use Dijkstra's algorithm to find a quickest route from \(A\) to \(L\). Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling. [7]
2. Show that there is another route which also takes the minimum time [1]

Two fertilizers are available, a liquid \(X\) and a powder \(Y\). A bottle of \(X\) contains 5 units of chemical \(A\), 2 units of chemical \(B\) and \(\frac{1}{2}\) unit of chemical \(C\). A packet of \(Y\) contains 1 unit of \(A\), 2 units of \(B\) and 2 units of \(C\). A professional gardener makes her own fertilizer. She requires at least 10 units of \(A\), at least 12 units of \(B\) and at least 6 units of \(C\). She buys \(x\) bottles of \(X\) and \(y\) packets of \(Y\).

1. Write down the inequalities which model this situation. [4]
2. On the grid provided construct and label the feasible region. [3]

A bottle of \(X\) costs £2 and a packet of \(Y\) costs £3.

1. Write down an expression, in terms of \(x\) and \(y\), for the total cost \(£T\). [1]
2. Using your graph, obtain the values of \(x\) and \(y\) that give the minimum value of \(T\). Make your method clear and calculate the minimum value of \(T\). [4]
3. Suggest how the situation might be changed so that it could no longer be represented graphically. [2]

\includegraphics{figure_2} A company has 3 warehouses \(W_1\), \(W_2\), and \(W_3\). It needs to transport the goods stored there to 2 retail outlets \(R_1\) and \(R_2\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W_1\), \(W_2\) and \(W_3\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R_1\) and \(R_2\) can accept 6 and 25 van loads respectively per day.

1. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added. [3]
2. State the maximum flow along
   1. \(W\) \(W_1\) \(A\) \(R_1\) \(R\),
   2. \(W\) \(W_3\) \(C\) \(R_2\) \(R\). [2]
3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flow-augmenting route you use, together with its flow. [5]
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. [1]

The company has the opportunity to increase the number of vans loads from one of the warehouses \(W_1\), \(W_2\), \(W_3\), to \(A\), \(B\) or \(C\).

1. Determine how the company should use this opportunity so that it achieves a maximal flow. [3]

\includegraphics{figure_3} A project is modelled by the activity network shown in Fig 3. The activities are represented by the edges. The number in brackets on each edge gives the time, in days, taken to complete the activity.

1. Calculate the early time and the late time for each event. Write these in the boxes on the answer sheet. [4]
2. Hence determine the critical activities and the length of the critical path. [2]
3. Obtain the total float for each of the non-critical activities. [3]
4. On the first grid on the answer sheet, draw a cascade (Gantt) chart showing the information obtained in parts (b) and (c). [4]

Each activity requires one worker. Only two workers are available.

1. On the second grid on the answer sheet, draw up a schedule and find the minimum time in which the 2 workers can complete the project. [4]