Edexcel D1 (Decision Mathematics 1)

1. \begin{figure}[h] \end{figure}

1. Find a Hamiltonian cycle for the graph shown in Figure 1.
2. Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
   (5 marks)

2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.

3. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows an activity network. The nodes represent events and the arcs represent the activities. The number in each bracket gives the time, in days, needed to complete the activity.

1. Calculate the early and late times for each event using appropriate forward and backward scanning.
   (5 marks)
2. Hence, determine the activities which lie on the critical path.
3. State the minimum number of days needed to complete the entire project.

4. This question should be answered on the sheet provided. The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.

1. Draw a bipartite graph to model this situation. Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
2. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.
   (6 marks)

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 3 shows a weighted network. The number on each arc indicates the weight of that arc.

1. Use Dijkstra's algorithm to find a path of least weight from \(A\) to \(J\) and state the weight of the path. Your solution must show clearly how you have applied the algorithm including:
   1. the order in which the vertices were labelled,
   2. how you determined the path of least weight.
2. Find if there are any other paths of least weight and explain your answer.
3. Describe a practical problem that could be modelled by the above network.

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. Calculate the values of cut \(C _ { 1 }\) and \(C _ { 2 }\).
2. Find the minimum cut and state its value.
   (2 marks) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347} \captionsetup{labelformat=empty} \caption{Fig. 5}
   \end{figure} Figure 5 shows a feasible flow through the same network.
3. State the values of \(x , y\) and \(z\).
4. Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow. State how you know that you have found a maximal flow.
   (8 marks)

7. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that a maximum combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.

1. Model this as a linear programming problem simplifying your expressions so that they have integer coefficients.
   (4 marks)
2. Show that the initial tableau, when using the simplex algorithm, can be written as:

   Basic Variable	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	Value
   \(s\)	1	2	4	1	0	0	20
   \(t\)	4	3	14	0	1	0	75
   \(u\)	5	2	10	0	0	1	60
   \(R\)	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0

3. Explain the purpose of the variables \(s\), \(t\) and \(u\).
4. By increasing the value of \(y\) first, work out the next two complete tableaus.
5. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms. Sheet for answering question 3
   NAME \section*{Please hand this sheet in for marking}
8. 
   \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
   \section*{Please hand this sheet in for marking}
9. \(F \quad \bullet\)
   • \(W\)
     \(G \quad \bullet\)
   • \(S\)
   H •
   • \(C\)
   I •
   • \(O\)
   J •
   • \(D\)
   • Initial matching:
     \(\begin{array} { l l l l } F & \bullet & \bullet & W
     G & \bullet & \bullet & S
     H & \bullet & \bullet & C
     I & \bullet & \bullet & O
     J & \bullet & \bullet & D \end{array}\) \(\_\_\_\_\)
     
   Complete matching:
   F •
   • \(W\)
     \(G \quad \bullet\)
   • \(S\)
     H •
   • \(C\)
     I •
   • \(O\)
     J •
   • \(D\)
   \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking}
   \includegraphics[max width=\textwidth, alt={}]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-10_2398_643_248_1224}
   Sheet for answering question 6
   NAME \section*{Please hand this sheet in for marking}
10. \(\_\_\_\_\)
11. \(\_\_\_\_\)
12. \(\_\_\_\_\)
13. 
    \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-11_592_1292_1078_312}
    Sheet for answering question 6 (cont.)
    \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_595_1299_351_312}
    \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_597_1298_1409_308}