TY - JOUR
T1 - A network simplex algorithm for solving the minimum distribution cost problem
AU - Wang, I. Lin
AU - Lin, Shiou Jie
PY - 2009
Y1 - 2009
N2 - To model the distillation or decomposition of products in some manufacturing processes, a minimum distribution cost problem (MDCP) for a specialized manufacturing network flow 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 flow entering a D-node has to be distributed according to a pre-specified ratio associated with each of its outgoing arcs. This proportional relationship between arc flows associated with each D-node complicates the problem and makes the MDCP more difficult to solve than a conventional minimum cost network flow 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 flows have never been reported. In this paper, we resolve these issues and propose a modified network simplex algorithm including detailed graphical operations in each elementary procedure. Our method not only deals with a capacitated MDCP, but also orers more theoretical insights into the mathematical properties of an MDCP.
AB - To model the distillation or decomposition of products in some manufacturing processes, a minimum distribution cost problem (MDCP) for a specialized manufacturing network flow 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 flow entering a D-node has to be distributed according to a pre-specified ratio associated with each of its outgoing arcs. This proportional relationship between arc flows associated with each D-node complicates the problem and makes the MDCP more difficult to solve than a conventional minimum cost network flow 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 flows have never been reported. In this paper, we resolve these issues and propose a modified network simplex algorithm including detailed graphical operations in each elementary procedure. Our method not only deals with a capacitated MDCP, but also orers more theoretical insights into the mathematical properties of an MDCP.
UR - http://www.scopus.com/inward/record.url?scp=70350510798&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350510798&partnerID=8YFLogxK
U2 - 10.3934/jimo.2009.5.929
DO - 10.3934/jimo.2009.5.929
M3 - Article
AN - SCOPUS:70350510798
SN - 1547-5816
VL - 5
SP - 929
EP - 950
JO - Journal of Industrial and Management Optimization
JF - Journal of Industrial and Management Optimization
IS - 4
ER -