《管理科学教学课件新杜 五章二节网络分析》由会员分享，可在线阅读，更多相关《管理科学教学课件新杜 五章二节网络分析（21页珍藏版）》请在金锄头文库上搜索。
1、1 2008 12 5 第二节网络分析 网络 赋权图 记D V E C 其中C c1 cn ci为边ei上的权 设ci 网络分析主要内容 最小部分树 最短路 最大流 0 2 2008 12 5 一 最小部分 支撑 树问题 问题 求网络D的部分树 使其权和最小 方法 避圈法 Kruskal 1956 破圈法 管梅谷 1975 例 2 求如图网络的最小部分树 v5 v1 v3v6 v4 v2 v7 2 55 2 3 3 5 7 5 7 1 1 3 2008 12 5 避圈法是一种选边的过程 其步骤如下 1 从网络D中任选一点vi 找出与vi相关联的 权最小的边 vi vj 得第二个顶点vj 2 把
2、顶点集V分为互补的两部分V1 1 其中V 集 不与已选边相关联的点 与已选边相关联的点集 1 1 V V 其中权最小的 挑选其中考虑所有这样的边 3 11 VvVvvv jiji 即 直至全部顶点属于重复 3 4 11 VV 4 2008 12 5 用避圈法解例2 v5 v1 v3v6 v4 v2 v7 2 55 2 3 3 5 7 5 7 1 1 最小部分树如图上红线所示 最小权和为14 思考 破圈法是怎样做的呢 见圈就破 去掉其中权最大的 5 2008 12 5 最小部分树问题的应用例子 已知有A B C D E F六个城镇间的道路网络 如图 现要在六个城镇间架设通讯网络 均沿道路架 设
3、每段道路上的架设费用如图 求能保证各城镇均 能通话且总架设费用最少的架设方案 E A C B F D 5 10 6 9 3 5 3 9 7 82 8 4 6 2008 12 5 二 最短路问题 1 问题 求网络D中一定点v1到其它点的最短路 例3 求如图网络中v1至v7的最短路 图中数字 为两点间距离 v5 v1 v3v6 v4 v2 v7 2 55 2 3 3 5 7 5 7 1 1 2 方法 标号法 Dijkstra 1959 给每点vj标号 dj vi 其中dj为v1至vj的最短距 vi为 最短路上的前一点 7 2008 12 5 标号法步骤 反向追踪可求出最短路即最短距 则 标上号 直
4、至终点 本例即重复 进行标号 的距最短 挑选其中与 其中考虑所有这样的边 未标号点集 已标号点集 分为互补的两部分把顶点集 标号给 3 4 3 2 0 1 7 77 1 11 1 1 11 d vdv vcdv VvVvvv V V V vv i jiji jiji min 8 2008 12 5 用标号法解例3 v5 v1 v3v6 v4 v2 v7 2 55 2 3 3 5 7 5 7 1 1 0 v1 2 v1 3 v1 其中2 min 0 2 0 5 0 3 其中3 min 0 3 0 5 2 2 2 7 4 v2 7 v3 8 v5 13 v6 最短距为13 最短路为v1 v2 v3
5、 v5 v6 v7 9 2008 12 5 最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划 下面给出一辆新汽车的价格以及一辆汽车的使用 维修费用 万元 年号12 3 45 价格22 12 32 42 6 汽车使用年龄0 11 22 33 44 5 维修费用0 71 11 522 5 试用网络分析中求最短路的方法确定公司可采用 的最优策略 方法 以年号作顶点绘图 连线表示连续使用期间 以 费用作路长 10 2008 12 5 三 最大流问题 1 问题已知网络D V A C 其中V为顶点 集 A为弧集 C cij 为容量集 cij为弧 vi vj 上的容量 现D上要通过一个流f fi
6、j 其中fij为弧 vi vj 上的流量 问应如何安排流量fij可使D上 通过的总流量v最大 例如 v4v2 vs v1 vt v3 2 1 3 1 4 5 3 2 5 11 2008 12 5 2 数学模型 ijji fvv 上的流量各弧 决策变量 fv Maxv 目标函数 tifv tsi sifv ff cf jiij ijij 0 0 约束条件 容量约束 平衡条件 问题 最大流问题的决策变量 目标函数 约束条件各是什么 12 2008 12 5 3 基本概念与定理 0 1 ij ijij ijij f cf c f 零流弧 未饱和弧 饱和弧 弧按流量分为 如 在前面例举的网络流问题中
7、若已给定一个可行流 如括号中后一个数字所示 请指出相应的弧的类型 v4v2 vs v1 vt v3 2 2 1 1 3 3 1 1 4 3 5 1 3 0 2 1 5 3 13 2008 12 5 2 可增值链 增广链 一条可增值链 的中关于可行流为 则称 中弧皆非零 中弧皆未饱 若 中的反向弧集 中的正向弧集 记的链至中由 fD vvD ts v4v2 vs v1 vt v3 2 2 1 1 3 3 1 1 4 3 5 1 3 0 2 1 5 3 14 2008 12 5 3 截集与截量 的一个截集 记为 为 称弧集使 与分为二非空互补集截集 割集 将 11 1111 11 VVD VvVv
8、vvVvVv VVV jijits 截量 截集上的容量和 记为 11 VVC v4v2 vs v1 vt v3 2 2 1 1 3 3 1 1 4 3 5 1 3 0 2 1 5 3 例4 对于下图 若V1 vs v1 请指出相应的截 集与截量 15 2008 12 5 例4 对于下图 若V1 vs v1 请指出相应的截 集与截量 解 v4v2 vs v1 vt v3 2 2 1 1 3 3 1 1 4 3 5 1 3 0 2 1 5 3 31211 vvvvVV s 523 11 VVC 16 2008 12 5 4 流量与截量的关系 111111 VVCVVfVVffv 截集上的流量和 相
9、应于截 集的反向 弧上流量和 11 V VMinCfMaxv 最大流最小割定理 v4v2 vs v1 vt v3 2 2 1 1 3 3 1 1 4 3 5 1 3 0 2 1 5 3 17 2008 12 5 4 解法 链 调整的过程 调可增值 的前接点 为 为可增值上限 其中标号 链 给每点标号的过程 找可增值 分两大步 ji jij j vv v v 5 最大流的判别条件 的可增值链 关于 中不存在是最大流的充要条件是可行流 f Df 18 2008 12 5 为流入非零弧 为流出未饱弧 其中标流入非零弧 则给 为流出未饱或或反之 若 其中 考虑所有这样的弧 未标号点集 已标号点集 分为
10、 把顶点集 标号 给 jiiji jiijiji j ijj jij iji ss vvf vvfc vv vvVv Vvvv V V V vv min min 3 2 1 1 1 1 1 步骤 19 2008 12 5 时得最小截集 同可增值链 当前流即 存在但进行不下去 说明不 转 追踪找出 反向说明存在可增值链 依此进行的结局 11 1 1 4 VV f V V 后 转 得新流 令 调整 取 1 min ij jiij jiij jiij ijj v f vvf vvf vvf f j 4 20 2008 12 5 例5 用标号法求下面网络的最大流 解 第一次标号及所得可增值链如图 调量
11、 1 调后进 行第二次标号如图 第二次标号未进行到底 得最大流如 图 最大流量v 5 同时得最小截 31211 vvvvVV s v4v2 vs v1 vt v3 2 2 1 1 3 3 1 1 4 3 5 1 3 0 2 1 5 3 s v 2 v1 2 v1 1 v1 4 s v 3 v1 s v 3 s v 2 0 2 0 21 2008 12 5 最大流问题的应用例子 汽车由A城通往B城的可能的路线如下图所示 环境保护 部门拟建立足够数量的汽车尾气检查站 以便使每辆汽车至 少必须经过一个检查站 建立检查站的费用根据各路段的条 件而有所不同 如图上数字所示 若求这个问题的最小费用 解 可使用模型 a 最短路模型 b 最大流模型 c 最小支撑树模型 A a c b d e f g B 8 2 4 45 2 6 4 3 3 6 7 3 7 8
