Question 4 - A-Level Maths

AQA D2 — Question 4

Exam Board	AQA
Module	D2 (Decision Mathematics 2)
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Lower and upper capacity networks
Difficulty	Standard +0.3 This is a standard network flows question with lower/upper capacities requiring routine application of flow augmentation algorithm. While it involves multiple steps (completing a feasible flow, flow augmentation, finding max flow and minimum cut), these are all textbook procedures in D2 with no novel problem-solving required. The presence of lower capacities adds minor complexity but follows standard methods taught at this level.
Spec	7.02p Networks: weighted graphs, modelling connections

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.

Show mark scheme Show mark scheme source

Question 4:

Part (a):

Answer	Marks	Guidance
Answer	Mark	Guidance
Introduce slack variables \(s_1, s_2, s_3\) to give: \(x + y + 2z + s_1 = 20\), \(3x + 2y + z + s_2 = 30\), \(2x + 3y + z + s_3 = 40\)	B1	Correct slack variables introduced
Correct tableau with columns \(x, y, z, s_1, s_2, s_3\), RHS and objective row \(P - 2x - 3y - 4z = 0\)	B1	All entries correct

Part (b)(i):

Answer	Marks	Guidance
Answer	Mark	Guidance
Pivot is \(2\) in row 1, \(z\)-column	B1	Correct pivot identified
Chosen because it gives smallest ratio \(20/2 = 10\) (compared to \(30/1 = 30\) and \(40/1 = 40\))	B1	Must give rationale using minimum ratio test

Part (b)(ii):

Answer	Marks	Guidance
Answer	Mark	Guidance
New row 1: divide by 2: \(\frac{1}{2}, \frac{1}{2}, 1, \frac{1}{2}, 0, 0 \mid 10\)	M1	Correct pivot row operation
Correct elimination in remaining rows	A1
Correct objective row update	A1

Part (c)(i):

Answer	Marks	Guidance
Answer	Mark	Guidance
Correct identification of next pivot	M1
Correct row operations performed	A1
Correct resulting tableau	A1

Part (c)(ii):

Answer	Marks	Guidance
Answer	Mark	Guidance
Correct values of \(x, y, z\) read from tableau	B1
Correct value of \(P\)	B1
Correct values of all three slack variables stated	B1

# Question 4:

## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Introduce slack variables $s_1, s_2, s_3$ to give: $x + y + 2z + s_1 = 20$, $3x + 2y + z + s_2 = 30$, $2x + 3y + z + s_3 = 40$ | B1 | Correct slack variables introduced |
| Correct tableau with columns $x, y, z, s_1, s_2, s_3$, RHS and objective row $P - 2x - 3y - 4z = 0$ | B1 | All entries correct |

## Part (b)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| Pivot is $2$ in row 1, $z$-column | B1 | Correct pivot identified |
| Chosen because it gives smallest ratio $20/2 = 10$ (compared to $30/1 = 30$ and $40/1 = 40$) | B1 | Must give rationale using minimum ratio test |

## Part (b)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| New row 1: divide by 2: $\frac{1}{2}, \frac{1}{2}, 1, \frac{1}{2}, 0, 0 \mid 10$ | M1 | Correct pivot row operation |
| Correct elimination in remaining rows | A1 | |
| Correct objective row update | A1 | |

## Part (c)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct identification of next pivot | M1 | |
| Correct row operations performed | A1 | |
| Correct resulting tableau | A1 | |

## Part (c)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct values of $x, y, z$ read from tableau | B1 | |
| Correct value of $P$ | B1 | |
| Correct values of all three slack variables stated | B1 | |

---

Show LaTeX source

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}
\begin{enumerate}[label=(\alph*)]
\item 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$.
\item \begin{enumerate}[label=(\roman*)]
\item 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$.
\item State the value of the maximum flow and illustrate this flow on Figure 5.
\end{enumerate}\item Find a cut with capacity equal to that of the maximum flow.
\end{enumerate}

\hfill \mbox{\textit{AQA D2  Q4}}

This paper (3 questions)

View full paper

Q4 Q7 Q8