Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 35 / 3

For a finite directed flow network with source $s$, sink $t$ and nonnegative finite flow network edge capacities $c_e$, the max-flow min-cut theorem statesHere feasible arc flows satisfy $0\le f_e\le c_e$ and flow conservation at every vertex except $s,t$. Their strength of a flow is the net outflow at $s$. A cut of a flow network has cut capacity equal to the sum of capacities on arcs directed from $S$ to $S^c$.

For any feasible flow and any such cut of a flow network, summing flow conservation over $S$ cancels internal arcs and givesThus every flow value is bounded by every cut capacity.

A maximum flow exists: the feasible arc-flow vectors form a nonempty closed subset of the finite-dimensional compact box ${\prod }_e[0,c_e]$, and flow value is continuous. Choose one, $f^{\ast }$. Its residual network has a forward arc of capacity $c_e-f_e^{\ast }$ and a reverse arc of capacity $f_e^{\ast }$ for each original arc. If a residual $s$–$t$ augmenting path existed, its smallest positive residual capacity would permit increasing forward flows and decreasing reverse flows along the path. This preserves all capacity bounds and internal flow conservation while strictly increasing $|f^{\ast }|$, a contradiction.

Let $S$ be the vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. Every original arc leaving $S$ is saturated, since otherwise its endpoint would also be reachable. Every original arc entering $S$ carries zero flow, since a positive flow would create a residual reverse arc leaving $S$. ThereforeTogether with the universal upper bound, this proves both optimality claims and the theorem. This existence argument works for real capacities; it does not assume that arbitrary choices in the Ford-Fulkerson algorithm terminate. For integer capacities, positive augmentations are integral and increase the flow value by at least one, so the algorithm does terminate.

Start with zero flow and apply the Ford-Fulkerson algorithm. The following augmenting paths and bottlenecks use the capacities in the original PDF diagram:For example, the second path is limited by the remaining capacity two on $6\to 8$ and by capacity two on $5\to 6$. After the third augmentation, $7\to 8$ has residual capacity one; the fourth path supplies it through $5\to 4\to 6\to 7$. Every displayed increment is the smallest residual capacity of its path.

The resulting arc flows areHere $uv$ denotes $u\to v$. These satisfy every capacity bound and flow conservation. The final residual network has source-reachable set $S=\{1,2,3,5\}$. Its outgoing arcs are $2\to 4$, $5\to 4$, $5\to 6$ and $5\to 7$, with capacities $2,1,2,1$, all saturated. ConsequentlyThis is a minimum cut, and the equal flow and cut values certify optimality by the max-flow min-cut theorem. The cut immediately before node eight also has capacity six, so the minimum cut is not unique.

Use the transportation simplex algorithm, with transportation dual potentials $u_i,v_j$ and reduced costs $r_{ij}=c_{ij}-u_i-v_j$. On a basic cell choose $u_i+v_j=c_{ij}$. The initial shipment matrix, read from the circled entries in the PDF, isIts six positive cells form a transportation spanning tree. Setting $u_1=0$ givesEnter cell $(1,1)$, whose reduced cost is $-6$. The cycle pivot has signsThe maximum feasible increment is $\theta =\min (5,4)=4$, so cell $(4,1)$ leaves the basis. The result isFor the new transportation spanning tree,Enter cell $(2,3)$ with reduced cost $-4$. Its cycle pivot isNow $\theta =\min (5,1)=1$, and cell $(1,3)$ leaves. We obtainIts row sums are $(12,5,7,12)$ and its column sums $(9,14,13)$, as required. The final transportation dual potentials areAll reduced costs are nonnegative, proving optimality. More explicitly, for any feasible shipment matrix $X$,Our shipments use only zero-reduced-cost cells and attain this lower bound. This supplies an independent weak duality certificate for the transportation optimum.