论文部分内容阅读
随着社会的不断发展,网络规划与图论广泛应用于各个领域。大量的实际问题可抽象为网络规划问题,而圈问题是解决一些重要的网络规划问题的基础问题。本文主要采用图论、不确定理论、网络规划、最优化理论等知识与方法研究基于不确定图生成树的圈及基于测度矩阵的不确定网络规划中的圈问题。在深入学习图论及不确定理论的基础上,推广了不确定图生成树的一般概念和其矩阵表示方法及相关定理,并基于它们提出了不确定图的圈的一般概念、矩阵表示方法及其性质定理;设计了基于Prim算法的不确定图的圈及圈的环边连通度的计算方法。根据不确定理论和网络规划等知识,建立了基于测度矩阵的不确定网络规划中的两类圈问题模型,并设计了它们的求解算法。针对不确定网络规划中的旅游路线规划问题,利用提出的圈问题理论和方法,对它们的最佳路线进行了规划,规划结果表明本文提出的理论和方法是正确和合理的。主要工作如下:(1)不确定图生成树的定义和相关定理及矩阵表示的研究。利用不确定测度,在边结构不确定图和点结构不确定图的基础上,首先分别提出了边结构不确定图生成树和点结构不确定图生成树的定义,这些定义能够根据边结构或点结构不确定图的测度矩阵的形式和特征判定不确定图是否为生成树;然后,类比不确定图的测度矩阵表示方法,提出了不确定图生成树测度矩阵对边结构不确定图生成树和点结构不确定图生成树进行统一标识;最后分析对比了这两类不确定图生成树测度矩阵。(2)不确定图的圈的相关概念和定理及矩阵表示的研究。利用图论中圈的构成性质,基于提出的不确定图生成树,首先类比确定图基本圈数和圈数的计算方法,提出并证明了不确定图基本圈数和圈数计算的定理;然后类比确定图的完全圈矩阵表示方法,提出了用测度矩阵表示不确定图的圈,能直观提供不确定图各圈的构成信息;其次基于圈测度矩阵,分别给出了不确定图圈环边数和连通度的定义;最后借助Prim算法的思想,以不确定图生成树的阶数优先级为贪心准则,设计了求解不确定图圈及圈的环边连通度的算法,并进行了数值实例验证了算法的合理性。(3)基于测度矩阵的不确定网络规划中圈问题模型及算法的研究。首先,类比传统的欧拉圈和哈密尔顿圈问题的建模思想,在不确定图的基础上,利用测度矩阵建立了基于测度矩阵的不确定网络规划中的欧拉圈模型和哈密尔顿圈模型;然后利用模拟算法将图结构不确定的欧拉圈和哈密尔顿圈问题转化为图结构确定的欧拉圈和哈密尔顿圈问题,再基于确定欧拉圈的Edmonds算法和确定哈密尔顿圈的二边逐次修正法,分别设计了不确定网络规划中的欧拉圈模型和哈密尔顿圈模型的求解算法。(4)不确定网络规划中旅游路线规划的实例研究。首先基于不确定图的圈和图结构不确定的网络规划中圈问题的研究,若将景点和省会城市所在位置看作网络图的顶点,将实际行驶时间与能接受平均行驶时间的比值关系看作两顶点间存在边的关系,则旅游路线规划问题可抽象为不确定网络中的圈问题;然后,基于旅游者偏好的不确定性,建立不确定网络中顶点和边的不确定测度的计算模型,分别利用旅游者到景点的实际花费时间和能接受的平均花费时间、实际行驶时间和能接受的平均行驶时间刻画顶点存在的不确定测度和边存在的不确定测度;最后构建最大可能性的最佳旅游路线规划模型,利用(3)中的方法获得了旅游者最大可能性的最佳旅游路线,其结果表明本文所提出的方法是合理的。