基于不确定图的网络优化模型及应用研究

发布时间：2020-07-24 05:16

【摘要】：随着社会的不断发展,图论与网络优化的应用越来越广泛,大量的实际问题可抽象为图与网络优化的问题。本文主要采用图论、不确定理论、不确定规划、最优化理论等知识与方法研究不确定图及基于不确定图的网络优化问题。在深入学习图论及不确定理论的基础上,完善了不确定图的一般概念及相关性质定理的推导与证明,设计了求解不确定图连通度的改进Prim算法。根据不确定规划,从三种不同的建模机理,建立了基于不确定图的六种网络优化模型,并设计了它们的求解模拟算法。在应用实例中,针对地下物流系统进行了物流节点的选址及其网络路线规划。主要工作如下:(1)不确定图的定义、矩阵表示、及相关性质定理的研究。利用不确定理论将随机、模糊、粗糙及它们交叉不确定性因素进行了统一。首先,类比边结构不确定图的定义,借助邻接矩阵的形式,提出了不确定图的定义,它统一了边结构不确定图、点结构不确定图与确定图的概念。然后,提出了利用不确定测度矩阵对不确定图进行统一标识,并分别在确定图和不确定图两种情况下,对不确定测度矩阵及邻接矩阵、关联矩阵进行了对比。其次,分析并证明了不确定图的阶数、边数的性质及其不确定分布。最后,基于Prim算法的思想,以不确定图的阶数的优先级为贪心准则,设计了改进的Prim算法求解不确定图的连通度,并利用数值实例验证了算法的合理性。(2)基于不确定图的网络优化模型及算法的研究。首先,在不确定图的基础上,分析了基于不确定图的网络的两种类型:图结构不确定、图属性不确定。接下来,在“图结构不确定但属性确定的网络”的前提下,进行网络优化模型的构建。然后,根据不确定规划中三大建模机理:期望值规划、相关机会规划、机会约束规划,分别针对最短路及物流选址问题,建立了基于不确定图的期望值最短路优化模型、最大可能性最短路优化模型、α-最短路优化模型、及期望值物流选址模型、最大可能性物流选址模型、α-物流选址优化模型。其次,从多个角度对构建的网络优化模型进行了对比分析。最后,类比随机模拟及模糊模拟方法,设计了求解模型的模拟算法,即通过模拟算法模拟不确定函数将不确定图的网络优化模型转化为确定性网络优化模型;再用相应的算法求解。(3)针对缓解城市交通拥堵的新型系统——地下物流系统,进行物流节点选址及最佳隧道网络规划的实例研究。首先,基于对不确定图及不确定图的网络的研究,只要将区域中心位置看作不确定图中的顶点、两物流节点对应的区域有货运关系看作两顶点间有边,那么地下物流系统规划问题可抽象为不确定图的网络优化问题。然后,基于物流节点不确定,建立不确定图中顶点和边的不确定测度的计算模型,利用各区域的实时交通拥堵指数刻画在各区域被修建地下物流节点的不确定测度,两地间的货运量刻画边的不确定测度。最后,构建最大可能性物流选址模型,并基于本文设计的模拟算法及交替选址-分配法对模型求解,解决了地下物流系统的物流节点选址及最佳隧道网络规划。
【学位授予单位】：西南石油大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

基于不确定图的网络优化模型及应用研究

图４－１不确定图的网络类型逡逑目前大部分不确定的网络，均为第一类不确定网络

基于不确定图的网络优化模型及应用研究

各级物流节点分布示意图

基于不确定图的网络优化模型及应用研究

地下物流系统的最佳隧道网络规划图

【参考文献】