管理科学-图和网络分析-2.pptVIP

习 题 1 * 由于与V6相连的点V2 ， V3 ， V4 ，均已获得标号，故可计算 在V6处标以（6，V3） 在V5 ，V7处依次标以（8，V6）， （7，V6） v1 v2 v3 v4 v5 v7 v6 v8 3 7 4 1 1 6 5 2 3 2 6 1 5 5 9 （7，V5） （6，V3） （8，V5） （0，V1） （3，V1） （5，V3） （4，V2） 习 题 1 * v1 v2 v3 v4 v5 v7 v6 v8 3 7 4 1 1 6 5 2 3 2 6 1 5 5 9 （12，V7） V1→V2 → V3 → V6 → V7 → V8 （7，V5） （6，V3） （8，V5） （0，V1） （3，V1） （5，V3） （4，V2） 最短路问题模型的应用 * 某企业使用一台设备，在每年年底，企业都要决策下年度是购买新设备还是继续使用这台设备。若购买新的，就需要一笔购置费；如果使用旧设备，就要支付维修费；而维修费随之使用年限的延长而增加。现根据以往统计资料已经估算出设备在各年初的价格和不同使用年限的维修费用分别如表所示。 年份 一 二 三 四 五 购置费 11 11 12 12 13 使用年限 0~1 1～2 2～3 3～4 4～5 年修理费 5 6 8 11 18 试确定一个五年内的设备更新计划，使五年内总支出最小。 * 设备更新问题 节点 相当于第1、2、…、5年的年初， 相当于第5年年末。 网络图中的弧 相当于第i年年初购买一台设备一直用到第j-1年年末。 网络图中每一个条从 到 的路标是一种可能的设备更新方案， 设备更新问题 * 年份 一 二 三 四 五 购置费 11 11 12 12 13 使用年限 0~1 1～2 2～3 3～4 4～5 年修理费 5 6 8 11 18 v1 v2 v3 v4 v5 v6 16 16 17 17 18 22 30 41 59 22 30 41 23 31 23 （0，1） （16，1） （22，1） （30，1） （41，1） （53，3或4） 作业 * 求下面网络的最短路径。 v1 v2 v3 v4 v5 v7 v6 v11 1 6 4 3 5 3 2 3 4 3 2 1 2 5 4 v8 v9 v10 3 4 5 作业 * 习题5.3 P.130 作业 * 习题5.7 P.131 * * * Dijkstra被西方学术界称为“结构程序设计之父”和“先知先觉”（Oracle） * * * 第3章 图与网络分析 最 小 支 撑 树 最 短 路 问 题 最 大 流 问 题 本章内容重点 * 最 短 路 问 题 单行线交通网：v1到v8使总费用最小的旅行路线。 v2 v1 v3 v4 v9 6 v8 v7 v6 v5 3 1 2 2 1 6 10 4 10 2 3 6 3 2 4 5.3 最短路问题 问题：求网络中一定点到其它点的最短路。 5.3.1 最短路问题的Dijstra解法 方法：给vi点标号[wi,vk] 其中：wi：vi点到起点vs的最短距离 vk: vi的前接点 方法：(1) 给起点vs标号[0，vs]。 （2）把顶点集v分为互补的两部分A和ā 其中：A：已标号点集 ā：未标号点集 （3）考虑所有这样的弧[vi, vj],即由已标号点vi出发流向未标号点vj的弧。 其中vi ∈A, vj ∈ ā 挑选其中与vs距离最短的点vj标号 [min{wi+cij},vi] （4）重复（3），直至终点vt标上号[wt,vk]，则wt即为vs至vt的最短距。 反向追踪可求得最短路。 例：求v1至v8的最短路。 v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (1) v1:[0,v1] 计算min {0+2, 0+1, 0+3}= min {2,1,3}=1 v4:[1.v1] [1,v1] [0,v1] (2)A={v1} 检查边（v1,v2),(v1,v4),(v1,v3) v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (3)A