运筹学第六章图与网络分析.ppt

第六章图与网络分析 6 1图的基本概念与数学模型6 2树图和图的最小部分树6 3最短路问题6 4中国邮路问题6 5网络最大流问题6 6网络模型的实际应用 第六章图与网络分析 图是一种模型 如公路 铁路交通图 通讯网络图等 图是对现实的抽象 以点和线段的连接组合表示 6 1图的基本概念和模型 一 概念 1 图 点V和边E的集合 用以表示对某种现实事物的抽象 记作G V E V v1 v2 vn E e1 e2 em 点 表示所研究的事物对象 边 表示事物之间的联系 v1 v2 v3 v4 v0 e1 e2 e3 e4 e5 e6 e7 e0 2 若边e的两个端点重合 则称e为环 3 多重边 若某两端点之间多于一条边 则称为多重边 4 简单图 无环 无多重边的图称为简单图 5 链 点和边的交替序列 其中点可重复 但边不能重复 6 路 点和边的交替序列 但点和边均不能重复 7 圈 始点和终点重合的链 8 回路 始点和终点重合的路 9 连通图 若一个图中 任意两点之间至少存在一条链 称这样的图为连通图 10 子图 部分图 设图G1 V1 E1 G2 V2 E2 如果有V1 V2 E1 E2 则称G1是G2的一个子图 若V1 V2 E1 E2 则称G1是G2的一个部分图 11 次 某点的关联边的个数称为该点的次 以d vi 表示 二 图的模型 例 有甲 乙 丙 丁 戊 己六名运动员报名参加A B C D E F六个项目的比赛 如表中所示 打 的项目是各运动员报名参加比赛的项目 问 六个项目的比赛顺序应如何安排 才能做到使每名运动员不连续地参加两项比赛 甲乙丙丁戊己 项目 人 ABCDEF 建立模型 解 项目作为研究对象 排序 设点 表示运动项目 边 若两个项目之间无同一名运动员参加 A B C D E F A C D E F B A F E D C B A C B F E D A F B C D E 顺序 6 2树图和图的最小部分树 1 树 无圈的连通图称为树图 简称为树 一 树图的概念 2 树的特性 树是边数最多的无圈连通图 在树中任加一条边 就会形成圈 树是边数最少的连通图 在树中任减一条边 则不连通 3 图的最小部分树 定义 若G1是G2的一个部分图 且为树图 则称G1是G2的一个部分树 G2 A B C D 5 4 7 3 6 5 5 7 6 G1 A C B D 定义 树枝总长为最短的部分树称为图的最小部分树 二 最小部分树的求法 例 要在下图所示的各个位置之间建立起通信网络 试确定使总距离最佳的方案 树枝 树图中的边称为树枝 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分树长Lmin 14 1 避圈法 1 避圈法 将图中所有的点分V为V两部分 V 最小部分树内点的集合V 非最小部分树内点的集合 任取一点vi加粗 令vi V 取V中与V相连的边中一条最短的边 vi vj 加粗 vi vj 令vj V 重复 至所有的点均在V之内 2 破圈法 任取一圈 去掉其中一条最长的边 重复 至图中不存在任何的圈为止 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分树长Lmin 14 2 破圈法 6 3最短路问题 在图示的网络图中 从给定的点S出发 要到达目的地T 问 选择怎样的行走路线 可使总行程最短 方法 Dijkstra D氏 标号法 按离出发点的距离由近至远逐渐标出最短距离和最佳行进路线 S 1 求某两点间最短距离的D Dijkstra 氏标号法 2 4 7 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 0 2 4 4 7 8 9 14 13 5 9 4 最短路线 S A B E D T最短距离 Lmin 13 2 求任意两点间最短距离的矩阵算法 构造任意两点间直接到达的最短距离矩阵D 0 dij 0 SABCDETS0254 A202 7 B520153 C4 10 4 D 75 015E 34107T 570 D 0 构造任意两点间直接到达 或者最多经过1个中间点到达的最短距离矩阵D 1 dij 1 其中dij 1 min dir 0 drj 0 SABCDETS024498 A20237512B42014310C43105411D9745015E8534106T 121011570 D 1 i r j dir 0 drj 0 r dSE 1 min dSS 0 dSE 0 dSA 0 dAE 0 dSB 0 dBE 0 dSC 0 dCE 0 dSD 0 dDE 0 dSE 0 dEE 0 dST 0 dTE 0 8 例如 其中dij 2 min dir 1 drj 1 SABCDETS02448714A20236511B4201439C43105410D8645015E7534106T1411910560 D 2 i r j dir 1 drj 1 r 构造任意两点间最多可经过3个中间点到达的最短距离矩阵D 2 dij 2 其中dij 3 min dir 2 drj 2 SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560 D 3 i r j dir 2 drj 2 r 构造任意两点间最多可经过7个中间点到达的最短距离矩阵D 3 dij 3 说明 一般 对于D k dij k 其中dij k min dir k 1 drj k 1 k 0 1 2 3 最多可经过2k 1个中间点 其数列为 0 1 3 7 15 31 2k 1 收敛条件 当D k 1 D k 时 计算结束 设网络中有p个点 即有p 2个中间点 则2k 1 1 p 2 2k 1 k 1 log2 p 1 k K log2 p 1 1 计算到k lg p 1 lg2 1时 收敛 计算结束 例 有7个村镇要联合建立一所小学 已知各村镇小学生的人数大致为S 30人 A 40人 B 20人 C 15人 D 35人 E 25人 T 50人 问 学校应建在那一个地点 可使学生总行程最少 SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560 L 30402015352550 人数 1325103088010359108651485 T 解 6 4中国邮路问题 问题 一名邮递员从邮局出发 试选择一条最短的投递路线 v1 v2 v3 v4 v5 v6 v8 v7 v9 v10 v11 v12 v13 邮局 4 4 4 5 5 1 2 4 1 2 5 4 4 7 4 2 2 奇点 图中次为奇数的点称为奇点 偶点 图中次为偶数的点称为偶点 结论 最短投递路线应具有下述特征 若图中所有的点均为偶点 则可不重复走遍所有街道 重复走的路线长度应不超过所在回路总长度的一半 步骤 两两连接所有的奇点 使之均成为偶点 2 检查重复走的路线长度 是否不超过其所在回路总长的一半 若超过 则调整连线 改走另一半 v1 v2 v3 v4 v5 v6 v8 v7 v9 v10 v11 v12 v13 邮局 4 4 4 5 5 1 2 4 1 2 5 4 4 7 4 2 2 投递距离 L 60 18 78 6 5网络最大流问题 一 网络最大流中有关概念 有向图 含有以箭头指示方向的边的网络图 弧 有向图上的边称为弧 用 vi vj 表示 弧的容量 弧上通过负载的最大能力 简称容量 以cij表示 流 加在网络每条弧上的一组负载量 以fij表示 可行流 能够通过网络的负载量 通常应满足两个条件 容量限制条件 对所有的弧 0 fij cij 中间点平衡条件 对任何一个中间点 流入量 流出量 发点 收点 中间点 流的起源点称发点 终到点称收点 其余的点称中间点 最大流 能够通过网络的最大流量 割集 一组弧的集合 割断这些弧 能使流中断 简称割 8 8 v1 vs v2 v3 v4 vt 7 5 9 4 9 9 2 0 6 1 5 5 10 8 0 vs 2 v2 2 v1 2 v3 1 v4 1 5 4 cij fij 割的容量 割集中各弧的容量之和 最小割 所有割集中容量之和为最小的一个割集 前向弧 一条发点到收点链中 由发点指向收点的弧 又称正向弧 后向弧 一条发点到收点链中 由收点指向发点的弧 又称逆向弧 增广链 由发点到收点之间的一条链 如果在前向弧上满足流量小于容量 即fij0 则称这样的链为增广链 二 两个定理定理 网络的最大流量等于它的最小割集的容量 定理 当网络中不存在任何增广链时 则网络达到最大流状态 s t 6 4 5 3 4 4 8 7 设有如下增广链 f 1 该网络没有达到最大流状态 三 网络最大流的标号算法 Ford Fulkerson标号算法 基本思想 寻找增广链 改善流量分布 再重复 直到不存在任何增广链为止 步骤 给始点标号 0 从已标号点i出发 看与其相关联的未标号点j上的弧 对 若有0 fij cij 则可对j点标号 记 i j 其中 j min i cij fij 对 若有0 fji cij 也可对j点标号 记 i j 其中 j min i fji 注 若有多个可标号点 可任选其中之一 若标号中断 则得到最大流状态 否则 重复 继续标号 至收点得到标号 转 当收点得到标号 则沿标号得到的增广链进行流量调整 对 f ij fij t 对 f ij fij t 其余弧上的流量不变 重复上述过程 最小割集 已标号点集合与未标号点集合相连接的弧中 流量 容量的弧 8 8 v1 vs v2 v3 v4 vt 7 6 9 5 9 9 2 0 6 0 5 5 10 9 5 3 0 vs 1 v2 1 v1 1 最大流量 fmax 14 最小割集 v3 vt v2 v4 6 6网络模型的实际应用 例1 王经理花费12000元购买了一台微型车 以后年度的维护费用取决于年初时汽车的役龄 如表示 为避免使用旧车带来较高的维护费用 王经理可选择卖掉旧车 购买新车使用的方案 旧车的预计收入如表示 为简化计算 假定任何时刻购买新车都需花费12000元 王经理的目标是使净费用最小 购置费 维护费 卖旧车收入 役龄 年 年维护费 预计收入 单位 元 012345 200040005000900012000 70006000200010000 解 用网络图模型描述 归结为最短路问题 7 7 7 7 7 1 2 3 4 5 6 12 12 12 12 21 21 21 31 31 44 1年初 5年末 例2 图示岛屿与河岸有数座桥相联 问至少需要炸毁几座桥 可中断两岸的交通 A B C D E F A B C F E D 2 2 2 1 3 1 1 1 1 例3 有3根相同的轴A1 A2 A3 另有三根相同的齿轮B1 B2 B3 因为精度不高 不能做到任意的互相配合 其中A1能与B1 B2配合 A2能与B2 B3配合 A3能与B1 B3配合 要求确定合适的配合方案 以得到最多的配合数 将此问题归为网络最大流问题 A1 A2 A3 B1 B2 B3 1 1 1 1 1 1 S T 1 1 1 1 1 1