A network simplex algorithm for solving the minimum distribution cost problem

To model the distillation or decomposition of products in some manufacturing processes, a minimum distribution cost problem (MDCP) for a specialized manufacturing network ∞ow model has been investigated. In an MDCP, a specialized node called a D-node is used to model a distillation process that connects with a single incoming arc and several outgoing arcs. The ∞ow entering a D-node has to be distributed according to a pre-specifled ratio associated with each of its outgoing arcs. This proportional relationship between arc ∞ows associated with each D-node complicates the problem and makes the MDCP more di-cult to solve than a conventional minimum cost network ∞ow problem. A network simplex algorithm for an uncapacitated MDCP has been outlined in the literature. However, its detailed graphical procedures including the operations to obtain an initial basic feasible solution, to calculate or update the dual variables, and to pivot ∞ows have never been reported. In this paper, we resolve these issues and propose a modifled network simplex algorithm including detailed graphical operations in each elementary procedure. Our method not only deals with a capacitated MDCP, but also ofiers more theoretical insights into the mathematical properties of an MDCP.