A modified 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) on a specialized manufacturing network flow model has been investigated. In a MDCP, a specialized node called D-node is used to model a distillation process which only connects with a single incoming arc and several outgoing arcs. The flows entering a D-node have to be distributed according to a pre-specified ratio associated with each of its outgoing arc. Such a proportional relationship between the arc flows associated with each D-node complicates the problem and makes the MDCP harder than conventional min-cost network flow problem. A network simplex algorithm for uncapacitated MDCP has been outlined in literature, but its detailed graphical procedures such as initial basic feasible solution computation, dual variables updates, and flow pivoting operations have not yet been given. In this paper, we resolve these issues and propose a modified network simplex algorithm including detailed graphical operations in each elementary procedure. Our method can not only deal with capacitated MDCP, but also offer more theoretical insights in the basis and properties of MDCP.