Questions - AQA 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}

AQA D2 Q4

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-005_547_1214_555_404}

Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from $S$ to $T$. Indicate, on Figure 3, the flows along the edges $M N , P Q , N P$ and $N T$.
1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from $S$ to $T$.
2. State the value of the maximum flow and illustrate this flow on Figure 5.
Find a cut with capacity equal to that of the maximum flow.

AQA D2 Q7

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from $A$ to $I$.
\includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-144_867_1644_552_191}

Working backwards from $\boldsymbol { I }$, use dynamic programming to find the maximum number of bags that can be collected when driving from $A$ to $I$. You must complete the table opposite as your solution.
State the route that the collector should take in order to collect the maximum number of bags.
Stage State From Value
1 G I
H I
2

AQA D2 Q8

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge.
\includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-146_743_977_404_536}

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]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_746_972_397_845}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_739_971_1311_539}
\end{figure}

AQA D2 2006 January Q1

1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below.

	Ali	Bo	Chas	Dee	Eve
Team 1	16	19	18	25	24
Team 2	22	21	20	26	25
Team 3	21	22	23	21	24
Team 4	20	21	21	23	20

Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.

Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.

AQA D2 2006 January Q2

2 A manufacturing company is planning to build three new machines, $A , B$ and $C$, at the rate of one per month. The order in which they are built is a matter of choice, but the profits will vary according to the number of workers available and the suppliers' costs. The expected profits in thousands of pounds are given in the table.

\multirow[b]{2}{*}{Month}	\multirow[b]{2}{*}{Already built}	Profit (in units of £1000)
		$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$
1	-	52	47	48
\multirow[t]{3}{*}{2}	A	-	58	54
	B	70	-	54
	$\boldsymbol { C }$	68	63	-
\multirow[t]{3}{*}{3}	$\boldsymbol { A }$ and $\boldsymbol { B }$	-	-	64
	$\boldsymbol { A }$ and $\boldsymbol { C }$	-	67	-
	$\boldsymbol { B }$ and $\boldsymbol { C }$	69	-	-

Draw a labelled network such that the most profitable order of manufacture corresponds to the longest path within that network.
Use dynamic programming to determine the order of manufacture that maximises the total profit, and state this maximum profit.

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

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

	\(\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 — AQA D2 (121 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

AQA D2 Q4

AQA D2 Q7

AQA D2 Q8

AQA D2 2006 January Q1

AQA D2 2006 January Q2