= Transportation dual certificate with capacity inequalities
{title2=$u_i\leq0,\quad u_i+v_j\leq c_{ij}$}
For shipments $x_{ij}\geq0$ with factory row sums at most capacities $s_i$ and shop column sums exactly demands $d_j$, the displayed dual potentials give $\sum c_{ij}x_{ij}\geq\sum_i u_i s_i+\sum_jv_jd_j$. The sign $u_i\leq0$ ensures $u_i\sum_jx_{ij}\geq u_i s_i$. Equality proves optimality. It occurs when every used cell is tight and every row with spare capacity has $u_i=0$, the relevant <complementary slackness> conditions. A dummy demand column with zero costs converts unused capacity into a balanced <transportation problem>.
Back to article page
