Solution of a Multi-Product Manufacturing and Distribution Problem

An actual multi-product production and distribution problem is described and an optimizing algorithm is developed. The problem, which is an example of a multi-commodity capacitated trans-shipment problem, is solved by the technique suggested by Ford and Fulkerson [Ford, L. R., D. R. Fulkerson. 1958. A suggested computation for maximal multi-commodity network flows. Management Sci.3 (1) 97–101.]. Due to the size of the problem and computational constraints, the usefulness of this technique is improved by incorporating the Generalized Upper Bound algorithm of Dantzig and Van Slyke [Dantzig, G. B., R. M. Van Slyke. 1967. Generalized upper bounding technique. J. Comput. System Sci.1 213–226.]. The modified technique requires manipulation of a relatively small matrix whose order is N by N where N is the number of capacitated links in the network. The traditional node-arc formulation solved by linear programming, the original arc-chain technique and the modified arc-chain algorithm are each compared in terms of computer storage requirements and solution times, resulting in considerable time efficiencies, of the order of fifty to one, for the modified Ford-Fulkerson method.