不确定随机网络下的度约束最小生成树问题

发布时间：2018-11-19 12:40

【摘要】：最小生成树问题是网络优化中的基本问题之一,在通信网络、交通网络、物流网络等领域中有广泛的应用。电路设计中为了减小节点的脆弱性,Narula和Ho在1980年提出度约束最小生成树问题。该问题旨在寻找最小权重的生成树,且每个节点的度满足给定的约束的要求。在经典网络中,所有权重都是已知的常数,因此可以利用经典的算法求解。然而在现实网络中,由于非决定性因素的存在,导致网络中的权重是非决定性的。为了描述非决定性的网络,Frank和Hakimi在1965年首先提出了随机网络的概念,目的是描述通信网络的随机现象。在2010年,Knowles和David首先把度约束最小生成树问题引入到随机网络中,但该方法对权重的估计十分依赖历史数据。然而在现实网络中,很多网络是没有历史数据的,因此Liu在2010年提出了不确定网络的概念。本文主要研究了不确定网络下的度约束最小生成树问题。基于不确定变量的不同的比较原则,我提出了三种不确定规划模型:不确定期望值度约束最小生成树模型,不确定?-度约束最小生成树模型和不确定最大机会度约束最小生成树模型。论文运用改进的遗传求解模型,并给出数值算例。在实际生活的网络中,有的权重没有历史数据,有的权重有历史数据,因此不确定性和随机性往往同时出现在一个复杂的网络。最近,Liu在不确定网络的基础上进一步提出了不确定随机网络的概念。本文首次研究了不确定随机网络下的度约束最小生成树问题,提出了一个理想机会分布的概念。为了寻找与理想机会分布最接近的度约束生成树作为度约束最小生成树,建立了一个不确定随机规划模型,最后论文给出了数值算法求解该模型。
[Abstract]:The minimum spanning tree problem is one of the basic problems in network optimization. It is widely used in communication network, transportation network, logistics network and so on. In order to reduce the vulnerability of nodes in circuit design, Narula and Ho proposed the minimum spanning tree problem with degree constraints in 1980. The aim of this problem is to find the spanning tree of minimum weight, and the degree of each node satisfies the requirement of given constraints. In classical networks, all weights are known constants, so the classical algorithm can be used to solve the problem. However, in real networks, the weights in networks are indeterminate due to the existence of indeterminate factors. In order to describe indeterminate networks, Frank and Hakimi first proposed the concept of stochastic networks in 1965, the purpose of which is to describe the stochastic phenomena of communication networks. In 2010, Knowles and David first introduced the degree constrained minimum spanning tree problem into stochastic networks, but the estimation of weights in this method relies heavily on historical data. However, in real networks, many networks do not have historical data, so Liu put forward the concept of uncertain networks in 2010. In this paper, we study the minimum spanning tree problem of degree constraints in uncertain networks. Based on the different comparison principles of uncertain variables, I propose three uncertain programming models: uncertain expectation degree constrained minimum spanning tree model. Uncertainty-degree constraint minimum spanning tree model and uncertain maximum opportunity constraint minimum spanning tree model. In this paper, an improved genetic solution model is used and a numerical example is given. In real life networks, some weights have no historical data, some weights have historical data, so uncertainty and randomness often appear in a complex network at the same time. Recently, Liu put forward the concept of uncertain stochastic network on the basis of uncertain network. In this paper, the degree constrained minimum spanning tree problem for uncertain stochastic networks is studied for the first time, and a concept of ideal opportunity distribution is proposed. In order to find the degree constraint spanning tree which is closest to the ideal chance distribution as the minimum spanning tree of degree constraint, an uncertain stochastic programming model is established. Finally, a numerical algorithm is presented to solve the model.
【学位授予单位】：华北电力大学(北京)
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】