网络优化图及网络（运筹学）

1 第六章网络优化模型 图的基本概念最小树问题最短路问题最大流问题 2 18世纪 哥尼斯堡城中有一条普雷格尔河 河上有七座桥将河中的两个小岛与河岸连接起来 人们提出了这样的问题 一个散步者能否从某地出发 走遍七桥且每座桥恰好经过一次 最后回到原地 陆地A 陆地B 岛D 岛C A D B C 1736年瑞士数学家欧拉将两岸和小岛抽象为四个点 将桥抽象为七条边 此问题归结为一笔画问题 3 例1 6个球队之间的赛事关系 P131 4 例2在五个城市之间架设电话线 要求任两个城市之间都可以相互通话 允许通过其他城市 并且电话线的根数最少 用v1 v2 v3 v4 v5代表五个城市 如果在某两个城市之间架设电话线 则在相应的两点之间联一条边 这样一个电话线网就可以用一个图来表示 显然 这个图必须是连通的 而且是不含圈的连通图 如左图所示 5 例3某工厂的组织机构如下图所示 厂长 行政办公室 生产办公室 生产计划科 技术科 设计组 工艺组 供销科 财务科 行政科 车间 铸造工段 锻压工段 二车间 三车间 四车间 该厂的组织机构图就是一个树 6 例4树图倒置的树 根 root 在上 叶 leaf 在下 7 例5 石油流向管网示意图 P131 此为一个有向图 8 1图的基本概念 无向图 G V E 顶点或节点 v 图5 3子图与部分图 边 e eij vi vj vj vi 有向图 G V A 弧 a aij vi vj vj vi 树图 T V E 没有任何圈的连通图最小支撑树 最小树 能够把所有节点连接起来 且树枝总长最小的树图 连通图G 如果图G中任何两点间至少有一条链 链 连接两个顶点的一个序列 例1中 a b c a b e d 等 圈 两个端点重合的链 例1中 a b c a a b d a 等 路 从节点vi到vj的弧和节点组成的一个序列回路 圈 始点和终点重合的路 9 图的引入 例6 在一个人群中 相互认识这个关系我们可以用图来表示 右图就是一个表示这种关系的图 我们用G V E 来表示图 其中V为图中点的集合 E为边的集合 本例中 V v1 v2 v7 E e1 e2 e5 10 如果我们把上面的例子中 相互认识 的关系改成 认识 的关系 那么只用两点的联线就很难刻间他们之间的关系了 例如 周认识赵 而赵却不认识周 这时我们引入一个带箭头的联线 称之为弧 这就是有向图 右图就是一个反映这七人 认识 关系的有向图 有向图记为D V A 其中V为图D的点集合 A为图D的弧集合 本例中 V v1 v2 v7 D a1 a2 a15 无向图是一种特殊的有向图 无向图的边实际就是等价于两条反向的弧 11 2 最小树的计算 方法一避圈法开始选一条权最小的边 以后每一步中 总从未被选取的边中选一条权最小的边 并使之与已选取的边不构成圈 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 这就得到了该图的一个最小树 12 方法二破圈法任取一个圈 从圈中去掉一条权最大的边 在余下的图中 重复这个步骤 一直到一个不含圈的图为止 这时的图便是最小树 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 这就得到了该图的一个最小树 13 例7 某公园要为主要景点铺设光缆 为减少成本 要让这个光缆线路在连接所有景点的条件下 费用尽可能的少 下图每个点A E是一个主要景点 S和T分别是入口和出口 线段边上的数字表示在这两点之间铺设光缆所要花费的成本 问应该如何铺设 公园问题的路径系统 14 分析显然 此问题是一个最小树的生成问题 用避圈法来做 软件实现在WinQSB中模块NetworkModeling的 MinimalSpanningTree 实现结果与此完全相同 最小树 如图中红线所示 公园各景观间的最小电话安装 15 例8 求最小树 16 方法1 避圈法 将图中的边按权的大小从小到大排列 先取边 v1 v2 再依次加入不形成圈的各边 就可以得最小树 总权数为11 17 方法2 破圈法 将图中的各圈中权重最大的边去掉 直到没有圈为止 18 用WinQSB求最小树 19 例9某大学准备对其所属的7个学院办公室计算机联网 这个网络的可能联通的途径如下图所示 图中v1 v2 v7表示7个学院办公室 图中的边为可能联网的途径 边上所赋的权数为这条路线的长度 单位为百米 请设计一个网络能联通7个学院办公室 并使总的线路长度为最短 线路总长度1 2 3 3 3 7 19 20 3 最短路问题 实际例子 公园的入口到各个景点 各个景点之间 以及各景点到出口处的道路都有很多条线路 需要事先确定从公园入口 各个景点到出口处的最短线路 作为游客的最佳游玩线路 最短路问题是对一个赋权的有向图D 其赋权根据具体问题的要求可以是路程的长度 成本的花费等等 中的指定的两个点s和t找到一条从s到t的路 使得这条路上所有弧的权数的总和最小 这条路被称之为从s到t的最短路 这条路上所有弧的权数的总和被称之为从s到t的距离 21 举例 求下图v1到v6的最短路径 给点vi标号 d vj d表示路径从v1到vj的最短距离 vj是最短路径上vi的前一节点 0 s 2 v1 3 v3 3 v1 8 v4 22 双标号法 计算步骤 1 给起点v1以标号 0 s 表示从v1到v1的距离为0 v1为起点 2 找出已标号的点的集合I 没标号的点的集合J 以及弧的集合 vi vj vi I vj J 这里弧的集合是指所有从已标号的点到未标号的点的弧的集合 3 如果上述弧的集合是空集 则计算结束 如果vt已标号 lt kt 则vs到vt的距离是lt 而从vs到vt的最短路径 则可以从vt反向追踪到起点vs而得到 23 例10 求节点1 5的最短路径 0 S 1 1 2 1 4 2 4 3 7 4 最短路径 1 2 4 5 24 用WinQSB求解只有存在i j的有向边时才输入数据 否则为空 也可以用线性规划来求解书P129 例6 2 25 例11 电信公司准备在甲 乙两地沿路架设一条光缆线 问如何架设使其光缆线路最短 下图给出了甲 乙两地间的交通图 图中的点v1 v2 v7表示7个地名 其中v1表示甲地 v7表示乙地 点之间的联线 边 表示两地之间的公路 边所赋的权数表示两地间公路的长度 单位为km 26 实际中我们还可以从各点的标号找到v1到各点的距离 以及从v1到各点最短路径 例如 从v4的标号 18 v5 可知v1到v4的距离为18 并可找到v1到v4的最短路径为 10 v1 0 s 13 v3 16 v5 14 v3 18 v5 22 v6 27 例11 求节点1 6之间的最短路 28 2 1 0 S 29 3 3 2 1 0 S 30 3 3 2 1 0 S 5 2 31 3 3 2 1 0 S 5 2 7 5 32 3 3 2 1 0 S 5 2 7 5 8 4 33 用WinQSB求解把节点数和节点之间边的长度输入 节点间没有边则不输入任何值注意 无向图中i j的边与j i的边的长度相同 34 应用举例 例12设备更新问题 某企业使用一台设备 在每年年初都要决定是购置新设备还是继续使用旧的 购置新设备要支付一定的购置费 使用旧设备则要支付维修费 制定一个五年内的设备更新计划 使得总支付费用最少 已知该设备在各年年初的价格为 已知使用不同时间的设备维修费用为 35 设以vi i 1 2 3 4 5 表示 第i年初购进一台新设备 这种状态 以v6表示 第5年末 这种状态 以弧 vi vj 表示 第i年初购置的一台设备一直使用到第j年初 这一方案 以wij表示这一方案所需购置费和维修费之和 这样可建立本例的网络模型 于是 该问题就可归结为从图中找出一条从v1到v6的最短路问题 36 v1 v2 v3 v5 v6 v4 16 30 22 16 59 41 22 41 30 17 31 23 17 23 18 0 S 16 v1 37 v1 v2 v3 v5 v6 v4 16 30 22 16 59 41 22 41 30 17 31 23 17 23 18 0 S 16 v1 22 v1 38 v1 v2 v3 v5 v6 v4 16 30 22 16 59 41 22 41 30 17 31 23 17 23 18 0 S 16 v1 22 v1 30 v1 39 v1 v2 v3 v5 v6 v4 16 30 22 16 59 41 22 41 30 17 31 23 17 23 18 0 S 16 v1 22 v1 30 v1 41 v1 40 v1 v2 v3 v5 v6 v4 16 30 22 16 59 41 22 41 30 17 31 23 17 23 18 0 S 16 v1 22 v1 30 v1 41 v1 53 v3 53 v4 从图中可以得出两条最短路 v1 v3 v6 v1 v4 v6 41 4 最大流问题 许多系统中包含了流量问题 例如 公路系统中有车辆流 控制系统中有信息流 供水系统中有水流 金融系统中有现金流等等 对于这样一些包含了流量问题的系统 我们往往要求出其系统的最大流量 例如 某公路系统容许通过的最多车辆数 某供水系统的最大水流量等等 以便我们加深对某个系统的认识并加以改造 所谓的最大流量问题就是 给了一个带收发点的网络 其每条弧的赋权称之为容量 在不超过每条弧的容量的前提下 求出从发点到收点的最大流量 42 例13 某石油公司拥有一个管道网络 使用这个网络可以把石油从采地运送到一些销售点 这个网络的一部分如下图所示 由于管道直径的不同 它的各段管道 vi vj 的流量 容量 cij也是不一样的 这在下图中已标出 cij的单位为万加仑 小时 如果使用这个网络系统从采地v1向销地v7运送石油 问每小时能运送多少加仑石油 43 方法1 线性规划模型 设弧 vi vj 上的流量为fij 网络上的总的流量为F 则有 v2 v4 v3 v5 v6 v1 v7 容量限制 非负性 44 方法2 网络图法 1 我们对网络上弧的容量的表示作一些改进 对一条弧 vi vj 的容量我们用一对数 cij 0 标在弧 vi vj 上 cij靠近vi点 0靠近vj点表 cij表示从vi到vj容许通过的可用容量 0表示已分配的流量 如下图所示 原问题图画为 45 基本思路 1 找出一条从发点到收点的路 在这条路上的每一条弧的可用容量都大于零 如果不存在这样的路 则已求得最大流 2 找出这条路上各条弧的最小的可用容量Pf 通过这条路增加网络的流量Pf 3 在这条路上 减少每一条弧的可用容量Pf 同时增加这些弧的流量Pf 返回步骤 1 当然由于在步骤 1 中所选择的路不一样 计算过程也不一样 但最终所求得的最大流量应该是一样的 为了使算法更快捷有效 我们一般在步骤 1 中尽量选择包含弧数最少的路 46 第一次迭代 选择路为v1 v4 v7 弧 v4 v7 的可用容量为2 决定了pf 2 改进的网络流量图如下 47 第二次迭代 选择路为v1 v2 v5 v7 弧 v2 v5 的可用容量为3 决定了pf 3 改进的网络流量图如下 48 第三次迭代 选择路为v1 v4 v6 v7 弧 v4 v6 的可用容量为1 决定了pf 1 改进的网络流量图如下 3 4 49 第四次迭代 选择路为v1 v4 v3 v6 v7 弧 v3 v6 的可用容量为2 决定了pf 2 改进的网络流量图如下 50 第五次迭代 选择路为v1 v2 v3 v5 v7 弧 v2 v3 的可用容量为2 决定了pf 2 改进的网络流量图如下 通过第五次迭代后在上图中已找不到从发点到收点每一条弧可用容量都大于零的一条路 运算停止 则我们得到此网络从vl到v7的最大流量为10 也就是从采地v1 向销地v7每小时可运送10万加仑石油 51 最大流量图如下 52 方法3 WinQSB软件求解 53 最小费用最大流问题 在求解网络最大流问题的时候 我们常常还考虑 费用 多少的问题 最小费用最大流问题就是这样的问题 所谓最小费用最大流问题就是 给了一个带收发点的网络 对每一条弧 vi vj 除了给出了容量cij外 还给出了这条弧的单位流量的费用bij 要求一个最大流F 并使得总运送费用最小 54 例14 由于输油管道的长短不一 所以在例6中每段管道 vi vj 除了有不同的流量限制cij之外 还有不同的单位流量的费用bij cij的单位为万加仑 小时 bij的单位为百元 万加仑 对每段管道 vi vj 我们都用 cij bij 标出 如下图所示 如果使用这个网络系统从采地v1向销地v7运送石油 怎样运送才能运送最多的石油并使得总的运送费用最小 并求出其每小时的最大的流量及每小时的最大流量的最小费用 55 方法1 线性规划模型 我们用线性规划来求解此题 可以分两步走 第一步 先求出此网络图中的最大流量F 这已在例13建立了线性规划的模型获得结果 第二步 在最大流量F的所有解中 找出一个最小费用的解 我们来建立第二步中的线性规划的模型 仍然设弧 vi vj 上的流量为fij 这时已知网络上最大流量为F 只要在例13的约束条件上 再加上一总流量必须等于F的约束条件 f12 f14 F 即得此线性规划的约束条件 此线性规划的目标显然是求其流量的最小费用 我们就得到线性规划模型如下 56 目标函数 约束条件 57 如果我们把例14的问题改为 每小时运送6万加仑的石油从采地v1到销地v7最小的费用是多少 应怎样运送 这就变成了一个最小费用流的问题 一般来说 所谓最小费用流的问题就是 在给定了收点及发点并对每条弧 vi vj 赋权以容量cij及单位费用bij的网络中 求一个给定值f的流量的最小费用 这个给定值f的流量应小于等于最大流量F 否则无解 求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可 在例6中只要把f12 f14 10改为f12 f14 f 6得到了最小费用流的线性规划模型 58 方法2 网络图解法 类似于最大流的网络图解法 每条边采用双标号法标号 cij bij 表示从vi到vj的可用容量为cij 单位流量的费用为bij 标号 0 bij 表示从vj到vi的流量为0 59 方法的基本思想 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样 不同的只是在步骤 1 中要选择一条总的单位费用最小的路 而不是包含边数最少的路 如果我们把每条弧的单位费用看成弧的长度 也就是要选择一条从发点到收点的最短路 60 第一次迭代 基于费用找最短路径 v1 v4 v6 v7 此路的总单位费用为3 3 4 10 弧 v4 v6 的可用容量为1 决定了pf 1 改进的网络流量图如下图所示 第一次迭代后总流量为1 总的费用10 x1 10 v5 v4 v3 v2 61 第二次迭代 把弧 v4 v6 去掉 然后再基于费用找最短路径 v1 v4 v7 此路的总单位费用为3 8 11 弧 v4 v7 的可用容量为2 决定了pf 2 改进的网络流量图如下图所示 第二次迭代后总流量为3 总的费用10 11x2 32 v5 v4 v3 v2 62 第三次迭代 把弧 v4 v6 v4 v7 去掉 基于费用找最短路径 v1 v4 v3 v6 v7 此路的总单位费用为3 2 3 4 12 弧 v3 v6 的可用容量为2 决定了pf 2 改进的网络流量图如下图所示 第三次迭代后总流量为5 总的费用32 12x2 56 63 第四次迭代 把弧 v4 v6 v4 v7 v3 v6 去掉 基于费用找最短路径 v1 v4 v3 v5 v7 此路的总单位费用为3