11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-10_723_1172_476_337}
\end{figure}
- On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
- State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
- Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
Taking your answer to part (b)(ii) as the initial flow pattern,
- use the labelling procedure to find a maximum flow from \(S\) to \(R\).
Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
- Prove that your final flow is maximal.