运筹学课件--第七章 网络分析

1、管理运筹学-管理科学方法,李军,桂林电子科技大学商学院,Sub title,OR:SM,第7 章 图与网络分析 内容提要,2,第一节 第二节 第三节 第四节 第五节,图论的概念 最小树问题 最短路问题 网络最大流 最小费用流,OR:SM,OR:SM,哥尼斯堡，原属 波兰，现属俄罗 斯，名为加里宁 格勒,3,OR:SM,18世纪，哥尼斯堡城（当时东普鲁士柯尼斯堡，今日俄罗斯加里宁 格勒）中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸 连接起来。,茶余饭后，人们提出了这样的问题：一个散步者能否从某地出发，,走遍七座桥且每座桥恰好经过一次，最后回到原地？,4,OR:SM,第7 章 网络分析

2、1736年瑞士数学家欧拉将两岸和小岛抽象 为四个点，将桥抽象为七条边，此问题归结为 一笔画问题。,陆地A,A,岛D,岛C,D,C,B 陆地B 欧拉回答的根据是：若图是连通的，且图中奇点(和奇数条边相关联的点) 的数目为0或2时，则图能“一笔画”。奇点的数目为零时，则图中任一点即是 “一笔画”的起点又是终点。奇点的数目为2时，则两点中任一点为“一笔画” 的起点，而另一点为终点。前图中奇点数目为4，不满足“一笔画”规则，因 此是无解的。 哥尼斯堡七桥问题，用图论的方法得到了简捷的证明，所以欧拉被人们 公认为图论的创始人，人们称他为“图论之父”。,5,OR:SM,OR:SM,第一节,图论的概念,一、

3、图的内涵 1、图的定义 图论的图与一般几何图形或代数函数图形是完全不同的 图论中的图:由一些点和连接点的线所组成的“图形” 点和线的位置是任意的 线的曲直、长短与实际无关，代表的只是点与点之间的相互关系 例：表示苏州v1 、杭州v2 、上海v3 、南京v4仓储网点之间的物流运输线路关系,v2,e4,e1,e5 v1 e2 v3,e3,e6, v4,e2,e3,v2 e4 v3 e5,e6,e5 e2,e1, v4 e3 v1,6, v1,e1, v2,e4, v3,e6, v4,OR:SM,OR:SM,第一节,图论的概念,一、图的内涵 2、图的分类 不带箭头的连线称为“边”，如公路运输线路；

4、带箭头的连线称为“弧”，如供排水的管道运输线路。,1、无向图 由点和边的集合所构成,2、有向图 由点和弧的集合所构成, 链：无向网络中，前后相继点和边 路径：有向网络图中，前后相继并且,7,的交替序列称为一条链。 圈：闭合的链称为一个圈。,方向一致的点弧序列称为一条路径。 回路：闭合的路径称为一个回路。 OR:SM,OR:SM,8,第一节 图与网络的基本概念 图及其分类 3、简单图 无环，且任意两点间 不多于一条边,图论的概念 4、多重图 有环，或有多重边,OR:SM,OR:SM,第一节 图与网络的基本概念 母图、子图、支撑子图,图论的概念,9,母图,子图,支撑子图（生成子图）,OR:SM,O

5、R:SM,第一节,图论的概念,图与网络的基本概念 网络（赋权图） 在实际问题中，只用图来描述所研究的对象间的关系往往是不够的，而常 常还需要考虑与点或边有关的某些数量指标（即“权”），其可以代表诸如距离、 费用、通过能力（容量）等等。 网络点或边带有某种数量指标的图,2,2,3,4,2,2,3,4,6,1,3,7,6,1,3,7,10,5,5,OR:SM,OR:SM,第一节,图论的概念,图与网络的基本概念 连通图 在众多各类图中有一类在实际应用中占有重要地位的图 连通图在图中，任意两点间至少存在着一条链。,11,连通图,不连通图,OR:SM,OR:SM,第二节 最小树问题 树及其性质 无圈且连

6、通的无向图称为树。例如，企业的组织结构，文 件的目录管理等都可以用一个树状图来表示。 性质： 树中任两点之间必有且只有一条链； 树中去掉任一条边，则成为不连通图； 树中不相邻两顶点之间添一条边，则得到一个圈； 顶点个数nv与边的个数ne的关系：ne = nv 1。,12,OR:SM, v , v T,i,j,OR:SM,第二节,最小树问题,支撑树：如果图G（V，E）的支撑子图T=（V，E/）是树，则 称T为G的支撑树。 权数总和为最小的那棵支撑树，称为最小树。w (T ) w ij 求解方法： 破圈法；避圈法 例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走 线方式如下图所示，如何铺

7、设网线才能使网线总长为最短？,8,v2,4,v5,6,v1,3,5,6,v6,2,6,v3,8,v4,最短网线总长度为最小树权之和2+3+4+6+6=21,13,OR:SM,OR:SM,14,第二节,最小树问题,方法一：破圈法 ：任取一个圈，从圈中去掉一条权最大的边。 在余下的图中，重复这个步骤，一直到一个不含圈的图为止， 这时的图便是最小树。,6,v3,5,v5,4,v1,1,7,3,v6,5,4,v2,2,v4,这就得到了该图的一个最小支撑树。,14,2011-03-25,OR:SM,OR:SM,15,第二节,最小树问题,方法二 ：避圈法：开始选一条权最小的边（也可从一点开 始），以后每一

8、步中，总从未被选取的边中选一条权最小 的边，并使之与已选取的边不构成圈。,6,v3,5,v5,4,v1,1,7,3,v6,5,4,v2,2,v4,这就得到了该图的一个最小支撑树。,15,2011-03-25,OR:SM,OR:SM,第三节 一、最短路问题,最短路问题 Shortest Route (Path) Problems, 路权：弧(vi, vj)的权为wij；路权是路p中各条弧权之和 最短路：在所有从vs到vt 的路p中，求一条路权最短的路,狄克斯特拉(Dijkstra)算法 算法说明：,w(P*) minw(P) P, 1959年提出，目前公认的最短路算法 适合于求解所有弧权wij

9、0的最短路问题 算法假设：有向图D是完备图 图D中任意两点vi , vj 之间，恰有两条弧(vi , vj)和(vj , vi) 若vivj 不存在弧, 可设想一条从vi vj 的弧, 权wij=+； 若vi vj 有重复的弧，则保留弧权最小的弧,16,OR:SM,OR:SM,17,OR:SM,OR:SM,第三节 一、双标号算法,最短路问题,18, ,基本思路: 从始点vs 出发，逐步探寻，给每个点标号； 标号分永久标号P(vk)和临时标号T(vk) 两种： 永久标号P(vk) 是从点 vs vk 的最短路权 临时标号T(vk) 是从点 vs vk 最短路权的上界 算法的每一步从临时标号集中选

10、最小者变为永久标号； 经过逐次改变，就可以得到从点vs 到各点的最短路。 标号形式： 单标号法是对每一点赋予一个路权标号 双标号法是对每一点赋予两个标号：路标、路权,OR:SM,OR:SM,第三节,最短路问题,一、双标号算法 例：用双标号法求下图网络最短路,v1,2,v5,3,7,4,1,8,vs,10,9,v2 4,1 3,v4,6,7,1,vt,19,v3,2,v6,OR:SM,2,OR:SM,vs,第三节 一、双标号算法,最短路问题,第一步： 3,(vs ,3) v1 7,2 4,v5,1,(vs , ),8,(vs , 0),vs,9,v2,(vs ,9) 1,v4,(vs , ) 7

11、,vt,(vs , ),10,4,3,6,1,20,v3 (vs ,10),v6 (vs , ),OR:SM,2,OR:SM,第三节 一、双标号算法,最短路问题,第二步：,(vs ,3),(v1 ,5),v1,2,v5,3,7,4,1,8,(vs , 0),vs,9,v2,(vs ,9) 1,v4,(v1 , 7),7,vt,(vs , ),10,4,3,6,1,21,v3 (vs ,10),v6 (vs , ),OR:SM,2,OR:SM,第三节 一、双标号算法,最短路问题,第三步：,(vs ,3),(v1 ,5),v1,2,v5,3,7,4,1,8,(vs , 0),vs,9,v2,(vs

12、 ,9) 1,v4,(v5 , 6),7,vt,(v5 ,13),10,4,3,6,1,22,v3 (vs ,10),v6 (vs , ),OR:SM,2,OR:SM,第三节,最短路问题,一、双标号算法 最终：依此类推，重复上述标号过程。得最短路。,(vs ,3),(v1 ,5),v1,2,v5,3,7,4,1,8,(vs , 0),vs,9,v2,(vs ,9),1,v4,(v5 , 6),7,vt,(v6 ,12),10,4,3,6,1,23,v3 (v4 ,9),v6 (v3 ,11),OR:SM,OR:SM,即时练习： 某一个配送中心要给一个快餐店送快餐原料，应按 照什么路线送货才能使

13、送货时间最短。,(4,1),(18,3),(25,4),2,16,4,7,6,4,6,1,12,2,8,7,(27,5),18,3 (16,2),6,5,5,(22,3),24,OR:SM,OR:SM,第三节,最短路问题,二、最短路的应用 1、网络的中心 所谓网络的中心是指一个网络中，选择某一点，使之其 余各点到该中心点的距离之和为最小。 例：如果要在下表中6个销售点中选一个作为仓库所在地，应 该建在哪个经销点，使其余各销售点都离它较近？,25,OR:SM,OR:SM,第三节,最短路问题,二、最短路的应用 2、网络的重心 引进点的权系数，将权系数与最短距离阵各列对应元素加权 求和，再从中选择最

14、小的即为网络重心。,26,OR:SM,OR:SM,27,第三节,最短路问题,3、设备更新问题:制订一设备更新问题，使得总费用最小？,第1年,第2年,第3年,第4年,第5年,购买费 使用年数 维修费,13 0-1 8,14 1-2 10,16 2-3 13,19 3-4 18,24 4-5 27,解设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种 状态，以v6表示“第5年末”这种状态；以弧(vi, vj)表示“第i年 初购置的一台设备一直使用到第j年初”这一方案，以wij表示这 一方案所需购置费和维护费之和。于是，该问题就可归结为从 图中找出一条从v1到v6的最短路问题。其网

15、络模型如下：,27,2011-03-25,OR:SM,OR:SM,28,设备更新的网络模型,(21),v2,32,(44) v4,63,21,44,22,45,27,37,(0)v1,31,89 62,24,(78) v6,用Dijkstra标 号法，求得最 短路为: v1 v3v6,v3,(31),47,34,v5 (62),32,28,2011-03-25,OR:SM,OR:SM,*设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买 新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置 费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置 费，但维修费用就

16、高了。请设计一个五年之内的更新设备的计划，使得五 年内购置费用和维修费用总的支付费用最小。 表1：设备每年年初的价格表,年份 年初价格,1 11,2 11,3 12,4 12,5 13,表2：设备维修费如下表,使用年数 每年维修,0-1 5,1-2 6,2-3 8,3-4 11,4-5 18,费用,29,OR:SM,OR:SM,解： 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的 设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,把所有弧的权数计算如下表：,1 2 3,1,2 16,3 22 16,4 30 22 1

17、7,5 41 30 23,6 59 41 31,30,4 5 6,17,23 18,OR:SM,22,23,18,OR:SM,(继上页) 把权数赋到图中，再用Dijkstra算法求最短路。 59,22,30,41,23,v1,16,v2,16 v3 17,v4,17 v5,18,v6,22,30,23,31,41 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6 59,V1 （0,s）,16,（16,1） (22,1),41 30 (30,1) V2 16 v3 17 v4 30,17 31,23 (41,1) v5,v6 (53,3) (53

18、,4),41,31,OR:SM,OR:SM,第四节 网络最大流Maximal,flows in Networks,许多系统包含了流量问题，例如铁、公路系统中的车辆流、 工业流程中的物流、通风网络中的风流、供水系统中的水流、控 制系统中的信息流和金融系统中的资金流等。对这些系统求最大 流量的问题就转化为图论中求网络中一个相容的最大流问题，运 输上称之为网络的最大通过能力。,32,OR:SM,OR:SM,引例：一个公路交通运输网络如图7-10所示，它联接了产地vs和 销售地点vt。其中每一条弧（vi，vj）表示vi到vj的运输线，弧旁 的数字表示该支线的最大通过能力。要求制定一个运输方案， 使vs

19、到vt的运输量达到最大。 这就是一个求网络最大流的问题。可给出一个运输方案， 用圆圈中的数字表示。它表明有8个单位的运量从vs运往vt。问 题在于运量是否还能增加，或者说如何求最大运量？这是本节 要解决的一类主要问题。,9,v1,5,5,v3,8,vs,4,4 ,vt,2,33,7 v2 6 图7-10 公路交通运输网络图,v4,6,OR:SM,OR:SM,第四节,网络最大流,一、相关概念与定理 1、弧容量与容量网络 对于有向图 D=(V,A),，弧 (vi , v j )的容量表示弧的最大流通能力。 在V中指定一点称为发点(记为vs )，另一点称收点(记为vt)，其余点 叫中间点，这样的赋权

20、有向图就称为一个容量网络，记N=(V,A,B) 2、弧的流量与可行流 弧的实际通过量称为该弧的流量。弧集A上的流量集合 f xij 称 为网络上的流。 满足下述条件的流称为可行流。,34,容量限制：对每条弧 (vi , v j ) A 平衡条件：中间点流出量=流入量,，都有,0 xij bij,OR:SM,(,OR:SM,第四节,网络最大流,一、相关概念与定理 3、前向弧与后向弧 是从vs 到vt 的链，方向从vs vt ，则链上的弧分为两类 前向弧：弧的方向与链的方向相同，记+ 后向弧：弧的方向与链的方向相反，记- 4、饱和弧与非饱和弧 弧 vi , v j ) 的流量 xij 与之容量 b

21、ij 比较： 满足 xij bij 的弧称为饱和弧，弧的流量不能再扩充； 满足 xij bij 的弧称为非饱和弧，弧的流量允许再被扩大。 5、零弧与非零弧 满足 xij 0 的弧称为零弧。由于 xij 0 ， 所以弧的流量不能减小； 满足 xij 0 的弧称为非零弧。弧的流量可以被减小， 但要满足 xij 0。,35,OR:SM,OR:SM,第四节,网络最大流,一、相关概念与定理 6、流量可以扩充的路 设 f xij 是一可行流，是从vs 到vt 的链，若链满足： 上的所有前向弧为非饱和弧，即满足 xij bij ，可以扩充流量 上的所有后向弧为非零弧，即满足 xij 0 ，可以减少流量； 则

22、称是一条关于可行流 f 的可扩充流量的路，亦称增广链。 7、流量可以扩充的路 可行流中，网络发点的流出量（或网络收点的流入量）就 是网络的流量。 一个容量网络的诸可行流中，网络流量最大的可行流，称 为最大流,36,OR:SM,OR:SM,图与网络分析,Graph Theory and Network Analysis,网络流（Flow）与最大流问题 理论 1、流量截量定理 容量网络上任何一个可行流的流量不超过任何一个截集的截量。 2、增广链调整定理 在增广链上对可行流进行调整可以得到一个流量更大的可行流。 3、最大流定理 可行流是最大流的充分必要条件是不存在关于该可行流的增广链。,37,OR:

23、SM,OR:SM,第四节,网络最大流,二、求最大流标号法 1956年，福特和富尔克逊提出了寻求网络最大流的基本方法，称为福 特-富尔克逊算法（Fold-Fulkerson Algorithm）。 标号过程 给定可行流X=xij ，标号判断有无增广链 先给vs 标上(vs, +)，vs已标号尚未检查，其余未标号 取一个已标号但未检查的点vi进行检查，对未标号点vj ： 前向弧(vi, vj)可以扩充流量(xijrij) vj尚未标号，则给vj 标号(vi，+)，vj 成为己标号尚未检查的点 后向弧(vk, vi)可以减少流量(xki0) vk尚未标号，则给vk 标号(vi, -)，vk成为己标号

24、尚未检查的点 vi 成为已标号已检查的点，在其标号下划横线 检查收点vt 是否已标号： vt被标上号则找到增广链，进行流量调整；否则转第步 若所有标号都已检查，vt又未标号，则不存在增广链,38,OR:SM,rij xij, ij,OR:SM,第四节,网络最大流,二、求最大流标号法 流量调整过程 反向追踪找出vs 到vt 的增广链 计算增广链上可调整的流量, min xij,(vi , v j ) (vi , v j ) , 调整可行流的流量，得新的可行流xij , x ij x ij x ij x ,( v i , v j ) ( v i , v j ) ( v i , v j ) , 抹去

25、所有标号，对新的可行流X =xij，重新进入标号过程,39,OR:SM,OR:SM,第四节,网络最大流,二、求最大流标号法 例：下图表示了企业所处的供应市场（v1和v2）、配送中心（v3 和v4、以及销售市场（v5、v6和 v7）组成的网络，各弧上括号里的 前一个数字表示弧的容量，后一个数字是目前的实际流量。 试求这个供应-销售网络的最大流方案。,v1,(10,6),v3,(4,4),v5,(5,5),(4,3),(6,3),v6,v2,(15,9),v4,(6,6),v7,40,OR:SM,OR:SM,第四节,网络最大流,二、求最大流标号法 供应-销售网络的可行流,v1,(10,6),v3,

26、(4,4),v5,(5,4),(15,6),(5,5),vs,(4,3),(6,3),v6,(10,8),vt,(12,12),v2,(15,9),v4,(6,6),v7,(8,6),41,OR:SM,vt,OR:SM,第四节,网络最大流,二、求最大流标号法 供应-销售网络的可扩充路,(+vs ,9) v1,(10,6),(+ v1 ,4) v3,(4,4),v5,(5,4),(15,6),(5,5),(+ v6 ,2),(+ vs ,) vs,(4,3),(6,3),(10,8) v6 (+ v4 ,3),(12,12),v2 (- v3 ,3),(15,9),v4 (+ v2 ,3) (6

27、,6),v7,(8,6),42,OR:SM,OR:SM,第四节,网络最大流,二、求最大流标号法 调整后的可行流,v1,(10,8),v3,(4,4),v5,(5,4),(15,8),(5,5),vs,(4,1),(6,5),v6,(10,10),vt,(12,12),v2,(15,11),v4,(6,6),v7,(8,6),最大流量为 f xs1 xs 2 x5t x6t x7 t 20,43,OR:SM,OR:SM,第四节,网络最大流,三、网络的瓶颈识别 1、截集-截量与最小截集 截集： 对于网络N=(V,A,R)，将V分为两个非空集合S和S，使 发点vsS，收点vtS 所有起点属于S而终点

28、属于S的弧的集合称为截集 (S,S) 截量：截集(S,S) 中所有弧的容量之和 r(S,S) 最小截集：截量最小的截集 2、最大流-最小截量定理 网络中，任一可行流的流量恒不超过任一截集的截量，称为 流量-截量定理。 最小截量的大小影响总流量的提高,44,OR:SM,2,7,1,5,OR:SM,(4,1),第四节 K,网络最大流 (2,1),V2,3(2),V5,5(5),3(3),4(4),8(6),(0,+)V1,3(3),V4,(6,1),2(2),2(0),V7,(5,1),6(4),V3 (1,2),2(0) K,5(4),V6 (3,1),6(6),45,最大流=13,截集：v1,

29、v2;v1,v4;v3,v6,OR:SM,(3,1),(0,+),(5,1),7,OR:SM,(4,1),第四节 （1，2）,网络最大流 (2,1),12(10),V2,4(3),5(4),3(3),V5,9(9),K,(0,+) V1,6(5),3(3) 5(4),V4 (2,1),4(4),2(2) V6 (7,1) 2(2) 9(6),V8 (7,1),5(4),46,V3 (1,1) 最大流=9+7=16,V7 (3,1) K 截集：v5,v8;v6,v7;v3,v7,OR:SM,20,30,S ,20,10,47 CBE=5,例 ：某公司下属三家工厂A、B、C生产能力分别为30、20

30、、10个单位/天，每天产品要通过下图所 示运输网络运到F、G、H三个仓库。工厂车队作出调度，安排了每条运输道路的一天运输量。 问：这样的安排能否完成全部产品的进库任务？为了完成进库任务，应如何调整各运输道路上 的运输量？(为了使用最大流标号法，对下图在工厂左侧虚设发货点，发货量分别为30、 20、10 ， 经A、B、C三个工厂，作为它们的生产量，并沿St的路径给出一可行流。),A ,15 ,15,5 ,5,F,10,20 ,5 15 5 10 ,5 20 ,20 B 10 ,10 10 10 ,10 ,20 Smin=(S,C),(B,C),(B,D), 20 (E,D),(E,G),(E,F

31、) C 容量为C(v*,v*)=10+10+,E 10 ,10 D,5 ,5 ,20 20 30 ,20,G,10 ,5 ,20 20,0 H, T ,20,10+10+5+5=50 最大流量(F*)= C(v*,v*)=5060。 故当前安排不足以完成产品进库任务，还差10个单位的运输量。 第一步：给出一个初始可行流。题目巳给出。 第二步：给顶点标号找增广链。无增广链，当前可行流为最大流。 第三步：确实最小割和最大流量。 第四步：抽调弧(A,B)和(B,E)上各个单位运输能力去加强关键弧(B,D)，使BD=20,CAB=15, OR:SM OR:SM,G,OR:SM,S ,+10 ,20 3

32、0 20 ,20 10 ,10, B,A 15 ,15 15 ,5 +10 5 ,5 20 ,10 +10 10 ,10 ,20 20 C,E D,5 ,5 5 ,5 10 ,10 ,20 20 30 ,20 +10,F ,10 10 ,5 ,20 20,0 H, T ,20 +10,第五步：在新可行流中,继续给顶点标号找增广链。 找到增广链L=S，A，B，D，H，T，故当前可行流为非最大流。 第六步：沿增广链L方向调整10个单位的流量，得一新可行流。,48,OR:SM,OR:SM,A ,15 ,15,5 ,5,F,10,S ,30 30 20 ,20 10 ,10, B,15 ,15 5 ,

33、5 20 ,20 10 ,10 ,20 20 C,E 10 ,10 D,5 ,5 ,20 20 30 ,30,G,10 ,5 ,20 20,0 H, T ,30,Smin=(S,A),(S,B),(S,C) 容量为 C(v*,v*)=30+20+10=60 最大流量(F*)= C(v*,v*)=60。 故当前安排足以完成产品进库任务。,49,OR:SM,2,OR:SM,问题提出- 最小费用最大流问题 不仅考虑流量，而且还要考虑输送的费用 最大流量的流量分布图往往不只一个，谁最优？,容量cij，费用bij,研究的目标：是要找到 一个最大流F*=fij使总,10,4 1 8,1,5,2,7,1 2

34、,6,5,的输送费用最小，即： Min b(F*) =bij fij*,50,3,10,3,4,4,2,OR:SM,OR:SM,基本原理 找费用最小的可行流，找出该可行流的增广链，沿链调 整流量；直到找不到费用最小的增广链为止。 费用最小的增广链含义 是费用最小的链 可以增大流量的链,51,OR:SM,2,OR:SM,标量型的费用用方向图的表示方法,2 容量cij 费用bij 流量fij,赋权系数wij -1,10,4,0 1,7,1,5,1,4,1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2 仅有正向弧,52,wij=bi

35、j | fij0 反向弧,仅有反向弧 既有正向弧，又有反向弧,OR:SM,OR:SM,最小费用最大流算法步骤 生成法： 取 fij (0) 0 作为初始最小费用可行流(总费 用为0) 对 fij (0) =构造一个赋权有向图W(f(0),在图上 找到从发点到收点的最短路(最小费用的有向图) ，若存在最短路，则寻找增广链L，在增广链上 对 fij (0) 进行调整。 对 fij (1) 重复上步骤，直到在赋权有向图中不存 在最短路。则获得最小费用最大流。,53,OR:SM,2,OR:SM,最小费用最大流-例,容量,费用,流量,第1步：令所有流量为0, fij (0) =0,10,4,0 1,7,

36、1,0,8,1,0,5,2,0,2,6,0,5,54,3,10,3,0,4,4,2,0,OR:SM,OR:SM,第2步：构造赋权有向图,Q=0,找最短路径,10,4,0 1,2,容量,费用,流量 7,1,0,1,4,2,费用 1,5,2,0,2,6,0,5,2,6,5,8,1,0,3,10,3,0,4,4,2,0,1,3,3,4,2,55,流量图,费用赋权图,OR:SM,OR:SM,第3步：求调整量，,Q=0 2,可均增加5，其他不变 2,10,4,0 1,5,2,5,7,1,5 7,1,0,1,4,1,5,2,0,2,6,0,5,2,6,5,8,1,0 8,1,5 3,10,3,0,4,4,

37、2,0,1,3,3,4,2,56,流量图,费用赋权图,OR:SM,OR:SM,第4步：重新构造赋权有,Q=5 2,2,向图,-1,10,4,0 1,7,1,5,1,4,1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2,57,流量图,费用赋权图,OR:SM,OR:SM,第5步：找最短路径,Q=5 2,第6步：沿最短路径调整 流量,可增加2 2,10,4,2 10,4,0,7,1,7 7,1,5,4,1,-1,1,1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2,

38、58,流量图,费用赋权图,OR:SM,OR:SM,Q=7,第7步：重新构造赋权有 向图，找最短路径,2,-4,2,10,4,2 1,7,1,7,1,4,-1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2,59,流量图,费用赋权图,OR:SM,OR:SM,第8步：沿最短路径调整,Q=7,流量,可增加3,2,-4,2,10,4,2 1,7,1,7,1,4,-1,5,2,5,2,6,0,5,-2,6,5,8,1,5 8,1,8,3,10,3,0 10,3,3,4,4,2,0 4,2,3,-1,1,3,3,4,2,60,流量图,费用赋

39、权图,OR:SM,OR:SM,Q=10,第9步：重新构造赋权有 向图，找最短路径,2,-4,2,10,4,2 1,7,1,7,1,4,-1,5,2,5,2,6,0,5,-2,6,5,8,1,8,3,10,3,3,4,4,2,3,-1,3,3,4,2 -2,-3,61,流量图,费用赋权图,OR:SM,4,OR:SM,Q=10,第10步：沿最短路径调 整流量,可增加1,10,4,2 10,4,3,2,7,1,7,-4,4,2,-1,1,1,8,1,8,3,5,2,5 5,2,4 10,3,3 10,3,4,2,6,0 4,2,3 4,2,4,5,-1,3,-2,3 -3,6 4,2 -2,5,62,流量图,费用赋权图,OR:SM,OR:SM,Q*=11,第11步：重新构造赋权 有向图，找最短路径,10,4,3,2,7,1,7,-4,4,2,-1,1,1,-2,5,2,4,2,6,0,5,2,6,5,8,1,8,3,10,3,4,4,4,2,4,-1,3,3,4,-2,-3,63,流量图,费用赋