Questions D2 - A-Level Maths

	cutting	stitching	filling	dressing
\(A\)	66	101	85	36
\(B\)	66	98	74	38
\(C\)	63	97	71	34
\(D\)	67	102	78	35

Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the time taken by this team to produce one Teddy Bear. You must make your method clear and show the table after each iteration.
State the minimum time it will take this team to produce one Teddy Bear. Using the allocation found in (a),
calculate the minimum total time this team will take to complete 20 Teddy Bears. You should make your reasoning clear and state your answer in minutes and seconds.
(Total 13 marks)

Edexcel D2 2007 June Q4

4. A group of students and teachers from a performing arts college are attending the Glasenburgh drama festival. All of the group want to see an innovative modern production of the play 'The Decision is Final'. Unfortunately there are not enough seats left for them all to see the same performance. There are three performances of the play, 1,2 , and 3 . There

	Adult	Student
Performance 1	\(\pounds 5.00\)	\(\pounds 4.50\)
Performance 2	\(\pounds 4.20\)	\(\pounds 3.80\)
Performance 3	\(\pounds 4.60\)	\(\pounds 4.00\)

are two types of ticket, Adult and Student. Student tickets will be purchased for the students and Adult tickets for the teachers. The table below shows the price of tickets for each performance of the play. There are 18 teachers and 200 students requiring tickets. There are 94,65 and 80 seats available for performances 1,2 , and 3 espectively.

Complete the table below.
Adult Student Dummy Seats available
Performance 1 £5.00 £4.50
Performance 2 £4.20 £3.80
Performance 3 £4.60 £4.00
Tickets needed
Explain why a dummy column was added to the table above.
Use the north-west corner method to obtain a possible solution.
Taking the most negative improvement index to indicate the entering square, use the stepping stone method once to obtain an improved solution. You must make your shadow costs and improvement indices clear. After a further iteration the table becomes:
Adult Student Dummy
Performance 1 73 21
Performance 2 18 47
Performance 3 80
Demonstrate that this solution gives the minimum cost, and find its value.
(Total 16 marks)

Edexcel D2 2007 June Q5

5. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-3_1026_1609_772_169}

\end{figure} In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.
The arrow on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.

Add a supersource S , a supersink T and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs.
Write down the value of the initial flow shown in Figure 1.
Use Figure 2 below, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow.
Show your flow on the diagram below and state its value.
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-4_967_1520_114_214}
Prove that your flow is maximal.
(2)
(Total 14 marks)

Edexcel D2 2007 June Q6

6. Anna (A) and Roland (R) play a two-person zero-sum game which is represented by the following pay-off matrix for Anna.

	R plays 1	R plays 2	R plays 3
A plays 1	6	- 2	- 3
A plays 2	- 3	1	2
A plays 3	5	4	- 1

Formulate the game as a linear programming problem for player \(\mathbf { R }\). Write the constraints as inequalities. Define your variables clearly.
(Total 8 marks)

Edexcel D2 2007 June Q7

7.
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121} Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A , B , C , D , E , F , G , H , I , J , K\) and \(L\), at which there are air pockets where he can take a breath. The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next. Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.

Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie. Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
Find an optimal route for Agent Goodie avoiding tunnel XA.

Edexcel D2 2007 June Q8

8. 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\)	12	4	5	1	0	0	246
\(s\)	9	6	3	0	1	0	153
\(t\)	5	2	- 2	0	0	1	171
\(P\)	- 2	- 4	- 3	0	0	0	0

Using the information in the tableau, write down

the objective function,
the three constraints as inequalities with integer coefficients. 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.
b.v. x y z r s t Value Row operations

b.v. x y z r s t Value Row operations

b.v. x y z r s t Value Row operations

b.v. x y z r s t Value Row operations
State the final values of the objective function and each variable.
One of the constraints is not at capacity. Explain how it can be identified.

Edexcel D2 2007 June Q9

9. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-7_931_1651_196_118} \captionsetup{labelformat=empty} \caption{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.}

\end{figure}

State the value of the initial flow.
State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\). Figure 2 shows the labelling procedure applied to the above network.
Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
Prove that the flow is now maximal. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure}

Edexcel D2 2008 June Q1

\includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-1_746_1413_262_267}

The diagram above shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.

State the values of \(x\) and \(y\).
List the saturated arcs.
State the value of the feasible flow.
State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
Prove that the new flow is maximal.

Edexcel D2 2008 June Q2

2. Explain what is meant, in a network, by (a) a walk, (b) a tour.
(2) (2) (Total 4 marks)

Edexcel D2 2008 June Q3

3. Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The table below shows the cost, in pounds, of transporting one car from each factory to each showroom. It also shows the number of cars available at each factory and the number required at each showroom.

	London (L)	Edinburgh (E)	Supply
A	80	70	55
B	60	50	45
Demand	35	60

It is decided to use the transportation algorithm to obtain a minimal cost solution.

Explain why it is necessary to add a dummy demand point.
Complete the table below.
L E Dummy Supply
A 80 70 55
B 60 50 45
Demand 35 60 100
Use the north-west corner rule to obtain a possible pattern of distribution.
(1)
Taking the most negative improvement index to indicate the entering square, use the stepping-stone method to obtain an optimal solution. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.
(7)
State the cost of your optimal solution.
(1) (Total 13 marks)

Edexcel D2 2008 June Q4

4. (a) Explain the difference between a maximin route and a minimax route in dynamic programming.
(2)
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376} A maximin route from L to R is to be found through the staged network shown above.
(b) Use dynamic programming to complete a table below and hence find a maximin route.
(10) (Total 12 marks)

Edexcel D2 2008 June Q5

5. (a) In game theory, explain the circumstances under which column \(( x )\) dominates column \(( y )\) in a two-person zero-sum game. Liz and Mark play a zero-sum game. This game is represented by the following pay-off matrix for Liz.

	Mark plays 1	Mark plays 2	Mark plays 3
Liz plays 1	5	3	2
Liz plays 2	4	5	6
Liz plays 3	6	4	3

(b) Verify that there is no stable solution to this game.
(c) Find the best strategy for Liz and the value of the game to her. The game now changes so that when Liz plays 1 and Mark plays 3 the pay-off to Liz changes from 2 to
4. All other pay-offs for this zero-sum game remain the same.
(d) Explain why a graphical approach is no longer possible and briefly describe the method Liz should use to determine her best strategy.
(2) (Total 16 marks)

Edexcel D2 2008 June Q6

6. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, \(A , B , C\) and \(D\). Each salesperson must attend just one fair and each fair must be attended by just one salesperson. The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.

	\(A\)	\(B\)	\(C\)	\(D\)
Joe	48	49	42	42
Min-Seong	53	49	51	50
Olivia	51	53	48	48
Robert	47	50	46	43

Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage.
State all possible optimal allocations and the optimal total value.
(4)(Total 14 marks)

Edexcel D2 2008 June Q7

7.
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
Use your answer to part (a) to determine an initial upper bound for the length of the route.
Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
By deleting C, and all of its arcs, find a lower bound for the length of the route.
Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
(2) (Total 16 marks)

Edexcel D2 2008 June Q8

8. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\).

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

Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. You may not need to use all of these tableaux.
b.v. \(x\) \(y\) \(z\) \(r\) S \(t\) Value Row operations
\(P\)

b.v. \(x\) \(y\) \(z\) \(r\) \(s\) \(t\) Value Row operations
\includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374}
\(P\)

b.v. \(x\) \(y\) \(z\) \(r\) \(s\) \(t\) Value Row operations
\(P\)

b.v. \(x\) \(y\) \(z\) \(r\) \(S\) \(t\) Value Row operations
\(P\)

Edexcel D2 2009 June Q1

A company, Kleenitquick, has developed a new stain remover. To promote sales, three salespersons, Jess, Matt and Rachel, will be assigned to three of four department stores \(1,2,3\) and 4 , to demonstrate the stain remover. Each salesperson can only be assigned to one department store.

The table below shows the cost, in pounds, of assigning each salesperson to each department store.

	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
Jess	15	11	14	12
Matt	13	8	17	13
Rachel	14	9	13	15

Explain why a dummy row needs to be added to the table.
Complete Table 1 in the answer book.
Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.
Find the minimum cost.

Edexcel D2 2009 June Q2

2. (a) Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\), and F .

	A	B	C	D	E	F
A	-	77	34	56	67	21
B	77	-	58	58	36	74
C	34	58	-	73	70	42
D	56	58	73	-	68	38
E	67	36	70	68	-	71
F	21	74	42	38	71	-

Rachel must visit each collection point. She will start and finish at A and wishes to minimise the total distance travelled.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your method clear. Starting at B, a second upper bound of 293 km was found.
(c) State the better upper bound of these two, giving a reason for your answer. By deleting A, a lower bound was found to be 245 km .
(d) By deleting B, find a second lower bound. Make your method clear.
(e) State the better lower bound of these two, giving a reason for your answer.
(f) Taking your answers to (c) and (e), use inequalities to write down an interval that must contain the length of Rachel's optimal route.

Edexcel D2 2009 June Q3

3. 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	- 5	6	- 3
A plays 2	1	- 4	13
A plays 3	- 2	3	- 1

Verify that there is no stable solution to this game.
Reduce the game so that player B has a choice of only two actions.
Write down the reduced pay-off matrix for player B.
Find the best strategy for player B and the value of the game to player B.

Edexcel D2 2009 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{4002eb3f-9d7e-40a1-8fd4-5a271d14c8e7-5_888_1607_248_228} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers in circles represent an initial flow from S to T . Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown in Figure 1.

Find the capacity of each of the two cuts.
(2)
Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
(3)

Edexcel D2 2009 June Q5

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

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

Write down the values of \(\mathrm { x } , \mathrm { y }\) and z as indicated by this tableau.
Write down the profit equation from the tableau.

Edexcel D2 2009 June Q6

6. The table below shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { X } , \mathrm { Y }\) and Z to 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.

	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	Supply
\(\mathbf { X }\)	17	8	7	22
\(\mathbf { Y }\)	16	12	15	17
\(\mathbf { Z }\)	6	10	9	15
Demand	16	15	23

This is a balanced problem. Explain what this means.
Use the north west corner method to obtain a possible solution.
Taking ZA as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear and state your exiting cell.
Perform one more iteration of the stepping-stone method to find a further improved solution. You must make your shadow costs, improvement indices, entering cell, exiting cell and route clear.
State the cost of the solution you found in part (d).

Edexcel D2 2009 June Q7

7. Minty has \(\pounds 250000\) to allocate to three investment schemes. She will allocate the money to these schemes in units of \(\pounds 50000\). The net income generated by each scheme, in \(\pounds 1000\) s, is given in the table below.

	\(\mathbf { \pounds 0 }\)	\(\mathbf { \pounds 5 0 0 0 0 }\)	\(\mathbf { \pounds 1 0 0 0 0 0 }\)	\(\mathbf { \pounds 1 5 0 0 0 0 }\)	\(\mathbf { \pounds 2 0 0 0 0 0 }\)	\(\mathbf { \pounds 2 5 0 0 0 0 }\)
Scheme1	0	60	120	180	240	300
Scheme 2	0	65	125	190	235	280
Scheme 3	0	55	110	170	230	300

Minty wishes to maximise the net income. She decides to use dynamic programming to determine the optimal allocation, and starts the table shown in your answer book.

Complete the table in the answer book to determine the amount Minty should allocate to each scheme in order to maximise the income. State the maximum income and the amount that should be allocated to each scheme.
For this problem give the meaning of the table headings
1. Stage,
2. State,
3. Action.

Edexcel D2 2009 June Q8

8. Laura (L) and Sam (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Laura.

	S plays 1	S plays 2	S plays 3
L plays 1	- 2	8	- 1
L plays 2	7	4	- 3
L plays 3	1	- 5	4

Formulate the game as a linear programming problem for Laura, writing the constraints as inequalities. Define your variables clearly.

Edexcel D2 2010 June Q1

The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

	A	B	C	D	E	F
A	-	36	18	28	24	22
B	36	-	54	22	20	27
C	18	54	-	42	27	24
D	28	22	42	-	20	30
E	24	20	27	20	-	13
F	22	27	24	30	13	-

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
(2)
Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
(1)
Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
State the best upper bound from your answers to (b) and (c).
Starting by deleting A , and all of its arcs, find a lower bound for the route length.

Edexcel D2 2010 June Q2

2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker. Jess cannot be assigned to task 4.
The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.

	1	2	3	4
Harry	18	24	22	17
Jess	20	25	19	-
Louis	25	24	27	22
Saul	19	26	23	14

Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total amount earned by the team. You must make your method clear and show the table after each stage.
State who should be assigned to each task and the total amount earned by the team.

	Adult	Student	Dummy	Seats available
Performance 1	£5.00	£4.50
Performance 2	£4.20	£3.80
Performance 3	£4.60	£4.00
Tickets needed

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

\includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374}


\(P\)

	A	B	C	D	E	F
A	-	77	34	56	67	21
B	77	-	58	58	36	74
C	34	58	-	73	70	42
D	56	58	73	-	68	38
E	67	36	70	68	-	71
F	21	74	42	38	71	-

	A	B	C	D	E	F
A	-	36	18	28	24	22
B	36	-	54	22	20	27
C	18	54	-	42	27	24
D	28	22	42	-	20	30
E	24	20	27	20	-	13
F	22	27	24	30	13	-

	A	B	C	D	E	F
A	-	77	34	56	67	21
B	77	-	58	58	36	74
C	34	58	-	73	70	42
D	56	58	73	-	68	38
E	67	36	70	68	-	71
F	21	74	42	38	71	-

	A	B	C	D	E	F
A	-	36	18	28	24	22
B	36	-	54	22	20	27
C	18	54	-	42	27	24
D	28	22	42	-	20	30
E	24	20	27	20	-	13
F	22	27	24	30	13	-

Questions D2 (547 questions)

Browse by module

Browse by board

Edexcel D2 2007 June Q3

Edexcel D2 2007 June Q4

Edexcel D2 2007 June Q5

Edexcel D2 2007 June Q6

Edexcel D2 2007 June Q7

Edexcel D2 2007 June Q8

Edexcel D2 2007 June Q9

Edexcel D2 2008 June Q1

Edexcel D2 2008 June Q2

Edexcel D2 2008 June Q3

Edexcel D2 2008 June Q4

Edexcel D2 2008 June Q5

Edexcel D2 2008 June Q6

Edexcel D2 2008 June Q7

Edexcel D2 2008 June Q8

Edexcel D2 2009 June Q1

Edexcel D2 2009 June Q2

Edexcel D2 2009 June Q3

Edexcel D2 2009 June Q4

Edexcel D2 2009 June Q5

Edexcel D2 2009 June Q6

Edexcel D2 2009 June Q7

Edexcel D2 2009 June Q8

Edexcel D2 2010 June Q1

Edexcel D2 2010 June Q2

	A	B	C	D	E	F
A	-	77	34	56	67	21
B	77	-	58	58	36	74
C	34	58	-	73	70	42
D	56	58	73	-	68	38
E	67	36	70	68	-	71
F	21	74	42	38	71	-

	A	B	C	D	E	F
A	-	36	18	28	24	22
B	36	-	54	22	20	27
C	18	54	-	42	27	24
D	28	22	42	-	20	30
E	24	20	27	20	-	13
F	22	27	24	30	13	-