运筹学-图论.ppt

图论 第五章图与网络分析 主要内容 1图的基本概念与基本定理2树和最小支撑树3最短路问题4最大流问题5最小费用流问题 什么是图 图论中所谓的图是由一些点 vertices 和一些连接兩点的边 edges 所形成的 5 1图的基本概念与基本定理 图论是应用非常广泛的运筹学分支 它已经广泛地应用于物理学控制论 信息论 工程技术 交通运输 经济管理 电子计算机等各项领域 对于科学研究 市场和社会生活中的许多问题 可以同图论的理论和方法来加以解决 例如 各种通信线路的架设 输油管道的铺设 铁路或者公路交通网络的合理布局等问题 都可以应用图论的方法 简便 快捷地加以解决问题 关于图的第一篇论文是瑞士数学家欧拉 E Euler 在1736年发表的解决 哥尼斯堡 七桥难题的论文 德国的哥尼斯堡城有一条普雷格尔河 河中有两个岛屿 河的两岸和岛屿之间有七座桥相互连接 当地的居民热衷于这样一个问题 一个散步者如何能够走过这七座桥 并且每座桥只能走过一次 最终回到原出发地 尽管试验者很多 但是都没有成功 为了寻找答案 1736年欧拉将这个问题抽象成图所示图形的一笔画问题 K nigsberg Koenigsberg 哥尼斯堡 原为东普鲁士 Prussia 首府 现属俄罗斯 飞地 名为加里宁格勒 Kaliningrad 哥尼斯堡七桥问題 要如何走过每座桥恰一次 再返回出发点 普瑞格爾河 哥尼斯堡七桥问题 A B C D 哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点 A B C D 哥尼斯堡七橋問題可以看成是 对这样一个封闭的图形 是否可以一笔画完成它并且回到原点 数学家欧拉 Euler 1707 1783 于1736年严格地证明了上述哥尼斯堡七桥问题无解 并且由此开创了图论的典型思维方式及论证方式 即能否从某一点开始不重复地一笔画出这个图形 最终回到原点 欧拉在他的论文中证明了这是不可能的 因为这个图形中每一个顶点都与奇数条边相连接 不可能将它一笔画出 这就是古典图论中的第一个著名问题 在实际的生产和生活中 人们为了反映事物之间的关系 常常在纸上用点和线来画出各式各样的示意图 图论应用举例 例如 在组织生产中 为完成某项任务 各工序之间怎样衔接 才能使生产任务完成得既快又好 一个邮递员送信 要走完他负责投递的全部街道 完成任务后回到邮局 应该按照怎样的路线走 所走的路程最短 各种通信网络的合理架设交通网络的合理分布等 生活中的一些例子 台大网路架构图 例5 1图5 2是我国北京 上海 重庆等十四个城市之间的铁路交通图 这里用点表示城市 用点与点之间的线表示城市之间的铁路线 诸如此类还有城市中的市政管道图 民用航空线图等等 图5 3 例5 2有六支球队进行足球比赛 我们分别用点v1 v6表示这六支球队 它们之间的比赛情况 也可以用图反映出来 已知v1队战胜v2队 v2队战胜v3队 v3队战胜v5队 如此等等 这个胜负情况 可以用图5 3所示的有向图反映出来 从以上的几个例子可以看出 我们用点和点之间的线所构成的图 反映实际生产和生活中的某些特定对象之间的特定关系 通常用点表示研究对象 用点与点之间的线表示研究对象之间的特定关系 由于在一般情况下 图中对象的相对位置如何 点与点之间线的长短曲直 对于反映研究对象之间的关系 显的并不重要 因此 图论中的图与几何图 工程图等本质上是不同的 图论中的图是由点 点与点之间的线所组成的 通常 我们把点与点之间不带箭头的线叫做边 带箭头的线叫做弧 如果一个图是由点和边所构成的 那么称为无向图 记作G V E 其中V表示图G的点集合 E表示图G的边集合 连接点vi vj V的边记作 vi vj 或者 vj vi 如果一个图是由点和弧所构成的 那么称为它为有向图 记作D V A 其中V表示有向图D的点集合 A表示有向图D的弧集合 一条方向从vi指向vj的弧 记作 vi vj 图的基本概念 图5 4是一个无向图G V E 其中V v1 v2 v3 v4 E v1 v2 v2 v1 v2 v3 v3 v4 v1 v4 v2 v4 v3 v3 图5 4 图5 5是一个有向图D V A 其中V v1 v2 v3 v4 v5 v6 v7 A v1 v2 v1 v3 v3 v2 v3 v4 v2 v4 v4 v5 v4 v6 v5 v3 v5 v4 v5 v6 v6 v7 图5 5 图的基本概念 一个图G或有向图D中的点数 记作P G 或P D 简记作P 边数或者弧数 记作q G 或者q D 简记作q 如果边 vi vj E 那么称vi vj是边的端点 或者vi vj是相邻的 如果一个图G中 一条边的两个端点是相同的 那么称为这条边是环 如图5 4中的边 v3 v3 是环 图的基本概念 如果两个端点之间有两条以上的边 那么称为它们为多重边 如图5 4中的边 v1 v2 v2 v1 多重图 一个无环 无多重边的图称为简单图 一个无环 有多重边的图称为多重图 以点v为端点的边的个数称为点v的度 次 记作d v 如图5 4中d v1 3 d v2 4 d v3 4 d v4 3 度为零的点称为弧立点 度为1的点称为悬挂点 悬挂点的边称为悬挂边 度为奇数的点称为奇点 度为偶数的点称为偶点 端点的度d v 点v作为端点的边的个数奇点 d v 奇数 偶点 d v 偶数 悬挂点 d v 1 悬挂边 与悬挂点连接的边 孤立点 d v 0 空图 E 无边图 V v1 v2 v3 v4 v5 v6 v7 d v1 3 d v2 5 d v3 4 d v4 4 d v5 1 d v6 3 d v7 0 其中v5为悬挂点 v7为孤立点 图5 7 定理5 1所有顶点度数之和等于所有边数的2倍 证明 因为在计算各个点的度时 每条边被它的两个端点个用了一次 定理5 2在任一图中 奇点的个数必为偶数 证明 设V1 V2分别是图G中奇点和偶点的集合 由定理5 1 有 因为是偶数 也是偶数 因此 也必是偶数 从而V1中的点数是偶数 图的连通性 链 由两两相邻的点及其相关联的边构成的点边序列 如 v0 e1 v1 e2 v2 e3 v3 vn 1 en vn v0 vn分别为链的起点和终点 记作 v0 v1 v2 v3 vn 1 vn 简单链 链中所含的边均不相同 初等链 链中所含的点均不相同 也称通路 圈 若v0 vn则称该链为开链 否则称为闭链或回路或圈 简单圈 如果在一个圈中所含的边均不相同初等圈 除起点和终点外链中所含的点均不相同的圈 v1 v2 v4 v3 v5 v6 v7 初等链 v1 v2 v3 v6 v7 v5 初等圈 v1 v2 v3 v5 v4 v1 简单链 v1 v2 v3 v4 v5 v3 简单圈 v4 v1 v2 v3 v5 v7 v6 v3 v4 以后除特别声明 均指初等链和初等圈 v1 v2 v3 v4 v5 不连通图 v1 v5 v4 v3 v2 v6 连通图 图中任意两点之间均至少有一条通路 否则称为不连通图 连通图 有向图 关联边有方向弧 有向图的边a u v 起点u 终点v 路 若有从u到v不考虑方向的链 且各方向一致 则称之为从u到v的路 初等路 各顶点都不相同的路 初等回路 u v的初等路 连通图 若不考虑方向是无向连通图 强连通图 任两点有路 基本概念 例一摆渡人欲将一只狼 一头羊 一篮菜从河西渡过河到河东 由于船小 一次只能带一物过河 并且狼与羊 羊与菜不能独处 给出渡河方法 解 用四维0 1向量表示 人 狼 羊 菜 在河西岸的状态 在河西岸则分量取1 否则取0 共有24 16种状态 在河东岸的状态类似记作 由题设 状态 0 1 1 0 0 0 1 1 0 1 1 1 是不允许的 从而对应状态 1 0 0 1 1 1 0 0 1 0 0 0 也是不允许的 以可允许的10个状态向量作为顶点 将可能互相转移的状态用线段连接起来构成一个图 根据此图便可找到渡河方法 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 河西 人 狼 羊 菜 河东 人 狼 羊 菜 将10个顶点分别记为A1 A2 A10 则渡河问题化为在该图中求一条从A1到A10的路 从图中易得到两条路 A1A6A3A7A2A8A5A10 A1A6A3A9A4A8A5A10 图的矩阵表示 1 邻接矩阵Adjacencymatrix表示图中两点之间的相互关系两点之间有弧或边的 用1表示 否则用0表示 构成一个矩阵A 有向图 v1 v7 v2 v5 v3 v4 v6 v8 v9 矩阵A的元素全为0的行所对应的点称为汇点上图v8矩阵A的元素全为0的列所对应的点称为源点上图v1 v9 5 2树和最小支撑树 一 树及其性质在各种各样的图中 有一类图是十分简单又非常具有应用价值的图 这就是树 例5 3已知有六个城市 它们之间要架设电话线 要求任意两个城市均可以互相通话 并且电话线的总长度最短 如果用六个点v1 v6代表这六个城市 在任意两个城市之间架设电话线 即在相应的两个点之间连一条边 这样 六个城市的一个电话网就作成一个图 表示任意两个城市之间均可以通话 这个图必须是连通图 并且 这个图必须是无圈的 否则 从圈上任意去掉一条边 剩下的图仍然是六个城市的一个电话网 图5 2 1是一个不含圈的连通图 代表了一个电话线网 图5 2 1 v6 v3 v4 v2 v5 v1 树及其性质 树 既简单又很有用树 一个无圈的连通图 组织结构图 荣国公 贾代善 贾赦 贾政 贾琏 贾珠 贾宝玉 贾环 贾兰 定理 定理1 设G V E 是一个树 p G 2 则G中至少有两个悬挂点 定理2 图G V E 是一个树的充要条件是G不含圈 且恰有p 1条边 定理3 图G V E 是一个树的充要条件是G是连通图 且q G p G 1 定理4 图G V E 是一个树的充要条件是任意两个顶点之间恰有一条链 推论 从一个树中去掉任意一条边 则余下的图是不连通的 在树中不相邻的两个点间添上一条边 则恰好得到一个圈 图的支撑树 设图T V E 是图G V E 的一个支撑子图 如果T是一个树 则称T是G的一个支撑树定理5 图G有支撑树的充要条件是图G是连通的 破圈法 任取一个圈 从中去掉一条边 再对余下的图重复直到不再含图时为止 破圈法 避圈法 在图中任取一条边 找到一条与之不构成圈的边 再找一条前两边不构成圈的边重复直到不再能进行为止取出的边数为p 1条 避圈法 最小支撑树问题 给定图G V E 对G中的每一条边 vi vj 相应地有一个数wij 则称这样的图为赋权图wij称为边 vi vj 上的权权是与边有关的数量指标 可以是距离 时间 费用等 赋权图不仅指出各个点之间的邻接关系 而且同时也表示出各点之间的数量关系广泛应用于解决工程技术及管理等领域的最优化问题最小支撑树问题就是赋权图上的最优化问题之一 设有一个连通图G V E 每一边e vi vj 有一个非负权w e wij wij 0 如果T V E 是G的一个支撑树 称E 中所有边的权之和为支撑树T的权 记为w T 如果支撑树T 的权w T 是G的所有支撑树的权中最小者 则称T 是G的最小支撑树 最小树 即 式中对G的所有支撑树T取最小 最小支撑树问题就是要求G的最小支撑树 方法有二 避圈法Kruskal破圈法常见求赋权图的最小树 例5 4某厂内联结六个车间的道路网如下所示 已知每条路的长 要求沿道路架设联结六个车间的电话线网 使电话线的总长最小 v1 v2 v4 v6 v3 v5 6 5 7 1 5 2 3 4 4 避圈法求最小支撑树 v1 v2 v4 v6 v3 v5 1 5 2 3 4 i 1 E0 从E中选最小权边 依次选最小权边 并使之不构成圈 共选5条边 v1 v2 v4 v6 v5 6 5 7 1 5 2 3 4 4 最后 电话线总长1 2 3 4 5 15 v3 破圈法求最小支撑树 任取一个圈 从中去掉一条权最大的边 依次重复 直到不含圈为止 v1 v2 v4 v6 v5 6 5 7 1 5 2 3 4 4 最后 电话线总长1 2 3 4 5 15 v3 矩阵计算方法 T T T T T T T T T T T T T T T T T T T T T 矩阵计算结果 一 引言最短路径问题是图论中十分重要的最优化问题之一 它作为一个经常被用到的基本工具 可以解决生产实际中的许多问题 比如城市中的管道铺设 线路安排 工厂布局 设备更新等等 也可以用于解决其它的最优化问题 5 3最短路问题 例5 6如图所示的单行线交通网 每弧旁的数字表示这条单行线的距离 现在某人要从v1出发 通过这个交通网到达v8 求使总距离最短的旅行线路 v1 v7 v2 v5 v3 v4 v6 v8 v9 路很多 v1 v7 v2 v5 v3 v4 v6 v8 v9 1 10 2 4 17 6 1 6 13 3 2 1 3 4 13 3 2 10 10 6 31 哪一条最短 最短路算法 如果P是D中从vs到vi的最短路 vi是P中的一个点 那么从vs沿P到vi的路是从vs到vi的最短路 1 图形的标号法2 所有wij 0的情形 Dijkstra法1959 1 图形的标号法 先标出离终点最近的一段 然后标号与该点距离最短的点 继续逆推至始点 C4 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 6 8 7 6 6 6 8 8 2 2 2 2 5 5 3 3 3 3 3 3 4 4 3 5 1 0 4 3 7 5 9 7 6 8 13 10 9 13 12 16 18 从A到G的最短路为 A B1 C2 D1 E2 F2 G 2 Dijkstra法 基本思路 从vs出发 逐步地向外探寻最短路 执行过程中 与每个点对应 记录下一个数 称为此点的标号 它或者表示从vs到该点的最短路的权 称为P标号 或者是从vs到该点的最短路的权的上界 称为T标号 方法的每一步是修改T标号 并且把某一个具T标号的点改变为具P标号的点 从而使D中具P标号的点多一个 如此经过p 1步 就可以求出从vs到各点的最短路 Dijkstra法具体步骤 开始 i 0 令S0 vs P vs 0 vs 0 对每一个v vs 令T v v M 令k s1 如果Si V 算法终止 这时 对每个v Si d vs v P v 否则转入步骤22 考察每个使 vk vj A且vj Si的点vj 如果T v P vk wkj 则把T vj 修改为P vk wkj 把 vj 修改为k 否则转入步骤3 3 令T vji min T vj 如果T vji 则把vji的T标号变为P标号P vji T vji 令Si 1 SiU vji k ji 把i换成i 1 转入步骤1 否则终止 这时对每一个 而对每一个v Si d vs v T v v1 v2 v3 v4 v5 v6 v7 v8 0 v2 v3 v4 v5 v6 v7 v8 P T 0 0 M M M M M M M v1 v7 v2 v5 v3 v4 v6 v8 v9 若T v P vk wkj则T v P vk wkj vj 修改为k找到min T vj 将其T P标号P vj T vj S v1 6 3 1 1 1 1 1 v4 v3 11 4 3 5 3 5 v2 6 2 6 v5 10 5 9 5 12 5 9 v7 10 v6 12 v8 v1到v8最短路V13258 求s到t的最短路 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0 S PQ s 2 3 4 5 6 7 t s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0 S PQ s 2 3 4 5 6 7 t s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s PQ 2 3 4 5 6 7 t X X X s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s PQ 2 3 4 5 6 7 t X X X s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 PQ 3 4 5 6 7 t X X X s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 PQ 3 4 5 6 7 t X X X X 33 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 PQ 3 4 5 6 7 t X X X X 33 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 PQ 3 4 5 7 t X X X X 33 44 X X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 PQ 3 4 5 7 t X X X 44 X X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 7 PQ 3 4 5 t X X X 44 X 35 X 59 X 24 X 33 X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 7 PQ 3 4 5 t X X X 44 X 35 X 59 X X 33 X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 6 7 PQ 4 5 t X X X 44 X 35 X 59 X X 51 X 34 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 6 7 PQ 4 5 t X X X 44 X 35 X 59 X X 51 X 34 X 33 X 32 24 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 5 6 7 PQ 4 t X X X 44 X 35 X 59 X X 51 X 34 24 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 5 6 7 PQ 4 t X X X 44 X 35 X 59 X X 51 X 34 24 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 PQ t X X X 44 X 35 X 59 X X 51 X 34 24 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 PQ t X X X 44 X 35 X 59 X X 51 X 34 X 50 X 45 X 33 X 32 24 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 t PQ X X X 44 X 35 X 59 X X 51 X 34 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 t PQ X X X 44 X 35 X 59 X X 51 X 34 X 50 X 45 X 33 X 32 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求从1到8的最短路径 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 w1 0 min c12 c14 c16 min 0 2 0 1 0 3 min 2 1 3 1X 1 4 p4 1 p4 1 p1 0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 4 min c12 c16 c42 c47 min 0 2 0 3 1 10 1 2 min 2 3 11 3 2X 1 2 4 p2 2 p1 0 p4 1 p2 2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 min c13 c23 c25 c47 min 0 3 2 6 2 5 1 2 min 3 8 7 3 3X 1 2 4 6 p6 3 p2 2 p4 1 p1 0 p6 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 min c23 c25 c47 c67 min 2 6 2 5 1 2 3 4 min 8 7 3 7 3X 1 2 4 6 7 p7 3 p2 2 p4 1 p1 0 p6 3 p7 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min c23 c25 c75 c78 min 2 6 2 5 3 3 3 8 min 8 7 6 11 6X 1 2 4 5 6 7 p5 6 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min c23 c53 c58 c78 min 2 6 6 9 6 4 3 8 min 8 15 10 11 8X 1 2 3 4 5 6 7 p3 8 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 min c38 c58 c78 min 8 6 6 4 3 7 min 14 10 11 10X 1 2 3 4 5 6 7 8 p8 10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 8 1到8的最短路径为 1 4 7 5 8 长度为10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 三 含有负权的最短路的求法 例 求从v1到v8的最短路 0 1 2 3 0 5 2 7 1 1 5 0 5 2 7 3 1 5 6 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 3 1 5 6 从v1到v8的最短路的长度为 6从v1到v8的最短路线为 v8 v6 v3 v1 应用举例 设备更新问题 某企业使用一台设备 在每年年初 企业领导部门就要决定是购置新的 还是继续使用旧的 若购置新设备 就要支付一定的购置费用 若继续使用旧的 则需支付一定的维修费用 现在的问题是如何制定一个几年之内的设备更新计划 使得总的支付费用最少 我们用一个五年之内要更新某种设备的计划为例 若已知该种设备在各年年初的价格如下表 还知使用不同时间的设备所需要的维修费用如下表 可供选择的设备更新方案显然是很多的 例如 每年都购置一台新设备 则其购置费用为11 11 12 12 13 59 而每年支付的维修费用为5 五年合计为25 于是5年的总费用为59 25 84再如 每1 3 5年各购进一台 此时设备购置费用为11 12 13 36 维修费用为5 6 5 6 5 27 5年总费用为36 27 63 如何制定总费用最省的设备更新计划呢 转化为最短路问题 用点代表 第i年年初购进一台新设备 这样上述设备更新问题就变为 在有向赋权图G V E F 图解如下 中求v1到v6的最短路问题 由实际问题可知 设备使用三年后应当更新 因此删除该图中v1到v5 v1到v6 v2到v6的连线 又设备使用一年后就更新则不划算 因此再删除该图中v1v2 v2v3 v3v4 v4v5 v5v6五条连线后得到 从上图中容易得到v1到v6只有两条路 v1v3v6和v1v4v6 而这两条路都是v1到v6的最短路 五年的总费用为53 例拣货路径问题Pickpath 货架分布要拣货物 第1步从第1通道到第2通道每条路径代表图中的一条边 第2步找出从第2通道到第3通道的每条路径 第3步找出从第3通道到第4通道的每条路径 第4步找出从第4通道到完成的每条路径 Findtheshortestpathoftheassociatedgraph Theshortestpathontheassociatedgraphgivesanefficientpickpathinwarehouse 对应图的最短路给出了仓库的有效拣选路径 5 4网络的最大流 5 4 1网络的最大流的概念网络流一般在有向图上讨论定义网络上支路的容量为其最大通过能力 记为cij 支路上的实际流量记为fij图中规定一个发点s 一个收点t节点没有容量限制 流在节点不会存储容量限制条件 0 fij cij平衡条件 5 4网络的最大流 图中规定一个发点s 一个收点t 节点没有容量限制 流在节点不会存储 容量限制条件 0 fij cij 平衡条件 满足上述条件的网络流称为可行流 总存在最大可行流当支路上fij cij 称为饱和弧 v f 为可行流的流量最大流问题也是一个线性规划问题 定义 设f是一个可行流 是vs从vt到的一条链 若 满足下列条件 则 是可行流的一条增广链 1 弧 vi vj 上 即 中每一条弧是非饱和弧 2 弧 vi vj 上 即 中每一条弧是非零流弧 定义 把网络分割为两个成分的弧的最小集合 其中一个成分包含s点 另一个包含t点 一般包含s点的成分中的节点集合用V表示 包含t点的成分中的节点集合用V表示截量集容量是指截量集中前向弧的容量之和 福特 富克森定理 网络的最大流等于最小截量集容量 5 4 2确定网络最大流的标号法 从任一个初始可行流出发 如0流基本算法 找一条从s到t点的增广链 若在当前可行流下找不到增广链 则已得到最大流增广链中与s到t方向一致的弧称为前向弧 反之后向弧 增广过程 前向弧f ij fij 后向弧f ij fij 增广后仍是可行流 最大流最小截量的标号法步骤 第一步 标号过程 找一条增广链1 给源点s标号 s q s 表示从s点有无限流出潜力2 找出与已标号节点i相邻的所有未标号节点j 若 1 i j 是前向弧且饱和 则节点j不标号 2 i j 是前向弧且未饱和 则节点j标号为 i q j 表示从节点i正向流出 可增广q j min q i cij fij 3 j i 是后向弧 若fji 0 则节点j不标号 4 j i 是后向弧 若fji 0 则节点j标号为 i q j 表示从节点j流向i 可增广q j min q i fji 最大流最小截量的标号法步骤 3 重复步骤2 可能出现两种情况 1 节点t尚未标号 但无法继续标记 说明网络中已不存在增广链 当前流v f 就是最大流 所有获标号的节点在V中 未获标号节点在V中 V与V间的弧即为最小截量集 算法结束 2 节点t获得标号 找到一条增广链 由节点t标号回溯可找出该增广链 到第二步 最大流最小截量的标号法步骤 第二步 增广过程1 对增广链中的前向弧 令f f q t q t 为节点t的标记值2 对增广链中的后向弧 令f f q t 3 非增广链上的所有支路流量保持不变第三步 抹除图上所有标号 回到第一步一次只找一条增广链 增广一次换一张图最后一次用广探法 以便找出最小截量集 最大流最小截量集的标号法举例 s s 6 2 6 3 1 4 1 s s 5 2 2 5 2 4 2 s s 3 2 3 最小截量集 5 5最小费用最大流问题 在实际的网络系统中 当涉及到有关流的问题的时候 我们往往不仅仅考虑的是流量 还经常要考虑费用的问题 比 如一个铁路系统的运输网络流 即要考虑网络流的货运量最大 又要考虑总费用最小 最小费用最大流问题就是要解决这一类问题 我们首先考察 在一个网络D中 当沿可行流f的一条增广链 以调整量 1改进f 得到的新可行流f 的流量 有v f v f 1 而此时总费用b f 比b f 增加了 设一个网络D V A C 对于每一个弧 vi vj A 给定一个单位流量的费用bij 0 网络系统的最小费用最大流问题 是指要寻求一个最大流f 并且流的总费用达到最小 结论 如果可行流f在流量为v f 的所有可行流中的费用最小 并且 是关于f的所有增广链中的费用最小的增广链 那么沿增广链 调整可行流f 得到的 我们将叫做这条增广链的费用 新可行流f 也是流量为v f 的所有可行流中的最小费用流 依次类推 当f 是最大流时 就是所要求的最小费用最大流 显然 零流f 0 是流量为0的最小费用流 寻求最小费用流 总可以从零流f 0 开始 下面的问题是 如果已知f是流量为v f 的最小费用流 那么就要去寻找关于f的最小费用增广链 对此 重新构造一个赋权有向图M f 其顶点是原网络D的顶点 而将D中的每一条弧 vi vj 变成两个相反方向的弧 vi vj 和 vj vi 并且定义M f 中弧的权wij为 并且将权为 的弧从M f 中略去 这样 在网络D中寻找关于f的最小费用增广链就等于价于在M f 中寻求从vs到vt的最短路 算法开始 取零流f 0 0 一般地 如果在第K 1步得到最小费用流f K 1 则构造图M f k 1 在图M f k 1 中 寻求从vs到vt的最短路 如果存在最短路 则f k 1 就是最小费用最大流 如果存在最短路 则在原网络D中得到相对应 一一对应 的增广链 0 在增广链 上对f k 1 进行调整 取调整量 令 得到一个新的可行流f k 在对f k 重复以上的步骤 直到D中找不到相对应的增广链时为止 例求图5 5 1所示网络中的最小费用最大流 弧旁的权是 bij cij 图5 5 1 解 1 取初始可行流为零流f 0 0 构造赋权有向图M f 0 求出从vs到vt的最短路 vs v2 v1 vt 如图5 5 1a中双箭头所示 图5 5 1a 2 在原网络D中 与这条最短路相对应的增广链为 vs v2 v1 vt 3 在 上对f 0 0 进行调整 取 5 得到新可行流f 1 如图5 5 1b所示 按照以上的算法 依次类推 可以得到f 1 f 2 f 3 f 4 流量分别为5 7 10 11 并且分别构造相对应的赋权有向图M f 1 M f 2 M f 3 M f 4 由于在M f 4 中已经不存在从vs到vt的最短路 因此 可行流f 4 v f 1 11是最小费用最大流 M f 1 图5 5 1c M f 2 图5 5 1e 8 8 10 3 4 3 2 0 7 7 10 2 5 5 图5 5 1f f 3 v f 3 10 v1 vs v2 v3 vt ApplicationsofNetworkOptimization网络最优化模型的应用 网络在交通 电子和通讯网络遍及我们日常生活的各个方面 网络规划也广泛用于解决不同领域中的各种问题 如生产 分配 项目计划 厂址选择 资源管理和财务策划等等 网络规划为描述系统各组成部分之间的关系提供了非常有效直观和概念上的帮助 广泛应用于科学 社会和经济活动的每个领域中 Networkrepresentation网络表述 这种描述还有其他应用吗 TypesofNetworkOptimizationProblem网络最优化问题类型 MinimumCostNetworkFlowModel最小费用流问题MaximumFlowProblems最大流问题ShortestPathProblem最短路问题MinimumSpanningTreeProblem最小支撑树问题 MinimumCostNetworkFlowModel最小费用流问题 最小费用流问题的构成 节点 nodes 供应点 需求点 转运点 弧 arcs 目标 通过网络满足需求提供供应 最小化流的总成本 AssumptionsofMinimumCostNetworkFlow最小费用流问题的假设 至少一个供应点一个需求点剩下都是转运点通过弧的流只允许沿着箭头方向流动 通过弧的最大流量取决于该弧的容量网络中有足够的弧提供足够容量 使得所有在供应点中产生的流都能够到达需求点在流的单位成本已知前提下 通过每一条弧的流的成本和流量成正比 CharacteristicofSolution解的特征 具有可行解的特征 在以上的假设下 当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时 最小费用流问题有可行解 具有整数解的特征 只要其所有的供应 需求和弧的容量都是整数值 那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解 DistributionUnlimitedCo 无限配送公司 无限配送公司的最小成本流问题的电子表格模型 实际举例 NetworkSimplexMethod网络单纯形法 实际运用中解决比较大型问题时需要用不同的方法 网络单纯形法可以用来解决那些对于单纯形法来说太大而无法解决的大型问题 ExcelSolver软件中没有网络单纯形法 但是其他的线性规划的商业软件包通常都有这种方法 SomeApplications一些实际