Questions - Edexcel - A-Level Maths

Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]

Edexcel D1 Q4

10 marks Moderate -0.5

This question should be answered on the sheet provided. \includegraphics{figure_1} Figure 1 above shows distances in miles between 10 cities. Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:

the order in which you labelled the vertices,
how you used your labelled diagram to find the shortest route. [10 marks]

Edexcel D1 Q5

12 marks Moderate -0.5

This question should be answered on the sheet provided. \includegraphics{figure_2} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.

Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected. [4 marks]
It is decided that a Greek translation is not needed. Find the minimum cost if:
1. translations to and from Greek are not available,
2. translations to and from Greek are still available. [3 marks]
Comment on your findings. [1 mark]

Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.

How would you overcome the problem of having different costs for reverse translations? [1 mark]
What algorithm would be suitable to find a computerised solution. [1 mark]
State another assumption you have made in answering this question and comment on its validity. [2 marks]

Edexcel D1 Q6

13 marks Standard +0.3

This question should be answered on the sheet provided. There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.

Computer	Applications
$E$	Animation
$F$	Office, Data
$G$	Simulation
$H$	Animation, Office
$I$	Data, CAD, Simulation

Draw a bipartite graph to model this situation. [1 mark]

Initially it is decided to run the Office application on computer $F$, Animation on computer $H$, and Data on computer $I$.

Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied. [9 marks]
Computer $H$ is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b). [3 marks]

Edexcel D1 Q7

18 marks Standard +0.3

An engineer makes three components $X$, $Y$ and $Z$. Relevant details are as follows: Component $X$ requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component $Y$ requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component $Z$ requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components $X$, $Y$ and $Z$ are £40, £90 and £60 respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components $X$, $Y$ and $Z$ the engineer makes each day be $x$, $y$ and $z$ respectively.

Write down the 3 inequalities that apply in addition to $x \geq 0$, $y \geq 0$ and $z \geq 0$. [3 marks]
Explain why it is not appropriate to use a graphical method to solve the problem. [1 mark]

It is decided to use the simplex algorithm to solve the problem.

Show that a possible initial tableau is:
Basic Variable $x$ $y$ $z$ $r$ $s$ $t$ Value
$r$ 6 15 12 1 0 0 185
$s$ 3 3 1 0 1 0 30
$t$ 1 4 4 0 0 1 60
$P$ $-4$ $-9$ $-6$ 0 0 0 0
[2 marks]

It is decided to increase $y$ first.

Perform sufficient complete iterations to obtain a final tableau and explain how you know that your solution is optimal. You may assume that work in progress is allowed. [9 marks]
State the number of each component that should be made per day and the total daily profit that this gives, assuming that all items can be sold. [1 mark]
If work in progress is not practicable, explain how you would obtain an integer solution to this problem. You are not expected to find this solution. [2 marks]

Edexcel D2 Q1

8 marks Moderate -0.8

\includegraphics{figure_1} Figure 1 shows a network of roads connecting six villages $A$, $B$, $C$, $D$, $E$ and $F$. The lengths of the roads are given in km.

Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. [2] The table can now be taken to represent a complete network.
Use the nearest-neighbour algorithm, starting at $A$, on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at $A$ and visits every village exactly once. [3]
Interpret your answer in part (b) in terms of the original network of roads connecting the six villages. [1]
By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length. [2]

Edexcel D2 Q2

8 marks Moderate -0.8

A two-person zero-sum game is represented by the following pay-off matrix for player $A$.

	I	II	III	IV
I	$-4$	$-5$	$-2$	4
II	$-1$	1	$-1$	2
III	0	5	$-2$	$-4$
IV	$-1$	3	$-1$	1

Determine the play-safe strategy for each player. [4]
Verify that there is a stable solution and determine the saddle points. [3]
State the value of the game to $B$. [1]

Edexcel D2 Q3

10 marks Standard +0.3

\includegraphics{figure_2} The network in Fig. 2 shows possible routes that an aircraft can take from $S$ to $T$. The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the minimax route.

Complete the table in the answer booklet. [8]
Hence obtain the minimax route from $S$ to $T$ and state the maximum amount of fuel used on any part of this route. [2]

Edexcel D2 Q4

8 marks Moderate -0.3

Andrew ($A$) and Barbara ($B$) play a zero-sum game. This game is represented by the following pay-off matrix for Andrew. $$A \begin{pmatrix} 3 & 5 & 4 \\ 1 & 4 & 2 \\ 6 & 3 & 7 \end{pmatrix}$$

Explain why this matrix may be reduced to $$\begin{pmatrix} 3 & 5 \\ 6 & 3 \end{pmatrix}$$ [8]
Hence find the best strategy for each player and the value of the game.

Edexcel D2 Q5

11 marks Moderate -0.5

An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.

	Job 1	Job 2	Job 3	Job 4
Machine 1	14	5	8	7
Machine 2	2	12	6	5
Machine 3	7	8	3	9
Machine 4	2	4	6	10

Use the Hungarian algorithm, \emph{reducing rows first}, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time. [11]

Edexcel D2 Q6

14 marks Moderate -0.3

The table below shows the distances, in km, between six towns $A$, $B$, $C$, $D$, $E$ and $F$.

	A	B	C	D	E	F
A	$-$	85	110	175	108	100
B	85	$-$	38	175	160	93
C	110	38	$-$	148	156	73
D	175	175	148	$-$	110	84
E	108	160	156	110	$-$	92
F	100	93	73	84	92	$-$

Starting from $A$, use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected. [4]
1. Using your answer to part (a) obtain an initial upper bound for the solution of the travelling salesman problem. [2]
2. Use a short cut to reduce the upper bound to a value less than 680. [4]
Starting by deleting $F$, find a lower bound for the solution of the travelling salesman problem. [4]

Edexcel D2 Q7

14 marks Standard +0.3

A steel manufacturer has 3 factories $F_1$, $F_2$ and $F_3$ which can produce 35, 25 and 15 kilotomnes of steel per year, respectively. Three businesses $B_1$, $B_2$ and $B_3$ have annual requirements of 20, 25 and 30 kilotomnes respectively. The table below shows the cost $C_{ij}$ in appropriate units, of transporting one kilotome of steel from factory $F_i$ to business $B_j$.

		Business
	$B_1$	$B_2$	$B_3$
$F_1$	10	4	11
Factory $F_2$	12	5	8
$F_3$	9	6	7

The manufacturer wishes to transport the steel to the businesses at minimum total cost.

Write down the transportation pattern obtained by using the North-West corner rule. [2]
Calculate all of the improvement indices $I_{ij}$ and hence show that this pattern is not optimal. [5]
Use the stepping-stone method to obtain an improved solution. [3]
Show that the transportation pattern obtained in part (c) is optimal and find its cost. [4]

Edexcel D2 Q8

14 marks Moderate -0.8

\includegraphics{figure_4} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

Write down the source vertices. [2]

\includegraphics{figure_5} Figure 5 shows a feasible flow through the same network.

State the value of the feasible flow shown in Fig. 5. [1]

Taking the flow in Fig. 5 as your initial flow pattern,

use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow. [6]
Show the maximal flow on Diagram 2 and state its value. [3]
Prove that your flow is maximal. [2]

Edexcel D2 Q9

17 marks Moderate -0.3

T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.

	Processing	Blending	Packing	Profit (£100)
Morning blend	3	1	3	4
Afternoon blend	2	3	4	5
Evening blend	4	2	3	3

The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let $x$, $y$ and $z$ be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. [4]

An initial Simplex tableau for the above situation is

Basic variable	$x$	$y$	$z$	$r$	$s$	$t$	Value
$r$	3	2	4	1	0	0	35
$s$	1	3	2	0	1	0	20
$t$	2	4	3	0	0	1	24
$P$	$-4$	$-5$	$-3$	0	0	0	0

Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. [11]

T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.

Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available. [2]

Edexcel D2 Q10

6 marks Moderate -0.3

While solving a maximizing linear programming problem, the following tableau was obtained.

Basic variable	$x$	$y$	$z$	$r$	$s$	$t$	Value
$r$	0	0	$1\frac{1}{3}$	1	0	$-\frac{1}{3}$	$\frac{5}{3}$
$y$	0	1	$3\frac{1}{3}$	0	1	$-\frac{1}{3}$	$\frac{1}{3}$
$x$	1	0	$-3$	0	$-1$	$\frac{1}{3}$	1
$P$	0	0	1	0	1	1	11

Explain why this is an optimal tableau. [1]
Write down the optimal solution of this problem, stating the value of every variable. [3]
Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of $P$. [2]

Edexcel D2 Q11

11 marks Standard +0.3

A company wishes to transport its products from 3 factories $F_1$, $F_2$ and $F_3$ to a single retail outlet $R$. The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \includegraphics{figure_5}

On Diagram 1 in the answer booklet add a supersource $S$ to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added. [2]
1. State the maximum flow along $SF_1ABR$ and $SF_2CR$. [2]
2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
Taking your answer to part (b)(ii) as the initial flow pattern,
1. use the labelling procedure to find a maximum flow from $S$ to $R$. Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow. [7]
2. Prove that your final flow is maximal.

Edexcel D2 Q12

11 marks Standard +0.3

\includegraphics{figure_2} A company has 3 warehouses $W_1$, $W_2$ and $W_3$. It needs to transport the goods stored there to 2 retail outlets $R_1$ and $R_2$. The capacities of the possible routes, in van loads per day, are shown in Fig. 2. Warehouses $W_1$, $W_2$ and $W_3$ have 14, 12 and 14 van loads respectively available per day and retail outlets $R_1$ and $R_2$ can accept 6 and 25 van loads respectively per day.

On Diagram 1 on the answer sheet add a supersource $W$ and a supersink $R$ and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added. [3]
State the maximum flow along
1. $W_1W_1R_1R$,
2. $W_2CR_2R$.
[2]
Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from $W$ to $R$. Show your working on Diagram 2. List each flow-augmenting route you find together with its flow. [5]
From your final flow pattern, determine the number of van loads passing through $B$ each day. [1]

Edexcel D2 2004 June Q1

4 marks Easy -2.0

In game theory explain what is meant by

zero-sum game, [2]
saddle point. [2]

(Total 4 marks)

Edexcel D2 2004 June Q2

9 marks Moderate -0.8

In a quiz there are four individual rounds, Art, Literature, Music and Science. A team consists of four people, Donna, Hannah, Kerwin and Thomas. Each of four rounds must be answered by a different team member. The table shows the number of points that each team member is likely to get on each individual round.

	Art	Literature	Music	Science
Donna	31	24	32	35
Hannah	16	10	19	22
Kerwin	19	14	20	21
Thomas	18	15	21	23

Use the Hungarian algorithm, reducing rows first, to obtain an allocation which maximises the total points likely to be scored in the four rounds. You must make your method clear and show the table after each stage. [9] (Total 9 marks)

Edexcel D2 2004 June Q3

12 marks Moderate -0.3

The table shows the least distances, in km, between five towns, $A$, $B$, $C$, $D$ and $E$.

	$A$	$B$	$C$	$D$	$E$
$A$	$-$	153	98	124	115
$B$	153	$-$	74	131	149
$C$	98	74	$-$	82	103
$D$	124	131	82	$-$	134
$E$	115	149	103	134	$-$

Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.

Making your method clear, find an initial upper bound starting at $A$ and using
1. the minimum spanning tree method, [4]
2. the nearest neighbour algorithm. [3]
By deleting $E$, find a lower bound. [4]
Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down. [1]

(Total 12 marks)

Edexcel D2 2004 June Q4

14 marks Standard +0.3

Emma and Freddie play a zero-sum game. This game is represented by the following pay-off matrix for Emma. $\begin{pmatrix} -4 & -1 & 3 \\ 2 & 1 & -2 \end{pmatrix}$

Show that there is no stable solution. [3]
Find the best strategy for Emma and the value of the game to her. [8]
Write down the value of the game to Freddie and his pay-off matrix. [3]

(Total 14 marks)

Edexcel D2 2004 June Q5

18 marks Moderate -0.8

Describe a practical problem that could be solved using the transportation algorithm. [2]

A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from $A$, $B$ and $C$ and the demand is at $d$ and $e$.

	$d$	$e$	Supply
$A$	5	3	45
$B$	4	6	35
$C$	2	4	40
Demand	50	60

Explain why it is necessary to add a third demand $f$. [1]
Use the north-west corner rule to obtain a possible pattern of distribution and find its cost.
$d$ $e$ $f$ Supply
$A$ 5 3 45
$B$ 4 6 35
$C$ 2 4 40
Demand 50 60
[5]
Calculate shadow costs and improvement indices for this pattern. [5]
Use the stepping-stone method once to obtain an improved solution and its cost. [5]

(Total 16 marks)

Activity	Depends on	Duration (hours)
\(A\)	\(-\)	5
\(B\)	\(A\)	4
\(C\)	\(A\)	2
\(D\)	\(B, C\)	11
\(E\)	\(C\)	4
\(F\)	\(D\)	3
\(G\)	\(D\)	8
\(H\)	\(D, E\)	2
\(I\)	\(F\)	1
\(J\)	\(F, G, H\)	7
\(K\)	\(I, J\)	2

Basic Variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	6	15	12	1	0	0	185
\(s\)	3	3	1	0	1	0	30
\(t\)	1	4	4	0	0	1	60
\(P\)	\(-4\)	\(-9\)	\(-6\)	0	0	0	0

	I	II	III	IV
I	\(-4\)	\(-5\)	\(-2\)	4
II	\(-1\)	1	\(-1\)	2
III	0	5	\(-2\)	\(-4\)
IV	\(-1\)	3	\(-1\)	1

		Business
	\(B_1\)	\(B_2\)	\(B_3\)
\(F_1\)	10	4	11
Factory \(F_2\)	12	5	8
\(F_3\)	9	6	7

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	3	2	4	1	0	0	35
\(s\)	1	3	2	0	1	0	20
\(t\)	2	4	3	0	0	1	24
\(P\)	\(-4\)	\(-5\)	\(-3\)	0	0	0	0

Questions — Edexcel (10514 questions)

Browse by module

Browse by board

Edexcel M5 Specimen Q8

Edexcel D1 Q1

Edexcel D1 Q2

Edexcel D1 Q3

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q3

Edexcel D2 Q4

Edexcel D2 Q5

Edexcel D2 Q6

Edexcel D2 Q7

Edexcel D2 Q8

Edexcel D2 Q9

Edexcel D2 Q10

Edexcel D2 Q11

Edexcel D2 Q12

Edexcel D2 2004 June Q1

Edexcel D2 2004 June Q2

Edexcel D2 2004 June Q3

Edexcel D2 2004 June Q4

Edexcel D2 2004 June Q5