Abstract
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 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 − 1) steps for primal nondegenerate transportation problems and [(2T + 1) ⋅ min (m, n)] − 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) ⋅ min (m, n) respectively.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M.L. Balinski and R.E. Gomory, “A primal method for the assignment and transportation problems”,Management Science 10 (1964) 578–593.
A. Charnes and W.W. Cooper,Management models and industrial applications of linear programming, Vols. I and II (Wiley, New York, 1961).
G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963).
J. Edmonds and R.M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”,Journal of the Association for Computing Machinery 19 (1972) 248–264.
L.R. Ford and D.R. Fulkerson,Flows in networks (Princeton University Press, Princeton, NJ, 1962).
A. Orden, “The transshipment problem”,Management Science 2 (1956), 276–285.
M. Simmonard,Linear programming (Prentice-Hall, Englewood Cliffs, N.J., 1966).
V. Srinivasan and G.L. Thompson, “An operator theory of parametric programming for the transportation problem — I and II”,Naval Research Logistics Quarterly 19 (1972) 205–252.
V. Srinivasan and G.L. Thompson, “Accelerated algorithms for labelling and relabelling of trees, with applications to distribution problems”,Journal of the Association for Computing Machinery 19 (1972) 712–726.
V. Srinivasan and G.L. Thompson, “Benefit-cost analysis of coding techniques for the primal transportation algorithm”,Journal of the Association for Computing Machinery 20 (1973) 194–213.
W. Szwarc, “Some remarks on the time transportation problem”,Naval Research Logistics Quarterly 18 (1971) 473–485.
Author information
Authors and Affiliations
Additional information
This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.
Rights and permissions
About this article
Cite this article
Srinivasan, V., Thompson, G.L. Cost operator algorithms for the transportation problem. Mathematical Programming 12, 372–391 (1977). https://doi.org/10.1007/BF01593805
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01593805