Past exam of the mathematics course of the University of Cambridge / 2005 / ib / Paper 1 / 8D / Solution

Associate free real dual variables $u_i$ and $v_j$ with the row and column equality constraints. The Lagrangian for the transportation problem isIts infimum over $x_{ij}\ge 0$ is finite exactly when $u_i+v_j\le c_{ij}$ for every pair. The linear programming duality therefore givesThe 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:Thus every occupied route must have $u_i+v_j=c_{ij}$. To see sufficiency explicitly, the primal minus dual objective isand 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)$.