Econometrica: May, 1970, Volume 38, Issue 3
A Decomposition Algorithm for Solving the Multifacility Production-Transportation Problem with Nonlinear Production Costs
J. Frank Sharp, James C. Snyder, James H. Greene
In the model considered in this paper, a firm with several plants must supply several markets with known demands. Production costs are nonlinear while transportation costs between any plant-market pair are linear. The firm desires to minimize total production and transportation costs. The Kuhn-Tucker conditions and the dual to the transportation model are used to derive optimal conditions for this problem. These conditions are shown to be both necessary and sufficient if the production costs are convex at each plant, and are necessary otherwise. An algorithm is developed for reaching an optimal solution to the production-transportation problem for the convex case. This algorithm utilizes a decomposition approach. It iterates between a linear programming transportation problem which optimally allocates previously set plant production quantities to various markets and a routine which optimally sets plant production quantities to equate total marginal production costs including a shadow price representing the relative location cost determined from the transportation problem.