The Minimum Cost Flow Problem And Its Extensions

This paper is divided into two parts,the first part is the sensitivity analysis of minimum-cost flow,the second part established the dynamic minimum-cost flow model and given a method to solve it.In Chapter1,we make a brief introduction to the basic concepts and necessary knowledge about network flows so to make the necessary preparations for the next chapters.In Chapter2,first we introduced the Current researches at home and abroad.Then we consider whether it can maintain the original plan when the cost of one side is adjusted, that is discussing the sensitivity of the minimum-cost flow.Minimum-cost flow problem is a linear programming problem;it can be directly discussed with the linear programming algorithm.So its sensitivity analysis can also use the traditional simplex tableau to solve.If we does not consider the network characteristics of this programming problem,but calls the simplex tableau of the general linear programming algorithm,the efficiency is very poor.According to the network characteristics of the minimum-cost flow problem,we design a different algorithm from the traditional one,experimental results show that this algorithm efficiency greatly.Chapter 3 established the dynamic minimum-cost flow model and given a method to solve it.Considering of the time effect on each parameter in the minimum cost flow problem,first we give the definitions of each parameter to propose the model of the dynamic minimum cost flow problem.On such directed network,the flow can wait at any medial points for a period of time;The capacity of arcs and medial points are time varying,the cost of the flow transmitting throw an arc are time varying too.Then we introduce the concept of dynamic minimum cost augmented chains,and prove some related theorems.At last,we proposed an algorithm to solve the dynamic minimum cost flow problem.