 Solution

A balanced transportation problem chooses nonnegative shipments $x_{ij}$ minimizing ${\sum }_{ij}{c}_{ij}{x}_{ij}$, subject to ${\sum }_j{x}_{ij}=s_i$ and ${\sum }_i{x}_{ij}=d_j$, where the total supply equals total demand. For multipliers $u_i,v_j$, its Lagrangian isTaking its infimum over $x_{ij}\ge 0$ produces the linear programming duality problem of maximizing ${\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$ subject to $u_i+v_j\le c_{ij}$. These are the transportation dual potentials.

The transportation simplex algorithm starts with a feasible transportation spanning tree of $m+n-1$ basic entries, obtainable by filling the north-west available cell with the smaller remaining supply or demand. Set $u_i+v_j=c_{ij}$ on basic cells; this determines all potentials up to adding a constant to all $u_i$ and subtracting it from all $v_j$. If all nonbasic reduced costs $r_{ij}=c_{ij}-u_i-v_j$ are nonnegative, feasibility and the dual bound prove optimality. Otherwise let a negative-cost cell enter. It closes a unique cycle in the basic tree. Alternate additions and subtractions around that cycle and choose the largest amount preserving nonnegativity, namely the minimum shipment on the subtraction cells. A cell that reaches zero leaves the basis. The cost changes by the entering reduced cost times the pivot amount. Zero basic cells and an anti-cycling rule can handle degeneracy; all pivots below are nondegenerate.

The north-west initial shipment matrix isWith $u_1=0$, its transportation dual potentials are $u=(0,1,0)$ and $v=(5,9,5)$. The most negative reduced cost is $r_{32}=-7$. The cycle is $+(3,2),-(3,3),+(2,3),-(2,2)$; the pivot amount is $\min (40,46)=40$. HenceNow $u=(0,1,-7)$ and $v=(5,9,5)$. Enter $(1,3)$, of reduced cost $-4$, on cycle $+(1,3),-(1,2),+(2,2),-(2,3)$. The amount is $\min (22,78)=22$, givingThe new potentials are $u=(0,5,-3)$ and $v=(5,5,1)$. Enter $(2,1)$, of reduced cost $-7$, on cycle $+(2,1),-(1,1),+(1,3),-(2,3)$. The amount is $\min (14,56)=14$. ThusTo certify optimality in the original transportation problem, take $u=(0,5,-3)$ and $v=(-2,5,1)$. Their entire reduced-cost matrix isThey satisfy dual feasibility, and their value is $5\cdot 84-3\cdot 40-2\cdot 14+5\cdot 68+78=690$, equal to the shipment cost. The minimum transportation cost is therefore $690$, with no unproved optimality assertion from the iterations alone.