Edexcel D1 (Decision Mathematics 1) 2005 January

1. \begin{figure}[h] \end{figure} The bipartite graph in Figure 1 shows a mapping between six people, Andy (A), David ( \(D\) ), Joan \(( J )\), Preety \(( P )\), Sally \(( S )\) and Trevor \(( T )\), and six tasks \(1,2,3,4,5\) and 6. The initial matching is \(A\) to \(2 , D\) to \(1 , J\) to 3 and \(P\) to 4.

1. Indicate this initial matching in a distinctive way on the bipartite graph drawn in the answer book.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths you use.
   (5)

2. The precedence table for activities involved in producing a computer game is shown below. An activity on arc network is to be drawn to model this production process.

1. Explain why it is necessary to use at least two dummies when drawing the activity network.
   (2)
2. Draw the activity network using exactly two dummies.
   (5)

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.

1. Find a minimum spanning tree for the network in Figure 2, showing clearly the order in which you selected the arcs for your tree, using
   1. Kruskal's algorithm,
   2. Prim's algorithm, starting from \(A\). Given that footpaths are already in place along \(A B\) and \(F I\) and so should be included in the spanning tree,
2. explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.)
   (2)

4. \(\quad \begin{array} { l l l l l l l l l l } 650 & 431 & 245 & 643 & 455 & 134 & 710 & 234 & 162 & 452 \end{array}\)

1. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements.
   (5) The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
2. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.)
   (4)
3. Determine whether your solution to part (b) is optimal. Give a reason for your answer.
   (2)

5. \begin{figure}[h] \end{figure} Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.

1. Use Dijkstra's algorithm to find the shortest distance from \(A\) to \(H\).
   (5)
2. Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length.
   [0pt] [The total weight of the network is 1241]
   (6) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{e64b50bc-13a3-4051-b8c1-d4e7ea49e3a5-6_634_1486_301_312}
   \end{figure} Figure 4 shows a capacitated directed network. The number on each arc is its capacity.
   (a) State the maximum flow along
3. SADT,
4. SCET,
5. \(S B F T\).
   (b) Show these maximum flows on Diagram 1 in the answer book. Take your answer to part (b) as the initial flow pattern.
   (c) (i) Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 in the answer book. List each flow-augmenting route you use, together with its flow.
6. Draw your final flow pattern on Diagram 3 in the answer book.
7. Prove that your flow is maximal.
   (d) Give an example of a practical situation that could have been modelled by the original network.

7. Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of \(\pounds 50 , \pounds 80\) and \(\pounds 60\) are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x , y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.
2. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac { 1 } { 2 }\)	0	\(1 \frac { 1 } { 2 }\)	1	\(- \frac { 1 } { 2 }\)	0	10
   \(y\)	\(\frac { 1 } { 2 }\)	1	\(\frac { 1 } { 2 }\)	0	\(\frac { 1 } { 2 }\)	0	20
   \(t\)	2	0	0	0	-1	1	10
   \(P\)	-10	0	-20	0	40	0	1600

3. Explain the practical meaning of the value 10 in the top row.
4. 1. Perform one further complete iteration of the Simplex algorithm.
   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable.