| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.3 This is a standard network flows question requiring identification of sources, reading a feasible flow value, applying the labelling procedure (Ford-Fulkerson algorithm), and proving maximality using a cut. While it involves multiple parts and the labelling procedure requires careful bookkeeping, these are routine algorithmic steps taught directly in D2 with no novel problem-solving required. The proof of maximality is straightforward application of the max-flow min-cut theorem. Slightly easier than average due to being a textbook application of a standard algorithm. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Action: number of robots produced in that month | B1 | Correct identification of stage, state, action |
| Answer | Marks | Guidance |
|---|---|---|
| - Storage £150 per robot carried over | M1 | Setting up cost structure correctly |
| Answer | Marks | Guidance |
|---|---|---|
| Working backwards or forwards through each month, computing minimum cost at each state | M1 A1 | Method mark for correct DP approach; accuracy marks for correct table values |
| Correct identification of optimal schedule (e.g. produce 2 in Jan, 3 in Feb/Mar, 4 in April or equivalent) with minimum total cost | A1 ft | Follow through from working |
| Total cost calculated correctly | A1 | Correct final answer |
# Question 8:
**Stage:** month (Jan, Feb, Mar, Apr)
**State:** number of robots in stock at start of month
**Action:** number of robots produced in that month | B1 | Correct identification of stage, state, action
**Cost function** includes:
- Overhead £300 if any robots produced
- Extra labour £400 if more than 3 produced
- Storage £150 per robot carried over | M1 | Setting up cost structure correctly
**Tabulation working through stages** with optimal substructure:
Working backwards or forwards through each month, computing minimum cost at each state | M1 A1 | Method mark for correct DP approach; accuracy marks for correct table values
**Correct identification of optimal schedule** (e.g. produce 2 in Jan, 3 in Feb/Mar, 4 in April or equivalent) with **minimum total cost** | A1 ft | Follow through from working
**Total cost calculated correctly** | A1 | Correct final answer8.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1404_285_343}
\end{center}
\end{figure}
The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
\begin{enumerate}[label=(\alph*)]
\item Write down the source vertices.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1402_1170_343}
\end{center}
\end{figure}
Figure 5 shows a feasible flow through the same network.
\item State the value of the feasible flow shown in Fig. 5.
Taking the flow in Fig. 5 as your initial flow pattern,
\item use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
\item Show the maximal flow on Diagram 2 and state its value.
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q8}}