Edexcel FD1 (Further Decision 1) 2024 June

1. $$\begin{array} { l l l l l l l l l l l } 17 & 8 & 16 & 12 & 24 & 19 & 23 & 11 & 20 & 13 & 4 \end{array}$$ The eleven numbers listed above are to be packed into bins of size \(n\) where \(n\) is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: 17812
Bin 2: 1624
Bin 3: 19114
Bin 4: 2313
Bin 5: 20

1. Explain why this packing means that the value of \(n\) must be 40 The original list of eleven numbers is to be sorted into descending order.
2. Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

1. Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
2. State the weight of the minimum spanning tree found in part (a).
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
4. Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
5. 1. Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
   2. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
6. State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
7. By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
   (2) By deleting J and all of its arcs, a lower bound of length 274 miles was found.
8. State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

1. Use Dijkstra's algorithm to find the shortest path from A to J. Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track.
2. By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
   • state which tracks she will repeat in her route
   • state the total length of her route
   The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route.
3. Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.

4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 A tree, T , has exactly six nodes. The degrees of the six nodes of T are
1
2
\(( 4 - x )\)
\(( 2 x - 5 )\)
\(( 4 x - 11 )\)
\(( 3 x - 5 )\)
where \(x\) is an integer.
(b) Explain how you know that T cannot be Eulerian.
(c) (i) Determine the value of \(x\)
(ii) Hence state whether T is semi-Eulerian or not. You must justify your answer.
(5)
\includegraphics[max width=\textwidth, alt={}, center]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-07_588_579_977_744} \section*{Figure 2} Figure 2 shows a graph, \(G\), with six nodes with degrees \(1,2,3,3,3\) and 4
(d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees \(1,2,3,3,3\) and 4 that is not isomorphic to G .

5. Two friends, Anaira and Tommi, play a game involving two positive numbers \(x\) and \(y\) Anaira gives Tommi the following clues to see if he can correctly determine the value of \(x\) and the value of \(y\)

• \(x\) is greater than \(y\) and the difference between the two is at least 100
• \(x\) is at most 5 times as large as \(y\)
• the sum of \(2 x\) and \(3 y\) is at least 350
• the sum of \(x\) and \(y\) is as small as possible

Tommi decides to solve this problem by using the big-M method.

1. Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show
   • how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables
   • how the objective function was formed
   The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.

   b.v.	\(x\)	\(y\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(x\)	1	0	\(- \frac { 3 } { 5 }\)	0	\(- \frac { 1 } { 5 }\)	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)	130

2. 1. State the value of \(x\)
   2. Hence deduce the value of \(y\), making your reasoning clear.

6. The precedence table below shows the 12 activities required to complete a project.

1. Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain the minimum number of dummies only.
   (5) Each of the activities shown in the precedence table requires one worker. The project is to be completed in the minimum possible time. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-11_303_1547_296_260} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 shows a schedule for the project using three workers.
2. 1. State the critical path for the network.
   2. State the minimum completion time for the project.
   3. Calculate the total float on activity B.
   4. Calculate the total float on activity G. Immediately after the start of the project, it is found that the duration of activity I, as shown in Figure 3, is incorrect. In fact, activity I will take 8 hours.
      The durations of all the other activities remain as shown in Figure 3.
3. Determine whether the project can still be completed in the minimum completion time using only three workers when the duration of activity I is 8 hours. Your answer must make specific reference to workers, times and activities.

7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the Simplex method. The tableau after the 1st iteration is shown below.

1. State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer.
2. By considering the equations represented in the above tableau, formulate the linear programming problem in \(x , y\) and \(z\) only. State the objective and list the constraints as inequalities with integer coefficients.
3. Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T . Make your method clear by stating the row operations you use.
4. 1. Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.
   2. State the values of the basic variables after the 2nd iteration. A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.

      b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	Value
      z	0	0	1	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 43 } { 2 }\)
      \(x\)	1	0	0	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 8 }\)	\(- \frac { 1 } { 8 }\)	\(\frac { 57 } { 4 }\)
      \(y\)	0	1	0	\(- \frac { 1 } { 2 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 3 } { 4 }\)	\(\frac { 9 } { 2 }\)
      \(P\)	0	1	0	\(\frac { 5 } { 4 }\)	\(\frac { 1 } { 8 }\)	\(\frac { 7 } { 8 }\)	\(\frac { 361 } { 4 }\)

5. Explain how you know that the student's attempt at the 3rd iteration is not correct.