1、1学习要点学习要点理解线性规划算法模型掌握解线性规划问题的单纯形算法 理解网络与网络流的基本概念掌握网络最大流的增广路算法掌握网络最小费用流的消圈算法第7章 线性规划与网络流2线性规划问题和单纯形算法线性规划问题和单纯形算法线性规划问题及其表示线性规划问题及其表示一般线性规划问题可表示为如下形式：一般线性规划问题可表示为如下形式：s.t.)1.8(max1njjjxc)5.8(,2,10)4.8(,1)3.8(,1)2.8(,2,1321211211111ntxmmmmmkbxammmjbxamibxatntktktntjtjtntitit3变量满足约束条件变量满足约束条件(7.2)-(7.5
2、)式的一组值称为线性规划问题的一个式的一组值称为线性规划问题的一个可可行解行解。所有可行解构成的集合称为线性规划问题的所有可行解构成的集合称为线性规划问题的可行区域可行区域。使目标函数取得极值的可行解称为使目标函数取得极值的可行解称为最优解最优解。在最优解处目标函数的值称为在最优解处目标函数的值称为最优值最优值。有些情况下可能不存在最优解。有些情况下可能不存在最优解。根本没有可行解，可行区域为空集；根本没有可行解，可行区域为空集；目标函数没有极值，目标函数值无界。目标函数没有极值，目标函数值无界。4标准线性规划问题描述标准线性规划问题描述),2,1(0max221122222121112121
3、112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn约束条件：目标函数：5将一般线性规划问题转化为标准型规划问题的方法将一般线性规划问题转化为标准型规划问题的方法(1)一般线性规划形式中目标函数如果是求极小值的，即一般线性规划形式中目标函数如果是求极小值的，即 那么，令那么，令 ，则，则，(2)右端常数项如果小于零，则不等式两边同乘以（右端常数项如果小于零，则不等式两边同乘以（-1），将其变成大于），将其变成大于零；同时改变不等号的方向，保证恒等变形。如零；同时改变不等号的方向，保证恒等变形。如2x1+x26，2x1x26。(3)约束条件为大于等
4、于约束时，则在不等式左边减去一个新的非负变量约束条件为大于等于约束时，则在不等式左边减去一个新的非负变量将不等式约束改为等式约束。如将不等式约束改为等式约束。如3x12x212，3x12x2x312，x30；(4)约束条件为小于等于约束时，则在左边加上一个新的非负变量将不等约束条件为小于等于约束时，则在左边加上一个新的非负变量将不等式约束改为等式约束。如式约束改为等式约束。如x12x28，x12x2x38，x30；(5)无约束的决策变量无约束的决策变量x，即可正可负的变量，则引入两个新的非负变量，即可正可负的变量，则引入两个新的非负变量x和和x”，令，令x=-x-x”，其中，其中x0，x”0，
5、将，将x代入线性规划模型。代入线性规划模型。(6)决策变量决策变量x小于等于小于等于0时，令时，令xx，显然，显然x0，将，将x代入线性规划代入线性规划模型。模型。在在(3)(6)中引入的新的非负变量称为中引入的新的非负变量称为松弛变量松弛变量。njjjxcz1minzznjjjxcz1maxmaxminzz6标准型线性规划问题的单纯形算法标准型线性规划问题的单纯形算法 单纯形法单纯形法是指是指1947年数学家年数学家George Dantzing(乔治乔治丹捷格丹捷格)发明发明的一种求解线性规划模型的一般性方法。的一种求解线性规划模型的一般性方法。约束标准型线性规划问题约束标准型线性规划问题
6、为了便于讨论，先考察一类特殊的标准形式的线性规划为了便于讨论，先考察一类特殊的标准形式的线性规划问题。在这类问题中，问题。在这类问题中，每个等式约束条件中均至少含有每个等式约束条件中均至少含有一个正系数的变量，且这个变量只出现在一个约束条件一个正系数的变量，且这个变量只出现在一个约束条件中。中。将每个约束条件中这样的变量作为非将每个约束条件中这样的变量作为非0变量来求解该变量来求解该约束方程。这类特殊的标准形式线性规划问题称为约束约束方程。这类特殊的标准形式线性规划问题称为约束标准型线性规划问题。标准型线性规划问题。7基本概念：基本概念：基本变量（基本变量（m个）：每个约束条件中的系数为正个）
7、：每个约束条件中的系数为正且只出现在一个约束条件中的变量。且只出现在一个约束条件中的变量。非基本变量非基本变量(n-m)：除基本变量外的变量全部为：除基本变量外的变量全部为非基本变量。非基本变量。基本可行解：满足标准形式约束条件的可行解称基本可行解：满足标准形式约束条件的可行解称为基本可行解。由此可知，如果令为基本可行解。由此可知，如果令n-m个非基本个非基本变量等于变量等于0，那么根据约束条件求出，那么根据约束条件求出m个基本变个基本变量的值，它们组成的一组可行解为一个基本可行量的值，它们组成的一组可行解为一个基本可行解。解。8线性规划基本定理线性规划基本定理定理定理1（最优解判别定理）若目
8、标函数中关于非（最优解判别定理）若目标函数中关于非基本变量的所有系数（以下称检验数）小于等于基本变量的所有系数（以下称检验数）小于等于0，则当前基本可行解就是最优解。，则当前基本可行解就是最优解。定理定理2（无穷多最优解判别定理）若目标函数中（无穷多最优解判别定理）若目标函数中关于非基本变量的所有检验数小于等于关于非基本变量的所有检验数小于等于0，同时，同时存在某个非基本变量的检验数等于存在某个非基本变量的检验数等于0，则线性规，则线性规划问题有无穷多个最优解。划问题有无穷多个最优解。定理定理3（无界解定理）如果某个检验数（无界解定理）如果某个检验数cj大于大于0，而而xj对应的列向量中所有基
9、本变量的系数对应的列向量中所有基本变量的系数a1j,a2j,amj都小于等于都小于等于0，则该线性规划问题有，则该线性规划问题有无界解。无界解。9约束标准型线性规划问题的单纯形算法约束标准型线性规划问题的单纯形算法步骤步骤1：找出基本变量和非基本变量，将目标函数由：找出基本变量和非基本变量，将目标函数由非基本变量表示，建立初始单纯形表如表非基本变量表示，建立初始单纯形表如表7-1所示。所示。表表7-1 初始单纯形表初始单纯形表110步骤步骤2；判别、检查目标函数的所有系数，即检验；判别、检查目标函数的所有系数，即检验数数cj(j=1,2,n)。（1）如果所有的）如果所有的cj0，则已获得最优解
10、，算法结，则已获得最优解，算法结束。束。（2）若在检验数）若在检验数cj中，有些为正数，但其中某一正中，有些为正数，但其中某一正的检验数所对应的列向量的各分量均小于等于的检验数所对应的列向量的各分量均小于等于0，则线性规划问题无界，算法结束。则线性规划问题无界，算法结束。（3）若在检验数）若在检验数cj中，有些为正数且它们所对应的中，有些为正数且它们所对应的列向量中有正的分量，则转步骤列向量中有正的分量，则转步骤3。步骤步骤3：选入基变量。在所有：选入基变量。在所有cj0的检验数中选取的检验数中选取值最大的一个，记为值最大的一个，记为ce，其对应的非基变量为，其对应的非基变量为xe，对应的列向
11、量为对应的列向量为a1e,a2e,ameT，称为入基列。，称为入基列。11步骤步骤4：选离基变量。选取：选离基变量。选取“常数列元素常数列元素/入基列元入基列元素素”正比值的最小者所对应的基本变量为离基变量，正比值的最小者所对应的基本变量为离基变量，即即 ，选取基本变量，选取基本变量xk为离基变量。为离基变量。步骤步骤5：换基变换（转轴变换）。在单纯形表上将：换基变换（转轴变换）。在单纯形表上将入基变量和离基变量互换位置，并按照式如下公式入基变量和离基变量互换位置，并按照式如下公式进行各元素的变换后得到一张新的单纯形表。转步进行各元素的变换后得到一张新的单纯形表。转步骤骤2。kekieiaab
12、abiemin012对应入基列位置元素对应入基列位置元素=-原入基列元素原入基列元素/交叉位置元素交叉位置元素（不包括交叉位置）。（不包括交叉位置）。对应离基行位置元素对应离基行位置元素=原离基行元素原离基行元素/交叉位置元素交叉位置元素（不包括交叉位置）。（不包括交叉位置）。交叉位置元素交叉位置元素=原交叉位置元素的倒数。原交叉位置元素的倒数。目标函数的值目标函数的值=原目标函数的值原目标函数的值+同行画线位置元素同行画线位置元素同列画线位置元素同列画线位置元素/交叉位置的元素。交叉位置的元素。其它位置的元素其它位置的元素=原对应位置的元素原对应位置的元素-同行画线位置同行画线位置元素元素同
13、列画线位置元素同列画线位置元素/交叉位置的元素交叉位置的元素13例题例题1)1,2,3,40(ix-108x 3x4x12 4x2x-7 2x x-3xx2x3x-xzmin i432 324321432zz)61,2,3,4,5,0(ix10 x8x 3x4x-12 x4x2x-7 2x x-3xx2x3xxzmin i64325 324321432解：将线性规划问题转化为约束标准型如下：解：将线性规划问题转化为约束标准型如下：令令14由约束标准形式可知：由约束标准形式可知：x1,x5,x6是基本变量，是基本变量，x2,x3,x4是非基本是非基本变量，建立初始单纯形表如表变量，建立初始单纯形
14、表如表7-2所示。由此可得，基本可行解所示。由此可得，基本可行解为为X(0)=（7,0,0,0,12,10），），z=0。由表由表7-2可知：可知：x3为入基变量，为入基变量，x5为离基变量，根据迭代公式得为离基变量，根据迭代公式得出如表出如表7-3所示的单纯形表所示的单纯形表3。由。由此可得，基本可行解为此可得，基本可行解为X(1)=（10,0,3,0,0,1）,z=915由表由表7-3可知：可知：x2为入基变量，为入基变量，x1为离基变量，根据迭代公式迭为离基变量，根据迭代公式迭代得如表代得如表7-4所示的单纯形表所示的单纯形表4。由此可得，基本可行解为由此可得，基本可行解为X(2)=（0
15、,4,5,0,0,11）,z=11。同时，。同时，由表由表7-4可知，所有检验数均小可知，所有检验数均小于等于于等于0，故，故X(2)=（0,4,5,0,0,11）为该线性）为该线性规划问题的唯一最优解，其最优规划问题的唯一最优解，其最优值值z=-11。练习：练习：00348242max21212121xxxxxxxxz0042222max2121212121xxxxxxxxxxz16两阶段单纯形算法两阶段单纯形算法一般线性规划问题转化为标准形式的线性规划问题后，每个一般线性规划问题转化为标准形式的线性规划问题后，每个约束条件中不一定都含有基本变量。在这种情况下，可在每约束条件中不一定都含有基
16、本变量。在这种情况下，可在每个约束条件表达式的左端添加一个非负变量个约束条件表达式的左端添加一个非负变量zi(i=1,2,m)，将其转化为约束标准型的线性规划问题。添加的非负变量将其转化为约束标准型的线性规划问题。添加的非负变量zi称为人工变量。形式如下：称为人工变量。形式如下：),2,1(0),2,1(0max221122222121211212111112211miznjxbxaxaxazbxaxaxazbxaxaxazxcxcxcxczijmnmnmmmnnnnniiinn17第一阶段：用辅助目标函数代替原来的目标函数。第一阶段：用辅助目标函数代替原来的目标函数。辅助目标函数：辅助目标函
17、数：。选择人工变量作为基本变量，其它变量作为非基本变量，构选择人工变量作为基本变量，其它变量作为非基本变量，构造初始单纯形表。然后，运行该算法，当所有人工变量均变造初始单纯形表。然后，运行该算法，当所有人工变量均变成非基本变量时，辅助目标函数达到最大值，第一阶段算法成非基本变量时，辅助目标函数达到最大值，第一阶段算法结束；如果所有人工变量无法全部变成非基本变量，则原线结束；如果所有人工变量无法全部变成非基本变量，则原线性规划问题无解。性规划问题无解。第二阶段：将第一阶段得到的最后一张单纯形表中第二阶段：将第一阶段得到的最后一张单纯形表中的所有人工变量所在的列全部划掉，剩下的就只含的所有人工变量
18、所在的列全部划掉，剩下的就只含有有xi的约束标准型线性规划问题，此时的目标函数的约束标准型线性规划问题，此时的目标函数由辅助目标函数改为原来的目标函数，用剩下的单由辅助目标函数改为原来的目标函数，用剩下的单纯形表作为第二阶段的初始单纯形表，再次运行约纯形表作为第二阶段的初始单纯形表，再次运行约束标准型单纯形算法，即得线性规划问题的解。束标准型单纯形算法，即得线性规划问题的解。mzzzz21187.2 最大网络流问题最大网络流问题1 基本概念和术语基本概念和术语 （1）网络网络G是一个简单有向图，是一个简单有向图，G=(V,E)，V=1，2，n。在。在V中中指定一个顶点指定一个顶点s，称为，称为
19、源源和另一个顶点和另一个顶点t，称为，称为汇汇。有向图。有向图G的每一条边的每一条边(v,w)E，对应有一个值，对应有一个值cap(v,w)0，称为边的，称为边的容量容量。这样的有向图。这样的有向图G称作一个称作一个网络网络。（2）网络流网络流网络上的网络上的流流是定义在网络的边集合是定义在网络的边集合E上的一个上的一个非负函数非负函数flow=flow(v,w)，并称，并称flow(v,w)为边为边(v,w)上的上的流量流量。19（3）可行流可行流满足下述条件的流flow称为可行流可行流：容量约束：容量约束：对每一条边(v,w)E，0flow(v,w)cap(v,w)。平衡约束：平衡约束：对
20、于中间顶点：流出量=流入量。即对每个vV(vs,t)有：顶点v的流出量顶点v的流入量=0，即对于源s：s的流出量s的流入量=源的净输出量f，即对于汇t：t的流入量t的流出量的=汇的净输入量f，即式中f 称为这个可行流的流量，即源的净输出量(或汇的净输入量)。0),(),(),(),(EvwEwvvwflowwvflowfsvflowvsflowEsvEvs),(),(),(),(fvtflowtvflowEvtEtv),(),(),(),(20（4）边流边流对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边饱和边；flow(v,w)0的边称为非
21、零流边非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边弱流边。（5）最大流最大流最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：0flow(v,w)cap(v,w)，(v,w)E；且tvftsvsvfvwflowwvflow,0),(),(21（6）流的费用流的费用网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：Ewvwvflowwvtflowt),(),(),(cos)(cos22（7）残余网络残余网络对于给定的一个流网络G及其上的一个流flo
22、w，网络G关于流flow的残余网络G*与G有相同的顶点集V，而网络G中的每一条边对应于G*中的1条边或2条边。设(v,w)是G的一条边。当原网络G中的边(v,w)是一条零流边时，残流网络G*中有唯一的一条边(v,w)与之对应，且该边的容量为cap(v,w)。当原网络G中的边(v,w)是一条饱和边时，残流网络G*中有唯一的一条边(w,v)与之对应，且该边的容量为cap(v,w)。当原网络G中的边(v,w)是一条弱流边时，残流网络G*中有2条边(v,w)和(w,v)与之对应，这2条边的容量分别为cap(v,w)-flow(v,w)和flow(v,w)。23（8）向前边和向后边）向前边和向后边设P是
23、网络G中连结源s和汇t的一条路。定义路的方向是从s到t。将路P上的边分成2类：一类边的方向与路的方向一致，称为向前边向前边。向前边的全体记为P+。另一类边的方向与路的方向相反，称为向后边向后边。向后边的全体记为P-。24（9）增广路设flow是一个可行流，P是从s到t的一条路，若P满足下列条件：在P的所有向前边(v,w)上，flow(v,w)0，即P-中的每一条边都是非零流。则称P为关于可行流flow的一条可增广路。25增广路定理：增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。增广路算法增广路算法（1）初始化为0流（2）找关
24、于当前可行流的可增广路，若找到，转（3）；否则，当前可行流为网络的最大流。（3）沿增广路增流。因此，增广路算法主要包括两个过程：找增广路和沿增广路增流。26可采用标号法找可增广路。对网络中的每个节点j，其标号包括两部分信息（pred(j)，maxl(j)），其中pred(j)表示节点j在可能的增广路中的前一个节点，maxl(j)表示沿该可能的增广路到节点j为止可以增加的最大流量。具体步骤为：步骤1：源点s的标号为（0，+）。步骤2：从已标号而未检查的点v出发，对于边，如果flow(v，w)cap(v，w)，则w的标号为(v，maxl(w)，maxl(w)=minmaxl(v),cap(v，w)
25、-flow(v，w)；对于边，flow(w，v)0，则w的标号为(-v，maxl(w)，maxl(w)=minmaxl(v)，flow(w，v)。步骤3：不断重复步骤2，直到已经不存在已标号未检查的点或标到了汇点结束。如果不存在已标号未检查的点，则说明不存在关于当前可行流的可增广路，当前流就是最大流。如果标到了汇点，则找到了一条可增广路，需要沿着该可增广路进行增流，转过程（2）。沿增广路增流具体方法 PwvwvflowPwvdwvflowPwvdwvflowwvflow),(),(),(),(),(),(),(27例题用增广路算法找出如下图所示的网络及可行流的最大流，其中，顶点1为源点，顶点6
26、为汇点，边上的权为（cap，flow）。28标号法找增广路 沿着增广路增流 29标号法找增广路 沿着增广路增流 30标号法找增广路 沿着增广路增流 31标号法找增广路，当前流为最大流 32最大网络流的变换与应用最大网络流的变换与应用 1.多源多汇的网络流问题多源多汇的网络流问题多源多汇的最大流问题可以转化为单源单汇的最大流问多源多汇的最大流问题可以转化为单源单汇的最大流问题。题。方法：方法：在原网络的基础上，增加一个虚源在原网络的基础上，增加一个虚源s和一个虚汇和一个虚汇t。从从s向原网络中的源点分别引一条有向边，每一条有向原网络中的源点分别引一条有向边，每一条有向边的流量等于与其相连的源点（
27、非虚源）的流出量，向边的流量等于与其相连的源点（非虚源）的流出量，容量为无穷大；容量为无穷大；从原网络中的汇点分别向虚汇引一条有向边，每一条从原网络中的汇点分别向虚汇引一条有向边，每一条有向边的流量等于与其相连的汇点的流入量，容量为有向边的流量等于与其相连的汇点的流入量，容量为无穷大。无穷大。33示例示例：342.网络的顶点容量约束网络的顶点容量约束流经某顶点的流量不能超过该顶点给定的约束值流经某顶点的流量不能超过该顶点给定的约束值 变换方法：变换方法：只要将有顶点容量约束的顶点只要将有顶点容量约束的顶点x用一条边用一条边来替换来替换原来顶点原来顶点x的入边仍为顶点的入边仍为顶点x的入边，原来
28、顶点的入边，原来顶点x的出的出边改为顶点边改为顶点y的出边。的出边。连接顶点连接顶点x和顶点和顶点y只有一条边只有一条边，其边容量为原，其边容量为原顶点顶点x的顶点容量。的顶点容量。35最大网络流的变换与应用最大网络流的变换与应用3.二分图的最大匹配问题二分图的最大匹配问题二分图的概念二分图的概念设设G(V,E)是一个无向图。如果是一个无向图。如果顶点集合顶点集合V可分割为两个可分割为两个互不相互不相交的交的子集子集X和和Y，并且图中每条边，并且图中每条边(v,w)所关联的两个顶点所关联的两个顶点v和和w分属分属于这两个不同的顶点集，则称图于这两个不同的顶点集，则称图G为一个二分图。为一个二分
29、图。二分图的匹配二分图的匹配设设G(V,E)是一个二分图。如果是一个二分图。如果M E，且，且M中任何两条边都不与中任何两条边都不与同一个顶点相关联，则称同一个顶点相关联，则称M是是G的的一个匹配。一个匹配。二分图的最大匹配。二分图的最大匹配。36最大网络流的变换与应用最大网络流的变换与应用将二分图的最大匹配问题将二分图的最大匹配问题转换为网络的最大流问题转换为网络的最大流问题（1）增加一个源）增加一个源s利利个汇个汇t。（2）从）从s向向X的每一个顶点的每一个顶点都增加一条有向边；从都增加一条有向边；从Y的每的每一个顶点都增加一条到一个顶点都增加一条到t的有的有向边。向边。（3）原图）原图G
30、中的每中的每条都改条都改为相应的由为相应的由X指向指向Y的有向边；的有向边；（4）置所有边的容量为）置所有边的容量为1。37最大网络流的变换与应用最大网络流的变换与应用4.带下界约束的最大流带下界约束的最大流在给定网络中，对于边在给定网络中，对于边(x,y)，不仅仅有边流量的上界约，不仅仅有边流量的上界约束，即容量约束束，即容量约束cap(x,y)，还有边流量的下界约束，还有边流量的下界约束caplow(x.y)。在这种情况下，对可行流。在这种情况下，对可行流flow的容量约束的容量约束相应地改变为相应地改变为:),(),(),(yxcapyxflowyxcaplow两个阶段求解两个阶段求解第
31、第1阶段先找满足约束条件的可行流阶段先找满足约束条件的可行流第第2阶段将找到的可行流扩展成最大流。阶段将找到的可行流扩展成最大流。38最大网络流的变换与应用最大网络流的变换与应用第第1阶段先找满足约束条件阶段先找满足约束条件的可行流的可行流一个等价的循环可行流一个等价的循环可行流问题问题 变换方法变换方法在原网络中增加一条容量在原网络中增加一条容量充分大的边从汇点指向源充分大的边从汇点指向源点，这条边将从源点流到点，这条边将从源点流到汇点的流量再送回到源点汇点的流量再送回到源点构成一个循环流。原网络构成一个循环流。原网络有可行流当且仅当新网络有可行流当且仅当新网络有循环可行流。有循环可行流。3
32、9最大网络流的变换与应用最大网络流的变换与应用设设flow是新网络的一个循环可行流，则是新网络的一个循环可行流，则(1)对于对于 有有:顶点顶点x的流出量的流出量-顶点顶点x的流入量的流入量=0(2)对于对于 ，有，有将其转化为一般网络的最大流问题。将其转化为一般网络的最大流问题。转化方法转化方法对对 且边且边(x,y)既有边容量上界约束，也有既有边容量上界约束，也有边容量下界约束，在循环网络中添加相应的源边容量下界约束，在循环网络中添加相应的源点点s和汇点和汇点t，添加两条有向边，添加两条有向边(x,t)、(s,y)，边，边上的容量均为上的容量均为caplow(x,y)。VxEyx),(),
33、(),(),(yxcapyxflowyxcaplowEyx),(40将其转化为单源单汇的将其转化为单源单汇的最大流问题最大流问题4142437.3 最小费用流问题最小费用流问题1 网络流的费用网络流的费用网络的每一条边网络的每一条边(v,w)除了给定容量除了给定容量cap(v,w)外，还定义了一个单位流量外，还定义了一个单位流量费用费用cost(v,w)。对于网络中一个给定的流对于网络中一个给定的流flow，其费用定义为：其费用定义为：2涉及流的费用的残余网络涉及流的费用的残余网络对于对于G中的任一条边中的任一条边：对应于：对应于G*中的中的，则设置，则设置G*中中的单位流量费用为的单位流量费
34、用为cost(x,y)；对应于；对应于G*中的中的，则设置，则设置G*中中的单位流量费用为的单位流量费用为-cost(x,y)。Ewvwvflowwvtflowt),(),(),(cos)(cos443最小费用最大流问题最小费用最大流问题给定网络给定网络G，要求要求G的一个最大流的一个最大流flow，使流的总费用最使流的总费用最小。小。4负费用圈负费用圈对于一个给定的网络对于一个给定的网络G、其上的可行流、其上的可行流flow及流的费用，及流的费用，残余网络中的负费用圈是指所有边的单位流量费用之和残余网络中的负费用圈是指所有边的单位流量费用之和为负的圈为负的圈 最小费用最大流问题的最优性定理最
35、小费用最大流问题的最优性定理网络网络G的最大流的最大流flow是是G的一个最小费用最大流的充分必的一个最小费用最大流的充分必要条件是要条件是flow所对应的残余网络中没有负费用圈所对应的残余网络中没有负费用圈 45最小费用流的消圈算法最小费用流的消圈算法 步骤步骤0：用最大流算法构造最大流：用最大流算法构造最大流flow。步骤步骤1：如果残余网络中不存在负费用圈，则计算结束，已经找到最小费用流；：如果残余网络中不存在负费用圈，则计算结束，已经找到最小费用流；否则转步骤否则转步骤2。步骤步骤2：沿找到的负费用圈增流，并转步骤：沿找到的负费用圈增流，并转步骤1。w算法主要包括两个过程算法主要包括两
36、个过程w找负费用圈找负费用圈w沿负费用圈增流沿负费用圈增流46找负费用圈的方法找负费用圈的方法步骤步骤1：初始化数组：初始化数组st中的元素全为中的元素全为0；数组；数组wts=0，其它均为无穷大；，其它均为无穷大；队列队列Q为空；为空；N=0。步骤步骤2：节点：节点s入队，令入队，令m=顶点个数顶点个数+1，m也入队；也入队；步骤步骤3：检查队列是否为空，如果为空，则残余网络中没有负费用圈，算：检查队列是否为空，如果为空，则残余网络中没有负费用圈，算法结束；如果不空，则转步骤法结束；如果不空，则转步骤4；步骤步骤4：取出队首元素：取出队首元素v；步骤步骤5：如果：如果v=m，判断，判断N是否
37、大于是否大于m，如果，如果N大于大于m，则残余网络中没有，则残余网络中没有负费用圈，算法结束；否则，负费用圈，算法结束；否则，N+，将，将m入队，转步骤入队，转步骤4；如果；如果vm，转步，转步骤骤6；步骤步骤6：残余网络中如果不存在以：残余网络中如果不存在以v为弧尾且未检查的弧，转步骤为弧尾且未检查的弧，转步骤3；否则；否则对其中一条以对其中一条以v为弧尾且未检查的弧，转步骤为弧尾且未检查的弧，转步骤7；步骤步骤7：取出弧的弧头：取出弧的弧头w；步骤步骤8；计算；计算wtv+cost(v,w)，记其值为，记其值为p;步骤步骤9：如果：如果p大于等于大于等于wtw，转步骤，转步骤6；否则；否则
38、wtw=p，stw=v；步骤步骤10：利用：利用st找出包含节点找出包含节点w的负费用圈，如果找到返回的负费用圈，如果找到返回w，算法结束；，算法结束；反之将反之将w入队；转步骤入队；转步骤6。47沿负费用圈增流的方法沿负费用圈增流的方法如果找到负费用圈，则沿负费用圈增流，设如果找到负费用圈，则沿负费用圈增流，设增量为增量为d。增流方法增流方法沿负费用圈方向的边容量减去沿负费用圈方向的边容量减去d，如果边的容量，如果边的容量等于等于0，则取消该方向的边；逆负费用圈方向的，则取消该方向的边；逆负费用圈方向的边容量加上边容量加上d。48例题：在下图中找负费用圈49步骤1：初始化。初始化数组st中的
39、元素均为0；wt1=0，其它均为；队列为空；N=0；m=6+1=7;步骤2：让节点1和m入队；数组st、wt及队列Q的数据如下图所示。50步骤3：取出队首元素1。检查以1为弧尾的所有弧。对于弧，记w=2。计算p=wt1+cost12=0+1=1。由于pwt2，所以wt2=1，st2=1；然后找以2为始点和终点的圈，结果未找到，将节点2入队。对于弧，记w=3。计算p=wt1+cost13=0+7=7。由于pwt3，所以wt3=7，st3=1；然后找以3为始点和终点的圈，结果未找到，将节点3入队。数组st、wt及队列Q的数据如图所示。51步骤5：取出队首元素，即m=7；N+；m入队；步骤6：取队首
40、元素2。检查以2为弧尾的所有弧。对于弧，记w=1。计算p=wt2+cost21=1+(-1)=0。由于p等于wt1，所以无需执行任何操作；对于弧，记w=4。计算p=wt2+cost24=1+4=5。由于pwt4，所以wt4=5，st4=2；然后找以4为始点和终点的圈，结果未找到，将节点4入队。对于弧，记w=5。计算p=wt2+cost25=1+5=6。由于pwt5，所以wt5=6，st5=2；然后找以5为始点和终点的圈，结果未找到，将节点5入队。数组st、wt及队列Q的数据如图所示。52步骤7：取队首元素3。检查以3为弧尾的所有弧。对于弧，记w=1。计算p=wt3+cost31=7+(-7)=
41、0。由于p等于wt1，所以无需执行任何操作；对于弧，记w=2。计算p=wt3+cost32=7+1=8。由于pwt2，所以无需执行任何操作;对于弧，记w=4。计算p=wt3+cost34=7+3=10。由于pwt4，所以无需执行任何操作；队列Q的数据所示。53步骤7：取出队首元素，即m=7；N+；m入队；步骤8：取队首元素4。检查以4为弧尾的所有弧。对于弧，记w=2。计算p=wt4+cost42=5+(-4)=1。由于p等于wt2，所以无需执行任何操作；对于弧，记w=5。计算p=wt4+cost45=5+(-3)=2。由于pwt5，所以wt5=2，st5=4；然后找以5为始点和终点的圈，结果未
42、找到，将节点5入队。对于弧，记w=6。计算p=wt4+cost46=5+6=11。由于pwt6，所以wt6=11，st6=4；然后找以6为始点和终点的圈，结果未找到，将节点6入队。数组st、wt及队列Q的数据如图7-30所示。54步骤9：取队首元素5。检查以5为弧尾的所有弧。对于弧，记w=3。计算p=wt5+cost53=2+(-6)=-4。由于pwt3，所以wt3=-4，st3=5；然后找以3为始点和终点的圈，结果未找到，将节点3入队。对于弧，记w=4。计算p=wt5+cost54=2+3=5。由于p等于wt4，所以无需执行任何操作；对于弧，记w=6。计算p=wt5+cost56=2+2=4
43、。由于pwt6，所以wt6=4，st6=5；然后找以6为始点和终点的圈，结果未找到，将节点6入队；数组st、wt及队列Q的数据如图7-31所示。55步骤10：取出队首元素，即m=7；N+；m入队；步骤11：取队首元素5。检查以5为弧尾的所有弧。与步骤9类似，数组st、wt及队列Q的数据如图7-32所示。56步骤12：取队首元素6。检查以6为弧尾的所有弧。对于弧，记w=4。计算p=wt6+cost64=4+(-6)=-2。由于pwt4，所以wt4=-2，st4=6；然后找以4为始点和终点的圈，由于st6等于5、st5等于4，即st5等于w，此时找到负费用圈4-5-6-4。数组st、wt及队列Q的数据如图7-33所示。57沿负费用圈增流重复上述过程，直到没有负费用圈为止即为最小费用流58练习：找出下图所示的最小费用流59答案：找到的最小费用流答案：找到的最小费用流
