| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| 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 max-flow problem using the labelling procedure (Ford-Fulkerson algorithm). While it requires multiple steps and careful bookkeeping, it's a routine application of a well-defined algorithm taught in the module. The supersource/supersink addition in part (a) is textbook standard, and verifying maximality using a cut is straightforward. Slightly above average difficulty due to the multi-source/multi-sink setup and the 9 marks for part (b), but no novel insight required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| (c) | 2x + 3y + 4z ≤ 8 |
| Answer | Marks |
|---|---|
| z = 0, r = 0, s = 0 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| b.v | x | y |
| r | 2 | 3 |
| s | 3 | 3 |
| P | −8 | −9 |
| b.v | x | y |
| y | 2 | |
| 3 | 1 | 4 |
| 3 | 1 | |
| 3 | 0 | 3 |
| s | 1 | 0 |
| P | −2 | 0 |
| b.v | x | y |
| y | 0 | 1 |
| 3 | 1 | −2 |
| 3 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| x | 1 | 0 |
| P | 0 | 0 |
Question 7:
7
8. (a)
(b)
(c) | 2x + 3y + 4z ≤ 8
3x + 3y + z ≤ 10
P = 8x + 9y + 5z
↓
b.v x y z r s Value
r 2 3 4 1 0 8
s 3 3 1 0 1 10
P −8 −9 −5 0 0 0
↓
b.v x y z r s Value
y 2 1 4 1 0 R ÷ 3
3 3 3 3 1
s 1 0 −3 −1 1 2 R – 3R
2 1
P −2 0 7 3 0 24 R + 9R
3 1
b.v x y z r s Value
y 0 1 10 1 −2 4 R 1 − 2 R 2
3 3 3 3
x 1 0 −3 −1 1 2
P 0 0 1 1 2 28 R + 2R
3 2
P = 28
x = 2, y = 4
3
z = 0, r = 0, s = 0 | B1
B1
B1 (3)
M1
A1
M1
A1
M1
A1
M1
A1 (8)
M1
A1
A1 (3)
(14 marks)
b.v | x | y | z | r | s | Value
r | 2 | 3 | 4 | 1 | 0 | 8
s | 3 | 3 | 1 | 0 | 1 | 10
P | −8 | −9 | −5 | 0 | 0 | 0
b.v | x | y | z | r | s | Value
y | 2
3 | 1 | 4
3 | 1
3 | 0 | 3
s | 1 | 0 | −3 | −1 | 1 | 2
P | −2 | 0 | 7 | 3 | 0 | 24
b.v | x | y | z | r | s | Value
y | 0 | 1 | 10
3 | 1 | −2
3 | 4
3
x | 1 | 0 | −3 | −1 | 1 | 2
P | 0 | 0 | 1 | 1 | 2 | 28\includegraphics{figure_4}
Figure 4 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow from sources $A$ and $B$ to sinks $I$, $J$ and $K$.
Take this as the initial flow pattern.
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 in the answer booklet, add a supersource $S$ and a supersink $W$ to obtain a capacitated network with a single source and single sink. State the minimum capacities of the arcs you have added.
[3]
\item \begin{enumerate}[label=(\roman*)]
\item Use the given initial flow and the labelling procedure on Diagram 2 to find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
\item Verify that your flow is maximal.
\end{enumerate}
[9]
\item Show your maximum flow pattern on Diagram 3.
[2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q7 [14]}}