Research On Some Models And Algorithms Of Network Optimization Problems In Uncertain Condition

The network optimization problem belongs to an important branch of operations research, which is often studied by the field of administration and science. Its aim is to study how to plan and control network system in the condition of constraints, and make the system to reach the maximal profits. It arises in a wide variety of management science, industrial engineering, transportation and communication network. As the applications and developments of computer science, operations research and computer science is saturation one another, and the application ranges of network optimization problem become more and more enlargement and depth. The research of algorithms design and analysis of network optimization problem, such as the shortest paths of network, the smallest cost spanning trees, the smallest cost flows, Steiner tree and so on, has become an important research aspect of computer science. Especially as the development of different applications of Internet, electronic business increasingly get popularization, the research demand which comes down to network optimization design, such as the foundation establishment construction of network, the reliability design of network and the design of brainpower route and so on, becomes more imminence. The key problem of network optimization is the solving technology of combinatorial optimization problem of network, and which has become the most active research aspect of computer science technology and other fields.In some applications, there are various types of uncertainty by the reason of various factors, such as randomness and fuzziness. We must be taken into account it in the process of establishing mathematic model. On one hand, the existence of uncertainty challenges the classical optimization method, on the other hand, it provides a chance for the improvement of optimization theory. Therefore, research on network optimization of uncertainty is very critical reference for decision makers in real network construction. In this dissertation, we focus on some new problems arising from uncertain environment; propose some models and their corresponding algorithms about network optimization problems. The main work is as follows:(1) Based on probability theory, the dissertation studies the stochastic shortest path problem with constraints, and three types of models including the expected value model, the chance-constrained programming and the dependent-chance programming are formulated. At the same time, a hybrid intelligent algorithm merging anneal method for these models is developed, and some numerical examples are given for effectiveness of the algorithm.(2) According to the credibility theory and fuzzy theory, the models such as the expected value model, the chance-constrained programming and the dependent-chance programming with respect to the degree-constrained minimum spanning tree problem are established, and some equivalents of models are given in the special cases. To solve the minimum spanning tree problem we propose to use a genetic algorithm based on encoding with Prufer number. What is more, an example of solving traveling salesman problems with this algorithm is given with concrete steps.(3) The fixed-charged transportation problem with random variables is studied. The mathematical model for the problem under uncertain condition is established considering the chance constraints. Accorging to Steiner tree, the problem is proved to be NP-hard. Applying the property that a transportation network is a spanning tree, a genetic algorithm based on tree is adopted to solve our problems.(4) The problems of network optimization design are introduced. A method of estimating network reliability using neural network is proposed. By means of training a neural network with sample produced by stochastic simulation, it can fit the non-linear relationship between input and output. After analyzing the characteristic of particle swarm optimization, the binary improved particle swarm optimization algorithm for our problem is brought forward, and the detailed realization of the algorithm is illustrate. The numeric experiments show that the algorithm is simple, efficiency and converges quickly. In order to select logistics location under uncertain demand and supply; we set up a model of chance-constrained programming, and solved the problem by Lagrangian relaxation heuristic algorithm. The general algorithm steps based on sub-gradient optimization mathematics method are presented. In view of the weak convergence performance in this algorithm, the Lagrangean relaxation algorithm is modified in some points.Finally, a summary has been done for all discussion in the dissertation. The researchworks in future study are presented.