网络优化-第7章+最小费用流问题

《网络优化-第7章+最小费用流问题》由会员分享，可在线阅读，更多相关《网络优化-第7章+最小费用流问题（76页珍藏版）》请在金锄头文库上搜索。

1、1,网 络 优 化,Network Optimization http:/ 谢金星 办公室：理科楼2206# （电话：62787812） Email: http:/ 最小费用流问题 (Minimum Cost Flow Problem) 第1讲,2,许多实际问题都可以转化为最小费用流问题,S,T,最小费用流问题的例子,公路交通网络：车辆路线确定,最短路问题,最小费用流问题,1辆车,多辆车:车流,3,定义7.1 在流网络N=(V,A，L,U,D) 上增加如下的权函数： C： A R为弧上的权函数，弧（i，j）对应的权 C（i，j）记为cij ，称为弧（i，j）的单位流量的成本或费用（cost）;

2、 此时网络可称为容量-费用网络 (一般仍可简称为网络),记为 N=(V,A,C，L,U,D).,7.1.1 最小费用流问题,di 0:供应点(supply node)或源(source)、起始点或发货点 di 0:需求点(demand node)或汇(sink) 、终止点或吸收点 di 0:转运点(transshipment node)或平衡点、中间点,可以把L 0的网络转化为L=0的网络进行研究(思考？) 除非特别说明, 假设L=0,网络简记为N=(V,A,C，U,D).,4,定义7.2 （容量-费用网络中的流(flow) 的定义同前一章） 流x的（总）费用定义为,通常又称为转运问题(tra

3、nsshipment problem)或容量受限的转运问题(capacitated transshipment problem).,最小费用流问题就是在网络中寻找总费用最小的可行流.,最小费用流问题,引理7.1 最小费用流问题存在可行流的必要条件,经典的最小费用流问题：单源单汇(起点s，终点t)，寻找从s流到t的给定流量(或最大流量、最小流量等)的最小费用流.,线性费用网络,思考： 经典问题与一般问题有什么关系？是否等价？,5,例 7.1 最短路问题,在有向网络中，令所有弧上容量下界为0，容量（上界）为1，并令图中节点s的供需量为1，节点t的供需量为-1，则： 从s到t的一条有向路正好对应于网

4、络中的一个可行流x （弧(i，j)位于s-t路上：xij =1；弧(i，j)不在s-t路上：xij=0）. 如果再令所有弧上的(单位流量)的费用为“弧长”, 则此时的最小费用流问题就是第五章讨论过的最短路问题. 在第五章我们正是用这样的方式对最短路问题进行建模的,7.1.2 最小费用流模型的特例及扩展,6,例 - 最大流问题,设s为起点,t为终点,增加弧(t,s), 令,7.1.2 最小费用流模型的特例及扩展,而令所有其他弧上的费用为0, 所有顶点上的供需量(外部流量)全为0.,7,例 -运输问题(transportation Problem) 又称Hitchcock问题（Hitchcock,

5、1941年）,完全二部图 只有源和汇 没有中间转运点,7.1.2 最小费用流模型的特例及扩展,如果每条弧上还有容量(上下限)的限制, 则称为容量受限的运输问题(capacitated transportation problem).,有解的必要条件,可以不失一般性,指派问题(assignment problem),8,7.1.2 最小费用流模型的特例及扩展,（1）当一定的流量流过一条弧时，该弧上导致的总费用与流量大小成线性正比关系，这样的流网络一般称为线性费用网络. 如果当一定的流量流过一条弧时，该弧上导致的总费用不一定与流量大小成线性正比关系，而是流量大小的一个凹（或凸）函数，则这样的网络称

6、为凹（或凸）费用网络，相应的最小费用流问题称为凹（凸）费用网络上的最小费用流问题.,（2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点的流量）与进入该弧的流量（即流出该弧起点的流量）相等. 如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量的一个线性函数，即流出该弧的流量是对进入该弧的流量按一定比例进行放大或缩小的结果，则这样的流网络一般称为带增益(或盈亏)的流网络（flow with gain network）. 增益除了可以发生在弧上，类似地可以考虑增益发生在节点上,9,7.1.2 最小费用流模型的特例及扩展,最 小 费 用 流 问 题,狭义模型,广义模型,10,单源单汇网络 可

7、行流x的流量（或流值）为v=v（x）= ds = - dt 如果我们并不给定ds 和dt , 则网络一般记为N=(s, t,V,A,C,U) 容量可行且转运点流量守恒的流称为s-t可行流，有时为了方便也称为可行流. 最小费用流问题就是在网络N=(s,t,V,A,C,U)中计算流值为v的最小费用流x 或者当不给定流值时, 计算流值最大的最小费用流x (此时流x称为最小费用最大流).,7.2 消圈算法与最小费用路算法,最小费用最小流?,11,7.2 消圈算法与最小费用路算法,定义7.3 对网络N=(s,t,V,A,C,U)中给定的s-t可行流x，网络N关于流x的残量网络N(x) = (s, t,

8、V, A(x), C(x), U(x) , 其中A(x), C(x) ，U(x)定义如下：（residual network，或增量网络或辅助网络 ）,讨论算法复杂度时，假定: 弧（i，j）A时，弧（j，i） A；c ij = - cji A（x）=A (允许容量为0的弧仍然保留在网络中就可以了),其中称, uij(x)为弧(i,j)上的残留容量(residual capacity).,12,定义W的费用为,对于N(x)中的任何一个有向圈W, 它一定对应于原网络N中的一个增广圈(增广弧构成的圈)； 通过沿W对当前流x进行增广，可以获得流值相等的s-t可行流y.,消圈算法的思想,则当增广的流量为

9、时,只要N中存在费用为负数的增广圈W，即C（W）0，则可以通过沿W 对当前流 x 进行增广，获得流值相等但费用更小的s-t可行流y.,13,设x0为不同于的可行流，但费用低于x的费用，即,7.2.1 消圈算法(cycle-canceling algorithm),定理7.1 可行流x为最小费用流的充要条件是N(x)中不存在负费用增广圈.,令 x1 =x0-x, 则 ，即令x1为网络N中的循环流.,一个循环流一定可以表示为至多m个非零圈流之和，所以可以将x1表示为r个非零圈流之和（ ）。设对应的有向圈为Wk，,至少存在一个费用为负的增广圈. 矛盾,必要性是显然的. 反证法证明充分性：,14,N(

10、x)中找负圈可用最短路算法(如Bellman-Ford算法，O(m n ) ) 则该算法的复杂度为O(n m 2CU), 不是多项式时间算法.,STEP 2. 沿找到的负圈增广流量, 转STEP 1.,Step0可借用最大流算法 ，复杂度为O(n2m),STEP 0 . 在网络N=(s,t,V,A,C,U)中计算流值为v的可行流 x.,7.2.1 消圈算法: Klein (1967)等,STEP 1. 在残量网络N(x)中判别负圈. 若无负圈, 则已经找到了最小费用流，结束；否则转STEP 2.,如按一些特定次序消圈, 可得到一些多项式时间算法,复杂度？,任何可行流的费用不可能超过mCU 设数

11、据是整数, 每次消去一个负圈至少使费用下降一个单位 设数据是整数, 消去负圈的STEP12最多执行O(mCU )次,15,略,7.2.1 消圈算法,例：,16,能否首先在网络N=(s,t,V,A,C,U)中计算流值为v且费用最小的s-t可行流(v v)，然后对它沿增广路增广以增加流值呢?,7.2.2 最小费用路算法,为了获得最小费用流，我们希望沿费用最小的增广路对当前流x进行增广，以最小的费用增加获得流值更大的s-t可行流y,对于N(x)中的一条从s到t的有向路P,它一定对应于原网络N中的一条增广路，即可以通过沿P对当前流x进行增广，获得流值更大的s-t可行流y. 定义P的费用为,则当增广的流

12、量为时,17,7.2.2 最小费用路算法,定理7.2 设x为流值为v的最小费用流，P为关于x的从s到t的一条最小费用增广路，且沿P所能增广的流量为 ，则增广后得到流值为v+ 的最小费用流y.,只需证明网络中不存在关于y的负费用增广圈. 用反证法,假设增广后存在关于y的负费用增广圈W. 由于除P以外的弧及其流量在增广前后没有发生改变, 于是P和W至少有一条公共弧. 不妨假设P和W只有一条公共弧,记为(i,j),如果 (i,j) 在P中是正向弧, 则在W中是反向弧; 反之, 如果 (i,j) 在P中是反向弧, 则在W中是正向弧,也是网络中关于x的增广路, 且,18,7.2.2 最小费用路算法,也称

13、为连续最短路算法, 即Successive Shortest Path Algorithm), Jewell(1958), Iri(1960), Busacker & Gowen (1961) 独立提出的,STEP 0 . 取x为任一s-t可行流、且在同一流值的流中费用最小的流 (如x=0).,STEP 1. 若x的流值达到v, 结束；否则在残量网络N(x)中判别最小费用路. 若无这样的路,则流值不可达到v, 结束；否则STEP 2.,STEP 2. 沿该最小费用增广路增广流量(增广后的流值不超过v), 转STEP 1.,STEP1可用最短路算法：记最短路算法的复杂度为S(n，m，C),STE

14、P12最多执行O(v )次,复杂度？,最大流流值不超过nU，本算法复杂度为 O(nUS(n，m，C),采用特定的变尺度技术, 可以得到一些多项式时间算法,19,略,7.2.2 最小费用路算法,例：,20,7.3.1对偶问题及互补松弛条件,仍然考虑传统的单源单汇网络的最小费用流问题,两类约束分别引入对偶变量和z, 则这一问题的对偶问题为,7.3 原始-对偶算法,21,互补松弛条件 设x和(,z)分别为原问题和对偶问题的可行解：,下面我们说明在一定的“约定”下, 这一条件可以等价地写成 当 时 ， =0； (7.19) 当 时， = ； (7.20) 当 时， . (7.21),约定:存在对偶可行

15、的变量z，使得上式成立.,定理7.3 设x为原问题的可行解, 则x为最小费用流的充要条件是: 存在节点的势（）, 满足条件(7.19)(7.21).,7.3.1对偶问题及互补松弛条件,记“相对费用”（Reduced Cost）,22,7.3.1对偶问题及互补松弛条件,引理7.2 最优性条件(7.19)(7.21)等价于，对于N(x)中任意的(i,j)弧, 0,当 时，即 0, 所以 = =-( )= - 0, 因此(j,i)弧不属于残量网络N(x). 所以 =0.,当 时，即 0, (i,j)弧不属于残量网络N(x), =,当 时， (i,j),(j,i)弧均属于残量网络N(x). 所以 , 所以,23,思路： 从流值不一定达到v的s-t可行流开始，迭代中始终保持最优性条件(7.19)(7.21)成立，直到流值达到v为止. 迭代包括两个方面：对弧上流的增广；对节点上势的修改,当N0(x)中找不到增广路且流值小于v时，必须进行下一个过程，修改节点上的势.,原始-对偶算法就是在允许网络N0(x)中寻找增广路并进行增广（最大流）,为保证流的增广过程