= Solution
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> is
$$
\min_{f\geq0}\sum_{(i,j)\in E}c_{ij}f_{ij}\quad\text{subject to }\sum_{j:(i,j)\in E}f_{ij}-\sum_{j:(j,i)\in E}f_{ji}=b_i,
$$
or $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> is
$$
L(f,\pi)=c^Tf+\pi^T(b-Bf)=\pi^Tb+\sum_{(i,j)\in E}(c_{ij}-\pi_i+\pi_j)f_{ij}.
$$
The infimum over $f\geq0$ 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> are
$$
\boxed{\max_\pi\pi^Tb\quad\text{subject to }r_{ij}\geq0,\qquad f_{ij}r_{ij}=0\text{ for every edge}.}
$$
A 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>.
Back to article page
