Feasible flow 2026-10-14
A feasible flow satisfies every flow balance and every capacity interval of a network problem. Feasibility is distinct from optimality: capacitated flow optimality conditions additionally certify that no allowed balanced flow displacement reduces the cost. With only one independent graph cycle, every balanced flow is determined by a single cycle parameter, and its feasible set is the intersection of the induced parameter intervals.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 38 3 Solution Created 2026-10-03 Updated 2026-10-14
In a minimum-cost flow problem, a directed graph has arc flows , unit costs , lower and upper capacities , and net supplies summing to zero. The linear program minimizes subject to the flow balances and .
Give each graph vertex a network dual potential . With the outgoing-minus-incoming oriented incidence matrix , the optimization Lagrangian isMinimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,For every other feasible flow , these conditions give . This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.
Put . The four flow balances determineIntersecting the four capacity intervals gives . In particular,is a feasible flow. Write . Its cost along the feasible interval isHence is optimal precisely when . A network dual potential certificate isThe three interior arcs have zero network reduced costs and , which has the required nonnegative sign at its lower capacity.
For the network simplex algorithm, start with the network simplex tree basis consisting of arcs , and fix nonbasic arc at its lower bound 2. These are exactly the potentials just found. If , no improving pivot is needed. If , arc enters and its fundamental graph cycle increases all four flows by the same amount. At the remaining upper capacities are , so the simplex ratio test allows an increase of 2. Arc reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs , with potentialsNow only the nonbasic arc has a possibly nonzero network reduced cost, namely . It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen , both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.
To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities areThere are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on and both give the identical flow at . Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only satisfy all capacities.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 38 3 b Solution Created 2026-10-03 Updated 2026-10-07
For a minimum-cost flow with bounds , 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 and a possible decrease has reverse cost . 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 be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge , . Taking 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 , 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 in the order . All four tree edges have zero network reduced cost, while have costs . More explicitly, every feasible flow satisfiesOur flow attains equality. This gives a direct cost certificate of 220. The strict signs also force , at any optimum; flow balance then fixes all remaining edges, so this flow is unique.