Questions - Edexcel D2 - A-Level Maths

Edexcel D2 Q5

5. A travel company offers a touring holiday which stops at four locations, $A , B , C$ and $D$. The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below.

\multirow{2}{*}{}	Stage
	1	2	3	4
A	7	8	5	6
$B$	6	9	6	5
C	9	8	5	7
D	7	7	6	6

Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.
(11 marks)

Edexcel D2 Q6

6. The payoff matrix for player $A$ in a two-person zero-sum game is shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B$
\cline { 2 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{3}{*}{$A$}	I	3	5	- 2
\cline { 2 - 5 }	II	7	- 4	- 1
\cline { 2 - 5 }	III	9	- 4	8

Applying the dominance rule, explain, with justification, which strategy can be ignored by
1. player $A$,
2. player $B$.
For the reduced table, find the optimal strategy for
1. player $A$,
2. player $B$.
Find the value of the game. Turn over

Edexcel D2 Q7

7. This question should be answered on the sheet provided. A tinned food producer delivers goods to six supermarket warehouses, $B , C , D , E , F$ and $G$, from its base, $A$. The distances, in kilometres, between each location are given in the table below. \section*{Please hand this sheet in for marking}

Edexcel D2 Q1

This question should be answered on the sheet provided.

The table below shows the distances in miles between five villages. Jane lives in village $A$ and is about to take her daughter's friends home to villages $B , C , D$ and $E$. She will begin and end her journey at $A$ and wishes to travel the minimum distance possible.

	$A$	$B$	$C$	$D$	$E$
$A$	-	4	7	8	2
$B$	4	-	1	5	6
$C$	7	1	-	2	7
$D$	8	5	2	-	3
$E$	2	6	7	3	-

Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey.
Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles.
(2 marks)

Edexcel D2 Q2

2. The payoff matrix for player $A$ in a two-person zero-sum game with value $V$ is shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B$
\cline { 2 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{3}{*}{$A$}	I	6	- 4	- 1
\cline { 2 - 5 }	II	${ } ^ { - } 2$	5	3
\cline { 2 - 5 }	III	5	1	- 3

Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player $B$.

Rewrite the matrix as necessary and state the new value of the game, $v$, in terms of $V$.
Define your decision variables.
Write down the objective function in terms of your decision variables.
Write down the constraints.

Edexcel D2 Q3

3. This question should be answered on the sheet provided. The table below gives distances, in miles, for a network relating to a travelling salesman problem. Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route.

Edexcel D2 Q5

5. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.

\multirow{2}{*}{}	Stage
	1	2	3
Alex	19	69	168
Darren	22	64	157
Leroy	20	72	166
Suraj	23	66	171

Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.

Edexcel D2 Q6

6. The payoff matrix for player $X$ in a two-person zero-sum game is shown below.

\cline { 3 - 4 } \multicolumn{2}{c\|}{}	$Y$
\cline { 3 - 4 } \multicolumn{2}{c\|}{}	$Y _ { 1 }$	$Y _ { 2 }$
\multirow{2}{*}{$X$}	$X _ { 1 }$	${ } ^ { - } 2$	4
\cline { 2 - 4 }	$X _ { 2 }$	6	${ } ^ { - } 1$

Explain why the game does not have a saddle point.
Find the optimal strategy for
1. player $X$,
2. player $Y$.
Find the value of the game.

Edexcel D2 Q7

7. A transportation problem has costs, in pounds, and supply and demand, in appropriate units, as given in the transportation tableau below. (c) \section*{Please hand this sheet in for marking}

Stage	State	Action
\multirow[t]{3}{*}{1}	I	IL
	J	JL
	K	KL
\multirow[t]{3}{*}{2}	$F$	FI FJ FK
	G	GI GJ GK
	H	HI HJ HK
\multirow[t]{4}{*}{3}	B	$B F B G B H$
	C	CF CH
	D	DF DH
	E	EF $E G E H$
4	A	$A B A C$ AD $A E$

Edexcel D2 Q1

A glazing company runs a promotion for a special type of window. As a result of this the company receives orders for 30 of these windows from business $B _ { 1 } , 18$ from business $B _ { 2 }$ and 22 from business $B _ { 3 }$. The company has stocks of 20 of these windows at factory $F _ { 1 } , 35$ at factory $F _ { 2 }$ and 15 at factory $F _ { 3 }$. The table below shows the profit, in pounds, that the company will make for each window it sells according to which factory supplies each business.

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	$B _ { 1 }$	$B _ { 2 }$	$B _ { 3 }$
$F _ { 1 }$	20	14	17
$F _ { 2 }$	18	19	19
$F _ { 3 }$	15	17	23

The glazing company wishes to supply the windows so that the total profit is a maximum.
Formulate this information as a linear programming problem.

State your decision variables.
Write down the objective function in terms of your decision variables.
Write down the constraints and state what each one represents.

Edexcel D2 Q2

2. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{726bca96-7f98-4ed5-b642-f5007a958c8b-03_492_862_301_502} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
(2 marks)
Use the nearest neighbour algorithm, starting at $A$, and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
Interpret the tour found in part (b) in terms of the original network.

Edexcel D2 Q3

3. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

strip the wallpaper,
paint the woodwork and ceiling,
hang the new wallpaper,
replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job.

	Alice	Bhavin	Carl	Dieter
Strip wallpaper	5	3	5	4
Paint	7	5	6	4
Hang wallpaper	8	4	7	6
Replace fittings	5	3	2	3

As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
(6 marks)
Hence, find the minimum time in which the friends can redecorate the lounge.
(1 mark)

Edexcel D2 Q4

4. This question should be answered on the sheet provided. The owner of a small plane is planning a journey from her local airport, $A$ to the airport nearest her parents, $K$. On the journey she will make three refuelling stops, the first at $B , C$ or $D$, the second at $E , F$ or $G$ and the third at $H , I$ or $J$. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{726bca96-7f98-4ed5-b642-f5007a958c8b-05_727_1303_523_356} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} Figure 2 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. As her plane does not have a large fuel tank, the owner wishes to choose a route that minimises the maximum distance of any one flight. Find the route that she should use and state the maximum distance of any one stage on this route.

Edexcel D2 Q5

5. A car-hire firm has six branches in a region. Three of the branches, $A , B$ and $C$, have spare cars, whereas the other three, $D , E$ and $F$, require cars. The total number of cars required is equal to the number of cars available. The table below shows the cost in pounds of sending one car from each branch with spares to each branch needing more cars and the number of cars available or required by each branch.

\backslashbox{Branches with spare cars}{Branches needing cars}	$D$	$E$	$F$	Available
$A$	6	4	7	7
B	8	5	3	8
C	4	4	2	5
Required	5	9	6

Use the north-west corner method to obtain a possible pattern of moving cars and find its cost. The firm wishes to minimise the cost of redistributing the cars.
Calculate shadow costs for the pattern found in part (a) and improvement indices for each unoccupied cell.
State, with a reason, whether or not the pattern found in part (a) is optimal.

Edexcel D2 Q6

6. This question should be answered on the sheet provided. A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.

	Leeds	Liverpool	Manchester	Newcastle	Nottingham	Oxford	York
Leeds	-	71	40	96	71	165	28
Liverpool	71	-	31	155	92	155	93
Manchester	40	31	-	136	62	141	67
Newcastle	96	155	136	-	156	250	78
Nottingham	71	92	62	156	-	94	78
Oxford	165	155	141	250	94	-	172
York	28	93	67	78	78	172	-

Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
(4 marks)
A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once. Assuming that the network satisfies the triangle inequality,
find an initial upper bound for the length of his journey,
improve this upper bound to find an upper bound of less than 575 miles.
By deleting Leeds, find a lower bound for his journey. Turn over

Edexcel D2 Q7

7. The payoff matrix for player $A$ in a two-person zero-sum game is shown below.

Edexcel D2 Q1

A team of gardeners is called in to attend to the grounds of a stately home. The three gardeners will each be assigned to one of three areas, the lawns, the hedgerows and the flower beds. The table below shows the estimated time, in hours, it will take each gardener to do each job.

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	Lawns	Hedgerows	Flower Beds
Alan	4	4.5	6
Beth	3	4	5
Colin	3.5	5	6

The team wishes to complete the tasks in the least total time.
Formulate this information as a linear programming problem.

State your decision variables.
Write down the objective function in terms of your decision variables.
Write down the constraints and explain what each one represents.

Edexcel D2 Q2

2. This question should be answered on the sheet provided. A pool player is to play in four tournaments. Some of the tournaments take place simultaneously and the player has to choose one of each of the following: $$\begin{array} { l l } 1 ^ { \text {st } } \text { tournament: } & A , B \text { or } C ,
2 ^ { \text {nd } } \text { tournament: } & D , E \text { or } F ,
3 ^ { \text {rd } } \text { tournament: } & G , H \text { or } I ,
4 ^ { \text {th } } \text { tournament: } & J , K \text { or } L \end{array}$$ Each tournament has six rounds and the player estimates how well he will do in each tournament based on which tournament he plays before it. The table below shows his expectations with each number indicating the round he expects to reach and a "7" indicating he expects to win the tournament.

\multirow{2}{*}{}		Expected performance in tournament
		A	B	C	$D$	E	$F$	$G$	$H$	I	J	$K$	$L$
\multirow{10}{*}{Previous tournament}	None	5	3	3
	A				6	3	7
	B				5	5	4
	C				7	5	5
	D							5	3	3
	E							3	5	6
	$F$							3	6	5
	G										2	4	1
	H										3	2	2
	$I$										2	5	3

He wishes to choose the tournaments such that his worst performance is as good as possible. Use dynamic programming to find which tournaments he should play.
(10 marks) Turn over

Edexcel D2 Q3

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below.

	Film	Musical	Ballet	Concert
Andrew	5	20	12	18
Betty	6	18	15	16
Carlos	4	21	9	15
Davina	5	16	11	13

Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
(10 marks)

Edexcel D2 Q4

4. The payoff matrix for player $A$ in a two-person zero-sum game is shown below.

\cline { 3 - 4 } \multicolumn{2}{c\|}{}	$B$
\cline { 3 - 4 }	I	II
\multirow{2}{*}{$A$}	I	4	${ } ^ { - } 8$
\cline { 2 - 4 }	II	2	${ } ^ { - } 4$
\cline { 2 - 4 }	III	${ } ^ { - } 8$	2

Explain why the game does not have a saddle point.
Using a graphical method, find the optimal strategy for player $B$.
Find the optimal strategy for player $A$.
Find the value of the game.

Edexcel D2 Q5

5. A carpet manufacturer has two warehouses, $W _ { 1 }$ and $W _ { 2 }$, which supply carpets for three sales outlets, $S _ { 1 } , S _ { 2 }$ and $S _ { 3 }$. At one point $S _ { 1 }$ requires 40 rolls of carpet, $S _ { 2 }$ requires 23 rolls of carpet and $S _ { 3 }$ requires 37 rolls of carpet. At this point $W _ { 1 }$ has 45 rolls in stock and $W _ { 2 }$ has 40 rolls in stock. The following table shows the cost, in pounds, of transporting one roll from each warehouse to each sales outlet:

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	$S _ { 1 }$	$S _ { 2 }$	$S _ { 3 }$
$W _ { 1 }$	8	7	11
$W _ { 2 }$	9	10	11

The company's manager wishes to supply the 85 rolls that are in stock such that transportation costs are kept to a minimum.

Use the north-west corner rule to obtain an initial solution to the problem.
Calculate improvement indices for the unused routes.
Use the stepping-stone method to obtain an optimal solution. Turn over

Edexcel D2 Q6

6. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{073926c5-03cc-41d4-82bf-315740ead663-6_672_984_322_431} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} A band is going on tour to play gigs in six towns, including their home town, $A$. The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at $A$ and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.

By inspection, draw a complete network showing the shortest distances between the towns.
Use your complete network and the nearest neighbour algorithm, starting at $A$, to find an upper bound for the total distance travelled.
1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
By deleting $A$, find a lower bound for the total distance travelled.
State an interval of as small a width as possible within which $d$, the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}
Stage Previous tournament Current tournament
\multirow[t]{3}{*}{1} G
J
K
L
$H$
J
K
L
I
J
K
L
\multirow[t]{3}{*}{2} D
G
H
I
$E$
G
H
I
$F$
G
H
I
\multirow[t]{3}{*}{3} A
D
E
F
$B$
D
E
F
C
D
E
F
4 None
A
B
C
\section*{Please hand this sheet in for marking}
\includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
\section*{Sheet for answering question 6 (cont.)}
2. $\_\_\_\_$
$\_\_\_\_$

Edexcel D2 Q1

1. \section*{Figure 1}

\includegraphics[max width=\textwidth, alt={}]{4f494f19-5690-4d9f-8c18-db03d41da203-01_435_682_383_374}

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

Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection.
(2) The table can now be taken to represent a complete network.
Use the nearest-neighbour algorithm, starting at $A$, on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at $A$ and visits every village exactly once.
Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
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.

Edexcel D2 Q2

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

		$B$
		I	II	III	IV
\cline { 2 - 6 }	I	- 4	- 5	- 2	4
A	II	- 1	1	- 1	2
	III	0	5	- 2	- 4
	IV	- 1	3	- 1	1

Determine the play-safe strategy for each player.
Verify that there is a stable solution and determine the saddle points.
State the value of the game to $B$. Figure 2 \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{3.} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-02_502_990_319_148}
\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.
Hence obtain the minimax route from $S$ to $T$ and state the maximum amount of fuel used on any part of this route.
(2)
4. Andrew ( $A$ ) and Barbara ( $B$ ) play a zero-sum game. This game is represented by the following payoff matrix for Andrew. $$A \left( \begin{array} { c c c } & B &
3 & 5 & 4
1 & 4 & 2
6 & 3 & 7 \end{array} \right)$$
Explain why this matrix may be reduced to $$\left( \begin{array} { l l } 3 & 5
6 & 3 \end{array} \right) .$$
Hence find the best strategy for each player and the value of the game.
5. An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.
\cline { 2 - 5 } \multicolumn{1}{c|}{} Job 1 Job 2 Job 3 Job 4
Machine 1 14 5 8 7
Machine 2 2 12 6 5
Machine 3 7 8 3 9
Machine 4 2 4 6 10
Use the Hungarian algorithm, reducing rows first, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time.
6. The table below shows the distances, in km , between six towns $A , B , C , D , E$ and $F$.
\cline { 2 - 7 } \multicolumn{1}{c|}{} $A$ $B$ $C$ $D$ $E$ $F$
$A$ - 85 110 175 108 100
$B$ 85 - 38 175 160 93
$C$ 110 38 - 148 156 73
$D$ 175 175 148 - 110 84
$E$ 108 160 156 110 - 92
$F$ 100 93 73 84 92 -
Starting from $A$, use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.
1. Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
2. Use a short cut to reduce the upper bound to a value less than 680 .

Starting by deleting $F$, find a lower bound for the solution of the travelling salesman problem.
7. A steel manufacturer has 3 factories $F _ { 1 } , F _ { 2 }$ and $F _ { 3 }$ which can produce 35,25 and 15 kilotonnes of steel per year, respectively. Three businesses $B _ { 1 } , B _ { 2 }$ and $B _ { 3 }$ have annual requirements of 20,25 and 30 kilotonnes respectively. The table below shows the cost $C _ { i j }$ in appropriate units, of transporting one kilotonne of steel from factory $F _ { i }$ to business $B _ { j }$.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	Business
\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B _ { 1 }$	$B _ { 2 }$	$B _ { 3 }$
\multirow{3}{*}{Factory}	$F _ { 1 }$	10	4	11
\cline { 2 - 5 }	$F _ { 2 }$	12	5	8
\cline { 2 - 5 }	$F _ { 3 }$	9	6	7

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

Write down the transportation pattern obtained by using the North-West corner rule.
Calculate all of the improvement indices $I _ { i j }$, and hence show that this pattern is not optimal.
Use the stepping-stone method to obtain an improved solution.
Show that the transportation pattern obtained in part (c) is optimal and find its cost. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-04_346_922_319_278}
\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]{4f494f19-5690-4d9f-8c18-db03d41da203-04_341_920_900_278}
\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.
9. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.
\cline { 2 - 5 } \multicolumn{1}{c|}{} Processing Blending Packing Profit (£100)
Morning blend 3 1 2 4
Afternoon blend 2 3 4 5
Evening blend 4 2 3 3
The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let $x , y$ and $z$ be the number of tonnes of Morning, Afternoon and Evening blend produced each week.
Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. An initial Simplex tableau for the above situation is
Basic
variable
$x$ $y$ $z$ $r$ $s$ $t$ Value
$r$ 3 2 4 1 0 0 35
$s$ 1 3 2 0 1 0 20
$t$ 2 4 3 0 0 1 24
$P$ - 4 - 5 - 3 0 0 0 0
Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage.
(11) T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.

Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
(2)
10. While solving a maximizing linear programming problem, the following tableau was obtained.

Basic

variable

$x$

$y$

$z$

$r$

$s$

$t$

Value

$r$

0

$1 \frac { 2 } { 3 }$

1

0

$- \frac { 1 } { 6 }$

$\frac { 2 } { 3 }$

$y$

0

1

$3 \frac { 1 } { 3 }$

0

1

$- \frac { 1 } { 3 }$

$\frac { 1 } { 3 }$

$x$

1

0

- 3

0

- 1

$\frac { 1 } { 2 }$

1

$P$

0

1

0

1

11

Explain why this is an optimal tableau.
Write down the optimal solution of this problem, stating the value of every variable.
Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of $P$.
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]{4f494f19-5690-4d9f-8c18-db03d41da203-05_470_766_447_1695}
\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.
  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$.
\cline { 2 - 4 } \multicolumn{1}{c|}{} B plays I $B$ plays II $B$ plays III
$A$ plays I - 3 2 5
$A$ plays II 4 - 1 - 4
Write down the pay off matrix for player $B$.
Formulate the game as a linear programming problem for player $B$, writing the constraints as equalities and stating your variables clearly.
2. (a) Explain the difference between the classical and practical travelling salesman problems.
\includegraphics[max width=\textwidth, alt={}, center]{4f494f19-5690-4d9f-8c18-db03d41da203-06_454_857_737_1736} The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at $A$, visit each restaurant at least once and cover a minimum distance.
Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
Use your answer to part (b) to determine an initial upper bound for the length of the route.
Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.

Edexcel D2 Q4

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

Explain why this matrix may be reduced to $$\left( \begin{array} { l l } 3 & 5
6 & 3 \end{array} \right) .$$
Hence find the best strategy for each player and the value of the game.

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
\(A\)	-	4	7	8	2
\(B\)	4	-	1	5	6
\(C\)	7	1	-	2	7
\(D\)	8	5	2	-	3
\(E\)	2	6	7	3	-

\cline { 3 - 4 } \multicolumn{2}{c\|}{}	\(Y\)
\cline { 3 - 4 } \multicolumn{2}{c\|}{}	\(Y _ { 1 }\)	\(Y _ { 2 }\)
\multirow{2}{*}{\(X\)}	\(X _ { 1 }\)	\({ } ^ { - } 2\)	4
\cline { 2 - 4 }	\(X _ { 2 }\)	6	\({ } ^ { - } 1\)

\backslashbox{Branches with spare cars}{Branches needing cars}	\(D\)	\(E\)	\(F\)	Available
\(A\)	6	4	7	7
B	8	5	3	8
C	4	4	2	5
Required	5	9	6

\multirow{2}{*}{}		Expected performance in tournament
		A	B	C	\(D\)	E	\(F\)	\(G\)	\(H\)	I	J	\(K\)	\(L\)
\multirow{10}{*}{Previous tournament}	None	5	3	3
	A				6	3	7
	B				5	5	4
	C				7	5	5
	D							5	3	3
	E							3	5	6
	\(F\)							3	6	5
	G										2	4	1
	H										3	2	2
	\(I\)										2	5	3

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	\(S _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)
\(W _ { 1 }\)	8	7	11
\(W _ { 2 }\)	9	10	11

Questions — Edexcel D2 (231 questions)

Browse by module

Browse by board

Edexcel D2 Q5

Edexcel D2 Q6

Edexcel D2 Q7

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q3

Edexcel D2 Q5

Edexcel D2 Q6

Edexcel D2 Q7

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q3

Edexcel D2 Q4

Edexcel D2 Q5

Edexcel D2 Q6

Edexcel D2 Q7

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q3

Edexcel D2 Q4

Edexcel D2 Q5

Edexcel D2 Q6

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q4

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	\(B _ { 1 }\)	\(B _ { 2 }\)	\(B _ { 3 }\)
\(F _ { 1 }\)	20	14	17
\(F _ { 2 }\)	18	19	19
\(F _ { 3 }\)	15	17	23

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	Job 1	Job 2	Job 3	Job 4
Machine 1	14	5	8	7
Machine 2	2	12	6	5
Machine 3	7	8	3	9
Machine 4	2	4	6	10

\cline { 2 - 7 } \multicolumn{1}{c\|}{}	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
\(A\)	-	85	110	175	108	100
\(B\)	85	-	38	175	160	93
\(C\)	110	38	-	148	156	73
\(D\)	175	175	148	-	110	84
\(E\)	108	160	156	110	-	92
\(F\)	100	93	73	84	92	-

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	Processing	Blending	Packing	Profit (£100)
Morning blend	3	1	2	4
Afternoon blend	2	3	4	5
Evening blend	4	2	3	3

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	B plays I	\(B\) plays II	\(B\) plays III
\(A\) plays I	- 3	2	5
\(A\) plays II	4	- 1	- 4