天津大学管理运筹学课件第二章_图论.ppt

2020 1 15 管理运筹学 第二章图论与网络分析 图的基本概念 网络分析 最小支撑树问题最短路径问题网络最大流问题网络计划问题 2020 1 15 管理运筹学 图论起源 哥尼斯堡七桥问题 结论 每个结点关联的边数均为偶数 问题 一个散步者能否从任一块陆地出发 走过七座桥 且每座桥只走过一次 最后回到出发点 2020 1 15 管理运筹学 1图的基本概念 由点和边组成 记作G V E 其中V v1 v2 vn 为结点的集合 E e1 e2 em 为边的集合 点表示研究对象 边表示表示研究对象之间的特定关系 1 图 2020 1 15 管理运筹学 图 无向图 记作G V E 有向图 记作D V A 例1 哥尼斯堡桥问题的图为一个无向图 有向图的边称为弧 2 图的分类 2020 1 15 管理运筹学 3 链与路 圈与回路 链 点边交错的序列 路 点弧交错的序列 回路 起点 终点的路 无向图 有向图 2020 1 15 管理运筹学 4 连通图 G1为不连通图 G2为连通图 例 2020 1 15 管理运筹学 5 支撑子图 图G V E 和G V E 若V V 且E E 则称G 为G的支撑子图 G2为G1的支撑子图 例 2020 1 15 管理运筹学 6 赋权图 网络 图的每条边都有一个表示一定实际含义的权数 称为赋权图 记作D V A C 例 2020 1 15 管理运筹学 2最小支撑树问题 本节主要内容 树 支撑树 最小支撑树 2020 1 15 管理运筹学 1 树中任两点中有且仅有一条链 2 树任删去一边则不连通 故树是使图保持连通且具有最少边数的一种图形 3 边数 顶点数 1 树 无圈连通图 树的性质 例判断下面图形哪个是树 一 树的概念与性质 2020 1 15 管理运筹学 若一个图G V E 的支撑子图T V E 构成树 则称T为G的支撑树 又称生成树 部分树 二 图的支撑树 例 2020 1 15 管理运筹学 例 某地新建5处居民点 拟修道路连接5处 经勘测其道路可铺成如图所示 为使5处居民点都有道路相连 问至少要铺几条路 解 该问题实为求图的支撑树问题 共需铺4条路 图的支撑树的应用举例 2020 1 15 管理运筹学 问题 求网络的支撑树 使其权和最小 三 最小支撑树问题 算法1 避圈法 把边按权从小到大依次添入图中 若出现圈 则删去其中最大边 直至填满n 1条边为止 n为结点数 例 求上例中的最小支撑树 解 4 2020 1 15 管理运筹学 算法2 破圈法 在图中找圈 并删除其中最大边 如此进行下去 直至图中不存在圈 2020 1 15 管理运筹学 算法2 破圈法 在图中找圈 并删除其中最大边 如此进行下去 直至图中不存在圈 5 5 5 v1 v2 v3 v4 v5 3 5 4 2 3 2020 1 15 管理运筹学 算法2 破圈法 在图中找圈 并删除其中最大边 如此进行下去 直至图中不存在圈 5 v1 v2 v3 v4 v5 3 5 4 2 3 2020 1 15 管理运筹学 算法2 破圈法 在图中找圈 并删除其中最大边 如此进行下去 直至图中不存在圈 5 v1 v2 v3 v4 v5 3 5 2 3 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 2020 1 15 管理运筹学 例 今有煤气站A 将给一居民区供应煤气 居民区各用户所在位置如图所示 铺设各用户点的煤气管道所需的费用 单位 万元 如图边上的数字所示 要求设计一个最经济的煤气管道路线 并求所需的总费用 此即为最经济的煤气管道路线 所需的总费用为25万元 2020 1 15 管理运筹学 案例分析 默登公司的联网问题 默登 Modern 公司的管理层决定铺设最先进的光纤网络 为它的主要中心之间提供高速通信 图1中的节点显示了该公司主要中心的分布图 虚线是铺设光缆可能的位置 每条虚线旁边的数字表示成本 单位 百万美元 问 需要铺设哪些光缆使得总成本最低 2020 1 15 管理运筹学 案例分析 默登公司的联网问题 2020 1 15 管理运筹学 3最短路问题 问题 求网络中起点到其它点之间的一条最短路线 2020 1 15 管理运筹学 算法 Dijkstra 狄克斯拉 标号法 基本思想 从起点vs开始 逐步给每个结点vj标号 dj vi 其中dj为起点vs到vj的最短距离 vi为该最短路线上的前一节点 0 v1 1 v1 1 给起点v1标号 0 v1 3 考虑所有这样的边 vi vj 其中vi VA vj VB 挑选其中与起点v1距离最短 min di cij 的vj 对vj进行标号 4 重复 2 3 直至终点vn标上号 dn vi 则dn即为v1 vn的最短距离 反向追踪可求出最短路 步骤 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 5 v3 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 5 v3 6 v2 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 5 v3 6 v2 9 v5 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 5 v3 6 v2 9 v5 10 v5 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 5 v3 6 v2 9 v5 10 v5 12 v5 此时终点v9已标号 12 v5 则12即为v1 vn的最短距离 反向追踪可求出最短路 2020 1 15 管理运筹学 0 v1 1 v1 3 v1 5 v3 6 v2 9 v5 10 v5 12 v5 v1到v9的最短路为 v1 v3 v2 v5 v9 最短距离为12 2020 1 15 管理运筹学 课堂练习 P129习题5 3 0 v1 4 v1 3 v1 5 v2 6 v2 9 v7 7 v4 v6 8 5 v6 6 v2 2020 1 15 管理运筹学 课堂练习 无向图情形 求网络中v1至v7的最短路 2020 1 15 管理运筹学 课堂练习 无向图情形 答案 1 v1 v2 v3 v4 v5 v6 v7 2 2 5 3 5 5 7 1 5 7 1 3 0 v1 2 v1 3 v1 4 v2 v4 7 v3 8 v5 13 v6 2020 1 15 管理运筹学 课堂练习 无向图情形 答案 2 v1 v2 v3 v4 v5 v6 v7 2 2 5 3 5 5 7 1 5 7 1 3 0 v1 2 v1 3 v1 4 v2 v4 7 v3 8 v5 13 v6 最短路模型的应用 设备更新问题 P119例5 3 16 分析 结点 V v1 v6 vi表示第i年初 边 E vi vj 表示第i年初购买 用至第j年初 i 1 5 j 2 6 权cij i年初 j年初的费用 即cij i年初购买费 j i 年里的维修费 30 22 41 59 16 22 30 41 17 23 31 17 23 18 2020 1 15 管理运筹学 4网络最大流问题 引例 下图为V1到V6的一交通网 权表示相应运输线的最大通过能力 制定一方案 使从V1到V6的产品数量最多 2020 1 15 管理运筹学 设有网络D V A C 其中C cij cij为弧 vi vj 上的容量 现在D上要通过一个流f fij fij为弧 vi vj 上的流量 问题 如何安排fij 可使网络D上的总流量V最大 一 一般提法 2020 1 15 管理运筹学 二 最大流问题的模型 maxv v f 容量约束 平衡约束 注 满足约束条件的流f称为可行流 2020 1 15 管理运筹学 三 基本概念与定理 2020 1 15 管理运筹学 2 增广链 f为一可行流 u为vs至vt的链 令u 正向弧 u 反向弧 若u 中弧皆非饱 且u 中弧皆非零 则称u为关于f的一条增广链 2020 1 15 管理运筹学 2 增广链 f为一可行流 u为vs至vt的链 令u 正向弧 u 反向弧 若u 中弧皆非饱 且u 中弧皆非零 则称u为关于f的一条增广链 2020 1 15 管理运筹学 2 增广链 f为一可行流 u为vs至vt的链 令u 正向弧 u 反向弧 若u 中弧皆非饱 且u 中弧皆非零 则称u为关于f的一条增广链 2020 1 15 管理运筹学 2 增广链 f为一可行流 u为vs至vt的链 令u 正向弧 u 反向弧 若u 中弧皆非饱 且u 中弧皆非零 则称u为关于f的一条增广链 2020 1 15 管理运筹学 3 截集与截量 把V分成两部分 V1和V2 V1 V2 V1 V2 V 且vs V1 vt V2 则弧集 V1 V2 称为D的截集 截集上的容量和称为截量 记为C V1 V2 vs v2 v1 vt 截量为 C V1 V2 4 3 7 截集为 2020 1 15 管理运筹学 4 流量与截量的关系 任一可行流的流量都不会超过任一截集的截量 v f f V1 V2 f V2 V1 f V1 V2 C V1 V2 最大流最小截定理 网络的最大流量等于最小截量 2020 1 15 管理运筹学 例 如图所示的网络中 弧旁数字为 cij fij 1 确定所有的截集 2 求最小截集的容量 3 证明图中的流为最大流 2020 1 15 管理运筹学 1 所有的截集 V1 vs 截集为 vs v1 vs v2 截量为 6 2020 1 15 管理运筹学 v1 vs v2 v3 vt 2 2 4 3 3 1 1 0 3 3 5 2 2 2 1 所有的截集 V1 vs 截集为 vs v1 vs v2 截量为 6 V1 vs v1 截集为 vs v2 v1 vt 截量为 7 2020 1 15 管理运筹学 v1 vs v2 v3 vt 2 2 4 3 3 1 1 0 3 3 5 2 2 2 1 所有的截集 V1 vs 截集为 vs v1 vs v2 截量为 6 V1 vs v1 截集为 vs v2 v1 vt 截量为 7 V1 vs v2 截集为 截量为 7 2020 1 15 管理运筹学 v1 vs v2 v3 vt 2 2 4 3 3 1 1 0 3 3 5 2 2 2 1 所有的截集 V1 vs 截集为 vs v1 vs v2 截量为 6 V1 vs v1 截集为 vs v2 v1 vt 截量为 7 V1 vs v2 截集为 截量为 7 V1 vs v3 截集为 截量为 12 2020 1 15 管理运筹学 v1 vs v2 v3 vt 2 2 4 3 3 1 1 0 3 3 5 2 2 2 1 所有的截集 V1 vs 截集为 vs v1 vs v2 截量为 6 V1 vs v1 截集为 vs v2 v1 vt 截量为 7 V1 vs v2 截集为 截量为 7 V1 vs v3 截集为 截量为 12 V1 vs v1 v2 截集为 截量为 5 2020 1 15 管理运筹学 v1 vs v2 v3 vt 2 2 4 3 3 1 1 0 3 3 5 2 2 2 1 所有的截集 V1 vs 截集为 vs v1 vs v2 截量为 6 V1 vs v1 截集为 vs v2 v1 vt 截量为 7 V1 vs v2 截集为 截量为 7 V1 vs v3 截集为 截量为 12 V1 vs v1 v2 截集为 截量为 5 2020 1 15 管理运筹学 2 最小截量minC V1 V2 5 3 v f 5 minC V1 V2 f 是最大流 2020 1 15 管理运筹学 四 求最大流方法 标号法 理论依据 思路 从始点开始标号 寻找是否存在增广链 给vj标号为 j vi 其中 j为调整量 vi为前一节点 2020 1 15 管理运筹学 步骤 1 给vs标号为 vs 流出未饱和弧 vs vj 给vj标号 j vs 其中 j csj fsj 例 图中网络弧旁数字为 cij fij 用标号法求最大流 vs 4 vs 选与vs关联的 2020 1 15 管理运筹学 2020 1 15 管理运筹学 考虑所有VA VB的弧 若该弧为 流出未饱弧 则给vj标号 j vi 其中 j cij fij 流入非零弧 则给vj标号 j vi 其中 j fij 3 1 v1 2020 1 15 管理运筹学 4 重复 2 3 依次进行的结局可能为 vt已标号 得到一条增广链u 反向追踪 转 5 vt未标号 且无法再标号 此时的流为最大流 此时的截集为最小截 3 0 2020 1 15 管理运筹学 1 v2 3 0 2020 1 15 管理运筹学 2 v4 2020 1 15 管理运筹学 2020 1 15 管理运筹学 2020 1 15 管理运筹学 v2 Vs v1 v4 v3 Vt 3 3 5 2 1 0 2 2 1 1 5 4 2 1 4 4 3 0 调整 2020 1 15 管理运筹学 vs 3 vs 2020 1 15 管理运筹学 此时标号无法进行 当前流为最大流 最大流量为5 最小截为 vs v2 v1 v3 截量为 5 2020 1 15 管理运筹学 例有三个发电站v1 v2 v3 发电能力分别为15 10和40兆瓦 经输电网可把电力送到8号地区 电网能力如图所示 求三个发电站输到该地区的最大电力 v0 10 20 15 15 15 10 20 10 20 20 15 35 2020 1 15 管理运筹学 例 图中A B C D E F分别表示陆地和岛屿 表示桥梁及其编号 河两岸分别互为敌对的双方部队占领 问至少应切断几座桥梁 具体指出编号 才能达到阻止对方部队过河的目的 试用图论方法进行分析 2020 1 15 管理运筹学 分析 转化为一个网络图 弧的容量为两点间的桥梁数 则问题为求最小截 2020 1 15 管理运筹学 分析 转化为一个网络图 弧的容量为两点间的桥梁数 则问题为求最小截 答案 最小截为 AE CD CF 2020 1 15 管理运筹学 例 有一批人从我国A城赴俄罗斯B城 可能的旅行路线如图 边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站 建立检查站的费用根据各路段条件有所不同 如图数字所示 求最小费用解 分析 最小截问题 2020 1 15 管理运筹学 例 过纽约ALBANY的北 南高速公路 路况通过能力如下图所示 图中弧上数字单位 千辆 小时 求 1 该路网能承受的北 南向最大流量 2 若要扩充通过能力 应在那一组路段上扩充 说明原因 2020 1 15 管理运筹学 案例 垃圾处理问题某地区有3个城镇 各城镇每天产生的垃圾要运往该地区的4个垃圾处理场处理 现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响 假设各城镇每日产生的垃圾量 各处理场的日处理能力及各条道路 可供运垃圾部分 的容量 其中容量为0表示无此直接道路 如右表所示 试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处理 如果不能 应首先拓宽哪条道路 2020 1 15 管理运筹学 5工程网络计划 引例 沏茶 2020 1 15 管理运筹学 一 问题描述 一项工程 已知各工序完成时间t及其先后关系求 工程完工期及关键工序 关键工序 主矛盾工序 不能延期完工路线 从始点到终点的一条路关键路线 由关键工序组成的路线 是所有路线中时间最长的路线 相关概念 2020 1 15 管理运筹学 二 求解方法 关键路径法 CPM 分为三步 绘制工程网络图标号法求工期T标号法求关键路线 2020 1 15 管理运筹学 将整个工程分解为若干工序确定各工序的前后顺序 紧前 紧后 确定工序完成时间 三点估计法 最乐观时间a 最可能时间m 最悲观时间b 一点估计法 准备工作 2020 1 15 管理运筹学 1 绘制工程网络图 1 顺序 按工序的先后从左至右 2 图的结构 弧 结点 相邻工序的时间分界点 称为事项 权 工序的完成时间 相邻弧 工序的前后衔接关系 称为紧前或紧后工序 3 绘图要求 图中不能出现缺口 回路和多重边 多重边的处理 虚工序 2020 1 15 管理运筹学 例某工厂进行技术改造 需要拆掉旧厂房 建造新厂房和安排设备 这项改建工程可以分解为7道工序 其相关资料如下表 2020 1 15 管理运筹学 1 2 3 4 5 A 2 B 3 C 2 5 D 6 E 20 F 4 6 G 2 解 2020 1 15 管理运筹学 例 绘制工程网络图 续左表 解 1 A 2 D 3 C 2 2 E 4 3 F 7 B 0 G 6 4 5 E 0 6 I 10 7 J 3 H 4 8 B 3 2020 1 15 管理运筹学 两种情况需要引入虚工序 2020 1 15 管理运筹学 课堂练习 P150习题6 1 2020 1 15 管理运筹学 2 用标号法求工期T 步骤 0 2 3 3 6 13 16 2020 1 15 管理运筹学 3 用标号法求关键路线 步骤 16 12 8 13 3 3 0 2020 1 15 管理运筹学 2020 1 15 管理运筹学 其他时间参数 1 工序 i j 最早开始时间 2 工序 i j 最晚开始时间 2020 1 15 管理运筹学 其他时间参数 3 工序 i j 最早结束时间 4 工序 i j 最晚结束时间 2020 1 15 管理运筹学 其他时间参数 5 工序 i j 的自由时差 2020 1 15 管理运筹学 课堂练习 P150习题6 1 2020 1 15 管理运筹学 三 工程工期的概率分析 计划评审技术 PERT PERT与CPM的主要区别 CPM工序时间是确定的 PERT工序时间tij是随机变量 而完工期T也是随机的 由概率知识 T服从正态分布 2020 1 15 管理运筹学 确定平均工序时间的三点估计法 总工期 其中 I为关键路线 2020 1 15 管理运筹学 1 给定时间T 求工期T T 内完工的概率 PERT的内容 2020 1 15 管理运筹学 例 已知某工程网络图 以及各工序的时间参数 TE 42 33 关键路线I为 A C F H 解 2020 1 15 管理运筹学 2 给定概率p 求完工可能性为p的工期 例 上例中 求完工可能性达95 的工期