Questions - Edexcel D2 - A-Level Maths

	\(B\) plays 1	\(B\) plays 2	\(B\) plays 3
\(A\) plays 1	5	7	2
\(A\) plays 2	3	8	4
\(A\) plays 3	6	4	9

Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables.
Explain why it is necessary to use the simplex algorithm to solve this game theory problem.
Write down an initial simplex tableau making your variables clear.
Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use.
(8)
(Total 16 marks)

Edexcel D2 2006 June Q8

8. The tableau below is the initial tableau for a maximising linear programming problem.

Basic variable	\(x\)	\(y\)	\(z\)	r	\(s\)	\(t\)	Value
\(r\)	7	10	10	1	0	0	3600
\(s\)	6	9	12	0	1	0	3600
\(t\)	2	3	4	0	0	1	2400
\(P\)	-35	-55	-60	0	0	0	0

Write down the four equations represented in the initial tableau above.
(4)
Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use.
State the values of the objective function and each variable.
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

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

Edexcel D2 2006 June Q9

\includegraphics[max width=\textwidth, alt={}]{83ddfbb1-d035-4fae-b39d-a643c877cfed-6_945_1484_255_285}

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

Write down the capacity of each of the two cuts and the value of the initial flow.
(3)
Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs \(A C , C D , D E\) and \(D T\).
\includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-7_2372_1131_121_475}
Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow.
Show your maximal flow pattern on the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-8_757_1472_210_294}
Prove that your flow is maximal.
(Total 14 marks)

Edexcel D2 2007 June Q1

The network above shows the distances, in miles, between seven gift shops, \(A , B\), \(C , D , E , F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances below.
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}
A \(B\) C \(D\) \(E\) \(F\) \(G\)
A - 15 36 53 23
B - 17 38 49 80 49
C 15 17 - 21 62 32
D 36 38 21 - 11 42
E 49 11 - 31 61
\(F\) 53 80 62 42 31 - 30
\(G\) 23 49 32 61 30 -
(4)
\(A\) \(B\) \(C\) \(D\) \(E\) \(F\) \(G\)
\(A\) - 15 36 53 23
\(B\) - 17 38 49 80 49
\(C\) 15 17 - 21 62 32
\(D\) 36 38 21 - 11 42
\(E\) 49 11 - 31 61
\(F\) 53 80 62 42 31 - 30
\(G\) 23 49 32 61 30 -
Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.
(3)
By deleting A, and all of its arcs, find a lower bound for the route length.
(4) (Total 11 marks)

Edexcel D2 2007 June Q2

2. Denis (D) and Hilary (H) play a two-person zero-sum game represented by the following pay-off matrix for Denis.

	H plays 1	H plays 2	H plays 3
D plays 1	2	- 1	3
D plays 2	- 3	4	- 4

Show that there is no stable solution to this game.
Find the best strategy for Denis and the value of the game to him.
(10) (Total 13 marks)

Edexcel D2 2007 June Q3

3. To raise money for charity it is decided to hold a Teddy Bear making competition. Teams of four compete against each other to make 20 Teddy Bears as quickly as possible. There are four stages: first cutting, then stitching, then filling and finally dressing.
Each team member can only work on one stage during the competition. As soon as a stage is completed on each Teddy Bear the work is passed immediately to the next team member. The table shows the time, in seconds, taken to complete each stage of the work on one Teddy Bear by the members \(A , B , C\) and \(D\) of one of the teams.

	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.

	A	\(B\)	C	\(D\)	\(E\)	\(F\)	\(G\)
A	-		15	36		53	23
B		-	17	38	49	80	49
C	15	17	-	21		62	32
D	36	38	21	-	11	42
E		49		11	-	31	61
\(F\)	53	80	62	42	31	-	30
\(G\)	23	49	32		61	30	-

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

Questions — Edexcel D2 (231 questions)

Browse by module

Browse by board

Edexcel D2 2006 June Q7

Edexcel D2 2006 June Q8

Edexcel D2 2006 June Q9

Edexcel D2 2007 June Q1

Edexcel D2 2007 June Q2

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

	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	-