Network Flows

The diagram shows a network of pipes. Each pipe is labelled with its upper capacity in \(\mathrm{m}^3 \mathrm{s}^{-1}\) \includegraphics{figure_3}

1. Find the value of Cut \(X\) [1 mark]
2. Find the value of Cut \(Y\) [1 mark]
3. Add a supersink \(T\) to the network. [2 marks]

2 The diagram below shows a network of pipes with their capacities. \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-04_691_1155_340_424} A supersource is added to the network. Which nodes are connected to the supersource? Tick ( ✓ ) one box. \(A\) and \(B\) □ \(A\) and \(G\) □ \(G\) and \(H\) \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-04_104_108_1822_685} \(H\) and \(I\) □

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
2. On Diagram 1 and Diagram 2 in the answer book, add a supersource S and a supersink T . On Diagram 1, show the minimum capacities of the arcs you have added.
3. Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on \(\operatorname { arcs } \mathrm { CD }\), DE , DG , FG, FI and GI.
4. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
5. Show your maximum flow on Diagram 3 in the answer book.
6. Prove that your flow is maximal.

2 The network below represents a system of pipes. The numbers on each arc represent the lower and upper capacity for each pipe. \includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-03_616_1415_447_310} Find the value of the cut \(\{ A , B , C , D , E \} \{ F , G , H , I \}\).
Circle your answer. 56586370

1 The network represents a system of pipes.
The number on each arc represents the upper capacity for each pipe in \(\mathrm { cm } ^ { 3 } \mathrm {~s} ^ { - 1 }\) \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-03_691_1067_721_482} The value of the cut \(\{ S , A , B \} \{ C , D , E , T \}\) is \(V \mathrm {~cm} ^ { 3 } \mathrm {~s} ^ { - 1 }\) Find \(V\). Circle your answer.
[0pt] [1 mark]
25303137

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-6_599_1580_402_280}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the arcs \(A C\) and \(A D\) cannot both be full to capacity and why the arcs \(D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{30a88efe-fe9e-4384-a3e3-da2a05326797-04_547_1214_555_404}

1. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(M N , P Q , N P\) and \(N T\).
2. 1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\).
   2. State the value of the maximum flow and illustrate this flow on Figure 5.
3. Find a cut with capacity equal to that of the maximum flow.

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-14_807_1472_429_276}

1. Find the value of the cut \(Q\).
2. Figure 2 shows most of the values of a feasible flow of 34 litres per second from \(S\) to \(T\).
   1. Insert the missing values of the flows along \(D E\) and \(F G\) on Figure 2.
   2. Using this feasible flow as the initial flow, indicate potential increases and decreases of the flow along each edge on Figure 3.
   3. Use flow augmentation on Figure 3 to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
3. 1. State the value of the maximum flow.
   2. Illustrate your maximum flow on Figure 4.
4. Find a cut with capacity equal to that of the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_1646_1463_280_381}
   \end{figure} Figure 3 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_668_1230_1998_404}
   \end{figure}

6. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid flows from a source, S , to a sink, T . The numbers ( \(l , u\) ) on each arc represent, in litres per second, the lower capacity, \(l\), and the upper capacity, \(u\), of the corresponding pipe. Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown.

1. Find the capacity of
   1. \(\operatorname { cut } C _ { 1 }\)
   2. \(\operatorname { cut } C _ { 2 }\)
2. Explain why the arcs AE and CE cannot be at their upper capacities simultaneously.
3. Explain why a flow of 31 litres per second through the system is not possible.
4. Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams in the answer book and give reasons to justify your answer. You should not apply the labelling procedure to find these flows.

6. (a) Define the term 'cut' as it applies to a directed network.
(2) \begin{figure}[h] \end{figure} Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
(b) Complete the labelling procedure on Diagram 2 in your answer book by entering values along CE, EG, HT and GT.
(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
(d) Show a maximal flow pattern on Diagram 3 in your answer book.
(e) State the value of the maximum flow through the network.
(f) Prove that your flow is maximal.

5. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
   (2)
3. By entering values along DH, FH, FI and IT, complete the labelling procedure on Diagram 1 in the answer book.
   (2)
4. Using Diagram 1, increase the flow by a further 4 units. You must list each flow-augmenting route you use, together with its flow.
   (3)
5. Prove that the flow is now maximal.
   (2)

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed, network. The capacity of each arc is shown on that arc and the numbers in circles represent an initial flow from S to T . Two cuts, \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown on Figure 1.

1. Find the capacity of each of the two cuts and the value of the initial flow.
   (3)
2. Complete the initialisation of the labelling procedure on Figure 1 in the answer book, by entering values along \(\mathrm { SB } , \mathrm { AB } , \mathrm { BE }\) and BG .
   (2)
3. Hence use the labelling procedure to find a maximum flow of 85 through the network. You must list each flow-augmenting path you use, together with its flow.
   (5)
4. Show your flow pattern on Figure 2.
   (2)
5. Prove that your flow is maximal.
   (2)

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\) and \(z\).
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

1. Write down the capacity of edge \(E F\).
2. State the source vertex.
3. State the sink vertex.
4. Find the values of \(x , y\) and \(z\).
5. Find the value of the initial flow.
6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).

3. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

1. Find the values of \(x\) and \(y\).
2. 1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. 1. Find a minimum cut, listing the arcs through which it passes.
   2. Explain why this proves that the flow found in part (b) is a maximum.
      (2 marks)

4

1. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}
2. \(\_\_\_\_\)
3. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour
4. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(v)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_671_729_1822_315}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(vi)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_735_1816_1171}
   \end{figure} Maximum flow = \(\_\_\_\_\) gallons per hour

9. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-6_540_1291_203_411} This diagram shows a capacitated directed network. The number on each arc is its capacity.

1. State the maximum flow along
   1. SADT,
   2. SCET,
   3. \(S B F T\).
2. Show these maximum flows on Diagram 1 below. \section*{Diagram 1}
   \includegraphics[max width=\textwidth, alt={}]{be329a47-a709-4719-abe6-41d388a6c631-6_561_1187_1283_721}
   Take your answer to part (b) as the initial flow pattern.
3. 1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 below. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_718_1525_205_269}
   2. Draw your final flow pattern on Diagram 3 below. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_611_1196_1082_717}
   3. Prove that your flow is maximal.
4. Give an example of a practical situation that could have been modelled by the original network.

6. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. State the maximum flow along
   1. SAET,
   2. SBDT,
   3. SCFT.
      (3 marks)
2. Show these maximum flows on Diagram 1 on the answer sheet.
3. Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
4. Indicate a maximum flow on Diagram 3.
5. Prove that your flow is maximal.

A transportation problem has costs, in pounds, and supply and demand, in appropriate units, as given in the transportation tableau below.

	D	E	F	Supply
A	13	11	14	20
B	10	9	12	15
C	15	6	8	25
Demand	30	5	25

1. Find the initial solution given by the north-west corner rule and state why it is degenerate. [3 marks]
2. Use the stepping-stone method to obtain an optimal solution minimising total cost. State the resulting transportation pattern and its total cost. [15 marks]

3. Table 1 below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to four demand points \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method.
Table 3 shows some of the improvement indices for this solution. \begin{table}[h] \end{table} \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell B3 in Table 2.
   (1)
2. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in your answer book.
3. Taking the most negative improvement index to indicate the entering cell, state the steppingstone route that should be used to obtain the next solution. You must state your entering cell and exiting cell.

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking DQ as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
2. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating the
   • shadow costs
   • improvement indices
   • route
   • entering cell and exiting cell.
   • Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer.
   • State the cost of the solution found in (b).

5

1. Capacity = \(\_\_\_\_\)
2. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
3. Route: \(\_\_\_\_\) Flow \(=\) \(\_\_\_\_\)
4. Maximum flow = \(\_\_\_\_\) Cut: \(\mathrm { X } = \{\) \} \(\quad \mathrm { Y } = \{\)
5. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

1. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.

1. Use the north-west corner rule to find an initial solution.
2. Obtain improvement indices for each unused route.
3. Use the stepping-stone method once to obtain a better solution and state its cost.

2. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

1. List the saturated arcs.
2. State the value of the initial flow.
3. State the capacities of the cuts \(C _ { 1 }\) and \(C _ { 2 }\)
4. By inspection, find a flow-augmenting route to increase the flow by three units. You must state your route.
5. Prove that the new flow is maximal.

2. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the maximum capacity of that arc. In addition to the restrictions on flow through the arcs a maximum flow of 6 units is allowed to pass through vertex \(C\).

1. Redraw the network to take into account this restriction.
2. Starting with an initial flow of 6 units along SADT and 6 units along SBT use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow and draw the maximal flow pattern.

1. Describe a practical problem that could be solved using the transportation algorithm. [2]

A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from \(A\), \(B\) and \(C\) and the demand is at \(d\) and \(e\).

1. Explain why it is necessary to add a third demand \(f\). [1]
2. Use the north-west corner rule to obtain a possible pattern of distribution and find its cost.

   	\(d\)	\(e\)	\(f\)	Supply
   \(A\)	5	3		45
   \(B\)	4	6		35
   \(C\)	2	4		40
   Demand	50	60

   [5]
3. Calculate shadow costs and improvement indices for this pattern. [5]
4. Use the stepping-stone method once to obtain an improved solution and its cost. [5]

(Total 16 marks)

5. Three warehouses \(W , X\) and \(Y\) supply televisions to three supermarkets \(J , K\) and \(L\). The table gives the cost, in pounds, of transporting a television from each warehouse to each supermarket. The warehouses have stocks of 34,57 and 25 televisions respectively, and the supermarkets require 20, 56 and 40 televisions respectively. The total cost of transporting the televisions is to be minimised. Formulate this transportation problem as a linear programming problem. Make clear your decision variables, objective function and constraints.

5. \begin{figure}[h] \end{figure} Figure 5 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.

1. State the values of \(x\) and \(y\).
2. List the saturated arcs.
3. State the value of the feasible flow.
4. State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
5. By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
6. Prove that the new flow is maximal.

1. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow from S to T .

1. State the value of the feasible flow.
   (1)
2. Find the capacity of cut \(\mathrm { C } _ { 1 }\) and the capacity of cut \(\mathrm { C } _ { 2 }\) (2)
3. By inspection, find a flow-augmenting route to increase the flow by two units. You must state your route.
   (1)
4. Prove that, once the flow-augmenting route found in (c) has been applied, the flow is now maximal.
   (3)

The following matrix gives the capacities of the pipes in a system. \begin{array}{c|c|c|c|c|c|c|c} To & & S & T & A & B & C & D
From & & & & & & &
\hline S & & -- & -- & 16 & 26 & -- & --
T & & -- & -- & -- & -- & -- & --
A & & -- & -- & -- & -- & 13 & 5
B & & -- & 16 & -- & -- & -- & 11
C & & -- & 11 & -- & -- & -- & --
D & & -- & 11 & -- & -- & -- & --
\end{array}

1. Represent this information as a digraph. [3 marks]
2. Find the minimum cut, expressing it in the form \(\{\) \(\}|\{\) \(\}\), and state its value. [2 marks]
3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow. [5 marks]
4. Explain how you know that this flow is maximal. [1 mark]

[11 marks]