1,网 络 优 化,Network Optimization ,清华大学数学科学系 谢金星 办公室：理科楼2206# （电话：62787812） Email: ,清华大学课号：70420133（研）,第7章 最小费用流问题 (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）; 此时网络可称为容量-费用网络 (一般仍可简称为网络),记为 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的（总）费用定义为,通常又称为转运问题(transshipment problem)或容量受限的转运问题(capacitated transshipment problem).,最小费用流问题就是在网络中寻找总费用最小的可行流.,最小费用流问题,引理7.1 最小费用流问题存在可行流的必要条件,经典的最小费用流问题：单源单汇(起点s，终点t)，寻找从s流到t的给定流量(或最大流量、最小流量等)的最小费用流.,线性费用网络,思考： 经典问题与一般问题有什么关系？是否等价？,6,例 - 最大流问题,设s为起点,t为终点,增加弧(t,s), 令,7.1.2 最小费用流模型的特例及扩展,而令所有其他弧上的费用为0, 所有顶点上的供需量(外部流量)全为0.,7,例 -运输问题(transportation Problem) 又称Hitchcock问题（Hitchcock,1941年）,完全二部图 只有源和汇 没有中间转运点,7.1.2 最小费用流模型的特例及扩展,如果每条弧上还有容量(上下限)的限制, 则称为容量受限的运输问题(capacitated transportation problem).,有解的必要条件,可以不失一般性,指派问题(assignment problem),8,7.1.2 最小费用流模型的特例及扩展,（1）当一定的流量流过一条弧时，该弧上导致的总费用与流量大小成线性正比关系，这样的流网络一般称为线性费用网络. 如果当一定的流量流过一条弧时，该弧上导致的总费用不一定与流量大小成线性正比关系，而是流量大小的一个凹（或凸）函数，则这样的网络称为凹（或凸）费用网络，相应的最小费用流问题称为凹（凸）费用网络上的最小费用流问题.,（2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点的流量）与进入该弧的流量（即流出该弧起点的流量）相等. 如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量的一个线性函数，即流出该弧的流量是对进入该弧的流量按一定比例进行放大或缩小的结果，则这样的流网络一般称为带增益(或盈亏)的流网络（flow with gain network）. 增益除了可以发生在弧上，类似地可以考虑增益发生在节点上,9,7.1.2 最小费用流模型的特例及扩展,最 小 费 用 流 问 题,狭义模型,广义模型,10,单源单汇网络 可行流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, 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.,消圈算法的思想,则当增广的流量为时,只要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(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 设数据是整数, 每次消去一个负圈至少使费用下降一个单位 设数据是整数, 消去负圈的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的费用为,则当增广的流量为时,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 最小费用路算法,也称为连续最短路算法, 即Successive Shortest Path Algorithm), Jewell(1958), Iri(1960), Busacker 节点上的数字表示节点的供需量).,7.3.2原始-对偶算法 ,例：,x=0, =0,计算得到 d=(0,0,0,1,2,1), 修改得到=(0, 0, 0, -1, -2, -1),（uij，cij）,31,7.3.2原始-对偶算法 ,例,计算得到 d=(0,0,0,1,0,1) , 修改得到=(0, 0, 0, -2, -2, -2),最大流流值为2, 增广,32,7.3.2原始-对偶算法 ,例,x的流值达到4 得到最小费用流,最大流流值为2, 增广,33,7.3.2原始-对偶算法 复杂性分析,算法每次循环迭代修改弧上的流值和节点上的势各一次. 由于流值不可能超过nU, 且任何节点上的势不可能低于-nC, 因此总迭代次数不会超过minnU,nC.,记求解非负弧长网络的最短路算法的复杂度为S(n，m，C), 最大流算法的复杂度为M(n，m，U) 本算法复杂度为O(minnU,nCS(n，m，nC)+ M(n，m，U) ) 这一算法仍然不是多项式时间算法,与最小费用路算法相比, 可能会以每次迭代调用一次最大流算法为代价, 希望减少一些迭代次数.,34,布 置 作 业,目的,掌握最小费用流问题的基本概念和建模方法； 掌握消圈算法与最小费用路算法及其复杂度； 掌握原始-对偶算法的基本思想。,内容,网络优化第245-251页 3；6；15；（第1讲）,思考,4； 5； （不交）,35,网 络 优 化,Network Optimization ,清华大学数学科学系 谢金星 办公室：理科楼2206# （电话：62787812） Email: ,清华大学课号：70420133（研）,第7章 最小费用流问题 (Minimum Cost Flow Problem) 第2讲,36,(Out-Of-Kilter Algorithm),瑕疵算法(也翻译为“状态算法”)在迭代过程中则对这些条件更为放宽: 只要求满足节点上的流量守恒条件, 而不要求x为伪流(即可能不满足容量约束), 并且也不一定保持互补松弛条件.,最小费用路算法和原始-对偶算法的特点 : 对偶变量为对偶问题的可行解, 并始终保持互补松弛条件； 但原始变量x在算法终止前通常不是原问题的可行解 （即只是伪流，而不一定满足节点上的流量守恒条件, 即不是流值为v的可行流）.,7.4瑕疵算法,37,(Out-Of-Kilter Algorithm),想一想,非循环流的情况是否都可以转化为循环流的情况?,算法的思想： 通过一定步骤, 使非最优的“程度”不断降低，最后达到最优. 可以认为, 瑕疵算法是原始-对偶算法的一种变形.,瑕疵算法的考察对象： 循环流(Circulation) ：流值为0的可行流（没有所谓源点和汇点, 网络中的所有节点都是转运点） 网络中容量下限 L 不一定为0；,7.4瑕疵算法,38,- Kilter条件,7.4瑕疵算法,L0,L=0,最小费用循环流模型,当 0 时 ， = 0； (7.19) 当 0 时， = ； (7.20) 当 时， = 0. (7.21),当 0 时 ， = ； (7.23) 当 0 时， = ； (7.24) 当 时， = 0. (7.25),互补松弛条件,Kilter条件（或译为瑕疵条件、状态条件等）,满足该条件的弧为无瑕的(In-Kilter), 否则称为有瑕的(Out-Of-Kilter).,39,- Kilter图;Kilter数,7.4瑕疵算法,如果所有弧都是无瑕的, 则得到了原问题的最优解.,定义