[理学]1研究报告-最短路径.pdf

科学技术成果鉴定资料之一 系统全局最短路径规划的可视化研究 研究报告 河南科技大学 系统科学与工程研究所 2007 年 7 月 15 日 《系统全局最短路径规划的可视化研究》 研究报告 目录 第1 章 项目背景 2 第2 章 理论分析 3 2.1 物理化学原理 3 2.2 数学原理 3 2.3 力学原理 7 第3 章 试验研究 9 3.1 试验研究的工作进展 9 3.2 可视化路径的探索试验 10 3.3 最短路径可视化仪的研制 13 3.4 试验结果分析 17 第4 章 最短路径可视化仪的应用 23 4.1 试验操作步骤 23 4.2 应用案例研究 24 第5 章 总结 32 参考文献 33 河南科技大学 系统科学与工程研究所 - 1 - 《系统全局最短路径规划的可视化研究》 研究报告 第 1 章 项目背景 本项目为多学科交叉学科群（系统科学学科）的集成探索项目，由河南科技大学系 统科学与工程研究所按照我国建设节约型社会的政策方针所需的技术支撑而自拟的科 技发明制作类探索性项目，旨在通过集成物理化学、运筹学、系统工程和设施规划等多 门交叉学科于一体，使得在系统工程上复杂的数学规划求解问题(The Minimal Steiner Tree Problem)能够通过简单易行的试验方案解决，并寻求其在工程实践或社会领域的应 用。 数世纪以来，系统最优路径研究一直是数学界和工程界的研究热点。早在18世纪， 伟大的数学家 Fermat 提出了在三角形中有一点到三顶点距离和为最小（Fermat 点），揭 开了系统整体最短路径研究的序幕。19 世纪初，瑞士数学家 Steiner 将其推广到由固定 点和虚设点（即 Steiner 点）组成的非线性规划难题，从而引发了许多启发式智能进化 算法来求解 Steiner Minimum Tree (SMT：最小 Steiner 生成树)问题。然而，如何结合SMT 问题，给出虚设点和求解最小生成树一直是运筹学和网络研究的热门课题。 作为上述理论的延伸，目前，国内外对最短路径问题的研究可以分为两类,一类是 Dijkstra 提出的网络中两结点之间最短路问题以及一点到多结点的最短路问题,它可以 扩展为电子商务下零售企业运输网络的路线规划问题。另一类是多个结点对之间的最短 路径，它涉及多个领域的发展，比如城市交通问题，物流配送及成本核算，城市的规划、 建设和管理以及现代电力和通讯网络的合理规划。然而，以上最短路径的研究及应用多 是用来求解在节点存在并不考虑添加其他节点的约束条件下最优路径问题，得到了从限 定始点到预计终点的局部最优路径，它们是在节点位置已定的情况下对路径的最优计 算。而对于用科学的方法探索成膜的状态特征，利用表面活性剂溶液的成膜特性通过添 加中间节点的方法解决实际问题的研究在国内尚属空白。 本项目的研究路线是通过可视化试验方法将运筹学、物理化学和系统工程方法融合 为一体，研发出试验装置并应用于工程实践中，方便地解决复杂的系统总体最短路径规 划问题，使得系统工程求解的复杂数学问题变成简单易行的试验解决方案，最终使得系 统构建的成本降低。本研究将致力于解决以上问题并设计提供一种系统最短路径规划的 可视化装置，可视化实验本身不仅可以确定不规则对象系统的内部节点的数目和位置， 而且试验结果将通过增加一定的结点给出总体最短路径的可视方案。 本项目由河南科技大学系统科学与工程研究所独立完成。 河南科技大学 系统