Sensitivity Analysis Of Information Network Flow Problems

With the development of science and technology, a new way of information transmission—information network flow transmission is becoming the mainstream, and the research of information network theory has become a hot issue as well. But topology of information network is not fixed, so studying the effects of information network structure's changes on t he optimal solution of network flow is very important to the study of information network's stability.This dissertation studies the information network, which focusing on the sensitivity analysis of information network flow problem. The main work and achievements are given below:1.To solve the arc tolerance of static network maximum flow problem, an algorithm which can find the arc tolerance's upper and lower bound of every arc in the maximum flow problem is proposed based on the analysis of the properties of maximum flow and minimum cut. In addition we show that different maximum flows and minimum cuts lead to the same arc tolerance of maximum flow with the algorithm.2.We improve the original maximal dynamic flow algorithm in the dynamic network maximum flow problem. Based on the analysis of maximal dynamic flow algorithm, we propose an algorithm to solve the vital arc of maximal dynamic flow problem, and make a comparison among it, original algorithm and the algorithm based on the definition. After that we construct an auxiliary network to solve the vital node of maximal dynamic flow problem.3.We analyze the properties of quickest flow problem in dynamic network and illustrate the relationship between quickest flow problem and maximal dynamic flow problem. Based on t hese works, we propose an algorithm to solve the quickest flow problem and vital arc of quickest flow problem. Then, numerical experiments are given to show the efficiency of the proposed algorithm by comparing our algorithm with the algorithm based on the definition.