Edexcel D1 (Decision Mathematics 1) 2004 January

1. Define the terms
   1. bipartite graph,
   2. alternating path,
   3. matching,
   4. complete matching.
   5. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit P . The following tableau was obtained.

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(s\)	3	0	2	0	1	\(- \frac { 2 } { 3 }\)	\(\frac { 2 } { 3 }\)
   \(r\)	4	0	\(\frac { 7 } { 2 }\)	1	0	8	\(\frac { 9 } { 2 }\)
   \(y\)	5	1	7	0	0	3	7
   P	3	0	2	0	0	8	63

1. State, giving your reason, whether this tableau represents the optimal solution.
2. State the values of every variable.
3. Calculate the profit made on each unit of \(y\). \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{a21a4565-800c-45c0-a513-bb813ef1086f-3_1193_1689_420_201}
   \end{figure} Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\). Three cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\) and \(\mathrm { C } _ { 3 }\) are shown on Fig. 1.
4. Find the capacity of each of the three cuts.
5. Verify that the flow of 26 is maximal. The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options.
   Option 1: Build a new road from \(E\) to \(J\) with capacity 5 .
   or
   Option 2: Build a new road from \(F\) to \(H\) with capacity 3.
6. By considering both options, explain which one meets the government's aim
   (3) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{a21a4565-800c-45c0-a513-bb813ef1086f-4_780_1002_358_486}
   \end{figure} An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled. The engineer's office is at \(G\), so he starts and ends his journey at \(G\).
7. Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length.
   (6) The engineer lives at \(D\). He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at \(G\).
8. State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not.
   (3)
   \includegraphics[max width=\textwidth, alt={}, center]{a21a4565-800c-45c0-a513-bb813ef1086f-5_1561_1568_347_178} Figure 3 describes an algorithm in the form of a flow chart, where \(a\) is a positive integer. List \(P\), which is referred to in the flow chart, comprises the prime numbers \(2,3,5,7,11,13\), 17, ...
9. Starting with \(a = 90\), implement this algorithm. Show your working in the table in the answer book.
10. Explain the significance of the output list.
11. Write down the final value of \(c\) for any initial value of \(a\).

6. The matrix represents a network of roads between six villages \(A , B , C , D , E\) and \(F\). The value in each cell represents the distance, in km, along these roads.

1. Show this information on the diagram in the answer book.
   (2)
2. Use Kruskal's algorithm to determine the minimum spanning tree. State the order in which you include the arcs and the length of the minimum spanning tree. Draw the minimum spanning tree.
   (5)
3. Starting at \(D\), use Prim's algorithm on the matrix given in the answer book to find the minimum spanning tree. State the order in which you include the arcs.
   (3)

7. Becky's bird food company makes two types of bird food. One type is for bird feeders and the other for bird tables. Let \(x\) represent the quantity of food made for bird feeders and \(y\) represent the quantity of food made for bird tables. Due to restrictions in the production process, and known demand, the following constraints apply. $$\begin{gathered} x + y \leq 12
y < 2 x
2 y \geq 7
y + 3 x \geq 15 \end{gathered}$$

1. On the axes provided, show these constraints and label the feasible region \(R\). The objective is to minimise \(C = 2 x + 5 y\).
2. Solve this problem, making your method clear. Give, as fractions, the value of \(C\) and the amount of each type of food that should be produced.
   (4) Another objective (for the same constraints given above) is to maximise \(P = 3 x + 2 y\), where the variables must take integer values.
3. Solve this problem, making your method clear. State the value of \(P\) and the amount of each type of food that should be produced.

8. \begin{figure}[h] \end{figure} A trainee at a building company is using critical path analysis to help plan a project. Figure 4 shows the trainee's activity network. Each activity is represented by an arc and the number in brackets on each arc is the duration of the activity, in hours.

1. Find the values of \(x , y\) and \(z\).
2. State the total length of the project and list the critical activities.
3. Calculate the total float time on
   1. activity \(N\),
   2. activity \(H\).
      (3) The trainee's activity network is checked by the supervisor who finds a number of errors and omissions in the diagram. The project should be represented by the following precedence table.

      Activity	Must be preceded by:	Duration
      A	-	4
      B	-	3
      C	-	5
      D	B	2
      E	A, \(D\)	8
      \(F\)	B	2
      G	C	2
      \(H\)	C	3
      I	\(F , G\)	4
      J	\(F , G\)	2
      K	\(F , G\)	7
      L	E, I	9
      M	H, J	3
      N	E, I, K, M	3
      \(P\)	E, \(I\)	6
      \(Q\)	H, J	5
      \(R\)	\(Q\)	7

4. By adding activities and dummies amend the diagram in the answer book so that it represents the precedence table. (The durations of activities \(A , B , \ldots , N\) are all correctly given on the diagram in the answer book.)
5. Find the total time needed to complete this project.