Questions D2 - A-Level Maths

Find the maximum flow along each of the routes $A B E H , A C F H$ and $A D G H$ and enter their values in the table on Figure 4 opposite.
1. Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
2. State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Figure 4}
Route Flow
$A B E H$
$A C F H$
$A D G H$
\end{table} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
\end{figure}
\includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}

AQA D2 2010 June Q1

1 Figure 1 below shows an activity diagram for a construction project. The time needed for each activity is given in days.

Find the earliest start time and latest finish time for each activity and insert their values on Figure 1.
Find the critical paths and state the minimum time for completion of the project.
On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as early as possible.
A delay in supplies means that Activity $I$ takes 9 days instead of 2 .
1. Determine the effect on the earliest possible starting times for activities $K$ and $L$.
2. State the number of days by which the completion of the project is now delayed.
  (1 mark) \section*{Figure 1}
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-02_815_1337_1573_395}
Critical paths are $\_\_\_\_$
Minimum completion time is $\_\_\_\_$ days. QUESTION PART REFERENCE
\begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-03_978_1207_354_461}
\end{figure}

AQA D2 2010 June Q2

2 Five students attempted five different games, and penalty points were given for any mistakes that they made. The table shows the penalty points incurred by the students.

	Game 1	Game 2	Game 3	Game 4	Game 5
Ali	5	7	3	8	8
Beth	8	6	4	8	7
Cat	6	1	2	10	3
Di	4	4	3	10	7
Ell	4	6	4	7	9

Using the Hungarian algorithm, each of the five students is to be allocated to a different game so that the total number of penalty points is minimised.

By reducing the rows first and then the columns, show that the new table of values is
2 4 0 2 3
4 2 0 1 1
5 0 1 $k$ 0
1 1 0 4 2
0 2 0 0 3
and state the value of the constant $k$.
Show that the zeros in the table in part (a) can be covered with three lines, and use augmentation to produce a table where five lines are required to cover the zeros.
Hence find the possible ways of allocating the five students to the five games with the minimum total of penalty points.
Find the minimum possible total of penalty points.
\includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-05_2484_1709_223_153}

AQA D2 2010 June Q3

Given that $k$ is a constant, display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 6 x + 5 y + 3 z
\text { subject to } & x + 2 y + k z \leqslant 8
& 2 x + 10 y + z \leqslant 17
& x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
1. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the $x$-column as pivot.
2. Given that the maximum value of $P$ has not been achieved after this first iteration, find the range of possible values of $k$.
In the case where $k = - 1$, perform one further iteration and interpret your final tableau.

\includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-07_2484_1707_223_155}

AQA D2 2010 June Q4

4 Two people, Roger and Corrie, play a zero-sum game.
The game is represented by the following pay-off matrix for Roger.

	Corrie
\cline { 2 - 5 }	Strategy	$\mathbf { C } _ { \mathbf { 1 } }$	$\mathbf { C } _ { \mathbf { 2 } }$	$\mathbf { C } _ { \mathbf { 3 } }$
\cline { 2 - 5 } Roger	$\mathbf { R } _ { \mathbf { 1 } }$	7	3	- 5
\cline { 2 - 5 }	$\mathbf { R } _ { \mathbf { 2 } }$	- 2	- 1	4
\cline { 2 - 5 }
\cline { 2 - 5 }

1. Find the optimal mixed strategy for Roger.
2. Show that the value of the game is $\frac { 7 } { 13 }$.
Given that the value of the game is $\frac { 7 } { 13 }$, find the optimal mixed strategy for Corrie.
\includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-09_2484_1709_223_153}

AQA D2 2010 June Q5

5 A three-day journey is to be made from $P$ to $V$, with overnight stops at the end of the first day at one of the locations $Q$ or $R$, and at the end of the second day at $S , T$ or $U$. The network shows the journey times, in hours, for each day of the journey.
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-10_737_1280_447_388} The optimal route, known as the minimax route, is that in which the longest day's journey is as small as possible.

Explain why the route $P Q S V$ is better than the route $P Q T V$.
By completing the table opposite, or otherwise, use dynamic programming, working backwards from $\boldsymbol { V }$, to find the optimal (minimax) route from $P$ to $V$. You should indicate the calculations as well as the values at stages 2 and 3.
(8 marks)
$\ldots . . .$. \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-11_1000_114_1710_159}

AQA D2 2010 June Q6

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute.
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}

Find the value of the cut $Q$.
Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from $S$ to $T$. Indicate, on Figure 3, the flows along the edges $B T , D E$ and $E T$.
1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4 opposite.
2. Use flow augmentation on Figure 4 to find the maximum flow from $S$ to $T$. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
3. Illustrate the maximum flow on Figure 5 opposite.
Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
\end{figure} Figure 4 \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
\end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153}
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}

AQA D2 2011 June Q1

1 Figure 1 below shows an activity diagram for a cleaning project. The duration of each activity is given in days.

Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
Find the critical paths and state the minimum time for completion of the project.
Find the activity with the greatest float time and state the value of its float time.
On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as late as possible.
\begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-02_846_1488_1391_292}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1295_1714_219_150} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{(d)} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1023_1584_1589_278}
\end{figure}

AQA D2 2011 June Q2

2 The times taken, in minutes, for five people, $A , B , C , D$ and $E$, to complete each of five different puzzles are recorded in the table below.

	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$	$\boldsymbol { E }$
Puzzle 1	16	13	15	16	15
Puzzle 2	14	16	16	14	18
Puzzle 3	14	12	18	13	16
Puzzle 4	15	15	17	12	14
Puzzle 5	13	17	16	14	15

Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.

By reducing the columns first and then the rows, show that the new table of values is
3 1 0 4 1
0 $k$ 0 1 3
1 0 3 1 2
2 3 2 0 0
0 5 1 2 1
State the value of the constant $k$.
1. Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
2. Use augmentation to produce a table where five lines are required to cover the zeros.
Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
Find the minimum total time for completing the five puzzles.
Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.

AQA D2 2011 June Q3

Two people, Tom and Jerry, play a zero-sum game. The game is represented by the following pay-off matrix for Tom.
Jerry
\cline { 2 - 5 } Strategy A B C
Tom I - 4 5 - 3
\cline { 2 - 5 } II - 3 - 2 8
\cline { 2 - 5 } III - 7 6 - 2
Show that this game has a stable solution and state the play-safe strategy for each player.

Rohan and Carla play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Rohan. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Carla} Rohan

Strategy	$\mathbf { C } _ { \mathbf { 1 } }$	$\mathbf { C } _ { \mathbf { 2 } }$	$\mathbf { C } _ { \mathbf { 3 } }$
$\mathbf { R } _ { \mathbf { 1 } }$	3	5	- 1
$\mathbf { R } _ { \mathbf { 2 } }$	1	- 2	4

\end{table}

Find the optimal mixed strategy for Rohan and show that the value of the game is $\frac { 3 } { 2 }$.
Carla plays strategy $\mathrm { C } _ { 1 }$ with probability $p$, and strategy $\mathrm { C } _ { 2 }$ with probability $q$. Find the values of $p$ and $q$ and hence find the optimal mixed strategy for Carla.
(4 marks)

\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-10_2486_1714_221_153}

\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-11_2486_1714_221_153}

AQA D2 2011 June Q4

4 A linear programming problem involving variables $x , y$ and $z$ is to be solved. The objective function to be maximised is $P = 2 x + 6 y + k z$, where $k$ is a constant. The initial Simplex tableau is given below.

$\boldsymbol { P }$	$x$	$y$	$\boldsymbol { Z }$	$\boldsymbol { s }$	$\boldsymbol { t }$	$\boldsymbol { u }$	value
1	-2	-6	$- k$	0	0	0	0
0	5	3	10	1	0	0	15
0	7	6	4	0	1	0	28
0	4	3	6	0	0	1	12

In addition to $x \geqslant 0 , y \geqslant 0 , z \geqslant 0$, write down three inequalities involving $x , y$ and $z$ for this problem.
1. By choosing the first pivot from the $\boldsymbol { y }$-column, perform one iteration of the Simplex method.
2. Given that the optimal value has not been reached, find the possible values of $k$.
In the case when $k = 20$ :
1. perform one further iteration;
2. interpret the final tableau and state the values of the slack variables.

AQA D2 2011 June Q5

5 The network shows the evacuation routes along corridors in a college, from two teaching areas to the exit, in case of a fire alarm sounding.
\includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-14_729_1013_434_497} The two teaching areas are at $A$ and $G$ and the exit is at $X$. The number on each edge represents the maximum number of people that can travel along a particular corridor in one minute.

Find the value of the cut shown on the diagram.
Find the maximum flow along each of the routes $A B D X , G F B X$ and $G H E X$ and enter their values in the table on Figure 3 opposite.
1. Taking your answers to part (b) as the initial flow, use the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
2. State the value of the maximum flow, and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
During one particular fire drill, there is an obstruction allowing no more than 45 people per minute to pass through vertex $B$. State the maximum number of people that can move through the network per minute during this fire drill. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_905_1559_331_292}
\end{figure} Figure 4
\includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_689_851_1370_598} Maximum flow is $\_\_\_\_$ people per minute.

AQA D2 2011 June Q6

6 Bob is planning to build four garden sheds, $A , B , C$ and $D$, at the rate of one per day. The order in which they are built is a matter of choice, but the costs will vary because some of the materials left over from making one shed can be used for the next one. The expected profits, in pounds, are given in the table below.

\multirow{2}{*}{Day}	\multirow{2}{*}{Already built}	Expected profit (£)
		$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$
Monday	-	50	65	70	80
\multirow{4}{*}{Tuesday}	A	-	72	83	84
	B	60	-	80	83
	C	57	68	-	85
	D	62	70	81	-
\multirow{6}{*}{Wednesday}	$\boldsymbol { A }$ and $\boldsymbol { B }$	-	-	84	88
	$\boldsymbol { A }$ and $\boldsymbol { C }$	-	71	-	82
	$A$ and $D$	-	74	83	-
	$\boldsymbol { B }$ and $\boldsymbol { C }$	65	-	-	86
	$\boldsymbol { B }$ and $\boldsymbol { D }$	69	-	85	-
	$\boldsymbol { C }$ and $\boldsymbol { D }$	66	73	-	-
\multirow{4}{*}{Thursday}	$\boldsymbol { A } , \boldsymbol { B }$ and $\boldsymbol { C }$	-	-	-	90
	$\boldsymbol { A } , \boldsymbol { B }$ and $\boldsymbol { D }$	-	-	87	-
	$A , C$ and $D$	-	76	-	-
	$\boldsymbol { B } , \boldsymbol { C }$ and $\boldsymbol { D }$	70	-	-	-

By completing the table of values opposite, or otherwise, use dynamic programming, working backwards from Thursday, to find the building schedule that maximises the total expected profit.

Stage (Day)	State (Sheds already built)	Action (Shed to build)	Calculation	Profit in pounds
Thursday	$A , B , C$	D		90
	$A , B , D$	C		87
	A, C, D	B		76
	B, C, D	A		70

Wednesday	A, B	C	$84 + 90$	174
		D	$88 + 87$	175
	A, $C$	B	$71 + 90$	161
		D	$82 + 76$	158
	A, $D$	B
		C
	$B , C$	A
		D
	$B , D$	A
		C
	$C , D$	A
		B

Tuesday	A	B	$72 + 175$	247
		C	$83 + 161$	244
		D










Monday

\section*{Schedule}

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	Monday	Tuesday	Wednesday	Thursday
Shed to build

Turn over

\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-18_2486_1714_221_153}

AQA D2 2013 June Q1

1 Figure 1 opposite shows an activity diagram for a project. The duration required for each activity is given in hours. The project is to be completed in the minimum time.

Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
Find the critical path.
Find the float time of activity $E$.
Given that activities $H$ and $K$ will both overrun by 10 hours, find the new minimum completion time for the project.
\includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-02_1515_1709_1192_153}
\begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-03_1656_869_627_611}
\end{figure}

AQA D2 2013 June Q2

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

Write down the capacity of edge $E F$.
State the source vertex.
State the sink vertex.
Find the values of $x , y$ and $z$.
Find the value of the initial flow.
Find the value of a cut through the edges $E B , E C , E D , E F$ and $E G$.

AQA D2 2013 June Q3

3 The table shows the times taken, in minutes, by five people, $A , B , C , D$ and $E$, to carry out the tasks $V , W , X , Y$ and $Z$.

	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$	$\boldsymbol { E }$
Task $\boldsymbol { V }$	100	110	112	102	95
Task $\boldsymbol { W }$	125	130	110	120	115
Task $\boldsymbol { X }$	105	110	101	108	120
Task $\boldsymbol { Y }$	115	115	120	135	110
Task $\boldsymbol { Z }$	100	98	99	100	102

Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.

By reducing the columns first, and then the rows, show that the new table of values is
0 12 13 2 0
14 21 0 $k$ 9
3 10 0 6 23
0 2 6 20 0
0 0 0 0 7
and state the value of the constant $k$.
Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
Find the minimum total time.

AQA D2 2013 June Q4

4 A haulage company, based in town $A$, is to deliver a tall statue to town $K$. The statue is being delivered on the back of a lorry. The network below shows a system of roads. The number on each edge represents the height, in feet, of the lowest bridge on that road. The company wants to ensure that the height of the lowest bridge along the route from $A$ to $K$ is maximised.
\includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-10_869_1593_715_221} Working backwards from $\boldsymbol { K }$, use dynamic programming to find the optimal route when driving from $A$ to $K$. You must complete the table opposite as your solution.

Stage	State	From	Value
1	H	$K$
	I	$K$
	J	K
2

Optimal route is

AQA D2 2013 June Q5

5 Romeo and Juliet play a zero-sum game. The game is represented by the following pay-off matrix for Romeo.

	Juliet
\cline { 2 - 5 }	Strategy	D	E	F
A	4	- 4	0
\cline { 2 - 5 } Romeo	B	- 2	- 5	3
\cline { 2 - 5 }	C	2	1	- 2
\cline { 2 - 5 }
\cline { 2 - 5 }

Find the play-safe strategy for each player.
Show that there is no stable solution.
Explain why Juliet should never play strategy D.
1. Explain why the following is a suitable pay-off matrix for Juliet.
  4 5 - 1
  0 - 3 2
2. Hence find the optimal strategy for Juliet.
3. Find the value of the game for Juliet.

AQA D2 2013 June Q6

Display the following linear programming problem in a Simplex tableau.
Maximise $\quad P = 4 x + 3 y + z$
subject to $$\begin{aligned} & 2 x + y + z \leqslant 25
& x + 2 y + z \leqslant 40
& x + y + 2 z \leqslant 30 \end{aligned}$$ and $x \geqslant 0 , \quad y \geqslant 0 , \quad z \geqslant 0$.
The first pivot to be chosen is from the $x$-column. Perform one iteration of the Simplex method.
1. Perform one further iteration.
2. Interpret your final tableau and state the values of your slack variables.

AQA D2 2013 June Q7

7 Figure 2 shows a network of pipes. Water from two reservoirs, $R _ { 1 }$ and $R _ { 2 }$, is used to supply three towns, $T _ { 1 } , T _ { 2 }$ and $T _ { 3 }$.
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.

Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
1. Use the initial flow and the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
2. State the value of the maximum flow and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
\end{figure}
\includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}

\includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}

Edexcel D2 2006 January Q1

A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.

	Hot dogs and beef burgers (H)	Ice cream (I)	Popcorn, candyfloss and drinks (P)	Snacks and hot drinks (S)
Site A	267	272	276	261
Site B	264	271	278	263
Site C	267	273	275	263
Site D	261	269	274	257

Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.
(Total 13 marks)

Edexcel D2 2006 January Q2

2. An engineering firm makes motors. They can make up to five in any one month, but if they make more than four they have to hire additional premises at a cost of $\pounds 500$ per month. They can store up to two motors for $\pounds 100$ per motor per month. The overhead costs are $\pounds 200$ in any month in which work is done.
Motors are delivered to buyers at the end of each month. There are no motors in stock at the beginning of May and there should be none in stock after the September delivery. The order book for motors is:

Month	May	June	July	August	September
Number of motors	3	3	7	5	4

Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided below.

Stage (month)	State (Number in store at start of month)	Action (Number made in month)	Destinatio n (Number in store at end of month)	Value (cost)

\section*{Production schedule}

Total cost: $\_\_\_\_$

Edexcel D2 2006 January Q3

3. Three depots, F, G and H, supply petrol to three service stations, S, T and U. The table gives the cost, in pounds, of transporting 1000 litres of petrol from each depot to each service station. F, G and H have stocks of 540000,789000 and 673000 litres respectively.
S, T and U require 257000,348000 and 412000 litres respectively. The total cost of transporting the petrol is to be minimised.

	S	T	U
F	23	31	46
G	35	38	51
H	41	50	63

Formulate this problem as a linear programming problem. Make clear your decision variables, objective function and constraints.

Edexcel D2 2006 January Q4

4. The following minimising transportation problem is to be solved.

	J	K	Supply
A	12	15	9
B	8	17	13
C	4	9	12
Demand	9	11

Complete the table below.
J K L Supply
A 12 15 9
B 8 17 13
C 4 9 12
Demand 9 11 34
Explain why an extra demand column was added to the table above. A possible north-west corner solution is:
J K L
A 9 0
B 11 2
C 12
Explain why it was necessary to place a zero in the first row of the second column. After three iterations of the stepping-stone method the table becomes:
J K L
A 8 1
B 13
C 9 3
Taking the most negative improvement index as the entering square for the stepping stone method, solve the transportation problem. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.

Edexcel D2 2006 January Q5

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

Verify that there is no stable solution to this game.
Explain why the $4 \times 4$ game above may be reduced to the following $3 \times 3$ game.
Formulate the $3 \times 3$ game as a linear programming problem for player A. Write the
- 2 1 3
- 1 3 2
1 - 2 - 1
constraints as inequalities. Define your variables clearly.

Route	Flow
\(A B E H\)
\(A C F H\)
\(A D G H\)

Strategy	\(\mathbf { C } _ { \mathbf { 1 } }\)	\(\mathbf { C } _ { \mathbf { 2 } }\)	\(\mathbf { C } _ { \mathbf { 3 } }\)
\(\mathbf { R } _ { \mathbf { 1 } }\)	3	5	- 1
\(\mathbf { R } _ { \mathbf { 2 } }\)	1	- 2	4

\(\boldsymbol { P }\)	\(x\)	\(y\)	\(\boldsymbol { Z }\)	\(\boldsymbol { s }\)	\(\boldsymbol { t }\)	\(\boldsymbol { u }\)	value
1	-2	-6	\(- k\)	0	0	0	0
0	5	3	10	1	0	0	15
0	7	6	4	0	1	0	28
0	4	3	6	0	0	1	12

	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { E }\)
Puzzle 1	16	13	15	16	15
Puzzle 2	14	16	16	14	18
Puzzle 3	14	12	18	13	16
Puzzle 4	15	15	17	12	14
Puzzle 5	13	17	16	14	15

	Jerry
\cline { 2 - 5 }	Strategy	A	B	C
Tom	I	- 4	5	- 3
\cline { 2 - 5 }	II	- 3	- 2	8
\cline { 2 - 5 }	III	- 7	6	- 2

2	4	0	2	3
4	2	0	1	1
5	0	1	\(k\)	0
1	1	0	4	2
0	2	0	0	3

3	1	0	4	1
0	\(k\)	0	1	3
1	0	3	1	2
2	3	2	0	0
0	5	1	2	1

0	12	13	2	0
14	21	0	\(k\)	9
3	10	0	6	23
0	2	6	20	0
0	0	0	0	7

Questions D2 (547 questions)

Browse by module

Browse by board

AQA D2 2013 January Q8

AQA D2 2010 June Q1

AQA D2 2010 June Q2

AQA D2 2010 June Q3

AQA D2 2010 June Q4

AQA D2 2010 June Q5

AQA D2 2010 June Q6

AQA D2 2011 June Q1

AQA D2 2011 June Q2

AQA D2 2011 June Q3

AQA D2 2011 June Q4

AQA D2 2011 June Q5

AQA D2 2011 June Q6

AQA D2 2013 June Q1

AQA D2 2013 June Q2

AQA D2 2013 June Q3

AQA D2 2013 June Q4

AQA D2 2013 June Q5

AQA D2 2013 June Q6

AQA D2 2013 June Q7

Edexcel D2 2006 January Q1

Edexcel D2 2006 January Q2

Edexcel D2 2006 January Q3

Edexcel D2 2006 January Q4

Edexcel D2 2006 January Q5