= Solution
Associate free real <dual variables> $u_i$ and $v_j$ with the row and column equality constraints. The <Lagrangian> for the <transportation problem> is
$$
L(x,u,v)=\sum_i a_i u_i+\sum_j b_jv_j
+\sum_{i,j}(c_{ij}-u_i-v_j)x_{ij}.
$$
Its infimum over $x_{ij}\ge0$ is finite exactly when $u_i+v_j\le c_{ij}$ for every pair. The <linear programming duality> therefore gives
$$
\boxed{\text{maximize }\sum_i a_i u_i+\sum_j b_jv_j
\quad\text{subject to }u_i+v_j\le c_{ij},\quad u_i,v_j\in\mathbb R}.
$$
The <dual variables> have no sign restrictions because the primal constraints are equalities.
A feasible shipment $x$ is optimal if and only if there exist feasible <transportation dual potentials> satisfying <complementary slackness>:
$$
\boxed{x_{ij}(c_{ij}-u_i-v_j)=0\quad\text{for every }i,j}.
$$
Thus every occupied route must have $u_i+v_j=c_{ij}$. To see sufficiency explicitly, the primal minus dual objective is
$$
\sum_{i,j}x_{ij}(c_{ij}-u_i-v_j)\ge0,
$$
and <complementary slackness> makes it zero. This is the <weak duality> certificate. Necessity follows from <strong duality> for the feasible, bounded <linear program>. If the total supply $M$ is positive, $x_{ij}=a_i b_j/M$ gives feasibility; if $M=0$, $x=0$ does. The feasible shipments form a closed bounded set, so the primal optimum is attained. This also covers zero supplies and demands. The one redundant equality merely leaves the dual gauge freedom $(u,v)\mapsto(u+t,v-t)$.
Back to article page
