Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 38 / 3

Label the vertices $S$ (left), $A$ (upper middle), $B$ (lower middle), $C$ (upper right), $T$ (lower right). Use the flow balance convention outgoing minus incoming equals supply. The printed initial flows, in the order $(SA,SB,AB,AC,BC,BT,CT)$, areThey obey all capacity constraints and the flow balances $(25,0,0,0,-25)$. The four strictly interior edges $SA,AB,BC,BT$ form a spanning tree. The remaining edges are at a bound: $SB$ at zero, $AC$ and $CT$ at their upper bounds. Thus this is already a feasible network simplex tree basis; no artificial feasibility phase is needed. Its total cost is $340$.

For a tree, choose network dual potentials with ${\pi }_S=0$ and zero network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ on each tree edge. InitiallyThe nonbasic lower-bound edge $SB$ has network reduced cost $-6$. Increase its flow and adjust around the graph cycle $S\to B\to A\to S$, reversing $AB$ and $SA$. The available step is $\min (20,15,25)=15$, so $AB$ leaves at zero. This givesThe tree is now $SA,SB,BC,BT$, and the potentials are $(0,-7,-6,-8,-8)$.

Now $AC$ is at its upper bound but has network reduced cost $3>0$, so decreasing it improves cost. Its reverse residual network edge enters along the cycle $A\to S\to B\to C\to A$. The forward edges $SB,BC$ increase; $SA,AC$ decrease. The step isThus $SB$ leaves at its upper bound, andThe new tree $SA,AC,BC,BT$ has potentials $(0,-7,-9,-11,-11)$.

The upper-bound edge $CT$ now has network reduced cost $1>0$. Enter its reverse direction along $T\to C\to B\to T$, decreasing $CT$ and $BC$ and increasing $BT$. The step is $\min (20,15,25-5)=15$, so $BC$ leaves at zero. The resulting flow isThe tree is $SA,AC,BT,CT$, with potentials $(0,-7,-10,-11,-12)$. The nonbasic edges have network reduced costs $r_{SB}=-4$ at its upper bound, $r_{AB}=2$ at its lower bound, and $r_{BC}=1$ at its lower bound. All have the correct signs, so there is no improving network simplex pivot. The next part proves these signs certify optimality.

For a minimum-cost flow with bounds $0\le x_{ij}\le m_{ij}$, the capacitated flow optimality conditions consist of primal feasibility and network dual potentials whose network reduced costs obeyFor a zero-capacity edge both bounds coincide and no sign restriction is needed; all capacities here are positive. These are the bound form of complementary slackness. To derive necessity directly, construct the residual network: a possible increase has original cost $c_{ij}$ and a possible decrease has reverse cost $-c_{ij}$. An optimal flow cannot admit a negative-cost directed cycle, since a positive step around it preserves flow balance and lowers cost. If there is no such cycle, connect a new source by zero-cost edges to every vertex and let $d_i$ be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge $i\to j$, $d_j\le d_i+c_{ij}^{\mathrm{res}}$. Taking ${\pi }_i=-d_i$ makes every residual network reduced cost nonnegative, exactly the displayed sign conditions: both directions exist for an interior edge.

Conversely, for any other feasible flow $y$, equal flow balances giveEach summand is nonnegative at a lower or upper bound, and zero at an interior edge. Hence the sign conditions suffice for optimality as well.

For the final flow, use $\pi =(0,-7,-10,-11,-12)$ in the order $(S,A,B,C,T)$. All four tree edges have zero network reduced cost, while $SB,AB,BC$ have costs $-4,2,1$. More explicitly, every feasible flow satisfiesOur flow attains equality. This gives a direct cost certificate of 220. The strict signs also force $y_{SB}=20$, $y_{AB}=y_{BC}=0$ at any optimum; flow balance then fixes all remaining edges, so this flow is unique.