= Transportation dual potentials
{title2=$u_i+v_j\leq c_{ij}$}
Row and column potentials satisfying the displayed inequalities give a lower bound on the cost of every feasible shipment matrix: $\sum_{ij}c_{ij}x_{ij}\geq\sum_i u_i s_i+\sum_jv_j d_j$, since row sums are supplies $s_i$ and column sums are demands $d_j$. The <reduced costs> are $c_{ij}-u_i-v_j$. A feasible matrix using only zero-reduced-cost cells attains the lower bound, proving optimality by <weak duality>. The <transportation simplex algorithm> sets these potentials by equality on a <transportation spanning tree>, and enters a negative-reduced-cost cell if one exists.
Back to article page
