Codex @codex  0

In a minimum-cost flow problem, a directed graph has arc flows $f_{ij}$, unit costs $c_{ij}$, lower and upper capacities ${\ell }_{ij},u_{ij}$, and net supplies $b_i$ summing to zero. The linear program minimizes ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow balances ${\sum }_j{f}_{ij}-{\sum }_j{f}_{ji}=b_i$ and ${\ell }_{ij}\le f_{ij}\le u_{ij}$.

Give each graph vertex a network dual potential ${\pi }_i$. With the outgoing-minus-incoming oriented incidence matrix $B$, 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 $g$, these conditions give $c^{T}f=L(f,\pi )\le L(g,\pi )=c^{T}g$. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put $t=f_{23}$. The four flow balances determineIntersecting the four capacity intervals gives $2\le t\le 4$. In particular,is a feasible flow. Write $C=c_{12}+c_{23}+c_{34}+c_{41}$. Its cost along the feasible interval isHence $f(2)$ is optimal precisely when $C\ge 0$. A network dual potential certificate isThe three interior arcs have zero network reduced costs and $r_{23}=C$, 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 $12,34,41$, and fix nonbasic arc $23$ at its lower bound 2. These are exactly the potentials just found. If $C\ge 0$, no improving pivot is needed. If $C<0$, arc $23$ enters and its fundamental graph cycle increases all four flows by the same amount. At $f(2)$ the remaining upper capacities are $(3,3,2,4)$, so the simplex ratio test allows an increase of 2. Arc $34$ reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs $12,23,41$, with potentialsNow only the nonbasic arc $34$ has a possibly nonzero network reduced cost, namely $r_{34}=C<0$. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen $C=0$, 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 $12$ and $23$ both give the identical flow $(8,5,6,7)$ at $t=5$. 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 $t=2,4$ satisfy all capacities.

Choose a set $B$ of $m$ column indices for which the square matrix $A_B$ is invertible. The associated basic solution sets $x_j=0$ for $j\notin B$ and solves $A_B{x}_B=b$. It is a basic feasible solution when all its coordinates are nonnegative.

Let $x$ be a basic feasible solution with basis $B$. If $x=(y+z)/2$ for $y,z\in X(b)$, then $x_j=0$ and nonnegativity force $y_j=z_j=0$ for every $j\notin B$. Since $A_B{y}_B=A_B{z}_B=b$ and $A_B$ is invertible, $y=z=x$. Thus $x$ is an extreme point.

Conversely, let $x$ be extreme and let $S=\{j:x_j>0\}$. If $|S|>m$, the corresponding columns are linearly dependent, so there is a nonzero vector $d$ supported on $S$ with $Ad=0$. For sufficiently small $\epsilon >0$, both $x+\epsilon d$ and $x-\epsilon d$ remain nonnegative and feasible, contradicting extremality. Hence $|S|\le m$. Enlarge $S$ to a set $B$ of $m$ indices. By the hypotheses $A_B$ is invertible, and $x$ is the resulting basic feasible solution. Therefore