Edexcel FD1 (Further Decision 1) 2019 June

1. 0.2
1.7
1.9
1.2
1.4
1.5
2.1
3.0
3.2
3.3

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 The list of numbers is now to be sorted into descending order.
2. Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. For a list of \(n\) numbers, the quick sort algorithm has, on average, order \(n \log n\).
   Given that it takes 2.32 seconds to run the algorithm when \(n = 450\)
3. calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when \(n = 11250\). You should make your method and working clear.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

1. Use Dijkstra's algorithm to find the shortest path from A to D, stating the path and its length. On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G .
2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Find the length of Naasir's route. On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B .
4. 1. Determine the possible starting and finishing points so that the length of Naasir's route is minimised. You must give reasons for your answer.
   2. Find the length of Naasir's new route.

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the direct roads linking five villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E .
The number on each arc represents the length, in miles, of the corresponding road.
The roads from A to E and from C to B are one-way, as indicated by the arrows.

1. Complete the initial distance and route tables for the network provided in the answer book.
   (2)
2. Perform the first three iterations of Floyd's algorithm. You should show the distance table and the route table after each of the three iterations. After five iterations of Floyd's algorithm the final distance table and partially completed final route table are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Distance table}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	12	7	6	3
   B	15	-	22	21	18
   C	7	5	-	4	7
   D	11	9	4	-	3
   E	14	12	7	3	-

   \end{table} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Route table}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	A
   B	A	B
   C	A	B	C
   D	C	C	C	D
   E	D	D	D	D	E

   \end{table}
3. 1. Explain how the partially completed final route table can be used to find the shortest route from E to A.
   2. State this route. Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table.
4. 1. State the cycle obtained using the nearest neighbour algorithm.
   2. State the length of this cycle.
   3. Interpret the cycle in terms of the actual villages visited.
   4. Prove that Mabintou's cycle is not optimal.

4. \begin{figure}[h] \end{figure} The network in Figure 3 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times and late event times are to be shown at each vertex and one late event time has been completed for you. The total float of activity H is 7 days.

1. Explain, with detailed reasoning, why \(x = 11\)
2. Determine the missing early event times and late event times, and hence complete Diagram 1 in your answer book. Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.
3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time.
4. Schedule the activities using Grid 1 in the answer book.

5.

1. Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies. Given that all the activities shown in the precedence table have the same duration, (b) state the critical path for the network.

6. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = 2 x + 2 y - z\)
subject to \(\quad 3 x + y + 2 z \leqslant 30\) $$\begin{aligned} x - y + z & \geqslant 8
4 y + 2 z & \geqslant 15
x , y , z & \geqslant 0 \end{aligned}$$

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem.
2. Set up the initial tableau for solving this linear programming problem using the big-M method. After a first iteration of the big-M method, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(s _ { 1 }\)	3	0	1.5	1	0	0.25	0	-0.25	26.25
   \(a _ { 1 }\)	1	0	1.5	0	-1	-0.25	1	0.25	11.75
   \(y\)	0	1	0.5	0	0	-0.25	0	0.25	3.75
   \(P\)	\(- ( 2 + M )\)	0	2-1.5M	0	M	\(- 0.5 + 0.25 M\)	0	\(0.5 + 0.75 M\)	7.5-11.75M

3. State the value of each variable after the first iteration.
4. Explain why the solution given by the first iteration is not feasible. Taking the most negative entry in the profit row to indicate the pivot column,
5. obtain the most efficient pivot for a second iteration. You must give reasons for your answer.