Edexcel FD1 (Further Decision 1) 2020 June

1. The table below shows the lengths, in km , of the roads in a network connecting seven towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .

1. By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
3. State the weight of the minimum spanning tree.

2. \begin{figure}[h] \end{figure} The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets.

1. Explain why each of the dummy activities is required.
2. Complete the table in the answer book to show the immediately preceding activities for each activity.
3. 1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
   2. State the minimum completion time for the project.
   3. State the critical activities. Each activity requires one worker. Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption.
4. On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time.
5. Determine whether or not the project can be completed in the minimum possible time using fewer workers than the number indicated by the resource histogram in (d). You must justify your answer with reference to the resource histogram and the completed Diagram 1.

3. \begin{figure}[h] \end{figure} Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.

1. Set up initial time and route matrices. The matrices after two iterations of Floyd's algorithm are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	8	4	7	18
   B	8	-	3	15	10
   C	4	3	-	11	6
   D	7	15	1	-	1
   E	18	10	6	1	-

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

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

   \end{table}
2. Perform the next two iterations of Floyd's algorithm that follow from the tables above. You should show the time and route matrices after each iteration. The final time matrix after completion of Floyd's algorithm is shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Final time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	7	4	7	8
   B	7	-	3	10	9
   C	4	3	-	7	6
   D	5	4	1	-	1
   E	6	5	2	1	-

   \end{table}
3. 1. Use the nearest neighbour algorithm, starting at A , to find a Hamiltonian cycle in the complete network of shortest times.
   2. Find the time taken for this cycle.
   3. Interpret the cycle in terms of the actual villages visited.

4. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

1. Write down the inequalities that define \(R\). The objective is to maximise \(P\), where \(P = 3 x + y\)
2. Obtain the exact value of \(P\) at each of the three vertices of \(R\) and hence find the optimal vertex, \(V\). The objective is changed to maximise \(Q\), where \(Q = 3 x + a y\). Given that \(a\) is a constant and the optimal vertex is still \(V\),
3. find the range of possible values of \(a\).

5. The nine distinct numbers in the following list are to be packed into bins of size 50 $$\begin{array} { l l l l l l l l l } 23 & 17 & 19 & x & 24 & 8 & 18 & 10 & 21 \end{array}$$ When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23178
Bin 2: \(19 \quad x \quad 10\)
Bin 3: 2418
Bin 4: 21

1. Explain why \(13 < x < 21\) The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is $$\begin{array} { l l l l l l l l l } 23 & 19 & 17 & 24 & x & 18 & 10 & 21 & 8 \end{array}$$
2. Using this information, write down the smallest interval that must contain \(x\), giving your answer as an inequality. When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 2423
   Bin 2: 211910
   Bin 3: \(1817 x\)
   Bin 4: 8
   Given that only one of the bins is full and that \(x\) is an integer,
3. calculate the value of \(x\). You must give reasons for your answer.

6. \begin{figure}[h] \end{figure} [The total weight of the network is \(320 + x + y\) ]

1. State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. The weights on the arcs in Figure 4 represent distances. The weight on arc EF is \(x\) where \(12 < x < 26\) and the weight on arc DG is \(y\) where \(0 < y < 10\) An inspection route of minimum length that traverses each arc at least once is found.
   The inspection route starts and finishes at A and has a length of 409
   It is also given that the length of the shortest route from F to G via A is 140
2. Using appropriate algorithms, find the value of \(x\) and the value of \(y\).

7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below.

1. Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.
2. Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

   Basic variable	\(x\)	\(y\)	\(z\)	\(S _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(S _ { 1 }\)	0	\(\frac { 5 } { 6 }\)	0	1	\(\frac { 7 } { 12 }\)	\(\frac { 3 } { 4 }\)	\(- \frac { 7 } { 12 }\)	\(- \frac { 3 } { 4 }\)	\(\frac { 147 } { 4 }\)
   \(x\)	1	\(\frac { 2 } { 3 }\)	0	0	\(- \frac { 1 } { 3 }\)	0	\(\frac { 1 } { 3 }\)	0	3
   \(z\)	0	\(\frac { 1 } { 6 }\)	1	0	\(- \frac { 1 } { 12 }\)	\(- \frac { 1 } { 4 }\)	\(\frac { 1 } { 12 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 7 } { 4 }\)
   \(P\)	0	\(\frac { 5 } { 6 }\)	0	0	\(- \frac { 11 } { 12 }\)	\(- \frac { 3 } { 4 }\)	\(\frac { 11 } { 12 }\)	\(\frac { 3 } { 4 }\)	\(\frac { 45 } { 4 }\)
   A	0	0	0	0	0	0	1	1	0

3. 1. Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
   2. Write down the basic feasible solution for the second stage.
4. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, \(T\). Make your method clear by stating the row operations you use.
5. 1. Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
   2. Write down the value of the objective function.
   3. State the values of the basic variables.