Cost Operator Algorithms for the Transportation Problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with the appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T-l) steps for nondegenerate transportation problems and (2T-l) min(m,n) steps for degenerate transportation problems, where T is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) and m and n denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps are T and T.min(m,n) respectively.