Uncertain Random Network Optimization

In many practical problems, we may get many types of indeterminate information,including random information or uncertain information. If the weights of the edges of the network are random variables, then we get a random network; if the weights of the edges of the network are random variables, then we get an uncertain network.In a complex network, the weights of some edges are random variables, and the weights of some other edges are uncertain variables. In this case, the network can only be modeled by uncertain random network. Due to the random factors and uncertain factors, the algorithms of the classical networks do not work well in the uncertain random networks. Even those methods for random networks or uncertain networks find many diffculties in solving the optimization problems of the uncertain random networks. Thus, it is of great significance to design new methods for the uncertain random networks.This thesis investigates the shortest path problem, the minimum spanning tree problem and the maximum flow problem of the uncertain random networks by using the chance theory. Firstly, the ideal chance distribution of the shortest path is derived,and three models are proposed to find the optimal real path in the uncertain random network according to the di?erence measures of the divergence between the ideal path and the real path, which are the area between their chance distributions, the distance between their chance distributions, and the relative entropy of their chance distributions. Secondly, the ideal chance distribution of the minimum spanning tree is derived,and three models are proposed to find the optimal real spanning tree in the uncertain random network according to three di?erence measures of the divergence between the ideal spanning tree and the real spanning tree. Lastly, the ideal chance distribution of the maximum flow is derived, and two models are proposed to find the optimal real flow in the uncertain random network according to two di?erence measures of the expected value constraint and the chance constraint. This thesis also proposes some algorithms and numerical examples of optimization problems of the uncertain random network to illustrate the e?ectiveness of the models and the algorithms.The contributions of this thesis are:? It derives the chance distribution of the ideal path, and presents three models to find the optimal real path in the uncertain random network. In addition, it designs some algorithms to solve the models, and illustrates the algorithm via some numerical examples.? It derives the chance distribution of the ideal spanning tree, and presents three models to find the optimal real spanning tree in the uncertain random network.In addition, it designs some algorithms to solve the models, and illustrates the algorithm via some numerical examples.? It derives the chance distribution of the ideal flow, and presents two models to find the optimal real flow in the uncertain random network. In addition, it designs some algorithms to solve the models, and illustrates the algorithm via some numerical examples.