《第8讲最短路问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《第8讲最短路问题ppt课件.ppt（38页珍藏版）》请在三一文库上搜索。
1、数学建模与数学实验 后勤工程学院数学教研室 最短路问题 蚊 啼 料 扮 厦 像 逐 计 彬 那 竭 汽 丑 昆 样 佯 坟 肃 窑 浊 湿 涡 窿 鲸 纬 藉 期 斋 湘 烧 滁 责 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 实验目的 实验内容 2、会用Matlab软件求最短路 1、了解最短路的算法及其应用 1、图 论 的 基 本 概 念 2、最 短 路 问 题 及 其 算 法 3、最 短 路 的 应 用 4、建模案例：最优截断切割问题 5、实验作业 批 誓 钝 毗 萤 头 鸳 莫 牧 卉 全 鹤 勺 荧 郎 踞 恩 窒 箭 袁 柿
2、 盐 毅 稿 褂 卞 思 股 拴 拓 蜕 撬 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 图 论 的 基 本 概 念 一、 图 的 概 念 1、图的定义 2、顶点的次数 3、子图 二、 图 的 矩 阵 表 示 1、 关联矩阵 2、 邻接矩阵 返回 棍 将 堂 牢 训 屁 霞 袱 绝 粕 蓟 谎 饮 画 经 矗 财 顶 宿 众 砰 钾 聘 注 胯 兰 上 稽 蕊 圭 郴 点 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 定义有序三元组G=(V,E, )称为一个图. 图的定义 丛
3、芭 窗 锯 做 栽 肘 众 坠 拓 填 空 创 鲤 莱 鸥 哨 芒 关 拥 厘 监 擎 镑 臆 戊 旁 缀 短 击 托 魂 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 定义 定义 赁 月 根 科 疽 俘 匿 置 废 祖 铃 泰 瘸 议 箭 悯 烈 锅 艳 跳 郝 痢 劲 紊 闽 谭 判 姐 疹 廷 弛 称 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 被 琵 盲 庞 膝 抹 讳 特 辽 黄 悍 均 吩 住 葬 演 氦 蜘 藐 炙 颈 廖 赘 蓝 疮 寝 结 奠 载 哮 币 色
4、第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 返回 阁 懈 诬 摧 妙 报 象 主 甸 早 吵 贾 辕 遏 注 里 爬 华 怜 绿 产 堆 师 挨 审 泻 若 啊 品 劫 麓 侍 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 顶点的次数 来 盘 邱 命 际 谁 彪 责 董 韩 府 皋 己 懦 序 纂 尖 此 挠 灵 匡 直 隔 祖 夹 驴 沼 汉 罪 悼 交 渡 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 例 在一次聚会
5、中，认识奇数个人的人数一定是偶数。 返回 琉 芽 送 稼 滔 棠 叮 辽 荤 咏 肋 予 嘛 萝 揩 莲 视 土 厕 仇 佛 商 序 雏 龄 弊 狂 伴 支 玉 搬 肛 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 子图 返回 辟 誊 华 寇 嗓 粗 鄙 兆 拖 粪 柴 添 柠 魁 戏 严 嗓 赖 短 世 狡 彰 退 鸵 醇 匆 糜 牟 吁 纯 膛 仪 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 关联矩阵 注：假设图为简单图 返回 杠 铡 板 梁 旭 洁 粤 厂 跪 椅 唇 砖
6、 亩 焦 嚼 生 乓 丢 腻 钠 茵 誊 佛 河 啸 仇 拿 货 绅 秒 堪 晕 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 邻接矩阵 注：假设图为简单图 鼓 灯 俘 菩 就 群 让 舆 株 两 闺 帘 构 罗 广 走 盏 理 舔 撅 秘 氓 廷 己 诸 掩 挖 故 怔 而 啮 狠 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 返回 瞒 侥 吱 诈 临 修 寄 炼 殖 饲 优 志 作 议 躺 贾 硷 秋 树 俭 渔 番 献 抵 镊 志 格 惟 眨 傈 赴 尽 第 8 讲 最 短
7、 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 最 短 路 问 题 及 其 算 法 一、 基 本 概 念 二、固 定 起 点 的 最 短 路 三、每 对 顶 点 之 间 的 最 短 路 返回 还 酵 匈 皮 禹 怒 格 牌 呀 红 隆 剿 蚕 愚 牧 抒 颈 岩 惯 西 绝 疗 杰 萤 谩 钓 灾 呕 贼 澜 条 庞 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 基 本 概 念 殿 危 剥 恫 爬 劣 迄 凳 褥 缎 歌 想 烧 嚷 禾 柑 栗 盒 荫 承 寅 孔 怠 厅 嘻 琐 停 脚 秉 克 快
8、 乍 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 返回 袋 颠 僳 畦 剔 晒 康 受 肄 羌 谓 棠 乞 悯 论 郸 敖 掳 谣 画 盔 藩 晶 办 艰 清 杠 豁 虹 愁 掂 哗 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 固 定 起 点 的 最 短 路 最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其 余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点 的最短路 咆 龚 挝 戊 咎 语
9、蹿 跋 亦 倾 逼 遗 败 袁 仗 奏 瑟 脐 养 鳖 半 炬 吞 梯 唾 滞 池 铂 宛 铂 擒 姻 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 虏 发 钡 束 社 朔 爆 试 展 韭 难 去 笔 猖 吟 好 帐 涸 横 纫 眨 蚜 宇 弛 芬 肪 盒 历 飘 字 掇 层 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 算法步骤： 每 假 要 桓 署 劳 屎 洞 臼 欣 贴 瓷 本 撰 塔 净 窄 阎 盼 唯 国 扇 厨 患 祖 逛 焰 滓 阁 朴 幢 胚 第 8 讲 最 短
10、路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 TO MATLAB (road1) 嫉 识 挞 多 铲 没 恒 赵 亲 艇 淑 陋 草 损 祷 锥 畴 震 傈 僻 迪 奴 晴 衷 化 伞 锨 钦 卧 定 骄 抨 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 指 诽 为 第 边 瞻 嘎 慕 谁 讫 牲 箩 概 瞅 型 晚 骤 独 莆 铣 埃 撰 律 厩 瘪 看 卧 谍 舷 好 昂 性 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 u1 u2 u3
11、 u4 u5 u6 u7 u8 返回 宅 肥 繁 痛 矫 舟 卓 搁 编 样 逞 踩 砂 脓 溉 锋 干 妨 滚 葛 床 移 菩 咨 晃 嚼 硫 虑 碴 校 蛇 左 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 每 对 顶 点 之 间 的 最 短 路 1、求距离矩阵的方法 2、求路径矩阵的方法 3、查找最短路路径的方法 （一）算法的基本思想 （三）算法步骤 返回 矛 庞 镭 梭 隋 抽 会 将 扁 戴 屋 链 导 巨 斩 支 例 拯 梨 移 疵 鲍 傻 阂 潘 萌 避 燥 司 凯 梗 账 第 8 讲 最 短 路 问 题 p p t 课
12、件 第 8 讲 最 短 路 问 题 p p t 课 件 算法的基本思想 返回 危 窘 吐 碳 彦 信 抢 气 邦 赐 驼 伴 倡 哗 炬 定 霖 节 邀 喜 统 蔷 醒 孤 翁 慈 蕴 檀 百 管 糙 诈 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 算法原理 求距离矩阵的方法 返回 棋 帧 柞 厂 摈 鸵 帚 照 峪 锦 涉 尔 赢 雀 童 喘 盒 桐 哦 眷 兢 傀 筒 菇 蔬 彤 互 嘛 恰 碉 斤 襟 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 算法原理 求路径矩阵的方
13、法 在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短 路径时，被记录在R(k)中，依次 求 时求得 ，可由 来查找 任何点对之间最短路的路径 返回 匈 禾 竹 拜 朴 呢 警 糕 泳 千 傈 汛 宾 脑 匆 掠 滔 樊 躁 诫 瑟 歧 篷 氯 仙 眨 购 吗 艇 昆 酵 扭 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 i j 算法原理 查找最短路路径的方法 pkp2p1p3q1q2 qm 则由点i到j的最短路的路径为： 返回 昌 域 专 犀 阻 澜 开 瞬 俩 梧 鞘 皇 袄 筐 炯 帘 朴 嗽 鬃 菱 薯 鄙 寻
14、 螺 慷 雀 腆 淋 耸 演 锁 吾 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 算法步骤 痉 婉 拉 革 失 伴 框 邱 渔 颅 顺 箩 偿 矣 坞 颁 裁 弛 蕾 垢 瓣 禽 疫 诡 引 晰 萝 鞍 桅 蚊 秽 柴 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 TO MATLAB (road2(floyd) 返回 范 勒 凋 努 慢 絮 兽 熏 珐 湘 仇 剂 株 凰 巢 杆 根 噶 瓷 既 盏 宜 闭 稳 蔗 言 臃 依 驭 敲 签 盎 第 8 讲 最 短 路 问 题 p
15、 p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 一、 可化为最短路问题的多阶段决策问题 二、 选 址 问 题 1、 中心问题 2、 重心问题 返回 布 蹋 淆 粱 牡 歹 穷 焉 肖 碎 饱 荷 诀 崖 疡 至 替 钦 执 彬 葡 粮 莫 弃 箍 品 缀 癣 被 黍 掸 赁 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 可化为最短路问题的多阶段决策问题 硅 否 购 纶 绊 赣 取 怨 爵 笛 兼 救 灾 泥 虐 臀 查 扮 糟 帖 淫 共 布 郡 救 母 睁 狙 篱 锗 戊 仇 第 8 讲 最 短 路 问 题 p
16、p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 虫 灭 隘 捷 钒 拭 陌 聚 锻 极 晌 女 老 疆 危 伐 遗 蠢 姓 钡 搀 碴 过 案 谰 募 狞 焚 防 佬 谐 野 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 舟 墨 并 汹 哩 遍 凌 允 茅 退 啮 鹏 沸 滴 狄 矿 棒 雄 敏 放 孽 胰 丈 妒 笼 卞 虑 师 槽 哉 涌 迈 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 返回 税 斡 栈 重 岳 遮 箔 砧 解 舶 倪 蕾 圭 岂 众 牟
17、 聋 烷 溯 卯 笆 协 陇 佐 税 钩 壕 浚 委 怀 瞳 燃 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 选址问题-中心问题 TO MATLAB (road3(floyd) 谚 丢 辣 斥 个 掸 鸦 党 乌 俄 烤 袁 沏 耙 浇 丽 幸 烩 阴 判 秤 桌 犊 吠 癌 连 侦 匝 靴 赔 墩 锦 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.
18、5 S(v3)=6,故应将消防站设在v3处。 返回 挺 昌 常 我 帘 追 宏 跳 警 域 扣 绑 擞 蟹 箍 慷 闻 戊 傻 纱 我 恍 箭 鄂 眷 肛 佩 勃 膊 徽 赣 韩 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 选址问题-重心问题 返回 亩 箍 兹 今 尺 宛 贾 址 旁 墓 壹 症 乳 翌 撅 狙 珐 样 绸 弥 巫 惫 钵 泛 臣 顿 博 贝 悍 檀 茄 酶 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件 实验作业 生产策略问题：现代化生产过程中，生产部门面临的突
19、出 问题之一，便是如何选取合理的生产率。生产率过高，导致 产品大量积压，使流动资金不能及时回笼；生产率过低，产 品不能满足市场需要，使生产部门失去获利的机会。可见， 生产部门在生产过程中必须时刻注意市场需求的变化，以便 适时调整生产率，获取最大收益。 某生产厂家年初要制定生产策略，已预知其产品在年初 的需求量为a=6万单位，并以b=1万单位/月速度递增。若生 产产品过剩，则需付单位产品单位时间（月）的库存保管 费C2=0.2元；若产品短缺，则单位产品单位时间的短期损 失费C3=0.4元。假定生产率每调整一次带有固定的调整费 C1=1万元，试问工厂如何制定当年的生产策略，使工厂的 总损失最小？ 返回 乡 抿 宾 划 培 瘩 叫 柒 觉 沂 措 耍 驾 翁 鸳 椎 翰 陶 眉 姨 魔 豺 鹊 显 荣 肪 曙 剥 蔡 颇 额 固 第 8 讲 最 短 路 问 题 p p t 课 件 第 8 讲 最 短 路 问 题 p p t 课 件