Edexcel D1 (Decision Mathematics 1)

1. This question should be answered on the sheet provided.

A College wants to connect the computerised registration equipment at its six sites, \(A\) to \(F\). The table below shows the cost, in pounds, of connecting any two of the sites. Starting at \(D\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. Hence, state the lowest cost of connecting all the sites.
(5 marks)

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The data $$x _ { 1 } = 8 , \quad x _ { 2 } = 2 , \quad x _ { 3 } = 4 , \quad x _ { 4 } = 3 , \quad x _ { 5 } = 5 , \quad x _ { 6 } = 1 , \quad x _ { 7 } = 7 ,$$ is to be used in the algorithm given in Figure 1.

1. Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output using the given data.
2. Explain what the algorithm achieves for any set of data \(x _ { 1 }\) to \(x _ { n }\).

3. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

1. Find the values of \(x\) and \(y\).
2. 1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. 1. Find a minimum cut, listing the arcs through which it passes.
   2. Explain why this proves that the flow found in part (b) is a maximum.
      (2 marks)

4. \begin{figure}[h] \end{figure} Figure 3 shows the graph \(K _ { 4 }\).

1. State the features of the graph that identify it as \(K _ { 4 }\).
2. In \(K _ { 4 }\), the Hamiltonian cycles \(A B C D A , B C D A B , C D A B C\) and \(D A B C D\) are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
   1. \(\quad K _ { 4 }\),
   2. \(K _ { 5 }\),
   3. \(K _ { 10 }\).
3. In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.

5. A clothes manufacturer has a trademark "VE" which it wants to embroider on all its garments. The stitching must be done continuously but stitching along the same line twice is allowed. Logo 1:
\includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_524_1338_495_296} Logo 2: \begin{figure}[h] \end{figure} The weighted networks in Figure 4 represent two possible Logos.
The weights denote lengths in millimetres.

1. Calculate the shortest length of stitch required to embroider Logo 1 .
2. Calculate the shortest length of stitch required to embroider Logo 2.
3. Hence, determine the difference in the length of stitching required for the two Logos.

6. A company makes lighting sets to be sold to stores for use during the Christmas period. As the product is only required at this time of year, all manufacturing takes place during September, October and November. The sets are delivered to stores at the end of each of these months. Any sets that have been made but do not need to be delivered at the end of each of September and October are put into storage which the company must pay for. Let \(x , y\) and \(z\) be the number of sets manufactured in September, October and November respectively. The demand for lighting sets and the relevant costs are shown in the table below. The company must be able to meet the demand at the end of each month and there must be no unsold articles at the end of November.

1. 1. Express \(z\) in terms of \(x\) and \(y\).
   2. Hence, find an expression for the total costs incurred in terms of \(x\) and \(y\). The company wishes to minimise its total costs by modelling this situation as a linear programming problem.
2. Find as inequalities the constraints that apply in addition to \(x \geq 800\) and \(y \geq 0\).
   (2 marks)
3. On graph paper, illustrate these inequalities and label clearly the feasible region.
   (4 marks)
4. Use your graph to solve the problem. You must state how many sets should be produced in each month and the total costs incurred by the company.
   (3 marks)

7. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The activity network in Figure 5 models the work involved in laying the foundations and putting in services for an industrial complex. The activities are represented by the arcs and the numbers in brackets give the time, in days, to complete each activity. Activity \(C\) is a dummy.

1. Execute a forward scan to calculate the early times and a backward scan to calculate the late times, for each event.
2. Determine which activities lie on the critical path and list them in order.
3. State the minimum length of time needed to complete the project. The contractor is committed to completing the project in this minimum time and faces a penalty of \(\pounds 50000\) for each day that the project is late. Unfortunately, before any work has begun, flooding means that activity \(F\) will take 3 days longer than the 7 days allocated.
4. Activity \(N\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
   (3 marks)
5. If the time taken to complete any one activity, other than \(F\), could be reduced by 2 days at an extra cost of \(\pounds 80000\), for which activities on their own would this be profitable. Explain your reasoning.
   (3 marks) END \section*{Please hand this sheet in for marking}

   	A	B	C	D	E	\(F\)
   A	-	130	190	155	140	125
   B	130	-	215	200	190	170
   C	190	215	-	110	180	100
   D	155	200	110	-	70	45
   E	140	190	180	70	-	75
   \(F\)	125	170	100	45	75	-

   \section*{Please hand this sheet in for marking}

6. \(n\)	\(x _ { n }\)	\(а\)	Any more data?	\(x _ { n + 1 }\)	\(b\)	\(( b - a ) > 0\) ?	\(a\)
   1	8	8	Yes	2	2	No	2
   2	-	-

   Final output
7. \(\_\_\_\_\)
   Sheet for answering question 3
   NAME \section*{Please hand this sheet in for marking}
9. 1. 
      \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_716_1218_502_331}
   2. 
      \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_709_1214_1498_333} Maximum flow =
10. 1. \(\_\_\_\_\)
    2. \(\_\_\_\_\)
       \section*{Please hand this sheet in for marking}
11. 
    \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
12. \(\_\_\_\_\)
13. \(\_\_\_\_\)
14. \(\_\_\_\_\)
15. \(\_\_\_\_\)