 Transportation dual potentials

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}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_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.