《《最短路问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《最短路问题》PPT课件.ppt（35页珍藏版）》请在金锄头文库上搜索。
1、应用数学模型应用数学模型2009年年4月月应应用用数数学学模模型型图论及其应用 图论概论图论概论 最短路问题最短路问题 行行 遍遍 性性 问问 题题 1、中、中 国国 邮邮 递递 员员 问问 题题 2、推、推 销销 员员 问问 题题应应用用数数学学模模型型概论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展
2、，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 应应用用数数学学模模型型图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。 应应用用数数学学模模型型哥尼斯堡七桥问题哥尼斯堡七桥问题在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题归结为：问题归结为：从任一点出发一笔画
3、出七条线再回到起点 问题问题：要从这四块陆地中的任何一块开始通过每一座 桥正好一次，再回到起点。一笔画的一个判定法则一笔画的一个判定法则：这个图是连通的，且每个点都 与偶数线相关联 应应用用数数学学模模型型图与网络图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。 基本问题：基本问题： 匹配问题匹配问题 最小费用流问题最小费用流问题 最大流问题最大流问题 最短路问题最短路问题应应用用数数学学模模型型例例1 最短路问题最短路问题 （SPPshortest path pr
4、oblem） 一名货柜车司机奉命在最短的时间内将一车货 物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种 行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问 题相当于需要找到一条从甲地到乙地的最短路最短路。 应应用用数数学学模模型型例例2 公路连接问题公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小总成本最小？应应用用数数学学模模型型例例3 指派问题指派问题 （a
5、ssignment problem）一家公司经理准备安排名员工去完成项任务， 每人一项。由于各员工的特点不同，不同的员工去完成同 一项任务时所获得的回报是不同的。 如何分配工作方案可以使总回报最大总回报最大？应应用用数数学学模模型型例例4 中国邮递员问题中国邮递员问题 （CPPchinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线最短的投递路线 （从邮局出发，经过投递区内每条街道至少 一次，最后返回邮局）？ 管梅谷教授 1960年首先提出的 应应用用数数学学模模型型例例5 旅行商问题旅行商问题 （TSPtraveling sal
6、esman problem） 一名推销员准备前往若干城市推销产品。 如何为他（她）设计一条最短的最短的旅行路线 （从驻地出发，经过每个城市恰好一次， 最后返回驻地）？ 应应用用数数学学模模型型例例6 运输问题运输问题 （transportation problem）某种原材料有个产地，现在需要将原材料从产 地运往个使用这些原材料的工厂。 假定个产地的产量和家工厂的需要量已知， 单位产品从任一产地到任一工厂的运费已知， 那么如何安排运输方案可以使总运输成本总运输成本 最低？最低？ 应应用用数数学学模模型型两个共同的特点：两个共同的特点： 1、目的都是从若干可能的安排或方案中寻求 某种意义下的最优
7、安排或方案，数学上把 这种问题称为最优化或优化(optimization) 问题； 2、易于用图形的形式直观地描述和表达，数学 上把这种与图相关的结构称为网络(network)。 与图和网络相关的最优化问题就是网络最优化或 称网络优化网络优化 （netwok optimization）问题。）问题。应应用用数数学学模模型型应应用用数数学学模模型型最短路问题最短路问题基本内容基本内容2、会用、会用Matlab软件求最短路软件求最短路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图、图 论论 的的 基基 本本 概概 念念2、最、最 短短 路路 问问 题题 及及 其其 算算 法法3、最、
8、最 短短 路路 的的 应应 用用4、建模案例：最优截断切割问题、建模案例：最优截断切割问题5、实验作业、实验作业应应用用数数学学模模型型图图 论论 的的 基基 本本 概概 念念一、一、 图图 的的 概概 念念1、图的定义、图的定义2、顶点的次数、顶点的次数 3、子图、子图二、二、 图图 的的 矩矩 阵阵 表表 示示1、 关联矩阵关联矩阵2、 邻接矩阵邻接矩阵返回返回应应用用数数学学模模型型定义定义有序三元组G=(V,E, )称为一个图图.图的定义图的定义应应用用数数学学模模型型定义定义定义定义应应用用数数学学模模型型应应用用数数学学模模型型应应用用数数学学模模型型顶点的次数顶点的次数应应用用数
9、数学学模模型型例例 在一次聚会中，认识奇数个人的人数一定是偶数。应应用用数数学学模模型型子图子图应应用用数数学学模模型型关联矩阵关联矩阵注：假设图为简单图返回返回应应用用数数学学模模型型邻接矩阵邻接矩阵注：假设图为简单图应应用用数数学学模模型型返回返回应应用用数数学学模模型型最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路返回返回应应用用数数学学模模型型基基 本本 概概 念念应应用用数数学学模模型型返回返回应应用用数数学学模模型型固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路应应用用数数学学模模型型应应用用数数学学模模型型算法步骤：算法步骤：应应用用数数学学模模型型 TO MATLAB(road1)应应用用数数学学模模型型应应用用数数学学模模型型u1u2u3u4u5u6u7u8返回返回
