海事运筹学课件 7.网络规划.ppt

第七章 网络规划,第七章 网络规划,第一节：现实中的网络规划问题 第二节：图的基本概念 第三节：树 第四节：最大流问题 第五节：最短路径问题 第六节：最小费用最大流问题 第七节：网络规划的应用,7.1现实中的网络规划问题,许多工程和管理的问题都可以用图与网络来描述，图与网络优化问题是一类应用十分广泛的问题。图与网络优化是线性规划等理论和算法在具有图结构的问题中的应用。由于图与网络问题具有特殊的结构，相应的优化算法也不同于一般的单纯形算法，具有其独特的直观和简捷的特点。,哥尼斯堡七桥问题,尼斯堡城有条河流，河中有两个小岛，河上共有七个桥，如图71。当地居民考虑这样一个问题：能否从某个地点（任意点）出发经过七个桥，且每个桥只经过一次，最后回到出发地点。,图7-1.哥尼斯堡七桥问题,哥尼斯堡七桥问题,欧拉在1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为图72所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。,图7-2.一笔画问题,欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。,7.2 图的基本概念,7.2.1图: 由节点（Node）和边（Edge）组成。节点和边是图中最基本的概念，我们不对其作出定义。图7-3的图中，有4个节点，7条边，每一条边都与2个节点对应。因此，一条边可以用它的两个节点来标记。图7.3中的边，可以记为v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1。,图7-3. 无向图,图的定义,定义 设V=v1，v2，vm表示节点的集合，E=e1，e2，en表示边的集合，若对任一ekE，均有vi，vjV与之对应，则称VE为图，记为G=(V，E)。 称vi为G的顶点，ek为G的边，记为ek=vi，vj= vj，vi。称vi，vj为ek的端点，ek为vi，vj的关联边。称vi，vj为邻接点。 将图7.3用数学定义表示如下： G=(V，E) V=v1，v2，v3，v4 E=e1，e2，e3，e4，e5，e6， e1，e2，e3，e4，e5，e6，e7=v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1 ,相关定义,如果图中一个边的两个端点为同一个点，称这样的边为环。如果两个点之间存在两个以上的边，称为多重边。一个没有环、也没有多重边的图，称为简单图。无环,允许有多重边的图称为多重图。本章讨论的图主要是指简单图。 图中的边是对节点的关系描述，所以我们讨论的图如果关系表示的相同，不论图的形状如何，我们认为这样的图都是相同的。 次: 以点v为端点的边的个数称为v的次， 表示为: d(v)。 悬挂点: 次为1的点。 悬挂边: 悬挂点的关联边。 孤立点: 次为0的点。 奇点: 次为奇数的点。 偶点: 次为偶数的点。,两个定理,定理7-1: 图G=(V,E)中,所有点的次之和是边数的两倍, 即: 证明:计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。 定理7-2: 任意一图中, 奇点的个数为偶数。 证明:设 V1表示奇点的集合， V2表示偶点的集合。由有： 因为偶点的次之和为偶数，总数为偶数，所以奇点的次之和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇点的个数必然为偶数个。,相关定义,链：点边交错系列， 记为： 如果满足 ，一般简记为： 圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。 连通图：任意两点之间至少有一条链。否则称为不连通图。 连通分图：对不连通图，每一连通的部分称为一个连通分图。 支撑子图： 对G=（V，E），若G=(V,E), 使V=V, E E, 则G是G的一个支撑子图（生成子图）,7.2.2有向图,前面讨论的图中，边是没有方向的，ek=vi，vj= vj，vi。这样的图称为无向图。但许多实际问题用无向图表示是不够的。例如，涉及交通网络中单行道、一项工程的各工序的前后次序关系等。,定义 设V=v1，v2，vm表示节点的集合，A=a1，a2，an表示边的集合，若对任一akA，均有vi，vjV与之对应，则称VA为图，记为D=(V，A)。 称ak为D的弧，记为ak=（vi，vj）（vj，vi）。,相关定义,始点和终点: 对弧a=(u,v), u为a的始点, v为a的终点。 基础图: 对D=(V, A), 去掉图上的箭头的无向图。 链: 点弧交错序列, 若在其基础图中对应一条链, 则称为 D的一条链。 路：若 是D中的一条链，且 ，t=1,2,k-1,称之为从 到 的一条路。 回路: 的路。 初等路: 路中点不相同。 初等回路: 回路中点不相同。,7.2.3 赋权图,如果给定一个图G=(V，E)或D=(V，A)的任一边（弧）有一个实数 与之相对应，由称这样的图为赋权无向（有向）图。如图7-5。 赋权图的应用是很广泛的。例如，在一个交通网络中，边的权数可以是两个点之间的距离，也可以表示两点之间的运输费用、运输时间、运输能力等。在一个设备维修的图中，权数可以表示维修费用，在工程项目计划网络图中可以表示各工序的完成时间等。,在赋权图中的链（路）上所有边（弧）对应的权之和，称为链（路）的权。 一个连通图连同定义在其边集上的实函数一起，称为一个网络,7.2.4图的矩阵表示,图形虽然有直观等优点，但随着实际问题的大型化，大多数算法需要在计算机上运算和求解，计算机处理直观图形是比较困难的。以下介绍将图用矩阵表示，将图的几何形状转化为代数矩阵，可以方便计算机对图形的处理与运算。以下举例说明。 例7-1将图7-6用矩阵表示。,不考虑权时的矩阵表示如下 ：,两个端点之间有边记为1，无边相连则记为0，对角线上记为0。这样得到一个对称的矩阵。,考虑权数时的矩阵表示为：,两个端点之间有边相连的，记上其权数，无边相连的记为，对称线上仍记为0。赋权无向图的矩阵也是对称矩阵。,第8章 网络分析,17,基本概念,一、树 树 一个连通无圈简单图，记为T ； 林 一个无圈简单图。 如：由六个结点构成的树，有以下不同形式：,7.3 树,第8章 网络分析,18,最小树问题,图的支撑树 若图G的一个支撑图T是树，则称T为G的一棵支撑树。,第8章 网络分析,19,最小树问题,最小支撑树 树的权数: 树的各边权数的总和； W(T) 图的最小支撑树: 网络所有支撑树中的权数最小者,记为 T*，简称网络最小树。,W(T*)= 6,图的支撑树,图的支撑树（Spanning Tree）:设图G有p个节点，q条边。由G中p个节点，p-1条边组成的树称为图G的支撑树，也称为图G的生成树。,图7-8(a). 图7-6的一个支撑树（1）,图7.8(b). 图7-6的一个支撑树（2）,图7-8就是一个树。树中只与一条边关联的节点称为悬挂点。与悬挂节点关联的边称为悬挂边。图7-8中节点3和节点5都是悬挂点，1，3和4，5都是悬挂边。 树有以下性质： （1）任何树至少有两个悬挂点。图7-8中节点3，节点5。 （2）如果树的节点数是p，则边的个数为p-1。图7-8的图有5个节点，有4条边。 （3）树中任意两个节点之间只有唯一的一条链。 （4）在树中任意两个不相邻的节点之间增加一条边，则会形成圈。,以下介绍三种求最小支撑树的方法,解法一：破圈法 解法二：避圈法 解法三：顶点扩充法,解法一：破圈法,例7-2设某个小区由六个楼组成，如图7-9，图上的数字为各相邻楼的距离（百米）。现要铺设光纤，试求光纤总长度最短的铺设方案。,图7-9. 例7-2的网络图,用破圈法求解过程如下：,用破圈法求解过程如下：一般先找权数最大的边所在的圈,（1）找圈v1，v2 ，v4，v3或v1，v3 ，v4，v2去掉边v3，v1，如图7-10,图7-10. 破圈法求解示意图（1）,（2）去掉边v4，v5 （3）去掉边v3，v6 （4）去掉边v3，v1,（5）去掉边v2，v5。得图7-12。此时图中已不含圈，剩下的边构成了原网络的最小支撑树，也就是铺设光纤的最优方案。 最小树的权为： W(T*)=1+2+2+2+1=8,图7-11. 破圈法求解示意图（2）,第8章 网络分析,24,破圈法,破 圈 法,7,3,2,4,7,6,4,1,2,1,3,4,5,6,7,4,3,5,2,2,w (T) = 13,任选一个圈，去掉圈中权数最大的边， 直到图中不含圈为止。,解法二: 避圈法,避圈法与破圈法的思想相反，先将所有边的权按从小到大的次序排列，然后依次检查，如果某个边加到图上不会产生圈，就将其加上，否则就不加到图上。直到所有边都检查完为止。 在图7-9中加边的顺序为v1，v2、v4，v6、v2，v4、v3，v4、v5，v6，由于本图为6个点，加上5个边即完成。得到如图7-11的结果，与破圈法得到的结果相同。 一般来说，一个图可以有多个不同的最小支撑树，但它们的总权一定相同。,解法三：顶点扩充法,顶点扩充法是先在图中任选一个点，记为S=a1，以该点为出发点，将与其相连的最小权的边加入图中，将相关连的点加入到S中，得到S=a1，a2；再寻找与S中的点相连的边中权数最小的边加入图中，将相关连的点加入到S中，反复进行以上步骤，直到所有的点都加入到S中为止。即可得到最小支撑树。,在例7-3中，以v4做为出发点，S=v4，与v4相连的边有5条，权数最小的为v4，v6，将v6加入S中，S=v4，v6； 与S=v4，v6相连的边有7条，其中权数最小的有3条，权数都是2，此时可任选一条。如将v5加入，得S=v4，v6，v5； 与S=v4，v6，v5相连的边有5条，其中权数最小的有2条，权数都是2，此时可任选一条。如将v2加入，得S=v4，v6，v5，v2； 与S=v4，v6，v5，v2相连的边有4条，其中权数最小的有1条，权数是1，将v1加入，得S=v4，v6，v5，v2，v1； 与S=v4，v6，v5，v2，v1相连的边有3条，其中权数最小的有1条，权数是2，将v3加入，得S=v4，v6，v5，v2，v1，v3。此时所有点都加入到S中，可以得到如图7-12的结果。,第8章 网络分析,27,最小树问题,重复 ,得 w (T) = 13,1,2,3,S,4,2,5,2,6,1,7,2,3,3,顶点扩充 法,最短为( 1，2 ),T,第8章 网络分析,28,7.4 最大流问题,7.4. 1 基本概念,一、网络流：是指在一定的条件下通过一个网络的某种流在各边上 的流量的集合。 一定条件指的是： （1）网络有一个始点 s 和终点 t 。 （2）流过网络的流量具有一定的方向，一般用有向网络 N = (V，A) 加以描述，各弧的方向就是流量通过的方向。 （3）对每一弧 ( i,j ) A，都赋予一个容量 c (i,j) = cij，表示容许 通过该弧的最大流量。 在一个网络 N = (V, A) 中，设以xij= x(i,j)表示通过弧(i,j)A 的 流量，则集合 X = xij(i ,j)A 称为该网络的一个流。其流量记为 f = f (X) 。,第8章 网络分析,29,7.4 最大流问题,二、可行流 满足下面条件的流称为一个可行流： (1) 弧流量限制条件 0 xijrij (i,j)A (2) 中间点平衡条件 xij - xji = 0， i s, t 这意味着每个中间点的净贮流量为0，即每个中间点的流 入量必须等于其流出量，二者必须平衡。,i,j,j,xji,xij, xji, xij,第8章 网络分析,30,7.4 最大流问题,可行流恒存在，如X0 = xij= 0(i,j)A 就是一个可行流，称为 零流，其流量 f(X0)= 0。 又如图所示 也是一个 可行流。,三、最大流 流量最大的可行流 称为最大流，记为 X* = xij*，其流量 记为 f * = f(X*).,最大流问题的 LP 模型,网络最大流问题可以用线性规划方法求解。例如图7-12的最大流问题，设xij为各弧的流量，f表示可行流的流量。则此最大流问题的线性规划形式为：,第8章 网络分析,32,7.4 最大流问题,六、截集,七、截量,在网络中，将点集分成两个不相交的非空集合S和,S,截集截量的例子,图7-13,图7-14,图7-15,图7-16,相关定理,定理7-3： 网络任一可行流的流量f必定小于或等于网络中任一截集的容量。即： 定理7-4： 网络中从vs 到vt 的最大流的流量等于分离vs 和vt的最小截集的截量。,第8章 网络分析,35,设 X = xij是一可行流， 是从 s 到 t 的一条链。若 上各弧的流量 满足下述条件：,设是网络N中的一条从s到t的链,则链上与链的方向一致的弧称 为前向弧，其集合记为；链上与链的方向相反的弧称为后向弧，其集合 记为- 。, = (s,2),(1,4),(3,t) - = (1,2),(3,4),xij 0 当(i, j)-,则称 为一条关于可行流X的增广链，记为(X)。,四、链的前向弧与后向弧,五、增广链,非零流弧,非饱和弧,第8章 网络分析,36,7.4 最大流问题,定理4：最大流的充要条件 设 X* = x*ij 是网络 N =(V,A) 的一个可行流，则 X* 为最大流的 充要条件是：网络 N 中不存在增广链 (X*)。 定理5：最大流量 最小截量定理 网络中从s到t的最大流的流量等于分离s和t的最小截集的截量。,再令, = min1 ,2,第8章 网络分析,37,7.4 最大流问题,7.4. 3 求网络最大流的标号法 （福特-富尔克逊标号法） 一、基本思想 从某一可行流 X（如零流）出发，按一定规则找出 一条增广链，并按定理3的方法（增广链调整法）调整 X, 得到一个流量增大 的新可行流 X 。重复上述做法直到 找不出增广链为止,这时就得到一个最大流，同时还得到 一个最小截集。 二、基本步骤 1 给始点 s 标号(0， ) ，则 s 已标号待检查；,前源点,当前最大可调整量,第8章 网络分析,38,8.4 最大流问题,2 取一个已标号待检查的点 i，对所有与 i 相邻而未标号 的点 j 依次判断、执行如下手续： (1) 若关联 j 与 i 的弧为(i, j)，则当该弧上的流量 xij 0 时, 给 j 标号( -i，b(j)，其中 b(j) = min b(i)，xji 而当 xji = 0 时, 不给 j 标号； 当所有与 i 相邻而未标号的点 j 都执行完上述手续后，就给 点 i 打，表示对它已检查完毕。,前向弧,后向弧,第8章 网络分析,39,8.4 最大流问题,3重复 2,可能出现两种结果： (1) 终点 t 得到标号。则从t回溯标号点的第一个 标号，就能找出一条由标号点和相应的弧连接而成的 从 s 到 t 的增广链 (X)，转 4； (2) 所有标号点均已打（检查过），而t又未得 标号。这说明不存在增广链，而当前的可行流即最大 流，算出其流量，停止。 4取调整量 = b(t) (即终点 t 的第二个标号),令 xij : = xij + ， 对一切 (i, j) xij : = xij - ， 对一切 (i, j) - 非增广链上的各弧流量 xij 不变。,第8章 网络分析,40,8.4 最大流问题,5删除网络中原有一切标号，返回 1；,例11,(0, ),(s，2),(s，2),(1，2),(-4，1),(3，1),调整量 =1,(0, ),(s，1),(s，2),(1，1),f(X*) = 4 + 7 = 11,2,0,4,8,三、举例,例子,图7-90. 可行流（1）,例子,第8章 网络分析,43,8.4 最大流问题,例12 求网络的最大流 与最小截集,1,2,s,t,2,s,t,3,2,s,t,3,t,3,1,s,1,s,t,3,s,t,3,2,12,8,7,1,2,1,2,2,4,2,13,4,3,2,9,5,3,11,8,10,12,2,1,8,2,3,2,4,2,3,5,2,4,6,11,12,第8章 网络分析,44,8.4 最大流问题,f ( X* ) = 20,例13 分配问题,A B C D, ,甲 乙 丙,需求量, , ,10 20 15 10,加工件数,18 19 18,55,第8章 网络分析,45,8.4 最大流问题,A B C D 甲： 18 乙： 19 丙： 18 10 20 15 10,甲,乙,丙,A,B,C,D,S,t,18，,18，,18，,19，,18，,19，,18，,19，,18，,19，,15，,10，,10，,20，,10,10,0,20,19,19,1,15,8,7,0,18,8,0, = 10,1,1,1,1,10,8,0,9,10,11,7,第8章 网络分析,46,8.3 最短路问题,概 念：在一网络中，给定一个始点s和终点t ，求s到t的 一条路，使路长最短(即路的各边权数之和最小)。 方 法：狄克斯屈标号法和距离矩阵摹乘法。 8.3.1 狄克斯屈标号法(适用于不含负权的网络) 一、基本思想 固定标号 P(i) - 从始点s到i的最短路长 临时标号 T(j) - 从始点s到j的最短路长上界,第8章 网络分析,47,8.3 最短路问题,二、基本步骤 给始点s标上固定标号0，即令 i= s，令 P(i)= 0； 给其余各点j标上临时标号(省略不写),即令T(j)= 。, 在所有临时标号中，选择权数最小的改为固定标号， 并且根据该标号的由来选择相应的边。 终点t 得到固定标号了吗？是则结束，否则返回。, 对刚得到固定标号那点i一切关联边的终点j ，修改 其临时标号：,关键步骤,第8章 网络分析,48,8.3 最短路问题,例6,（0）,（ ）,（ ）,（ ）,3,（ ）,10,1,4,7,2,4,5,7,11,8,（ ）,11,（ ）,5,6,7,w = 10,第8章 网络分析,49,8.3 最短路问题,例7 设备更新问题 各年初购价 年 度 i 1 2 3 4 5 年初购价pi 13 14 16 19 24,各年维护费 使用年数 k 1 2 3 4 5 第k年维护费ck 8 10 13 18 27,解：设以 6第5年末这一状态 (i ,j)第i年初购置的一台新设备一直使用到第j年初这一方案 wij 方案(i ,j ) 的费用,i第i年初这一状态， i = 1,2, ,5,第8章 网络分析,50,8.3 最短路问题,有 j - i wij = pi + ck k = 1,累积维护费 使用年数 j-i 1 2 3 4 5 第年维护费ck 8 10 13 18 27 累积维护费ck,76,8,18,31,49,第8章 网络分析,51,8.3 最短路问题,（0）,21,31,44,62,89,（ ）,84,（ ）,78,（ ）,（ ）,（ ）,1,3,6,第8章 网络分析,52,8.3.2 距离矩阵摹乘法(摹仿矩阵乘法) 一、 网络的距离矩阵 设一网络N中有n个结点，其中任意两点i与 j之间都有 一条边(i, j), 其权数wij -。 若i与 j不相邻,则虚设一条边(i,j), 并令其权数 wij = , 则 W = (wij)nn 称为网络N的直接距离矩阵。,（0）,1,2,（ ）,狄克斯屈标号法对于有负权的网络可能失效。,8.3 最短路问题,第8章 网络分析,53,8.3 最短路问题,0 3 2 4 0 4 4 1 0 -1 6 3 -2 0 1 5 0 3 3 3 0,W =,例8,从至,1 2 3 4 5 6,1 2 3 4 5 6,第8章 网络分析,54,8.3 最短路问题,二、求各点至某点的最短路,dk=,负回路,dk=w* dk-1 ， k=2，3, ,n -1,dk= dk-1 则也结束,若不含负回路， 至多算到 dn-1。,* 运算：两矩阵对应元素求和取小。 两矩阵元素对应方式，同矩阵乘法。,wij,第8章 网络分析,55,8.3 最短路问题,*,从至,1 2 3 4 5 6,1 2 3 4 5 6,d2,d1,d3,d4,d5,4,1,9,-1,3,0,= min 0+4, 3+1, 2+, +, +3, 4+0,0 3 2 4,4 1 3 0,= 4, 0 4 4 1, 0 -1 6 ,3 -2 0 1 ,5 0 3, 3 3 0,第8章 网络分析,56,8.3 最短路问题,2,1,-1,-2,0,3,4,2,6,2,6,6,最 短 路,按W阵中画圈元素的从至关系,0 1 -2 -1 3 0,最短路长,0,2,-1,-2,+1,= 0,第8章 网络分析,57,8.3 最短路问题,3,1,3,4,1,1,0 -1 2 1 2 0,最 短 路,最短路长,l2T=,l1T * W =,( 0 3 2 4 ),*,( 0 3 2 1 7 4 ),( 0 -1 2 1 2 4 ),( 0 -1 2 1 2 0 ),( 0 -1 2 1 2 0 ),l3T=,l4T=,l5T=,3,1,-1,1,1,三、 求某点至各点的最短路,2,7.5最短路径问题,最短路问题就是在一个网络图中，给定一个起点vs和一个终点vt，寻找vs到vt的路，使该路为从vs到vt的所有路中权数最小的路。 实际问题中最短路问题有广泛的应用。例如管道铺设、线路安排、运输线路选择、工厂布局、设备更新等问题。 解法： 标号法 矩阵法,标号法,最短路的标号法是由狄克斯屈（E.W.Dijkstra）于1959年提出的，是目前公认的求解权数为非负的网络最短路问题较好的算法。这种算法能够求出网络中任意一点出发到其它各点的最短路。 算法的思想如下： 对每一个网络中的点vj，均赋予一个标号，永久标号P（vj）或临时标号T（vj）。其含义如下： P（vj）从起点vs到vj最短路的长； T（vj）从起点vs到vj最短路的长的上界。 一个点只能有上述两种标号之一，如果有了P标号就不再改变了，如果有T标号则根据情况进行修改。,标号法,该算法的基本思想就是先给vs点标号为P（vs）=0，其余点标号为T（vj）=；然后检查有P标号的点，对与该点有关联边的vj的T标号进行修改；在所有T标号中找一个最小的，将其T标号修改成P标号。再检查新得到P标号的点，修改其它点的T标号，再在所有T标号中找最小的修改为P标号；如此反复，直到要求的终点（或所有点）得到P标号为止，即可得到网络最短路。因为此算法一次修改一个P标号，所以如果网络中有N个点，最多经过N-1步就能找出要求的最短路。 为了寻找到vs各点的最短路线，给每个顶点一个 值，算法终止时，如果 表示在从vs到vj的最短路上vj的前一个点为vm；若 ，则表示vs到vj不存在路；，则表示vj为起点。,Dijkstra方法的具体步骤为:,（1）给vs标上永久标号P(vs)=0，其余节点标上临时标号T(vj)=，同时给各点vj赋值如下： （2）若节点vi是刚得到P标号的点。把与vi有弧（边）直接相连而且有T标号的节点，对其T标号和 进行如下修改： 若T(vj)P（vi）+wij，则T(vj)=P（vi）+wij ； （3）把T标号中值最小的节点vj0的临时标号T(vj0)改为P(vj0)，如果所有点均有P标号、或要求的终点有P标号、或无法继续修改时，则算法终止；否则转（2）。,例7-4 用标号法求v1到其它各点的最短路。,用表格的一行表示一个步骤，表格中的左上角表示P（T）标号，其中表示P标号；右下角表示 值,例7-4,到各点的最短路的长就是各点的P标号之值。到各点的最短路线可从该点的最后的值出发，逆序寻找其前一点的值，直到起点为止，即可得到从起点到该点的最短路线。 例如：P(v7)=9，说明从v1到v7的最短路长为9 （v7）=5 （v5）=6 （v6）=4 （v4）=3 （v3）=1 v7 v5 v6 v4 v3 v1,对于无负权的无向图来说，标号法的程序也是相同的。,矩阵法,当一个网络存在负权时，Dijkstra算法会失效。如图7-22,图7-22. 负权网络,从v到v3的最短路长为-1，而不是2。,矩阵法的基本思想是利用本章第一节中介绍的网络图的矩阵表示，其中的wsj表示从vs经一步到vj的权，可记为：,则从vs经两步到达vj的权为：,一般，经K步从vs经两步到达vj的权为,矩阵法,k-1步,1步,图7-23. 求解存在负权网络步骤,如图7-23；,即：,由于 的计算就是n 个对应元素的求和取小，这与矩阵的乘法的计算是相类似的，所以此算法也称矩阵摹乘法。,当 （j=1,2,n）时，说明从 的最短路的权不能再减少，所以 （j=1,2,n）即为 的最短路的权。,7.6最小费用最大流问题,第三节讨论了网络最大流问题，在实际中涉及流的问题时，人们考虑的不只是流量，同时要考虑“费用”的因素。 对D=(V,A,C), 给定一个单位流量的费用bij0, 最小费用最大流即:求一最大流f, 使,增广链的费用,最大流的算法是从某个可行流出发，寻找关于可行流的增广链，然后沿着增广链调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。 对于增广链, 若调整流量=1, 那么新可行流F的费用比原可行流F的费用增加量为: 称为增广链的费用。,可以证明，若F是流量为f的所有可行流中费用最小的，而是关于F的费用最小的增广链，那么沿着增广链去调整流量，得到的新可行流F，就是流量为f的费用最小的可行流。这样当F为最大流时，也就是所求的最小费用最大流。,基本思想,由于bij0，所以零流的费用总是最小的。所以可以从零流出发去寻找最小费用最大流。 这里主要需要解决的问题就是如何寻找关于F的费用最小的增广链。为此，可构造网络图D的相对应的赋权有向图W（F），其节点与原网络图D相同，将D中的每一条弧（，）都变成两方向相反的弧（，）与（，）定义W（F）中弧的权为： 权数为的弧表示不能通过，可以在W（F）中省略。 这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。,权数为的弧表示不能通过，可以在W（F）中省略。,具体算法,这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。 具体算法为：从零流出发，构造其W（F），在W（F）中寻找最短路，在F中对应一个增广链，增广链的调整量由下式确定： 沿增广链，对流量进行调整，调整方法同最大流的调整方法。然后对新得到的可行流继续做前述的工作，直到在赋权有向图W（F）中找不到从始点到终点的最短路（也就是在网络图D中不存在增广链）为止，即可得到最小费用最大流。,第8章 网络分析,70,8.5 最小费用最大流问题,8.5. 1 基本概念 一、最小费用流 (1) 运价 设X是网络N=(V, A)的一个可行流,定义实值函数 c( i, j ) = cij 0， ( i, j ) A 表示该弧输送单位流量的费用，简称运价； (2) 可行流的费用 c(X)= cijxij ( i, j ) A (3) 最小费用流 在流量为 f 的一切可行流中，若X费用为最小，则称X为流量为 f 的 最小费用流。,第8章 网络分析,71,8.5 最小费用最大流问题,二、最小费用增广链 (1) 增广链的费用 设： (X ) 可行流 X 的增广链 X 沿着 (X )以 = 1 去调整 X 而得到的一个 新可行流 则增广链 (X )的费用定义为： c( ) = c( X )-c( X ) 由,第8章 网络分析,72,8.5 最小费用最大流问题,得,故有,c( ) = c( X ) c(X),= cij xij ( i, j ) A,= cij(xij xij) ( i, j ) A,= cij(xij xij) ( i, j ) ,+ cij(xij xij) ( i, j ) -,第8章 网络分析,73,8.5 最小费用最大流问题,即,(2) 最小费用增广链 在所有关于X的增广链中,若(X )的费用最小,则称(X )为关于X的最小 费用增广链。,三、对偶网络 设 X = xij 是网络 N = (V, A) 的一个可行流, 则称按下述方法所构造 的一个对应于N 和 X 的新网络 N( X）= ( D, w )为关于可行流 X 的对偶 网络: (1) N 的结点与 N 的结点完全一致； (2) 根据 N 中的每一弧(i, j ) A 及其流量 xij, 确定 N 的弧及其 权数如下：,第8章 网络分析,74,8.5 最小费用最大流问题, cij,() 若 xij = 0( 零流弧 )，则保留原弧，令 wij = cij ，即,() 若 0 xij rij( 非零流、非饱和弧 ) 则保留原弧，并增加一条反向弧，令 wij = cij， wji = cij， 即,() 若xij = rij ( 饱和弧 )，则将原弧反向，令 wij = cij， 即,第8章 网络分析,75,8.5 最小费用最大流问题,(a)中弧旁数字为： cij，rij，xij (b)中弧旁数字为： wij,图8-25,-2,-3,-5,-1,5,2,1,如下图,第8章 网络分析,76,8.5 最小费用最大