Edexcel D1 (Decision Mathematics 1) 2003 November

1. \begin{figure}[h] \end{figure} A local council is responsible for maintaining pavements in a district. The roads for which it is responsible are represented by arcs in Fig. 1.The junctions are labelled \(A , B , C , \ldots , G\). The number on each arc represents the length of that road in km. The council has received a number of complaints about the condition of the pavements. In order to inspect the pavements, a council employee needs to walk along each road twice (once on each side of the road) starting and ending at the council offices at \(C\). The length of the route is to be minimal. Ignore the widths of the roads.

1. Explain how this situation differs from the standard Route Inspection problem.
2. Find a route of minimum length and state its length.

2. An electronics company makes a product that consists of components \(A , B , C , D , E\) and \(F\). The table shows which components must be connected together to make the product work. The components are all placed on a circuit board and connected by wires, which are not allowed to cross.

1. On the diagram in the answer book draw straight lines to show which components need to be connected.
   (1)
2. Starting with the Hamiltonian cycle \(A B C D E F A\), use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
   (4)

3. \begin{figure}[h] \end{figure} The bipartite graph in Fig. 2 shows the possible allocations of people \(A , B , C , D , E\) and \(F\) to tasks \(1,2,3,4,5\) and 6. An initial matching is obtained by matching the following pairs \(A\) to \(3 , \quad B\) to \(4 , \quad C\) to \(1 , \quad F\) to 5 .

1. Show this matching in a distinctive way on the diagram in the answer book.
2. Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
   (5)

4. (a) Draw an activity network described in this precedence table, using as few dummies as possible.

1. A different project is represented by the activity network shown in Fig. 3. The duration of each activity is shown in brackets. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-05_710_1580_1509_239}
   \end{figure} Find the range of values of \(x\) that will make \(D\) a critical activity.
   (2)

5. Nine pieces of wood are required to build a small cabinet. The lengths, in cm, of the pieces of wood are listed below. $$20 , \quad 20 , \quad 20 , \quad 35 , \quad 40 , \quad 50 , \quad 60 , \quad 70 , \quad 75$$ Planks, one metre in length, can be purchased at a cost of \(\pounds 3\) each.

1. The first fit decreasing algorithm is used to determine how many of these planks are to be purchased to make this cabinet. Find the total cost and the amount of wood wasted.
   (5) Planks of wood can also be bought in 1.5 m lengths, at a cost of \(\pounds 4\) each. The cabinet can be built using a mixture of 1 m and 1.5 m planks.
2. Find the minimum cost of making this cabinet. Justify your answer.
   (4)

6. (a) Define the terms

1. tree,
2. spanning tree,
3. minimum spanning tree.
   (3)
   (b) State one difference between Kruskal's algorithm and Prim's algorithm, to find a minimum spanning tree.
   (1) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-08_894_1529_920_322}
   \end{figure} (c) Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Fig. 4. State the order in which you included the arcs. Draw the minimum spanning tree in Diagram 1 in the answer book and state its length.
   (4) \section*{Figure 5}
   \includegraphics[max width=\textwidth, alt={}]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-09_887_1536_342_258}
   Figure 5 models a car park. Currently there are two pay-stations, one at \(E\) and one at \(N\). These two are linked by a cable as shown. New pay-stations are to be installed at \(B , H , A , F\) and \(C\). The number on each arc represents the distance between the pay-stations in metres. All of the pay-stations need to be connected by cables, either directly or indirectly. The current cable between \(E\) and \(N\) must be included in the final network. The minimum amount of new cable is to be used.
   (d) Using your answer to part (c), or otherwise, determine the minimum amount of new cable needed. Use Diagram 2 to show where these cables should be installed. State the minimum amount of new cable needed.
   (3)

7. \begin{figure}[h] \end{figure} Figure 6 shows a capacitated, directed network of pipes flowing from two oil fields \(\mathrm { F } _ { 1 }\) and \(\mathrm { F } _ { 2 }\) to three refineries \(\mathrm { R } _ { 1 } , \mathrm { R } _ { 2 }\) and \(\mathrm { R } _ { 3 }\). The number on each arc represents the capacity of the pipe and the numbers in the circles represent a possible flow of 65.

1. Find the value of \(x\) and the value of \(y\).
2. On Diagram 1 in the answer book, add a supersource and a supersink, and arcs showing their minimum capacities.
3. Taking the given flow of 65 as the initial flow pattern, use the labelling procedure on Diagram 2 to find the maximum flow. State clearly your flow augmenting routes.
4. Show the maximum flow on Diagram 3 and write down its value.
5. Verify that this is the maximum flow by finding a cut equal to the flow.

8. A company makes three sizes of lamps, small, medium and large. The company is trying to determine how many of each size to make in a day, in order to maximise its profit. As part of the process the lamps need to be sanded, painted, dried and polished. A single machine carries out these tasks and is available 24 hours per day. A small lamp requires one hour on this machine, a medium lamp 2 hours and a large lamp 4 hours. Let \(x =\) number of small lamps made per day, $$\begin{aligned} & y = \text { number of medium lamps made per day, }
& z = \text { number of large lamps made per day, } \end{aligned}$$ where \(x \geq 0 , y \geq 0\) and \(z \geq 0\).

1. Write the information about this machine as a constraint.
2. 1. Re-write your constraint from part (a) using a slack variable \(s\).
   2. Explain what \(s\) means in practical terms. Another constraint and the objective function give the following Simplex tableau. The profit \(P\) is stated in euros.

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
      \(r\)	3	5	6	1	0	50
      \(s\)	1	2	4	0	1	24
      \(P\)	- 1	- 3	- 4	0	0	0

3. Write down the profit on each small lamp.
4. Use the Simplex algorithm to solve this linear programming problem.
5. Explain why the solution to part (d) is not practical.
6. Find a practical solution which gives a profit of 30 euros. Verify that it is feasible.