【作者】 刘强；

【导师】 赵庆祯；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2008， 博士

【摘要】 网络流理论是图论的一个重要分支,是研究网络上相关优化问题的理论和方法。1956年,L.R.福特和D.R.富尔克森等人给出了解决在给定的网络上寻求两点间最大运输量这类问题的算法,从而奠定了网络流理论的基础。网络流理论发展至今,已普遍应用于通讯、运输、电力、工程规划、任务分派等众多领域。为了更好的解决现实中的问题,网络流理论也在不断发展中,先后出现了具有增益的流、分派与匹配、网络优化的拉格朗日松弛法、多商品流、网络流的分解与合并等新的理论和方法。但以上研究都是在网络参数和拓扑结构固定的网络上进行的优化,而实际环境中的网络系统受多种因素影响往往会表现出随机性,所以传统网络流理论在具体应用时与实际情况会有一定的偏差,如果能在随机环境下对网络流进行优化,对提高网络流理论的实用性和针对性均有重要意义,这个问题已越来越引起关注。目前主要从3个方面将随机因素引入网络流理论:1.令网络的权值为随机变量;2.假设网络的拓扑结构为随机的;3.假设网络中各边的容量为随机变量,提出了随机型流量网络(Stochastic Flow Network)的概念。随机型流量网络上的网络流理论的研究目前处于起步阶段,研究主要集中在:设计算法寻找网络流在网络容量状态X下的最大流V(X)能满足接收端需求d的网络容量状态的临界点d-MCs或d-MPs,并根据这些点计算随机型流量网络的可靠性。但当随机型流量网络的容量处于非临界状态时,对网络流进行分配优化的研究还较少见,论文中将针对不同问题选取特定优化目标,研究网络流不处于最大流状态V(X)时的优化问题。论文主要研究了以下几方面的内容:1.以目前使用较多的两种随机型流量网络模型(网络节点可靠,单商品流,多发送端,多接收端的网络模型和网络节点不可靠,多商品流,多发送端,多接收端的网络模型)为基础,研究当网络流不处于最大流状态V(X)时如何对网络流流量进行分配优化。选定满足接收端需求的网络流可靠性为目标,建立整数随机规划模型。针对模型的特点,设计相应的算子,采用遗传算法对优化模型进行求解,并与使用Lingo软件方法求解得到的结果进行比较,分析两种求解方法的优缺点及其适用的问题。2.文中将网络流传输时间和成本从约束条件转化为整体优化目标,并结合网络流可靠性这一主要目标,研究随机型流量网络上网络流的多目标优化问题。为求解建立的多目标优化模型,对NSGA-II方法做出如下改进:改进2-联赛选择算子的比较规则,将模拟2进制交叉算子改进为单点复合交叉算子,改进精英保留策略,使用改进后的算法对模型进行求解,经过测试,得到的结果从多方面优于原NSGA-II算法。3.已有的随机型流量网络可靠性的算法,由于涉及到最大流最小割原理和Ford-Fulkerson算法等传统网络流理论,故不得不假设随机型流量网络中的所有变量为离散型变量。本文中由于采用了单目标/多目标遗传算法对网络流进行优化,故不受上面的限制。因此文中扩展随机型流量网络的容量为连续型随机变量,各条边上分配的网络流量为连续实数,建立连续型的多目标网络流优化模型,为了处理包含连续型变量的等式约束,对等式约束增加逼近参数,将等式约束分解为两条不等式约束以逼近方式处理。采用改进后的NSGA-II对处理后的优化模型进行求解。通过测试,可快速求出连续型多目标优化模型的Pareto前沿。4.论文对网络中各节点包含随机需求的网络流多目标优化问题进行了研究。针对这种复杂随机情况下的网络流优化问题建立了机会约束多目标随机规划模型。对建立的随机规划模型进行预处理,将部分以置信度表示的约束条件转化为对应的确定性等价约束。采用随机模拟方法对优化模型的其余部分进行处理。结合前面提到的改进后的多目标遗传算法,提出一个基于随机模拟的多目标遗传算法对机会约束随机规划模型进行求解。通过算例测试,可以求得优化问题的Pareto解集。更多还原

【Abstract】 Network flow theory is an important branch of Graph Theory, and it is the theory of studying optimization problems upon network. In 1956, L.R. Ford and D.R. Fulkerson propound the algorithm to solve the problem of seeking maximal transportation quantity between two nodes on the network. From then on, network flow theory was founded and developed. Network flow theory now has been widely applied to communication, transportation, power transmission, engineering programming and other fields. In order to solve the practical problem better, some new network flow theory were propounded, such as assignment and matching, LaGrange relaxation of network optimization, multi-commodity flow, network flow’s decomposition and combination and so on. But above research were all based on network whose parameters and topology structure were determinate. Network system in practical circumstance often presents randomicity because of influence of some factors. So it often causes some errors when apply traditional network flow theory to practical problems. It is significant for improving network flow theory’s practicability to optimize network flow in stochastic circumstance. This question has drawn attention.Presently, stochastic factor has been introduced into network flow theory from three aspects: 1. suppose arcs’weights in network are stochastic variables; 2. suppose network’s topology structure is stochastic; 3. suppose arcs’capacities are stochastic variables, and propound the conception of stochastic flow network. Previous research on network flow theory upon stochastic flow network focused on designing algorithms to seek network’s critical capacity states (d-MCS or d-MPs) and computing network’s reliability according to these states. But when stochastic flow network’s capacity is not critical state, research on network flow optimization is few. So author selected different objectives according to different circumstance and studied optimization problems under the condition that network flow was not maximal flow V(X). The article mainly contains four contents as follows:1. Basing two frequently used stochastic flow network models (network model with reliable nodes, single-commodity flow, multi-source nodes, multi-sink nodes and network model with unreliable nodes, multi-commodity flow, multi-source nodes, and multi-sink nodes), author studied how to optimize network flow when network flow was not maximal flow V(X).Author selected network flow’s reliability as objective, and constructed integer stochastic programming model. According to model’s characteristics, genetic algorithm was designed to solve constructed model. Author compared genetic algorithm’s result with that obtained by Lingo, and analyzed advantage and disadvantage of these two methods.2. Author transformed network flow transportation time and transportation cost from constraints to objectives, and studied multi-objective optimization problem upon stochastic flow network. In order to solve constructed model, author improved NSGA-II’s tournament selection operator, simulated binary crossover operator and elitist strategy. Tested by examples, improved algorithm was better than former NSGA-II.3. Existed algorithms on computing stochastic flow network’s reliability contained maximal flow minimal cut theory, Ford-Fulkerson algorithm and other traditional theory, so the variables in stochastic flow network was restricted to be discrete variables. Because of using genetic algorithm to optimize network flow in paper, above restriction was invalid and variables in model could be continuous. In order to deal with equation constraints containing continuous variables, author added a parameter and decomposed an equation constraint to two inequation constraints. Author solved decomposed model by improved NSGA-II. Tested by an example, algorithm can figure out the Pareto frontier of continuous optimization model.4. Network flow optimization problem was studied upon network which nodes’demand was stochastic. Author constructed chance constrained programming model and transformed confidence level constraints to corresponding determinate constraints and dealt with other constraints by stochastic simulation method. A multi-objective genetic algorithm based on stochastic simulation was propounded to solve constructed model. Tested by examples, the algorithm can figure out model’s Pareto solutions.更多还原