Questions D2 - A-Level Maths

Edexcel D2 Q12

12. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-06_405_791_301_221}

\end{figure} 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$, 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.
State the maximum flow along
1. $W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R$,
2. $W W _ { 3 } \quad C \quad R _ { 2 } \quad R$.
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 flowaugmenting route you use, together with its flow.
From your final flow pattern, determine the number of van loads passing through $B$ each day. \section*{D2 2003 (adapted for new spec)}
1. A two person zero-sum game is represented by the following pay-off matrix for player $A$.
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.
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 . 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.
Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
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.
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.
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.
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.
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. 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.
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.
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.
2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. The table shows the least distances, in km, between five hiding places, A, B, C, D and E.
Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.
Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
State the better upper bound from your answers to (b) and (c).
Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
Consider your answers to (d) and (e) and hence state an optimal route. You must ensure that your answers to parts of questions are clearly labelled.
You should show sufficient working to make your methods clear to the Examiner.
Answers without working may not gain full credit.
2. The table 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 each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
Complete Table 1.
Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
State the cost of your improved solution.
2. (a) Explain the difference between the classical and the practical travelling salesperson problem. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.
2. The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A, and five storage bins, B, C, D, E and F. The robot will start at A , visit each bin, and return to A . The total time taken for the robot's route is to be minimised.
Perform one 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$ and state the current values of the slack variables.

Edexcel D2 Q1

1. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-002_675_1052_378_485}

\end{figure} 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. 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 Q3

3. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-004_764_1514_283_141}

\end{figure} 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 rninimax 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 Q8

8. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1404_285_343}

\end{figure} 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. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1402_1170_343}
\end{figure} Figure 5 shows a feasible flow through the same network.
State the value of the feasible flow shown in Fig. 5. 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.
Show the maximal flow on Diagram 2 and state its value.
Prove that your flow is maximal.

Edexcel D2 Q11

11. 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. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-011_723_1172_476_337}

\end{figure}

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.
1. State the maximum flow along $S F _ { 1 } A B R$ and $S F _ { 3 } C R$.
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.
2. Prove that your final flow is maximal.

Edexcel D2 Q12

12. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-012_618_1211_253_253}

\end{figure} 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$, 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.
State the maximum flow along
1. $W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R$,
2. $W W _ { 3 } \quad C \quad R _ { 2 } \quad R$.
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 flowaugmenting route you use, together with its flow.
From your final flow pattern, determine the number of van loads passing through $B$ each day. \section*{Answer Book}
1. (a)
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.
2. (a) Explain the difference between the classical and the practical travelling salesperson problems.
(2) The table below shows the distances, in km, between six data collection points, A, B, C, D, E, and F. \section*{Table 1}
You may not need to use all of these tables 3. Maximum income: $\_\_\_\_$ 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.
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.
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] Table of least distances
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.
2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.
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.
2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. The table shows the least distances, in km, between five hiding places, A, B, C, D and E.
Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.
Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
State the better upper bound from your answers to (b) and (c).
Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
Consider your answers to (d) and (e) and hence state an optimal route.
2. The table 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 each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
Complete Table 1.
Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
State the cost of your improved solution.
2. (a) Explain the difference between the classical and the practical travelling salesperson problem. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{(a)}
P Q R S Supply
A 13
B 4
C 12
D 11
Demand 11 10 11 8
\end{table}
\begin{table}[h] Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.
2. The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A , and five storage bins, $\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F . The robot will start at A , visit each bin, and return to A . The total time taken for the robot's route is to be minimised.
Perform one iteration of the Simplex algorithm to obtain a new tableau, $T$. State the row operations you use.
(5)
Write down the profit equation given by $T$ and state the current values of the slack variables.
2. Rani and Greg play a zero-sum game. The pay-off matrix shows the number of points that Rani scores for each combination of strategies.
You may not need to use all these tableaux
b.v. $x$ $y$ z $r$ $s$ $t$ Value Row Ops

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops

b.v. $x$ $y$ z $r$ $s$ $t$ Value Row Ops

b.v. $X$ $y$ Z $r$ $s$ $t$ Value Row Ops
2.
Greg plays 1 Greg plays 2 Greg plays 3
Rani plays 1 - 3 1 2
Rani plays 2 0 2 1
Rani plays 3 2 4 - 5
3
3.
A B C D E F G
A - x 41 43 38 21 30
B $x$ - 27 38 19 29 51
C 41 27 - 24 37 35 40
D 43 38 24 - 44 52 25
E 38 19 37 44 - 20 28
F 21 29 35 52 20 - 49
G 30 51 40 25 28 49 -

A B C D E F G
A - $x$ 41 43 38 21 30
B $x$ - 27 38 19 29 51
C 41 27 - 24 37 35 40
D 43 38 24 - 44 52 25
E 38 19 37 44 - 20 28
F 21 29 35 52 20 - 49
G 30 51 40 25 28 49 -
4. .
Leave
\includegraphics[max width=\textwidth, alt={}, center]{195b1c1f-5ce3-4762-80c3-34c26382b88b-269_844_1431_1886_463}
5.
P Q R Supply
A 20 5 13 74
B 7 15 8 58
C 9 14 21 63
D 22 16 10 85
Demand 145 57 78

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

P Q R
A
B
C
D

$P$ $Q$ $R$
$A$
$B$
$C$
$D$

$P$ $Q$ $R$
$A$
$B$
$C$
$D$
\section*{6. (a)} You may not need to use all the rows of this table
Stage State Action Dest. Value

Stage State Action Dest. Value
Weight:
Route:
(ii)

Edexcel D2 2017 June Q1

1.

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

The table above shows the least distances, in km , between six towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F .

Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
1. the minimum spanning tree method,
2. the nearest neighbour algorithm.
  (5) By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km . By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.
(2)

Edexcel D2 2017 June Q2

2. The table shows the cost, in pounds, of transporting one unit of stock from each of three supply points, $\mathrm { A } , \mathrm { B }$ and C , to each of 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.

	1	2	3	4	Supply
A	15	17	20	11	33
B	12	11	18	21	21
C	18	13	10	16	25
Demand	21	17	28	13

Use the north-west corner method to obtain an initial solution.
(1)
Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
(2)
Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
Determine whether your current solution is optimal, giving a reason for your answer.

Edexcel D2 2017 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	0	- 2	6
A plays 2	3	4	1
A plays 3	- 1	1	- 3

Identify the play safe strategies for each player.
State, giving a reason, whether there is a stable solution to this game.
Find the best strategy for player A.
Find the value of the game to player B.

Edexcel D2 2017 June Q4

4. Four workers, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D , are to be assigned to four tasks, $1,2,3$ and 4 . Each worker must be assigned to only one task and each task must be done by only one worker. Worker A cannot do task 3 and worker D cannot do task 2
The cost, in pounds, of assigning each worker to each task is shown in the table below.

	1	2	3	4
A	53	84	-	20
B	87	72	41	38
C	70	51	52	25
D	45	-	81	70

The total cost is to be minimised.
Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. You do not need to solve this problem.

Edexcel D2 2017 June Q5

5. The tableau below is the initial tableau for a three-variable 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$	15	- 2	3	1	0	0	180
$s$	10	1	1	0	1	0	80
$t$	1	6	- 2	0	0	1	100
$P$	- 1	- 2	- 5	0	0	0	0

Using the information in the tableau, write down
1. the objective function,
2. the three constraints as inequalities.
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 values of the objective function and each variable.

Edexcel D2 2017 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-07_1155_1541_223_264} \captionsetup{labelformat=empty} \caption{Figure 1}

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

State the value of the initial flow.
State the capacity of cut $C _ { 1 }$
Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along $\mathrm { AC } , \mathrm { SB } , \mathrm { BE } , \mathrm { DE }$ and FG .
(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.
Draw a maximal flow pattern on Diagram 2 in the answer book.
Prove that your flow is maximal.

Edexcel D2 2017 June Q7

7. A clothing manufacturer can export a maximum of five batches of shirts each year. Each exported batch contains just one type of shirt, the types being T-shirts, Rugby shirts and Polo shirts. The table below shows the profit, in £ 1000 s, for the number of each exported batch type.

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

2.

	1	2	3	4	Supply
A	15	17	20	11	33
B	12	11	18	21	21
C	18	13	10	16	25
Demand	21	17	28	13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13
3.
B plays 1 B plays 2 B plays 3
A plays 1 0 - 2 6
A plays 2 3 4 1
A plays 3 - 1 1 - 3
4.
1 2 3 4
A 53 84 - 20
B 87 72 41 38
C 70 51 52 25
D 45 - 81 70
5. (a)
You may not need to use all of these tableaux
b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value
$r$ 15 - 2 3 1 0 0 180
$s$ 10 1 1 0 1 0 80
$t$ 1 6 - 2 0 0 1 100
$P$ - 1 - 2 - 5 0 0 0 0

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$
6. (a) Value of initial flow
Capacity of cut \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-20_1931_1099_507_408} \captionsetup{labelformat=empty} \caption{Diagram 1}
\end{figure} \includegraphics[max width=\textwidth, alt={}, center]{d5798c81-290a-4e4b-aa46-497b62ca899b-21_1874_953_653_589}
7. You may not need to use all the rows of this table
Stage State Action Dest. Value
T-shirt

Stage State Action Dest. Value
Maximum annual profit £ $\_\_\_\_$

Edexcel D2 2018 June Q1

Table 1 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 each of 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 to this transportation problem is required.

\begin{table}[h]

	1	2	3	4	Supply
A	24	32	21	34	27
B	28	31	29	37	41
C	25	41	33	35	31
D	23	32	31	36	14
Demand	33	35	25	20

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

\end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h]

	1	2	3	4
A	27
B	6	35
C		0	25	6
D				14

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

\end{table}

Explain why a zero has been placed in cell C 2 in Table 2. State the other cell in Table 2 in which the zero could have been placed.
State the shadow costs clearly and enter the improvement indices into Table 3 in your answer book. Taking the most negative improvement index to indicate the entering cell,
[0pt]
list the stepping-stone route that should be used to obtain the next solution. You should make clear the cells that are included in your route and state your entering and exiting cells. [You do not need to state the next solution. You do not need to solve this problem.]

Edexcel D2 2018 June Q2

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

Identify the play safe strategies for each player.
State, giving a reason, whether there is a stable solution to this game.
Explain why the game above can be reduced to the following $3 \times 3$ game.
- 3 2 5
- 2 5 4
2 - 3 - 1
Formulate the $3 \times 3$ game as a linear programming problem for player A, defining your variables clearly and writing the constraints as inequalities.

Edexcel D2 2018 June Q3

3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5 . Each worker must be assigned to only one task and each task must be done by only one worker. The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is $\pounds x$, where $x > 38$

	1	2	3	4	5
A	25	31	27	29	35
B	29	33	40	35	37
C	28	29	35	36	37
D	34	35	36	$x$	41
E	36	35	32	31	33

The total cost is to be minimised.

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.
(8)
Find the minimum total cost.
(1) Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now $\pounds 5$ more than the minimum cost found in (b).
Calculate the value of $x$. You must show your working.
(2)

Edexcel D2 2018 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-05_1054_1569_194_248} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 represents a system of pipes through which fluid can flow from the source node, S , to the sink node, T. The labelling procedure has been applied to Figure 1, and the numbers on the arrows, either side of each arc, show the excess capacities and potential backflows. Currently, no fluid is flowing through the system.

Calculate the capacity of the cut that passes through arcs $\mathrm { GT } , \mathrm { EG } , \mathrm { DE } , \mathrm { BE } , \mathrm { FE }$ and FH .
Explain why arc GT can never be full to capacity when fluid is flowing through the system.
Apply the labelling procedure to Diagram 1 in the answer book to show the maximum flow along SBET. State the amount that can flow along this route.
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.
State the maximum flow through the system and find a cut to show that this flow is maximal.
Show the maximum flow on Diagram 2 in the answer book.

Edexcel D2 2018 June Q5

5. The initial tableau for a linear programming problem in $x , y$ and $z$ is shown below. The objective function to be maximised is $P = 4 x + 2 y + k z$, where $k$ is a positive constant.

Basic Variable	$x$	$y$	$z$	r	$s$	$t$	Value
$r$	-2	-6	1	1	0	0	40
$s$	2	3	2	0	1	0	80
$t$	1	2	2	0	0	1	50
$P$	-4	-2	-k	0	0	0	0

Using the information in the tableau, write down the three constraints as inequalities.
By increasing $x$, perform one complete iteration of the simplex algorithm to obtain tableau $T _ { 1 }$ and state the row operations you use.
Given that $T _ { 1 }$ is not optimal, find an inequality for the value of $k$.
Perform a second complete iteration of the simplex algorithm to obtain tableau $T _ { 2 }$ and state the row operations you use.
Given that $T _ { 2 }$ is optimal, find a second inequality for the value of $k$.
State the final value of each variable and give an expression for the final value of $P$ in terms of $k$.
Hence find the range of possible values of $P$.

Edexcel D2 2018 June Q6

6. Jonathan is an author who is planning his next book tour. He will visit four countries over a period of four weeks. He will visit just one country each week. He will leave from his home, S , 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 each week. \begin{table}[h]

	1	2	3	4
A
B
C
D

	1	2	3	4
A
B
C
D

	1	2	3	4
A
B
C
D

2.

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

- 3	2	5
- 2	5	4
2	- 3	- 1

3.

	1	2	3	4	5
A	25	31	27	29	35
B	29	33	40	35	37
C	28	29	35	36	37
D	34	35	36	$x$	41
E	36	35	32	31	33

You may not need to use all of these tables
1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E

1 2 3 4 5
A
B
C
D
E
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-18_1056_1572_1450_185} \captionsetup{labelformat=empty} \caption{Diagram 1}
\end{figure} Maximum flow along SBET: $\_\_\_\_$ \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-19_1043_1572_1505_187} \captionsetup{labelformat=empty} \caption{Diagram 2}
\end{figure} 5.
b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value
$r$ - 2 - 6 1 1 0 0 40
$s$ 2 3 2 0 1 0 80
$t$ 1 2 2 0 0 1 50
$P$ - 4 - 2 $- k$ 0 0 0 0
You may not need to use all of these tableaux
b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$

b.v. $x$ $y$ $z$ $r$ $s$ $t$ Value Row Ops
$P$
6.
Stage State Action Destination Value
0 I IS S $30 - 5 = 25 ^ { * }$

Stage State Action Destination Value

END

Edexcel D2 2019 June Q1

1.

\cline { 2 - 7 } \multicolumn{1}{c\|}{}	A	B	C	D	E	F
A	-	53	47	39	35	40
B	53	-	32	46	41	43
C	47	32	-	51	47	37
D	39	46	51	-	36	49
E	35	41	47	36	-	42
F	40	43	37	49	42	-

The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D , and wishes to minimise the total distance she travels.

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

Edexcel D2 2019 June Q2

2. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of three supply points, $\mathrm { A } , \mathrm { B }$ and C , to each of 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	17	20	23	14	25
B	16	15	19	22	29
C	19	14	11	15	32
Demand	28	17	23	18

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

\end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h]

	1	2	3	4
$A$	25
$B$	3	17	9
$C$			14	18

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

\end{table}

Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
Determine whether your current solution is optimal, giving a reason for your answer.
State the cost of your current solution.

Edexcel D2 2019 June Q3

3. Five friends have rented a house that has five bedrooms. They each require their own bedroom. The table below shows how each friend rated the five bedrooms, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }$ and E , where 0 is low and 10 is high.

	A	B	C	D	E
Frank	5	0	7	3	4
Gill	5	3	8	10	1
Harry	4	3	7	9	0
Imogen	6	3	6	5	4
Jiao	0	2	7	3	2

Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total of all the ratings. You must make your method clear and show the table after each stage.
(Total 8 marks)

Edexcel D2 2019 June Q4

4. Eugene and Stephen play a zero-sum game. The pay-off matrix shows the number of points that Eugene scores for each combination of strategies.

	Stephen plays 1	Stephen plays 2	Stephen plays 3
Eugene plays 1	4	5	0
Eugene plays 2	-2	1	1
Eugene plays 3	-3	-4	3

Find the play-safe strategies for each of Eugene and Stephen, and hence show that this zero-sum game does not have a stable solution.
Suppose that Eugene knows that Stephen will use his play-safe strategy. Explain why Eugene should change from his play-safe strategy. You should state as part of your answer which strategy Eugene should now play.
Formulate the game as a linear programming problem for Stephen. Define your variables clearly. Write the constraints as equations.

Edexcel D2 2019 June Q5

5. A linear programming problem in $x , y$ and $z$ is described as follows. Maximise $P = 2 x + 3 y + z$
subject to $\quad 2 y - 3 z \leqslant 30$ $$\begin{array} { r } - 3 x + y + z \leqslant 60
x + 4 y - z \leqslant 80 \end{array}$$

Complete the initial tableau in the answer book for this linear programming problem.
(3)
Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm to obtain a new tableau, T. Make your method clear by stating the row operations you use.
(5)
Write down the profit equation given by T and state the values of the slack variables given by T . The following tableau is obtained after further iterations.
Basic variable $x$ $y$ $z$ $r$ $s$ $t$ Value
$r$ 0 2 -3 1 0 0 30
$s$ 0 13 -2 0 1 3 300
$x$ 1 4 -1 0 0 1 80
$P$ 0 5 -3 0 0 2 160
Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau.

Edexcel D2 2019 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c66144-9e34-42fc-9f40-a87a49331483-07_719_1313_246_376} \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. Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2 in the answer book.
2. Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values along the new arcs from S to T , and along $\operatorname { arcs } \mathrm { S } _ { 1 } \mathrm {~B}$ and $\mathrm { AT } _ { 1 }$
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.
Draw a maximal flow pattern on Diagram 3 in the answer book.
Prove that your flow is maximal.

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

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

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

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

b.v.	\(X\)	\(y\)	Z	\(r\)	\(s\)	\(t\)	Value	Row Ops

Questions D2 (547 questions)

Browse by module

Browse by board

Edexcel D2 Q12

Edexcel D2 Q1

Edexcel D2 Q3

Edexcel D2 Q8

Edexcel D2 Q11

Edexcel D2 Q12

Edexcel D2 2017 June Q1

Edexcel D2 2017 June Q2

Edexcel D2 2017 June Q3

Edexcel D2 2017 June Q4

Edexcel D2 2017 June Q5

Edexcel D2 2017 June Q6

Edexcel D2 2017 June Q7

Edexcel D2 2018 June Q1

Edexcel D2 2018 June Q2

Edexcel D2 2018 June Q3

Edexcel D2 2018 June Q4

Edexcel D2 2018 June Q5

Edexcel D2 2018 June Q6

Edexcel D2 2019 June Q1

Edexcel D2 2019 June Q2

Edexcel D2 2019 June Q3

Edexcel D2 2019 June Q4

Edexcel D2 2019 June Q5

Edexcel D2 2019 June Q6

	Greg plays 1	Greg plays 2	Greg plays 3
Rani plays 1	- 3	1	2
Rani plays 2	0	2	1
Rani plays 3	2	4	- 5

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

Stage	State	Action	Destination	Value
0	I	IS	S	\(30 - 5 = 25 ^ { * }\)

	\(P\)	\(Q\)	\(R\)
\(A\)
\(B\)
\(C\)
\(D\)

	\(P\)	\(Q\)	\(R\)
\(A\)
\(B\)
\(C\)
\(D\)

	\(P\)	\(Q\)	\(R\)
\(A\)
\(B\)
\(C\)
\(D\)

	\(P\)	\(Q\)	\(R\)
\(A\)
\(B\)
\(C\)
\(D\)

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-