Questions - Edexcel FD1 - A-Level Maths

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.
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$
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.

Edexcel FD1 2019 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-03_663_1421_203_322} \captionsetup{labelformat=empty} \caption{Figure 1
[0pt] [The total weight of the network is 370]}

\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.

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 .
Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
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 .
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.

Edexcel FD1 2019 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-04_666_940_173_534} \captionsetup{labelformat=empty} \caption{Figure 2}

\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.

Complete the initial distance and route tables for the network provided in the answer book.
(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}
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.
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.

Edexcel FD1 2019 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-05_1004_1797_205_134} \captionsetup{labelformat=empty} \caption{Figure 3}

\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.

Explain, with detailed reasoning, why $x = 11$
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.
Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time.
Schedule the activities using Grid 1 in the answer book.

Edexcel FD1 2019 June Q5

Activity	Immediately preceding activities
A	-
B	-
C	-
D	A
E	C
F	B, C, D
G	A
H	B, C, D
I	B, C, D, G
J	B, C, D, G
K	E, H

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.

Edexcel FD1 2019 June Q6

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}$$

Explain why the Simplex algorithm cannot be used to solve this linear programming problem.

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

State the value of each variable after the first iteration.
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,
obtain the most efficient pivot for a second iteration. You must give reasons for your answer.

Edexcel FD1 2020 June Q1

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 .

	A	B	C	D	E	F	G
A	-	24	-	22	35	-	-
B	24	-	25	27	-	-	-
C	-	25	-	33	31	36	26
D	22	27	33	-	-	42	-
E	35	-	31	-	-	37	29
F	-	-	36	42	37	-	40
G	-	-	26	-	29	40	-

By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book.
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.
State the weight of the minimum spanning tree.

Edexcel FD1 2020 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-03_688_1102_267_482} \captionsetup{labelformat=empty} \caption{Figure 1}

\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.

Explain why each of the dummy activities is required.
Complete the table in the answer book to show the immediately preceding activities for each activity.
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.
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.
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.

Edexcel FD1 2020 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-04_387_519_214_774} \captionsetup{labelformat=empty} \caption{Figure 2}

\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.

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}
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}
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.

Edexcel FD1 2020 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-06_1171_1758_269_150} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 shows the constraints of a linear programming problem in $x$ and $y$, where $R$ is the feasible region.

Write down the inequalities that define $R$. The objective is to maximise $P$, where $P = 3 x + y$
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$,
find the range of possible values of $a$.

Edexcel FD1 2020 June Q5

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

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}$$
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,
calculate the value of $x$. You must give reasons for your answer.

Edexcel FD1 2020 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-08_638_1107_212_479} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} [The total weight of the network is $320 + x + y$ ]

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
Using appropriate algorithms, find the value of $x$ and the value of $y$.

Edexcel FD1 2020 June Q7

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.

Basic variable	$x$	$y$	$z$	$S _ { 1 }$	$S _ { 2 }$	$S _ { 3 }$	$a _ { 1 }$	$a _ { 2 }$	Value
$S _ { 1 }$	1	2	3	1	0	0	0	0	45
$a _ { 1 }$	3	2	0	0	-1	0	1	0	9
$a _ { 2 }$	-1	0	4	0	0	-1	0	1	4
$P$	-2	-1	-3	0	0	0	0	0	0
A

Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.

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

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.
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.
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.

Edexcel FD1 2021 June Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-02_606_670_260_699} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} A Hamiltonian cycle for the graph in Figure 1 begins $\mathrm { C } , \mathrm { V } , \mathrm { E } , \mathrm { X } , \mathrm { A } , \mathrm { W } , \ldots$.

Complete the Hamiltonian cycle.
Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.

Edexcel FD1 2021 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-03_700_1412_258_331} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity.

Complete Diagram 1 in the answer book to show the early event times and the late event times. Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.
Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
Schedule the activities using Grid 1 in the answer book.

Edexcel FD1 2021 June Q3

3. \begin{table}[h]

\cline { 2 - 9 } \multicolumn{1}{c\|}{}	A	B	C	D	E	F	G	H
A	-	24	42	48	34	37	32	22
B	24	-	40	35	30	41	39	44
C	42	40	-	21	26	45	38	36
D	48	35	21	-	32	37	29	27
E	34	30	26	32	-	34	40	28
F	37	41	45	37	34	-	43	41
G	32	39	38	29	40	43	-	38
H	22	44	36	27	28	41	38	-

\captionsetup{labelformat=empty} \caption{Table 1}

\end{table} Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

Use Prim's algorithm, starting at A , to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree.

State the weight of the minimum spanning tree. \begin{table}[h]

\cline { 2 - 9 } \multicolumn{1}{c\|}{}	$\mathbf { A }$	$\mathbf { B }$	$\mathbf { C }$	$\mathbf { D }$	$\mathbf { E }$	$\mathbf { F }$	$\mathbf { G }$	$\mathbf { H }$
$\mathbf { J }$	31	27	50	29	43	25	49	35

\captionsetup{labelformat=empty} \caption{Table 2}

\end{table} Table 2 shows the distances, in miles, between town J and towns A , B , $\mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H .
Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.

Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.

Edexcel FD1 2021 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-05_668_1424_169_322} \captionsetup{labelformat=empty} \caption{Figure 3
[0pt] [The total weight of the network is 1648]}

\end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.
An initial route matrix is given in the answer book.

Set up the initial time matrix.
Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.
\cline { 2 - 7 } \multicolumn{1}{c|}{} A B C D E F
A - 57 95 147 63 220
B 57 - 72 204 120 197
C 95 72 - 242 158 125
D 147 204 242 - 84 275
E 63 120 158 84 - 191
F 220 197 125 275 191 -
A route is needed that minimises the total time taken to traverse each road at least once.
The route must start at B and finish at E .
Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
Write down the length of the route.

Edexcel FD1 2021 June Q5

30312522318136101524
1. The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
The ten numbers 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 original list of ten numbers, the following allocation is obtained.
Bin 1: 30 12 2
Bin 2: 5 23 10
Bin 3: 18 15
Bin 4: 36
Bin 5: 24
Explain why the value of the integer $n$ must be either 44 or 45
Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45

Edexcel FD1 2021 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-07_728_1465_248_301} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} In Figure 4 the weights on the arcs represent distances.

1. Use Dijkstra's algorithm to find the shortest path from A to H .
2. State the length of the shortest path from A to H . One application of Dijkstra's algorithm has order $n ^ { 2 }$, where $n$ is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
Explain why your answer to part (b) can only be an approximation.

Edexcel FD1 2021 June Q7

7. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-08_583_670_260_699} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} Figure 5 shows a partially completed activity network for a project that consists of 14 activities.

Complete the precedence table in the answer book for the 8 activities in Figure 5. The precedence table for the remaining 6 activities is given below.
Activity Immediately preceding activities
I D, E, G, H
J D, E, G, H
K E, G, H
L I, J, K
M J, K
N J, K
Complete the activity network in the answer book for the project. Your completed activity network must contain only the minimum number of dummies. Given that all 14 activities have the same duration,
explain why activity D cannot be critical.

Edexcel FD1 2021 June Q8

8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should

maximise the total time spent cycling and running
train for at most 39 hours
spend at least $40 \%$ of her time swimming
spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

$x$ represent the number of hours swimming
$y$ represent the number of hours cycling
$z$ represent the number of hours running
1. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.
  (5)

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how

the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable
the rows for the two objective functions are formed
(6)

The following tableau $T$ is obtained after one iteration of the second stage of the two-stage Simplex method.

b.v.	$x$	$y$	$z$	$s _ { 1 }$	$\mathrm { S } _ { 2 }$	$S _ { 3 }$	Value
$y$	0	1	0	1	0	1	11
$s _ { 2 }$	0	0	5	-2	1	-5	62
$x$	1	0	1	0	0	-1	28
$P$	0	0	-1	1	0	1	11

Obtain a suitable pivot for a second iteration. You must give reasons for your answer.

Starting from tableau $T$, solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.

Edexcel FD1 2022 June Q1

A gardener needs the following lengths of string. All lengths are in metres.
0.4
1.7
1.3
2.5
2.1
3.4
4.3
4.7
5.1
5.9
6.1

She cuts the lengths from balls of string. Each ball contains 10 m of string.

Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.
Use the first-fit bin packing algorithm to determine how the lengths could be cut from the balls of string.

Edexcel FD1 2022 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-03_563_1445_214_312} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to K .
2. State the length of the shortest path from A to K .
  (6) The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
1. State the edges that will need to be traversed twice.
2. Find the length of Blanche's route. It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.

Edexcel FD1 2022 June Q3

3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only. \begin{table}[h]

	A	B	C	D	E	F
A	-	12	32	24	29	11
B	12	-	17	8	$\infty$	$\infty$
C	32	17	-	4	12	$\infty$
D	24	$\infty$	4	-	$\infty$	13
E	$\infty$	$\infty$	12	18	-	12
F	11	$\infty$	$\infty$	13	12	-

\captionsetup{labelformat=empty} \caption{Table 1}

\end{table}

By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. Floyd's algorithm is to be used to find the complete network of shortest distances between the six classrooms. The distance matrix after two iterations of Floyd's algorithm is shown in Table 2. \begin{table}[h]
A B C D E F
A - 12 29 20 29 11
B 12 - 17 8 41 23
C 29 17 - 4 12 40
D 24 36 4 - 53 13
E $\infty$ $\infty$ 12 18 - 12
F 11 23 40 13 12 -
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table}
Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration. The final distance matrix after completion of Floyd's algorithm is shown in Table 3.
A B C D E F
A - 12 24 20 23 11
B 12 - 12 8 24 21
C 28 17 - 4 12 17
D 24 21 4 - 16 13
E 23 29 12 16 - 12
F 11 23 17 13 12 -
\section*{Table 3} Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.
1. Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.
2. Find the length of each of the two cycles.
3. State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka's route.

Edexcel FD1 2022 June Q4

4. A linear programming problem in $x , y$ and $z$ is to be solved using the big-M method. The initial tableau is shown below.

b.v.	$x$	$y$	$z$	$S _ { 1 }$	$s _ { 2 }$	$S _ { 3 }$	$a _ { 1 }$	$a _ { 2 }$	Value
$\mathrm { S } _ { 1 }$	2	3	4	1	0	0	0	0	13
$a _ { 1 }$	1	-2	2	0	-1	0	1	0	8
$a _ { 2 }$	3	0	-4	0	0	-1	0	1	12
P	2-4M	$- 3 + 2 M$	$- 1 + 2 M$	0	M	M	0	0	$- 20 M$

Using the information in the above tableau, formulate the linear programming problem. You should
- list each of the constraints as an inequality
- state the two possible objectives
- Obtain the most efficient pivot for a first iteration of the big-M method. You must give reasons for your answer.
\section*{Please turn over for Question 5}

Basic variable	\(x\)	\(y\)	\(z\)	\(S _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
\(S _ { 1 }\)	1	2	3	1	0	0	0	0	45
\(a _ { 1 }\)	3	2	0	0	-1	0	1	0	9
\(a _ { 2 }\)	-1	0	4	0	0	-1	0	1	4
\(P\)	-2	-1	-3	0	0	0	0	0	0
A

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

\cline { 2 - 9 } \multicolumn{1}{c\|}{}	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	\(\mathbf { D }\)	\(\mathbf { E }\)	\(\mathbf { F }\)	\(\mathbf { G }\)	\(\mathbf { H }\)
\(\mathbf { J }\)	31	27	50	29	43	25	49	35

b.v.	\(x\)	\(y\)	\(z\)	\(S _ { 1 }\)	\(s _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
\(\mathrm { S } _ { 1 }\)	2	3	4	1	0	0	0	0	13
\(a _ { 1 }\)	1	-2	2	0	-1	0	1	0	8
\(a _ { 2 }\)	3	0	-4	0	0	-1	0	1	12
P	2-4M	\(- 3 + 2 M\)	\(- 1 + 2 M\)	0	M	M	0	0	\(- 20 M\)

\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	-

	A	B	C	D	E	F	G
A	-	24	-	22	35	-	-
B	24	-	25	27	-	-	-
C	-	25	-	33	31	36	26
D	22	27	33	-	-	42	-
E	35	-	31	-	-	37	29
F	-	-	36	42	37	-	40
G	-	-	26	-	29	40	-

\cline { 2 - 7 } \multicolumn{1}{c\|}{}	A	B	C	D	E	F
A	-	57	95	147	63	220
B	57	-	72	204	120	197
C	95	72	-	242	158	125
D	147	204	242	-	84	275
E	63	120	158	84	-	191
F	220	197	125	275	191	-

Activity	Immediately preceding activities
I	D, E, G, H
J	D, E, G, H
K	E, G, H
L	I, J, K
M	J, K
N	J, K

	A	B	C	D	E	F
A	-	12	32	24	29	11
B	12	-	17	8	\(\infty\)	\(\infty\)
C	32	17	-	4	12	\(\infty\)
D	24	\(\infty\)	4	-	\(\infty\)	13
E	\(\infty\)	\(\infty\)	12	18	-	12
F	11	\(\infty\)	\(\infty\)	13	12	-

	A	B	C	D	E	F
A	-	12	24	20	23	11
B	12	-	12	8	24	21
C	28	17	-	4	12	17
D	24	21	4	-	16	13
E	23	29	12	16	-	12
F	11	23	17	13	12	-

	A	B	C	D	E	F	G
A	-	24	-	22	35	-	-
B	24	-	25	27	-	-	-
C	-	25	-	33	31	36	26
D	22	27	33	-	-	42	-
E	35	-	31	-	-	37	29
F	-	-	36	42	37	-	40
G	-	-	26	-	29	40	-

	A	B	C	D	E	F
A	-	12	24	20	23	11
B	12	-	12	8	24	21
C	28	17	-	4	12	17
D	24	21	4	-	16	13
E	23	29	12	16	-	12
F	11	23	17	13	12	-

Questions — Edexcel FD1 (49 questions)

Browse by module

Browse by board

Edexcel FD1 2019 June Q1

Edexcel FD1 2019 June Q2

Edexcel FD1 2019 June Q3

Edexcel FD1 2019 June Q4

Edexcel FD1 2019 June Q5

Edexcel FD1 2019 June Q6

Edexcel FD1 2020 June Q1

Edexcel FD1 2020 June Q2

Edexcel FD1 2020 June Q3

Edexcel FD1 2020 June Q4

Edexcel FD1 2020 June Q5

Edexcel FD1 2020 June Q6

Edexcel FD1 2020 June Q7

Edexcel FD1 2021 June Q1

Edexcel FD1 2021 June Q2

Edexcel FD1 2021 June Q3

Edexcel FD1 2021 June Q4

Edexcel FD1 2021 June Q5

Edexcel FD1 2021 June Q6

Edexcel FD1 2021 June Q7

Edexcel FD1 2021 June Q8

Edexcel FD1 2022 June Q1

Edexcel FD1 2022 June Q2

Edexcel FD1 2022 June Q3

Edexcel FD1 2022 June Q4

	A	B	C	D	E	F	G
A	-	24	-	22	35	-	-
B	24	-	25	27	-	-	-
C	-	25	-	33	31	36	26
D	22	27	33	-	-	42	-
E	35	-	31	-	-	37	29
F	-	-	36	42	37	-	40
G	-	-	26	-	29	40	-

	A	B	C	D	E	F
A	-	12	24	20	23	11
B	12	-	12	8	24	21
C	28	17	-	4	12	17
D	24	21	4	-	16	13
E	23	29	12	16	-	12
F	11	23	17	13	12	-