Article ID: | iaor2007370 |
Country: | Netherlands |
Volume: | 11 |
Issue: | 4 |
Start Page Number: | 351 |
End Page Number: | 371 |
Publication Date: | Jun 2006 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Qi Liqun, Yao Enyu, Lu Haiyan |
Manufacturing network flow (MNF) is a generalized network model that can model more complicated manufacturing scenarios, such as the synthesis of different materials to one product and/or the distilling of one material to many different products. Minimum distribution cost flow problem (MDCF) is a simplified version of MNF optimization problems, in which a general supplier wants to proportionally distribute certain amount of a particular product from a source node to several retailers at different destinations through a distribution network. A network simplex algorithm has been outlined in recent years for solving a special case of MDCF. In this paper, we characterize the network structure of the bases of the MDCF problem and develop a primal simplex algorithm that exploits the network structure of the problem. These results are extensions of those of the ordinary network flow problems. In conclusion, some related interesting problems are proposed for future research.