运筹学网络分析.ppt

清华大学出版社 管理运筹学教程第四章网络分析 清华大学出版社 第四章图论与网络分析 第一节图的基本概念及图的模型第二节图论和网络分析中常用的名词第三节路径问题第四节最小生成树问题第五节最短路问题第六节最大流问题第七节最小费用流问题第八节中国邮递员问题第九节网络计划技术 清华大学出版社 第一节图的基本概念及图的模型 哥尼斯堡七桥问题 清华大学出版社 哈密顿圈问题 清华大学出版社 几个图的模型例子 例4 1 化工品的贮存问题现要求贮藏8种化工品A B C D P R S T 出于安全的原因 下面各组产品不能放在一起 A R A C A T R P P S S T T B B D D C R S R B P D S C S D 问题 贮藏这8种化工品至少需要多少间贮藏室 清华大学出版社 例4 1的图模型 清华大学出版社 例4 1的解 方案1 ABS TCP DR方案2 DRT ABS CP 清华大学出版社 例4 2 考试课表安排问题 现有10名研究生要参加总计为六门课程的期末考试 每位研究生要考的课程数和门类是不同的 如下表4 1所示请你排一个考试课表 要求满足下列三个条件 1 全部考试要在三天内完成 2 每天上午和下午只能安排一门考试 3 对每位研究生 一天只能安排一门考试 清华大学出版社 例4 2的图模型 清华大学出版社 例4 2的解 因此考试课表是 第一天AE 第二天BC 第三DF 清华大学出版社 例4 3 农夫 狼 羊 草过河问题 有位农夫 携带一匹狼 一支羊和一挑草要过一条小河 河中只有一条小船 一次摆渡农夫只能携带一样东西 一匹狼或一支羊或一挑草 当农夫不在场时 狼要吃羊 羊要吃草 试问 农夫怎样才能将这三样东西摆渡到对岸 至少要摆渡几次 清华大学出版社 四个对象可能形成的组合情况 1 M W S G 2 M W S G x3 M S W G 4 M G W S x5 M W S G 6 M W G S 7 W S G M x8 M S G W 清华大学出版社 农夫摆渡狼 羊 草过河的模型图 清华大学出版社 摆渡的最优方案 用观察法不难发现这样的路线有两条即 V1 V7 V4 V10 V3 V9 V2 V1V1 V7 V4 V8 V5 V9 V2 V1 如何用图论的方法找到这条路线将会在第三节介绍 清华大学出版社 第一节网络分析中常用名词 图子图和生成子图网络图链 路 圈和回路连通图简单图 清华大学出版社 一 图 无向图 清华大学出版社 有向图 清华大学出版社 二 子图与生成子图 清华大学出版社 三 网络图 各边赋予一定的物理量 例如距离 则叫做网络图 所赋予的物理量叫做权 权可以是 距离 时间 成本 容量等 清华大学出版社 四 链 路 圈 回路 初等链 顶点和边相互交替出现的点不重复序列 路 在有向图中 方向和链的走向一致的链 圈 起点和终点相同的链叫做圈 回路 起点和终点相同的路叫做回路 清华大学出版社 五 连通图和简单图 连通图 在图中 任意两点之间都有一条链相连 叫做连通图 否则是非连通图 非连通图可以由几个连通图构成 环 多重边简单图 没有环和多重边的图是简单图 清华大学出版社 不连通图 清华大学出版社 六 图的矩阵表示法 1 图和网络的相邻矩阵X G 图G的相邻矩阵X G 为一个P P的方阵X G xij xij为方阵中的元素 清华大学出版社 清华大学出版社 2 有向图的矩阵表示法 设有向图D V A V v1 v2 vp A a1 a2 aq 则矩阵B D bij 清华大学出版社 清华大学出版社 3 边的顶点表示法 对于有向图 任一边a均可用其关联的两顶点vivj表示 a vivj 有向图D即是这些边的集合 把这些边按节点编号组装起来就是一个图的模型 如图4 10 它的边集合是 v1v3 v2v1 v2v3 v2v4 v3v4 v4v1 对于无向图 每一条边均可以用2条具有相同顶点 但方向相反的两条边表示 清华大学出版社 第三节路径问题 1 什么是路径问题图中的路径问题 是指在一个由顶点和弧构成的有向图中 是否存在一条从vi点到vj点通路 清华大学出版社 2 路径问题的解法原理 设有向图D的相邻矩阵为B D bij 因此 bikbkj 1代表在vivj之间存在一条经过两条边的路径 而代表vivj之间存在经过两条边路径的数目 依上面的推理 代表vivj之间存在经过3条边的路径数目 清华大学出版社 一般式 对于具有n个顶点的相邻矩阵B D bij 可以写出下面的一般形式代表vivj之间存在经过n条边的路径数目 清华大学出版社 图4 11 清华大学出版社 图4 11中从V1 V6经过两条边的路径 清华大学出版社 路径的跟踪方法 为了找到路径 要在各级矩阵中不等于0的位置上记录到该点的路径轨迹 如从B 2 矩阵中的第3项不为0得知v1 v3存在一条经过两条边的路径v1 v2 v3 清华大学出版社 下面计算B 3 清华大学出版社 由B 3 矩阵的第一行可知v1 v4和v1 v6各有一条经过3条边的路径 清华大学出版社 第二节最小生成树 什么是树 构造生成树的方法最小生成树问题寻找最小生成树的方法 清华大学出版社 一 什么是树 树 不含圈的连通图树的基本性质任意两点之间有且只有一条链若树有p个顶点 则共有q p 1条边若图是连通的 且q p 1 则该图不含圈 因此是树若图不含圈 且q p 1 则该图联通 因此是树 清华大学出版社 二 构造生成树的方法 破圈法避圈法 清华大学出版社 避圈法 清华大学出版社 三 最小生成树 最小生成树的定义最小生成树的定理 清华大学出版社 最小生成树的数学模型 清华大学出版社 四 寻找最小生成树的方法 Kruskal方法破圈法矩阵计算法 清华大学出版社 Kruskal方法 清华大学出版社 矩阵计算方法 T 清华大学出版社 矩阵计算方法 T T 清华大学出版社 矩阵计算方法 T T T 清华大学出版社 矩阵计算方法 T T T T 清华大学出版社 矩阵计算方法 T T T T T 清华大学出版社 矩阵计算方法 T T T T T T 清华大学出版社 矩阵计算结果 清华大学出版社 什么是最短路问题 求解最短路问题的基本思路Dijstra 荷兰人 算法 标号法Ford 美国人 算法 修正标号法寻找最短路径的方法 双标号 第三节最短路问题 清华大学出版社 一 什么是最短路问题 在连通图中 寻找一条从始点到终点的路 该路的权之和最小 清华大学出版社 图4 8最短路图例 清华大学出版社 二 求解最短路问题的基本思路 使用线性规划的解法 但不能利用最短路问题的特点 使解法更有效 利用动态规划的思路 即对于在始点到终点的总体最短路径上的任意一点 从始点到该点的最短路在总体最短路径上 根据上述第二点 可以用标号法求解 清华大学出版社 三 Dijkstra算法 对每个节点 用两种标号 T和P 表示从始点到该节电的距离 P是最短距离 T是目前路径的距离 通过不断改进T值 当其最小时 将其改为P表好 开始时 令始点有P 0 的P标号 其它节点有T M 清华大学出版社 图4 8的最短路1 清华大学出版社 图4 8的最短路2 清华大学出版社 图4 8的最短路3 清华大学出版社 图4 8的最短路4 清华大学出版社 图4 8的最短路5 清华大学出版社 图4 8的最短路6 清华大学出版社 四 Ford算法 Dijkstra算法不适用于负权网络具有负权的网络 应当用Ford算法又叫修正标号法修正标号法的特点是 不但最小T标号应当改为P标号 P标号也可以修改 修改后的P标号再次改为T表好 清华大学出版社 Ford算法算例 清华大学出版社 五 寻找最短路径的方法 使用双标号 清华大学出版社 网络流的基本概念求解网络最大流的基本原理寻找网络最大流的标号法确定网络中最大流的方法 第四节最大流问题 清华大学出版社 一 网络流的基本概念 流量与容量可行流 节点和边的限制条件饱和弧和非饱和弧正向弧和反向弧增广链 对于一可行流 网络的一条链满足 清华大学出版社 二 求解网络最大流的基本原理 数学模型 清华大学出版社 二 求解网络最大流的基本原理 给出一初始可行流 例如 寻找增广链 若存在 则通过该增广链调整 增加网络流 若不存在增广链 则网络流不可再增加 求得最大流 定理 可行流f为最大流的充分必要条件是当且仅当网络不存在增广链 清华大学出版社 三 寻找网络最大流的标号法 Ford Fulkson标号算法 给每个节点以一对标号 第一个标号表示箭尾节点 第二个标号表示可调整量 若终点有了标号 则找到一条增广链 否则不存在增广链 调整过程 在增广链上 正向弧加上调整量 反向弧减去调整量 经过调整网络流v f 增加一个调整量 清华大学出版社 例4 2 第一次迭代 清华大学出版社 第二次迭代 清华大学出版社 第三次迭代 最优解 清华大学出版社 四 确定网络中最大流的方法 最大流时始节点的净流出量最大流时中介点的净流入量最小割集的容量割集割集容量最小割集最小割集最大流定理标号法求得最小割集 清华大学出版社 一个简单的例子 再看例4 2 清华大学出版社 习题 P 266 习题4 图9 5 1 2 清华大学出版社 什么是最小费用流问题 求解最小费用流的赋权图法求解最小费用流的复合标号法 第五节最小费用流问题 清华大学出版社 一 什么是最小费用流 给定网络N V A c b 和经过网络的流量v 求流在网络上的最佳分布 使总费用最小 清华大学出版社 二 求解最小费用流的赋权图法 增广链费用 最小费用增广链 对于最小费用可行流 沿最小费用增广链调整流 可使流增加 并保持流费用最小 给定初始最小费用可行流 求最小费用增广链 若存在 则沿该增广链调整网络流 直到达到给定的网络流或不存在增广链为止 后一种情况为最小费用最大流 若给定网络流超过最大流 则不可能实现 清华大学出版社 如何求最小费用增广链 生成最小费用可行流的剩余网络 将饱和弧反向将非饱和非零流弧加一反向弧零流弧不变所有正向弧的权为该弧的费用 反向弧的权为该弧费用的相反数剩余网络又叫长度网络 本教材叫做赋权图 最小费用增广链对应剩余网络的最短路 清华大学出版社 最小费用流的实例 清华大学出版社 第一次剩余网络最短路 清华大学出版社 第一次调整网络流 清华大学出版社 第二次剩余网络最短路 清华大学出版社 第二次调整网络流 清华大学出版社 第三次剩余网络的最短路 清华大学出版社 第三次调整网络流 清华大学出版社 剩余网络已不存在最短路 清华大学出版社 已获最小费用最大流 最小费用最大流若规定网络流为7 则第二次调整量应为2 而不是3 见图 最小费用与网络流的关系是凸的 即随着流的增加 单位流的费用在增加 请见下页的图 清华大学出版社 清华大学出版社 三 求解最小费用流的复合标号法 将求最短路的标号法和求最大流的标号法相结合 即在求增广链的标号后加上一个距离标号 成为一组三标号 距离标号应采用修正标号法 并采用T标号和P标号的记法 下面以前例为例来说明符合标号的应用 清华大学出版社 第一次迭代 清华大学出版社 第二次迭代 清华大学出版社 第三次迭代 清华大学出版社 最后结果 清华大学出版社 提示思考 最短路问题 最大流问题可以看作最小费用流的特殊情况 请分析如何将最小费用流问题特化成最短路问题和最大流问题 运输问题和指派问题可以用最小费用流问题建模 请将它们化为最小费用流问题 清华大学出版社 习题 P 267 习题7 8 清华大学出版社 清华大学出版社 第六节中国邮递员问题 哥尼斯堡七桥问题与欧拉图中国邮递员问题求解中国邮递员问题的奇偶点图作业法奇偶点图作业法的改进方法 清华大学出版社 一 哥尼斯堡七桥问题与欧拉图 哥尼斯堡七桥问题欧拉图与一笔画问题 清华大学出版社 二 中国邮递员问题 1962年 管梅谷先生提出中国邮递员问题若图中无奇点 欧拉圈即为所求若图中有奇点 则奇点必为偶数 在奇点间加边 重复走 使其变为偶数而成欧拉图 中国邮递员问题是要求所加边的权之和最小 清华大学出版社 三 求解中国邮递员问题的奇偶点图作业法 在奇点间加边 构造初始可行方案 寻找改进可行方案 在两奇点间检查所有链 若某链的长度小于已加重复边的长度 则在该链的每边加上重复边 去掉原重复边 重复以上步骤 直到任意两奇点间加重复边的链是最短的为止 清华大学出版社 求解中国邮递员问题 例子 清华大学出版社 例子的初始可行解 清华大学出版社 例子的修正解 清华大学出版社 四 奇偶点作业法的改进方法 奇偶点作业法的瓶颈是需检查太多的链 可以首先求出任意一对奇点之间的最短路 从中选出总路长最小的组合方案 也可以由奇点构成偶图 求最小匹配得到最优解 清华大学出版社 一个四奇点的例子 清华大学出版社 习题 P 267 习题9P 268 习题10 图9 10 A B 清华大学出版社 4 7网络计划技术 网络计划技术的基本概念网络图的绘制网络图的时间参数计算网络优化 清华大学出版社 一 网络计划技术的基本概念 工程计划与甘特图不易表现工程全貌不便于对各项工作的安排进行筹划和推敲不能识别影响进度的关键工作不能反映一项工作不能按进度完成时对工程进度的影响计划评审技术 PERT 与关键路线法 CPM 系统性和协调性动态性和可控性科学性 清华大学出版社 甘特图 清华大学出版社 前甘特图的网络图 清华大学出版社 二 网络图的绘制 网络图的构成作业 工作 工序 活动 箭头表示 箭头之上表示工作名称 之下表示工作时间 可有虚工作 事项 节点表示 表示某个工作的结束和另一工作的开始 清华大学出版社 一个基建项目网络图 清华大学出版社 二 网络图的绘制 从开始节点到结束节点的一条路经叫做路线一个网络图的有多条路线 每条路线有一个总时间总时间最长的路线叫做关键路线 关键路线的总时间叫做工期看下面的例子 清华大学出版社 网络图的路线 清华大学出版社 以上网络图共有8条路线可以计算出这8条路线的总时间 最长的是16天 关键路线是当某些工作的时间调整后 可能引起关键路线的变化和工期的变化 例如将工作E的时间缩短为4天 则工期缩短为13天 关键路线将变为 清华大学出版社 网络图的画法 作业的串联作业的并联 清华大学出版社 网络图的画法 作业的交叉作业的合并 清华大学出版社 清华大学出版社 绘制网络图的基本原则 两事项间只能有一项作业 改为 清华大学出版社 绘制网络图的基本原则 网络图应从左向右延伸 编号应从小到大 且不重复 箭头事项编号大于箭尾事项编号网络图只能一个开始节点 一个终止节点不能出现循环路线尽量少交叉 采用暗桥 有层次性 清华大学出版社 清华大学出版社 使用暗桥 清华大学出版社 网络图的绘制步骤 确定目标 做好准备工作任务分解和分析绘制网络图 清华大学出版社 表4 1调查项目的任务分解和分析 清华大学出版社 绘制作业图的方法 试探性绘制法计算机辅助绘制法流程图过渡绘制法 清华大学出版社 试探性绘制法 试探 清华大学出版社 试探性绘制法 修改 清华大学出版社 流程图过渡绘制法 流程图 清华大学出版社 流程图过渡绘制法 加事项 清华大学出版社 流程图过渡绘制法 去方框 清华大学出版社 流程图过渡绘制法 修改 清华大学出版社 三 网络图时间参数计算 作业时间的确定事项时间参数的计算作业时间参数的计算关键路线的寻找方法按期完成计划的概率 清华大学出版社 作业时间的确定 对具有标准的作业 采用单一时间估计法对一般性作业 采用三点时间估计法最乐观时间 a最可能时间 m最悲观时间 b计算时间期望值和方差 清华大学出版社 作业时间计算方法 清华大学出版社 事项参数的计算 事项最早时间事项最迟时间 i i 清华大学出版社 图上计算法 清华大学出版社 矩阵法计算事项时间 清华大学出版社 作业时间参数的计算 作业开始最早时间作业结束最早时间作业开始最迟时间作业结束最迟时间总时差单时差 清华大学出版社 作业最早时间 作业最迟时间 清华大学出版社 时差 总时差 单时差 清华大学出版社 时差之间的关系 清华大学出版社 表4 3作业时间参数计算 清华大学出版社 关键路线的确定方法 总时差为零的作业即是关键作业 关键作业构成关键路线破圈法也可采用最长路线法 清华大学出版社 按期完成计划的概率 每项作业的时间是一个随机变量 近似服从分布 均质和标准差为工期也是一个随机变量 它的期望值为各关键作业时间期望之和 清华大学出版社 按期完成计划的概率 当作业数足够多时 工期近似服从正态分布 清华大学出版社 按期完成计划的概率 其中按期完成的概率 清华大学出版社 图4 44工期概率分析的例子 清华大学出版社 计算按期完成概率 工期的期望值和标准差是分别计算要求20天 21天和19天完成的概率 清华大学出版社 计算概率下完工的工期 由于所以可根据要求的概率 查表得到z 在用上式计算TD 例如 要求完工概率为0 9的工期 由得z 1 28 所以 清华大学出版社 四 网络优化 工期限定 资源需要平衡资源有限 工期希望最短工期