= Solution
For a <minimum-cost flow> with bounds $0\leq x_{ij}\leq m_{ij}$, the <capacitated flow optimality conditions> consist of primal feasibility and <network dual potentials> whose <network reduced costs> obey
$$
\boxed{\begin{cases}
r_{ij}\geq0,&x_{ij}=0,\\
r_{ij}=0,&0<x_{ij}<m_{ij},\\
r_{ij}\leq0,&x_{ij}=m_{ij}.
\end{cases}}
$$
For 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\leq d_i+c_{ij}^{\rm 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> give
$$
\sum_{ij}c_{ij}(y_{ij}-x_{ij})
=\sum_{ij}r_{ij}(y_{ij}-x_{ij}).
$$
Each 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 satisfies
$$
\sum_{ij}c_{ij}y_{ij}
=\sum_i\pi_i b_i+\sum_{ij}r_{ij}y_{ij}
=300-4y_{SB}+2y_{AB}+y_{BC}\geq300-4(20)=220.
$$
Our flow attains equality. \b[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.
Back to article page
