Research On The Minimum Cost Flow Problem In Manufacturing Network

Network flow problem is an important part of Network optimization. The minimum cost flow model is the most fundamental of all network flow problems. It has been extensively studied and fruitful results have been developed. As human activities and the production process are becoming increasingly complex, new restraints are emerging, which posed a challenge to the original network flow problems. Based on the above things, manufacturing network model is proposed, which consists of six kinds of vertices that express different types of additional constraints.The model and the minimum cost flow problem constitute a new class of network flow problems.Two typical representatives of these related problems are the minimum node with flow demands cost flow problem and the minimum distribution cost flow problem. They have wide applications in the real world.The main work is summarized as follows:Firstly, a new minimum cost flow algorithm is proposed for the minimum node with flow demands cost flow problem. The new algorithm makes all vertices stratified.The idea overcomes to shortcomings of the existing method which does not apply to the large network and reduces the size of network by order which is more conducive computerization. Numerical results show that the new algorithm has good performance.Secondly, a new algorithm is designed for the minimum distribution cost flow problem based on the classical minimum cost path algorithm. The algorithm labels vertexs three times.It firstly finds the minimum cost path, and then analyze the impact of special points to broaden flow value. Then we design the algorithm on the path.The paper gives an example to certificate the new algorithem.