| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Moderate -0.3 This is a standard textbook maximum flow problem using the labelling procedure (Ford-Fulkerson algorithm). Part (a) requires finding bottleneck capacities along given paths (straightforward), part (b) applies the standard algorithm with initial flows provided, and part (c) verifies using max-flow min-cut theorem. While multi-step, it follows a well-rehearsed algorithmic procedure with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Route | Flow |
| \(A B E H\) | |
| \(A C F H\) | |
| \(A D G H\) | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(x = 4\) (latest start time for D: latest finish 9, duration 5, so LST = 4) | B1 | |
| \(z = 17\) (earliest finish of G: EST 9 + duration 8 = 17) | B1 | |
| \(y = 19\) (latest finish of H: LFT = latest start of K minus ... \(= 24-5=19\)) | B1 | All three values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Critical path: \(B\)-\(D\)-\(G\)-\(I\)-\(K\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Critical path duration = 28 weeks; to reduce must crash activities on critical path | M1 | |
| Crash \(G\) by 3 weeks (cheapest on critical path, min 5 weeks, cost £6000/week) | A1 | With justification |
| Crash \(F\) and \(G\) simultaneously once \(F\) becomes critical (reduce both) | M1 A1 | Correct identification of when parallel paths become critical |
| Reduction: \(G\) reduced by 3 to give project time 25; then \(F\) and \(G\) both reduced | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Revised minimum completion time = 23 weeks | B1 | Follow through |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Total additional cost = \(3 \times 6000 + 2\times(7000+6000) = 18000 + 26000 = £44000\) | M1 A1 | Correct calculation |
# Question 8:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| $x = 4$ (latest start time for D: latest finish 9, duration 5, so LST = 4) | B1 | |
| $z = 17$ (earliest finish of G: EST 9 + duration 8 = 17) | B1 | |
| $y = 19$ (latest finish of H: LFT = latest start of K minus ... $= 24-5=19$) | B1 | All three values |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Critical path: $B$-$D$-$G$-$I$-$K$ | B1 | |
## Part (c)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| Critical path duration = 28 weeks; to reduce must crash activities on critical path | M1 | |
| Crash $G$ by 3 weeks (cheapest on critical path, min 5 weeks, cost £6000/week) | A1 | With justification |
| Crash $F$ and $G$ simultaneously once $F$ becomes critical (reduce both) | M1 A1 | Correct identification of when parallel paths become critical |
| Reduction: $G$ reduced by 3 to give project time 25; then $F$ and $G$ both reduced | A1 | |
## Part (c)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| Revised minimum completion time = 23 weeks | B1 | Follow through |
## Part (c)(iii):
| Answer | Mark | Guidance |
|--------|------|----------|
| Total additional cost = $3 \times 6000 + 2\times(7000+6000) = 18000 + 26000 = £44000$ | M1 A1 | Correct calculation |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}
\begin{enumerate}[label=(\alph*)]
\item 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.
\item \begin{enumerate}[label=(\roman*)]
\item 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.
\item State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
\end{enumerate}\item Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\begin{tabular}{ | l | l | }
\hline
Route & Flow \\
\hline
$A B E H$ & \\
\hline
$A C F H$ & \\
\hline
$A D G H$ & \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
\end{tabular}
\end{center}
\end{table}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_746_972_397_845}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_739_971_1311_539}
\end{center}
\end{figure}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 Q8}}