【作者】 何方国；

【导师】 齐欢；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2009， 博士

【摘要】 网络优化问题是生产管理和科学研究中经常遇到的问题，它属于运筹学的一个重要分支，主要研究在一组约束条件下如何有效地设计、安排、管理和控制一个网络系统，使这个网络系统总的效益最大化。在经济管理、工业工程、交通运输、通讯网络等诸多领域，网络优化都有广泛的应用。随着计算机科学应用和发展，运筹学与计算机科学相互渗透，推动着网络优化问题的应用范围不断扩大和深入。研究网络优化问题，如网络的最短路问题、最小费用支撑树问题、最小费用流问题及Steiner树问题等的算法设计与分析，已成为多个学科的一个重要研究方向。特别是随着Internet各种应用的发展，电子商务的日益普及，涉及到网络优化设计诸如网络基础设施建设、网络可靠性设计和智能路由设计等问题的研究需求更加迫切。网络优化的关键问题是研究面向网络的组合优化问题的求解技术，这方面已成为计算机科学技术领域的一个极为活跃的研究方向。在实际生活中，由于客观或主观的原因，我们所研究的问题存在着各种各样的不确定性，因而在解决实际问题时，我们必须对这些不确定因素给予考虑。由于不确定性的出现，对原有的网络优化模型提出了挑战，也为优化理论的进一步发展提供了新的机遇。本文主要就不确定条件下若干网络优化问题进行研究，提出了进一步的不确定性问题的模型，并给出了求解新模型的智能算法和拉格朗日松弛算法。其主要工作如下：利用随机理论研究了有约束的随机最短路问题，根据不同的决策准则，建立了三种不同的随机优化模型，提出了求解模型的退火遗传算法。通过算例验证了算法的合理性和有效性利用可信性理论和模糊环境下机会约束规划及其相关机会规划建模的思想，在模糊环境下建立了模糊度约束生成树问题的数学模型，并讨论了特殊情况下的等价问题。同时利用Prüfer数对生成树进行编码，设计了一个求解模糊度约束最小生成树问题的遗传算法，并将算法应用于TSP问题求解。研究了含随机变量的固定费用的运输问题，对运输问题数学模型进行了描述，通过Steiner树问题的转换证明了该问题是NP难问题。根据概率论知识，将不确定性问题转化成确定性的等价模型。利用运输图是一个生成树的特性，设计了基于生成树的遗传算法。研究了网络优化设计问题，提出了利用神经网络评估网络可靠性的方法，并给出了使用随机模拟技术产生训练样本的过程。在分析了粒子群算法的特性之后，设计了一个二进制粒子群算法求解本文的离散优化问题。仿真结果表明，该粒子群方法具有性能稳定和收敛速度快的特点，能较好地得到网络优化设计问题中的最优解。针对需求和供给不确定的物流网络的选址问题，按照成本最低化原则建立了不确定的数学模型，在假设随机变量服从正态分布的前提下，将不确定优化模型转化成确定模型，并采用拉格朗日松弛算法对模型进行求解，给出了次梯度优化求解算法的一般步骤。考虑到算法在实际求解过程中收敛速度较慢的问题，进一步对拉格朗日松弛算法进行了改进。最后，对全文的研究工作做了总结，并对今后要进一步开展的研究工作进行了展望。更多还原

【Abstract】 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.更多还原