数学建模案例分析第8讲最短路问题.ppt

2020 3 6 数学建模 数学建模与数学实验 最短路问题 2020 3 6 数学建模 实验目的 实验内容 2 会用MATLAB软件求最短路 1 了解最短路的算法及其应用 1 图论的基本概念 2 最短路问题及其算法 3 最短路的应用 4 建模案例 最优截断切割问题 5 实验作业 2020 3 6 数学建模 图论的基本概念 一 图的概念 1 图的定义 2 顶点的次数 3 子图 二 图的矩阵表示 1 关联矩阵 2 邻接矩阵 返回 2020 3 6 数学建模 图的定义 2020 3 6 数学建模 定义 定义 2020 3 6 数学建模 2020 3 6 数学建模 返回 2020 3 6 数学建模 顶点的次数 2020 3 6 数学建模 例在一次聚会中 认识奇数个人的人数一定是偶数 返回 2020 3 6 数学建模 子图 返回 2020 3 6 数学建模 关联矩阵 注 假设图为简单图 返回 2020 3 6 数学建模 邻接矩阵 注 假设图为简单图 2020 3 6 数学建模 返回 2020 3 6 数学建模 最短路问题及其算法 一 基本概念 二 固定起点的最短路 三 每对顶点之间的最短路 返回 2020 3 6 数学建模 基本概念 2020 3 6 数学建模 返回 2020 3 6 数学建模 固定起点的最短路 最短路是一条路径 且最短路的任一段也是最短路 假设在u0 v0的最短路中只取一条 则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此 可采用树生长的过程来求指定顶点到其余顶点的最短路 2020 3 6 数学建模 2020 3 6 数学建模 算法步骤 2020 3 6 数学建模 TOMATLAB road1 2020 3 6 数学建模 2020 3 6 数学建模 1 2 3 4 5 6 7 8 返回 2020 3 6 数学建模 每对顶点之间的最短路 1 求距离矩阵的方法 2 求路径矩阵的方法 3 查找最短路路径的方法 一 算法的基本思想 三 算法步骤 返回 2020 3 6 数学建模 算法的基本思想 返回 2020 3 6 数学建模 算法原理 求距离矩阵的方法 返回 2020 3 6 数学建模 算法原理 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时 被记录在R k 中 依次求时求得 可由来查找任何点对之间最短路的路径 返回 2020 3 6 数学建模 算法原理 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为 返回 2020 3 6 数学建模 算法步骤 2020 3 6 数学建模 TOMATLAB road2 floyd 返回 2020 3 6 数学建模 一 可化为最短路问题的多阶段决策问题 二 选址问题 1 中心问题 2 重心问题 返回 2020 3 6 数学建模 可化为最短路问题的多阶段决策问题 2020 3 6 数学建模 2020 3 6 数学建模 2020 3 6 数学建模 返回 2020 3 6 数学建模 选址问题 中心问题 TOMATLAB road3 floyd 2020 3 6 数学建模 S v1 10 S v2 7 S v3 6 S v4 8 5 S v5 7 S v6 7 S v7 8 5 S v3 6 故应将消防站设在v3处 返回 2020 3 6 数学建模 选址问题 重心问题 返回 2020 3 6 数学建模 实验作业 生产策略问题 现代化生产过程中 生产部门面临的突出问题之一 便是如何选取合理的生产率 生产率过高 导致产品大量积压 使流动资金不能及时回笼 生产率过低 产品不能满足市场需要 使生产部门失去获利的机会 可见 生产部门在生产过程中必须时刻注意市场需求的变化 以便适时调整生产率 获取最大收益 某生产厂家年初要制定生产策略 已预知其产品在年初的需求量为a 6万单位 并以b 1万单位 月速度递增 若生产产品过剩 则需付单位产品单位时间 月 的库存保管费C2 0 2元 若产品短缺 则单位产品单位时间的短期损失费C3 0 4元 假定生产率每调整一次带有固定的调整费C1 1万元 问 工厂应如何制定当年的生产策略 使工厂的总损失最小 返回