Questions D2 - A-Level Maths

	A	B	C	D	Supply
X	28	20	19	16	53
Y	15	12	14	17	47
Demand	18	31	22	29

Use the north-west corner method to obtain a possible solution.
(1)
Taking the most negative improvement index to indicate the entering square, use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
Is your current solution optimal? Give a reason for your answer.
(1)

Edexcel D2 2010 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{a91f96a3-a9b4-4bf5-bfdf-93c34912e54a-5_774_1623_264_221} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 represents the maintenance choices a council can make and their costs, in \(\pounds 1000\) s, over the next four years. The council wishes to minimise the greatest annual cost of maintenance.

Use dynamic programming to find a minimax route from S to T .
(9)
State your route and the greatest annual cost incurred by the council.
(2)
Calculate the average annual cost to the council.
(2)

Edexcel D2 2010 June Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{a91f96a3-a9b4-4bf5-bfdf-93c34912e54a-6_1012_1696_233_182} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 2 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

State the value of the initial flow.
(1)
State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
(2)
By entering values along DH, FH, FI and IT, complete the labelling procedure on Diagram 1 in the answer book.
(2)
Using Diagram 1, increase the flow by a further 4 units. You must list each flow-augmenting route you use, together with its flow.
(3)
Prove that the flow is now maximal.
(2)

Edexcel D2 2010 June Q6

6. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic Variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	0	1	2	1	0	0	24
\(s\)	2	1	4	0	1	0	28
\(t\)	-1	\(\frac { 1 } { 2 }\)	3	0	0	1	22
\(P\)	-1	-2	-6	0	0	0	0

Write down the profit equation represented in the initial tableau.
(1)
Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
State the final value of the objective function and of each variable.
(3)

Edexcel D2 2010 June Q7

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

	B plays 1	B plays 2	B plays 3
A plays 1	- 4	5	1
A plays 2	3	- 1	- 2
A plays 3	- 3	0	2

Formulate the game as a linear programming problem for player A. Write the constraints as inequalities and define your variables.

Edexcel D2 2011 June Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{d28d78c1-052d-4350-a7e3-284380e3bbab-2_703_958_351_552} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances in your answer book.
Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou's route. Write down the route which gives this upper bound.
Starting by deleting A, and all of its arcs, find a lower bound for the route length.

Edexcel D2 2011 June Q2

2. The table below shows the cost of transporting one unit of stock from each of four supply points, 1 , 2, 3 and 4, to each of three demand points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the stock required at each demand point. A minimal cost solution is required.

	A	B	C	Supply
1	31	29	32	20
2	22	33	27	22
3	25	27	32	20
4	23	26	38	38
Demand	35	25	30

Add a dummy demand point and appropriate values to Table 1 in the answer book. Table 2 shows an initial solution given by the north-west corner method.
Table 3 shows some of the improvement indices for this solution. \begin{table}[h]
A B C D
1 20
2 15 7
3 18 2
4 28 10
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table} \begin{table}[h]
A B C D
1 - 13 - 9
2 - 11
3
4 1 - 7
\captionsetup{labelformat=empty} \caption{Table 3}
\end{table}
Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in the answer book.
Taking the most negative improvement index to indicate the entering square, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.

Edexcel D2 2011 June Q3

3. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\).
The following tableau is obtained.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(- \frac { 1 } { 2 }\)	0	2	1	\(- \frac { 1 } { 2 }\)	0	10
\(y\)	\(\frac { 1 } { 2 }\)	1	\(\frac { 3 } { 4 }\)	0	\(\frac { 1 } { 4 }\)	0	5
\(t\)	\(\frac { 1 } { 2 }\)	0	1	0	\(- \frac { 1 } { 4 }\)	1	4
\(P\)	- 7	0	1	0	4	0	320

Write down the profit equation represented in the tableau.
Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
State the value of the objective function and of each variable.

Edexcel D2 2011 June Q4

4. Laura and Sam play a zero-sum game. This game is represented by the following pay-off matrix for Laura.

	S plays 1	S plays 2	S plays 3
L plays 1	- 4	- 1	1
L plays 2	3	- 1	- 2
L plays 3	- 3	0	2

Find the best strategy for Laura and the value of the game to her.

Edexcel D2 2011 June Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{d28d78c1-052d-4350-a7e3-284380e3bbab-6_663_1363_242_351} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 2 shows a capacitated directed network. The number on each arc is its capacity. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{d28d78c1-052d-4350-a7e3-284380e3bbab-6_665_1363_1117_351} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 shows an initial flow through the same network.

State the values of flows \(a , b\) and \(c\), and the value of the initial flow.
By entering values along HG, HT and FG, complete the labelling procedure on Diagram 1 in the answer book.
Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
State the value of the maximum flow through the network.
Show your maximum flow on Diagram 2 in the answer book.
Prove that your flow is maximal.

Edexcel D2 2011 June Q6

6. Three workers, \(\mathrm { P } , \mathrm { Q }\) and R , are to be assigned to three tasks, A, B and C. Each worker must be assigned to just one task and each task must be assigned to just one worker.
Table 1 shows the cost of using each worker for each task. The total cost is to be minimised. \begin{table}[h]

	Task A	Task B	Task C
Worker P	27	31	25
Worker Q	26	30	34
Worker R	35	29	32

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

\end{table}

Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective and constraints clear.
You are not required to solve the problem. Table 2 shows the profit gained by using each worker for each task. The total profit is to be maximised. \begin{table}[h]
Task A Task B Task C
Worker P 33 37 31
Worker Q 32 36 40
Worker R 41 35 38
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table}
Modify Table 2 in the answer book so that the Hungarian Algorithm could be used to find the maximum total profit. You are not required to solve the problem.
(2)
(Total 9 marks)

Edexcel D2 2011 June Q7

7. Patrick is to take orders for his company's products. He will visit four countries over the next four weeks.
He will visit just one country each week.
He will leave from his office in London and will only return there after visiting the four countries.
He will travel directly from one country to the next.
He wishes to determine a schedule of four countries to visit. Table 1 shows the countries he could visit in each week. \begin{table}[h]

Week	Week 1	Week 2	Week 3	Week 4
Possible countries	A or B	C, D or E	F or G	H or I

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

\end{table} Table 2 shows the value of the orders, in \(\pounds 100\) s, he expects to take in each country. \begin{table}[h]

Country	A	B	C	D	E	F	G	H	I
Value of expected orders in \(\pounds 100\) s	22	17	42	41	39	29	27	36	38

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

\end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the various countries. \begin{table}[h]

Travel costs in £100s	A	B	C	D	E	F	G	H	I
London	5	3						5	4
A			5	4	2
B			4	4	3
C						6	5
D						6	3
E						4	4
F								6	7
G								5	6

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

\end{table} The expected income is the value of the expected orders minus the cost of travel. It is decided to use dynamic programming to find a schedule that maximises the total expected income for these four weeks.

Complete the table in the answer book to determine the optimal expected income.
State Patrick's two optimal schedules.

Edexcel D2 2012 June Q1

Five workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , are to be assigned to five tasks, \(1,2,3,4\) and 5 . Each worker is to be assigned to one task and each task must be assigned to one worker.

The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.

	1	2	3	4	5
A	129	127	122	134	135
B	127	125	123	131	132
C	142	131	121	140	139
D	127	127	122	131	136
E	141	134	129	144	143

Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
Find the minimum cost.

Edexcel D2 2012 June Q2

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

	A	B	C	D	E	F
A	-	16	25	21	12	15
B	16	-	24	22	21	12
C	25	24	-	18	30	27
D	21	22	18	-	15	12
E	12	21	30	15	-	18
F	15	12	27	12	18	-

Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.

Use the nearest neighbour algorithm, starting at A , to find an upper bound for the length of Toby's route.
Starting by deleting A, and all of its arcs, find a lower bound for the route length.

Edexcel D2 2012 June Q3

3. The table below shows the cost, in pounds, of transporting one tonne of concrete from each of three supply depots, \(\mathrm { A } , \mathrm { B }\) and C , to each of four building sites, \(\mathrm { D } , \mathrm { E } , \mathrm { F }\) and G . It also shows the number of tonnes that can be supplied from each depot and the number of tonnes required at each building site. A minimum cost solution is required.

	D	E	F	G	Supply
A	17	19	21	20	18
B	21	20	19	22	23
C	18	17	16	21	29
Demand	15	24	18	13

The north-west corner method gives the following possible solution.

	D	E	F	G	Supply
A	15	3			18
B		21	2		23
C			16	13	29
Demand	15	24	18	13

Taking AG as the first entering cell,

use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
Determine whether your current solution is optimal. Justify your answer.

Edexcel D2 2012 June Q4

4. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\) which is to be solved.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	5	\(\frac { 1 } { 2 }\)	0	1	0	0	5
\(s\)	1	-2	4	0	1	0	3
\(t\)	8	4	6	0	0	1	6
\(P\)	-5	-7	-4	0	0	0	0

Starting by increasing \(y\), perform one complete iteration of the simplex algorithm, to obtain tableau T. State the row operations you use.
Write down the profit equation given by tableau T .
Use the profit equation from part (b) to explain why tableau T is optimal.

Edexcel D2 2012 June Q5

5. Agent Goodie is planning to break into Evil Doctor Fiendish's secret base. He uses game theory to determine whether to approach the base from air, sea or land.
Evil Doctor Fiendish decides each day which of three possible plans he should use to protect his base. Agent Goodie evaluates the situation. He assigns numbers, negative indicating he fails in his mission, positive indicating success, to create a pay-off matrix. The numbers range from - 3 (he fails in his mission and is captured) to 5 (he successfully achieves his mission and escapes uninjured) and the pay-off matrix is shown below.

	Fiendish uses plan 1	Fiendish uses plan 2	Fiendish uses plan 3
Air	0	4	5
Sea	2	-3	1
Land	-2	3	-2

Reduce the game so that Agent Goodie has only two choices, explaining your reasoning.
Use game theory to determine Agent Goodie's best strategy.
Find the value of the game to Agent Goodie.

Edexcel D2 2012 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{d0bede44-05dc-4edd-8436-cf5eea710d1a-7_1120_1691_260_187} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

State the value of the initial flow.
(1)
Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SB } , \mathrm { BD } , \mathrm { CF }\) and FT .
(2)
Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
(4)
Draw a maximal flow pattern on Diagram 2 in your answer book.
(2)
Prove that your flow is maximal.
(2)

Edexcel D2 2012 June Q7

7. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker is to be assigned to exactly one task and each task must be assigned to just one worker. The cost, in pounds, of using each worker for each task is given in the table below. The total cost is to be minimised.

	P	Q	R	S
A	23	41	34	44
B	21	45	33	42
C	26	43	31	40
D	20	47	35	46

Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
(Total 7 marks)

Edexcel D2 2012 June Q8

8. A company makes industrial robots. They can make up to four robots in any one month, but if they make more than three they will have to hire additional labour at a cost of \(\pounds 400\) per month.
They can store up to two robots at a cost of \(\pounds 150\) per robot per month.
The overhead costs are \(\pounds 300\) in any month in which work is done.
Robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock after the April delivery. The order book for robots is

Month	January	February	March	April
Number of robots required	2	2	3	4

Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table provided in the answer book.
(Total 12 marks)

Edexcel D2 2013 June Q1

Four workers, Chris (C), James (J), Katie (K) and Nicky (N), are to be allocated to four tasks, 1, 2, 3 and 4. Each worker is to be allocated to one task and each task must be allocated to one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

	1	2	3	4
Chris	127	116	111	113
James	225	208	205	208
Katie	130	113	112	114
Nicky	228	212	203	210

Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
State which worker should be allocated to each task and the resulting total profit made.

Edexcel D2 2013 June Q2

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

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound.
(2)
Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Liz's route.
Starting by deleting F , and all of its arcs, find a lower bound for the length of Liz's route.
Use your results to write down the smallest interval which you are confident contains the optimal length of the route.

Edexcel D2 2013 June Q3

3. Table 1 below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to four demand points \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h]

	1	2	3	4	Supply
A	22	36	19	37	35
B	29	35	30	36	15
C	24	32	25	41	20
D	23	30	23	38	30
Demand	30	20	30	20

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

\end{table} Table 2 shows an initial solution given by the north-west corner method.
Table 3 shows some of the improvement indices for this solution. \begin{table}[h]

	1	2	3	4
A	30	5
B		15	0
C			20
D			10	20

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

\end{table} \begin{table}[h]

	1	2	3	4
A	x	x
B		x	x
C	8	2	x	1
D	9	2	x	x

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

\end{table}

Explain why a zero has been placed in cell B3 in Table 2.
(1)
Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in your answer book.
Taking the most negative improvement index to indicate the entering cell, state the steppingstone route that should be used to obtain the next solution. You must state your entering cell and exiting cell.

Edexcel D2 2013 June Q4

4. Robin (R) and Steve (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Robin.

	S plays 1	S plays 2	S plays 3
R plays 1	2	1	3
R plays 2	1	- 1	2
R plays 3	- 1	3	- 3

Find the best strategy for Robin and the value of the game to him.

Edexcel D2 2013 June Q5

5. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\).
The following tableau is obtained.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 2 }\)	0	1	0	\(- \frac { 1 } { 2 }\)	10
\(s\)	\(1 \frac { 1 } { 2 }\)	\(2 \frac { 1 } { 2 }\)	0	0	1	\(- \frac { 1 } { 2 }\)	5
\(z\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 2 }\)	1	0	0	\(\frac { 1 } { 2 }\)	5
\(P\)	-5	-10	0	0	0	20	220

Starting by increasing \(y\), perform one complete iteration of the Simplex algorithm, to obtain a new tableau, T. State the row operations you use.
Write down the profit equation given by T .
Use the profit equation from part (b) to explain why T is optimal.

	1	2	3	4	5
A	129	127	122	134	135
B	127	125	123	131	132
C	142	131	121	140	139
D	127	127	122	131	136
E	141	134	129	144	143

	A	B	C	D	E	F
A	-	16	25	21	12	15
B	16	-	24	22	21	12
C	25	24	-	18	30	27
D	21	22	18	-	15	12
E	12	21	30	15	-	18
F	15	12	27	12	18	-

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

	1	2	3	4	5
A	129	127	122	134	135
B	127	125	123	131	132
C	142	131	121	140	139
D	127	127	122	131	136
E	141	134	129	144	143

	A	B	C	D	E	F
A	-	16	25	21	12	15
B	16	-	24	22	21	12
C	25	24	-	18	30	27
D	21	22	18	-	15	12
E	12	21	30	15	-	18
F	15	12	27	12	18	-

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

Questions D2 (547 questions)

Browse by module

Browse by board

Edexcel D2 2010 June Q3

Edexcel D2 2010 June Q4

Edexcel D2 2010 June Q5

Edexcel D2 2010 June Q6

Edexcel D2 2010 June Q7

Edexcel D2 2011 June Q1

Edexcel D2 2011 June Q2

Edexcel D2 2011 June Q3

Edexcel D2 2011 June Q4

Edexcel D2 2011 June Q5

Edexcel D2 2011 June Q6

Edexcel D2 2011 June Q7

Edexcel D2 2012 June Q1

Edexcel D2 2012 June Q2

Edexcel D2 2012 June Q3

Edexcel D2 2012 June Q4

Edexcel D2 2012 June Q5

Edexcel D2 2012 June Q6

Edexcel D2 2012 June Q7

Edexcel D2 2012 June Q8

Edexcel D2 2013 June Q1

Edexcel D2 2013 June Q2

Edexcel D2 2013 June Q3

Edexcel D2 2013 June Q4

Edexcel D2 2013 June Q5

	1	2	3	4	5
A	129	127	122	134	135
B	127	125	123	131	132
C	142	131	121	140	139
D	127	127	122	131	136
E	141	134	129	144	143

	A	B	C	D	E	F
A	-	16	25	21	12	15
B	16	-	24	22	21	12
C	25	24	-	18	30	27
D	21	22	18	-	15	12
E	12	21	30	15	-	18
F	15	12	27	12	18	-

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-