Research On Models For Network Saturated Problem And Algorithms

In a transportation network or an emergency evacuation network, when flow is usually uncontrolled, the network is usually blocked by a saturated flow, so it is one of the important indices for studying the network under stochastic flow. And analysing and solving saturated flow problem have directive significances to the design and improvement of the network. But in the classic theory of the network flow, the flow in the network must follow the designed route to arrive the optimal value. Then the direction of flow is stochastic, so this problem can not be solved by the methods of classic theory, and we must introduce the new theory.Since the early 1990s when the theory of saturated flow is rising, it has been hot spot in the research of network programming, and a mass of investigations have been done by many scholars by now. But because of difficulties of the problem and the time of research is not long enough, the known theory have many defects inevitable such as simplicity of model and low efficiency of algorithm. We have not discussed the saturated flow in fuzzy environment and with cost weight until now. In order to correct the defect, we must generalize the known theory and propose some new model and algorithm.In 3^rd chapter, the saturated flow is generalized into fuzzy environment. We discuss the problem where the arc capacities are fuzzy numbers, propose the fuzzy network minimal flow and construct the corresponding mathematical model. In order to guarantee the efficiency of the known algorithm to minimal flow in fuzzy environment, we improve the known algorithm by using a new definition of fuzzy operation which is based on goal programming. Furthermore, one specific example are presented to test the improved algorithm. In 4th chapter, we discuss the saturated flow with cost weight. The minimum-cost saturated flow the saturated flow with cost weight is proposed, and we formulate the problem as an optimization problem over efficient set. and then construct the mathematical model of D.C. optimization. Furthermore, we use the improved algorithm of D.C. optimization to solve the minimum-cost saturated flow problem.