不确定网络规划中的图论问题的研究及应用一圈问题

论文摘要

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

论文目录

摘要

Abstract

第1章绪论

1.1 研究目的和意义

1.1.1 研究目的

1.1.2 研究意义

1.2 国内外研究现状

1.2.1 图论的研究概况

1.2.2 不确定网络规划的研究概况

1.2.3 不确定网络规划中圈问题的研究概况

1.3 研究内容和研究方法

1.3.1 研究内容

1.3.2 研究方法及技术路线

1.4 研究成果和创新点

1.4.1 研究成果

1.4.2 创新点和特色

1.5 论文结构安排

第2章预备知识

2.1 图论基本概念

2.1.1 图的基本概念及矩阵表示

2.1.2 生成树的相关概念和矩阵表示

2.2 圈

2.2.1 基本概念及其性质

2.2.2 圈的生成方法

2.2.3 矩阵表示

2.3 网络规划中的圈问题

2.3.1 基本概念

2.3.2 基本模型与算法

2.4 不确定理论

2.4.1 不确定测度

2.4.2 不确定变量

2.4.3 不确定分布

第3章基于不确定图生成树的圈问题研究

3.1 问题的提出

3.2 不确定图的生成树

3.2.1 边结构不确定图生成树

3.2.2 点结构不确定图生成树

3.2.3 不确定图的生成树测度矩阵

3.3 基于不确定图生成树的圈

3.3.1 不确定图的圈数及圈测度矩阵

3.3.2 不确定图圈环边数和连通度概念及其算法

3.3.3 数值实例

第4章基于测度矩阵的不确定网络规划中圈问题的模型及算法

4.1 问题的提出

4.2 不确定网络中的欧拉圈问题的模型及算法

4.2.1 建模原理和思想

4.2.2 不确定网络中的欧拉圈模型

4.2.3 基于模拟算法和EDMONDS算法的不确定欧拉圈模型求解

4.3 不确定网络中的哈密尔顿圈问题的模型及算法

4.3.1 建模原理和思想

4.3.2 不确定网络中的哈密尔顿圈模型

4.3.3 基于模拟算法和二边逐次修正法求解不确定哈密尔顿圈模型

第5章基于不确定圈问题的旅游路线规划

5.1 问题背景

5.2 旅游路线规划问题抽象为不确定图中的圈问题

5.2.1 旅游路线规划问题

5.2.2 不确定图中圈问题的抽象

5.3 基于旅游景点不确定的顶点及边的不确定测度计算

5.3.1 网络图顶点存在的不确定测度的计算

5.3.2 网络图边存在的不确定测度的计算

5.4 最大可能性旅游路线规划

5.4.1 模型的建立

5.4.2 模型的求解

5.4.3 求解结果分析

第6章结论与进一步的工作

6.1 结论和认识

6.2 进一步的工作

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果

文章来源

类型: 硕士论文

作者: 包敏

导师: 钟仪华

关键词: 不确定网络规划,不确定图,圈问题,生成树,测度矩阵

来源: 西南石油大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西南石油大学

分类号: O157.5

DOI: 10.27420/d.cnki.gxsyc.2019.000659

总页数: 61

文件大小: 3341K

下载量: 28

不确定网络规划中的图论问题的研究及应用一圈问题

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢