A STRONGLY POLYNOMIAL ALGORITHM FOR A CONCAVE PRODUCTION-TRANSPORTATION PROBLEM WITH A FIXED NUMBER OF NONLINEAR VARIABLES

摘要

We show that the production-transportation problem involving an arbitrary fixed number of factories with concave production cost is solvable in strongly polynomial time. The algorithm is based on a parametric approach which takes full advantage of the specific structure of the problem: monotonicity of the objective function along certain directions, small proportion of nonlinear variables and combinatorial properties implied by transportation constraints. [References: 34]