Matlab最优化理论中的最短路问题
时间:2017-06-16 16:50 来源:毕业论文 作者:毕业论文 点击:次
| 摘要在日常生活和生产中，我们经常碰到各种各样的图，如交通图、管道系统图等等。在优化理论中所谓图就是上述各类图的抽象和概括，用图来描述我们所研究的对象，以及这些对象之间的相互联系。例如，许多生产管理、工程设施、计划安排、交通运输等问题都可以用图形来描述。 所谓最短路问题就是在一个加权图中，寻找某一点到另一点之间的最短路径。本课题的最重要的研究内容就是最短路问题的基本理论和二种算法，选用计算机软件实现算法，并能运用这些理论解决实际生活中的某些实际问题。 本课题论文涉及的最短路的算法有Dijkstra算法、Floyd算法。其中Dijkstra算法主要应用于求解某指定点到其他点的最短路，Floyd算法是目前求解任意两点间的最短路径的最优方法。 在实际网络中，权数还可以是时间、费用等等，如选址、管道铺设、投资、某些整数规划和动态规划等问题都可归结为最短路问题。所以研究最短路问题具有深远的现实意义。 关键词：最短路问题；Dijkstra算法；Floyd算法；Matlab；10242 ABSTRACT In daily life and production, we often encounter a variety of maps, such as communication maps, ductwork maps, and so on. Optimization of the so-called theory of the map is the map of the above types of abstraction and generalization, using maps to describe our research targets and the affiliation between those objects. For example, some production management, engineering facilities, the arrangement, transportation and other issues can be described by graphics. The shortest path problem is that in a weighted graph, find the shortest path from some or other point to another point. The major content of the disquisition is to study the basic theory and algorithms of the shortest path.,then we can choose computer softwares to carry out those algorithms, and will be able to use these theories to solve real-life problems of certain. The disquisition involves the algorithm of the shortest path is Dijkstra’s algorithm, Floyd algorithm, Warshall’s algorithm. Dijkstra’s algorithm which is mainly used for finding the shortest path from a point to the other point. Floyd algorithm is the optimal method to find the shortest path between arbitrary two points, Warshall’s algorithm can be applied to the negative weighted map of the shortest path problems. In the actual network, the weights can also be time, cost and so on, such as location, pipeline laying, investment, some integer programming and dynamic planning issues can be attributed to the shortest path problems. Therefore, to study the short path problems has far-reaching practical significance. Key words : Short circuit；Dijkstra’s algorithm；Floyd’s algorithm；Matlab； 目 录 1 图的基本概念 1 1.1 图的概念 1 1.2 图的矩阵表示 6 2 最短路问题算法及其MATLAB实现 11 2.1 最短路问题 11 2.2 Dijkstra算法 12 2.3 Floyd算法 18 3 最短路问题的应用 23 3.1 设备更新问题 23 3.2 多阶段存储问题 27 4 总结 30 致谢 30 参考文献 31 附录 32 1 图的基本概念 图论是近十年来得到蓬勃发展的一个新兴的数学分支，它的理论和方法在许多领域中得到广泛的应用并取得了丰硕的成果。我们可以用图论的方法来构造模型并求解某些线性规划、整数规划可以解决的资源分配、运输问题、设备更新问题和储备问题，且由于图的结构的直观性，更有助于我们分析和描述问题。 (责任编辑：qin) |