《图论最短路问题课件》由会员分享，可在线阅读，更多相关《图论最短路问题课件（38页珍藏版）》请在金锄头文库上搜索。
1、数学实验数学实验空军工程大学理学院应用数学教研室 最短路问题最短路问题实验目的实验目的实验内容实验内容2、会用、会用Matlab软件求最短路软件求最短路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图、图 论论 的的 基基 本本 概概 念念2、最、最 短短 路路 问问 题题 及及 其其 算算 法法3、最、最 短短 路路 的的 应应 用用4、建模案例：最优截断切割问题、建模案例：最优截断切割问题5、实验作业、实验作业图图 论论 的的 基基 本本 概概 念念一、一、 图图 的的 概概 念念1、图的定义、图的定义2、顶点的次数、顶点的次数 3、子图、子图二、二、 图图 的的 矩矩 阵阵
2、表表 示示1、 关联矩阵关联矩阵2、 邻接矩阵邻接矩阵返回返回定义定义有序三元组G=(V,E, )称为一个图图.图的定义图的定义定义定义定义定义返回返回顶点的次数顶点的次数例例 在一次聚会中，认识奇数个人的人数一定是偶数。返回返回子图子图返回返回关联矩阵关联矩阵注：假设图为简单图返回返回邻接矩阵邻接矩阵注：假设图为简单图返回返回最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路返回返回基基 本本 概概 念念返回返回固固 定定 起起 点点 的的
3、 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路算法步骤：算法步骤： TO MATLAB(road1)u1u2u3u4u5u6u7u8返回返回每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想一）算法的基本思想（三）算法步骤三）算法步骤返回返回算法的基本思想算法的基本思想返回返回算法原理算
4、法原理 求距离矩阵的方法求距离矩阵的方法返回返回算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径返回返回ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：返回返回算法步骤算法步骤 TO MATLAB(road2(floyd)返回返回一、一、 可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、 选选 址址 问问 题题1、 中心问题中心问题2、 重心问题重心
5、问题返回返回可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题返回返回 选址问题选址问题-中心问题中心问题 TO MATLAB(road3(floyd)S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故应将消防站设在v3处。 返回返回 选址问题选址问题-重心问题重心问题返回返回实验作业实验作业 生产策略问题生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益。 某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增。若生产产品过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费C3=0.4元。假定生产率每调整一次带有固定的调整费C1=1万元，试问工厂如何制定当年的生产策略，使工厂的总损失最小？返回返回
