| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.3 This is a standard D1 network flows question requiring routine application of the max-flow algorithm with supersource/supersink setup. While multi-part with 14 marks total, each step follows textbook procedures: adding supersource/sink (bookwork), finding simple paths, applying labelling procedure, and identifying bottlenecks. No novel insight required, just careful execution of a well-practiced algorithm. Slightly easier than average A-level due to being a standard algorithmic application rather than requiring problem-solving creativity. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| M1, A1, (3) |
| Answer | Marks |
|---|---|
| (i) \(WW_1, A, R_1, R = 6\) | B1 |
| (ii) \(WW_3 \subset R_1, R = 11\) | B1, (2) |
| Answer | Marks |
|---|---|
| [Network diagram with labeled edges and vertices] | M1, A1 |
| E.g. \(W, W_1, B, A, R_1, R - 6\); \(W, W_1, A, R_1, R - 2\); \(W, W_2, B, C, R_1, R - 5\); \(W, W_2, B, A, R_1, R - 1\) | A1, A1, A1, (5) |
| Correct for their network | B1, (1) |
| Answer | Marks |
|---|---|
| All candidates to receive 3 marks. | (3) |
## (a)
| M1, A1, (3) |
## (b)
(i) $WW_1, A, R_1, R = 6$ | B1 |
(ii) $WW_3 \subset R_1, R = 11$ | B1, (2) |
## (c)
[Network diagram with labeled edges and vertices] | M1, A1 |
E.g. $W, W_1, B, A, R_1, R - 6$; $W, W_1, A, R_1, R - 2$; $W, W_2, B, C, R_1, R - 5$; $W, W_2, B, A, R_1, R - 1$ | A1, A1, A1, (5) |
Correct for their network | B1, (1) |
## (d)
All candidates to receive 3 marks. | (3) |
---\includegraphics{figure_2}
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.
\begin{enumerate}[label=(\alph*)]
\item 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. [3]
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item $W$ $W_1$ $A$ $R_1$ $R$,
\item $W$ $W_3$ $C$ $R_2$ $R$. [2]
\end{enumerate}
\item 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 flow-augmenting route you use, together with its flow. [5]
\item From your final flow pattern, determine the number of van loads passing through $B$ each day. [1]
\end{enumerate}
The company has the opportunity to increase the number of vans loads from one of the warehouses $W_1$, $W_2$, $W_3$, to $A$, $B$ or $C$.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumii}{4}
\item Determine how the company should use this opportunity so that it achieves a maximal flow. [3]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q6 [14]}}