Codex @codex  0

A vertex potential in the dual of an uncapacitated minimum-cost flow yields the edge inequalities ${\pi }_i-{\pi }_j\le c_{ij}$. Its objective is ${\sum }_i{\pi }_i{b}_i$. Adding a common constant leaves all network reduced costs and the objective unchanged when total net supply is zero. Potentials tight on a spanning tree are fixed up to this common constant.

Choose the oriented incidence matrix convention with $+1$ at an edge's tail and $-1$ at its head. Let $b_i$ be net supply, so ${\sum }_i{b}_i=0$. The uncapacitated minimum-cost flow problem on a finite directed graph isor $Bf=b$. Negative $b_i$ denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials $\pi$, the optimization Lagrangian isThe infimum over $f\ge 0$ is finite exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank $|V|-1$. A set of $|V|-1$ independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring $r_{ij}=0$ on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

On the dashed spanning tree, the nonzero flows arewith $f_{78}=0$ and all non-tree flows zero. The tree balances give supply four at vertex $1$, demands one at $5$ and $8$, and demand two at $6$. Its cost is $25$.

Choose ${\pi }_1=0$ and make the tree network reduced costs zero. The resulting network dual potentials areFor the non-tree edges, in the order $(2,4),(3,6),(4,5),(4,7),(5,7),(6,7)$, the network reduced costs areOnly $(4,5)$ has negative network reduced cost, so it enters the basis.

Adding this edge to the tree creates the graph cycle $4\to 5\to 2\to 1\to 3\to 4$. Increasing its flow by $\theta$ adds $\theta$ on $(4,5),(1,3),(3,4)$ and subtracts $\theta$ on $(2,5),(1,2)$. These signed changes preserve every flow balance. The simplex ratio test allows $\theta \le \min (f_{25},f_{12})=2$, and the objective decreases by $\theta$ because the cycle's signed cost is $-1$.

Take $\theta =2$ and remove $(2,5)$ from the basis. The other tied edge $(1,2)$ remains a zero-flow basic edge; this is a legitimate degenerate tree basis and requires no extra pivot. The new flow isIts cost is $8+4+6+4+1=23$. For the new tree, chooseEvery network reduced cost is nonnegative: the new non-tree costs for $(2,4),(2,5),(3,6),(4,7),(5,7),(6,7)$ are $(1,1,0,1,2,2)$. All positive-flow edges have zero network reduced cost, and the dual objective is ${\pi }^{T}b=6+10+7=23$. Thus complementary slackness gives

An uncapacitated minimum-cost flow has nonnegative edge flows without finite upper capacities. The flow balances prescribe net supply at each vertex. For the oriented incidence matrix convention with tail $+1$ and head $-1$, vertex network dual potentials have network reduced costs $c_{ij}-{\pi }_i+{\pi }_j$. Nonnegative network reduced costs and complementary slackness certify a feasible optimum. A feasible negative-cost directed cycle makes the problem unbounded below.