第7章线性问题与网络流

1算法设计与分析授课教师：王秋芬办公地点：7307Email:2学习要点理解线性规划算法模型掌握解线性规划问题的单纯形算法理解网络与网络流的基本概念掌握网络最大流的增广路算法掌握网络最小费用流的消圈算法第7章线性规划与网络流3线性规划问题和单纯形算法线性规划问题及其表示一般线性规划问题可表示为如下形式：s.t.4变量满足约束条件(7.2)-(7.5)式的一组值称为线性规划问题的一个可行解。所有可行解构成的集合称为线性规划问题的可行区域。使目标函数取得极值的可行解称为最优解。在最优解处目标函数的值称为最优值。有些情况下可能不存在最优解。根本没有可行解，可行区域为空集；目标函数没有极值，目标函数值无界。5标准线性规划问题描述6将一般线性规划问题转化为标准型规划问题的方法

(1)一般线性规划形式中目标函数如果是求极小值的，即那么，令，则，(2)右端常数项如果小于零，则不等式两边同乘以（-1），将其变成大于零；同时改变不等号的方向，保证恒等变形。如2x1+x2≥－6，－2x1－x2≤6。(3)约束条件为大于等于约束时，则在不等式左边减去一个新的非负变量将不等式约束改为等式约束。如3x1－2x2≥12，3x1－2x2－x3＝12，x3≥0；(4)约束条件为小于等于约束时，则在左边加上一个新的非负变量将不等式约束改为等式约束。如x1－2x2≤8，x1－2x2＋x3＝8，x3≥0；(5)无约束的决策变量x，即可正可负的变量，则引入两个新的非负变量x’和x”，令x=-x’-x”，其中x’≥0，x”≥0，将x代入线性规划模型。(6)决策变量x小于等于0时，令x’＝－x，显然x’≥0，将x'代入线性规划模型。在(3)~(6)中引入的新的非负变量称为松弛变量。7标准型线性规划问题的单纯形算法单纯形法是指1947年数学家GeorgeDantzing(乔治·丹捷格)发明的一种求解线性规划模型的一般性方法。约束标准型线性规划问题为了便于讨论，先考察一类特殊的标准形式的线性规划问题。在这类问题中，每个等式约束条件中均至少含有一个正系数的变量，且这个变量只出现在一个约束条件中。将每个约束条件中这样的变量作为非0变量来求解该约束方程。这类特殊的标准形式线性规划问题称为约束标准型线性规划问题。8基本概念：基本变量（m个）：每个约束条件中的系数为正且只出现在一个约束条件中的变量。非基本变量(n-m)：除基本变量外的变量全部为非基本变量。基本可行解：满足标准形式约束条件的可行解称为基本可行解。由此可知，如果令n-m个非基本变量等于0，那么根据约束条件求出m个基本变量的值，它们组成的一组可行解为一个基本可行解。9线性规划基本定理定理1（最优解判别定理）若目标函数中关于非基本变量的所有系数（以下称检验数）小于等于0，则当前基本可行解就是最优解。定理2（无穷多最优解判别定理）若目标函数中关于非基本变量的所有检验数小于等于0，同时存在某个非基本变量的检验数等于0，则线性规划问题有无穷多个最优解。定理3（无界解定理）如果某个检验数cj大于0，而xj对应的列向量中所有基本变量的系数a1j,a2j,…,amj都小于等于0，则该线性规划问题有无界解。10约束标准型线性规划问题的单纯形算法步骤1：找出基本变量和非基本变量，将目标函数由非基本变量表示，建立初始单纯形表如表7-1所示。表7-1初始单纯形表111步骤2；判别、检查目标函数的所有系数，即检验数cj(j=1,2,…,n)。（1）如果所有的cj≤0，则已获得最优解，算法结束。（2）若在检验数cj中，有些为正数，但其中某一正的检验数所对应的列向量的各分量均小于等于0，则线性规划问题无界，算法结束。（3）若在检验数cj中，有些为正数且它们所对应的列向量中有正的分量，则转步骤3。步骤3：选入基变量。在所有cj＞0的检验数中选取值最大的一个，记为ce，其对应的非基变量为xe，对应的列向量为[a1e,a2e,…,ame]T，称为入基列。12步骤4：选离基变量。选取“常数列元素/入基列元素”正比值的最小者所对应的基本变量为离基变量，即，选取基本变量xk为离基变量。步骤5：换基变换（转轴变换）。在单纯形表上将入基变量和离基变量互换位置，并按照式如下公式进行各元素的变换后得到一张新的单纯形表。转步骤2。13对应入基列位置元素=-原入基列元素/交叉位置元素（不包括交叉位置）。对应离基行位置元素=原离基行元素/交叉位置元素（不包括交叉位置）。交叉位置元素=原交叉位置元素的倒数。目标函数的值=原目标函数的值+同行画线位置元素×同列画线位置元素/交叉位置的元素。其它位置的元素=原对应位置的元素-同行画线位置元素×同列画线位置元素/交叉位置的元素14例题1解：将线性规划问题转化为约束标准型如下：

令15由约束标准形式可知：x1,x5,x6是基本变量，x2,x3,x4是非基本变量，建立初始单纯形表如表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’=916由表7-3可知：x2为入基变量，x1为离基变量，根据迭代公式迭代得如表7-4所示的单纯形表4。由此可得，基本可行解为X(2)=（0,4,5,0,0,11）,z’=11。同时，由表7-4可知，所有检验数均小于等于0，故X(2)=（0,4,5,0,0,11）为该线性规划问题的唯一最优解，其最优值z=-11。练习：17两阶段单纯形算法一般线性规划问题转化为标准形式的线性规划问题后，每个约束条件中不一定都含有基本变量。在这种情况下，可在每个约束条件表达式的左端添加一个非负变量zi(i=1,2,…,m)，将其转化为约束标准型的线性规划问题。添加的非负变量zi称为人工变量。形式如下：18第一阶段：用辅助目标函数代替原来的目标函数。辅助目标函数：。选择人工变量作为基本变量，其它变量作为非基本变量，构造初始单纯形表。然后，运行该算法，当所有人工变量均变成非基本变量时，辅助目标函数达到最大值，第一阶段算法结束；如果所有人工变量无法全部变成非基本变量，则原线性规划问题无解。第二阶段：将第一阶段得到的最后一张单纯形表中的所有人工变量所在的列全部划掉，剩下的就只含有xi的约束标准型线性规划问题，此时的目标函数由辅助目标函数改为原来的目标函数，用剩下的单纯形表作为第二阶段的初始单纯形表，再次运行约束标准型单纯形算法，即得线性规划问题的解。197.2最大网络流问题1基本概念和术语（1）网络G是一个简单有向图，G=(V,E)，V={1，2，…，n}。在V中指定一个顶点s，称为源和另一个顶点t，称为汇。有向图G的每一条边(v,w)∈E，对应有一个值cap(v,w)≥0，称为边的容量。这样的有向图G称作一个网络。（2）网络流网络上的流是定义在网络的边集合E上的一个非负函数flow={flow(v,w)}，并称flow(v,w)为边(v,w)上的流量。20（3）可行流满足下述条件的流flow称为可行流：容量约束：对每一条边(v,w)∈E，0≤flow(v,w)≤cap(v,w)。平衡约束：对于中间顶点：流出量=流入量。即对每个v∈V(v≠s,t)有：顶点v的流出量－顶点v的流入量=0，即对于源s：s的流出量－s的流入量=源的净输出量f，即对于汇t：t的流入量－t的流出量的=汇的净输入量f，即式中f称为这个可行流的流量，即源的净输出量(或汇的净输入量)。21（4）边流对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边；flow(v,w)<cap(v,w)的边称为非饱和边；flow(v,w)=0的边称为零流边；flow(v,w)>0的边称为非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边。（5）最大流最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：0≤flow(v,w)≤cap(v,w)，(v,w)∈E；且22（6）流的费用网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：23（7）残余网络对于给定的一个流网络G及其上的一个流flow，网络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)。24（8）向前边和向后边设P是网络G中连结源s和汇t的一条路。定义路的方向是从s到t。将路P上的边分成2类：一类边的方向与路的方向一致，称为向前边。向前边的全体记为P+。另一类边的方向与路的方向相反，称为向后边。向后边的全体记为P-。25（9）增广路设flow是一个可行流，P是从s到t的一条路，若P满足下列条件：在P的所有向前边(v,w)上，flow(v,w)<cap(v,w)，即P+中的每一条边都是非饱和边；在P的所有向后边(v,w)上，flow(v,w)>0，即P-中的每一条边都是非零流。则称P为关于可行流flow的一条可增广路。26增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。增广路算法（1）初始化为0流（2）找关于当前可行流的可增广路，若找到，转（3）；否则，当前可行流为网络的最大流。（3）沿增广路增流。因此，增广路算法主要包括两个过程：找增广路和沿增广路增流。27可采用标号法找可增广路。对网络中的每个节点j，其标号包括两部分信息（pred(j)，maxl(j)），其中pred(j)表示节点j在可能的增广路中的前一个节点，maxl(j)表示沿该可能的增广路到节点j为止可以增加的最大流量。具体步骤为：步骤1：源点s的标号为（0，+∞）。步骤2：从已标号而未检查的点v出发，对于边<v，w>，如果flow(v，w)<cap(v，w)，则w的标号为(v，maxl(w))，maxl(w)=min{maxl(v),cap(v，w)-flow(v，w)}；对于边<w，v>，flow(w，v)>0，则w的标号为(-v，maxl(w))，maxl(w)=min{maxl(v)，flow(w，v)}。步骤3：不断重复步骤2，直到已经不存在已标号未检查的点或标到了汇点结束。如果不存在已标号未检查的点，则说明不存在关于当前可行流的可增广路，当前流就是最大流。如果标到了汇点，则找到了一条可增广路，需要沿着该可增广路进行增流，转过程（2）。沿增广路增流具体方法

28例题用增广路算法找出如下图所示的网络及可行流的最大流，其中，顶点1为源点，顶点6为汇点，边上的权为（cap，flow）。29标号法找增广路

沿着增广路增流

30标号法找增广路

沿着增广路增流

31标号法找增广路

沿着增广路增流

32标号法找增广路，当前流为最大流

33最大网络流的变换与应用1.多源多汇的网络流问题多源多汇的最大流问题可以转化为单源单汇的最大流问题。方法：在原网络的基础上，增加一个虚源s‘和一个虚汇t’。从s‘向原网络中的源点分别引一条有向边，每一条有向边的流量等于与其相连的源点（非虚源）的流出量，容量为无穷大；从原网络中的汇点分别向虚汇引一条有向边，每一条有向边的流量等于与其相连的汇点的流入量，容量为无穷大。34示例：352.网络的顶点容量约束流经某顶点的流量不能超过该顶点给定的约束值变换方法：只要将有顶点容量约束的顶点x用一条边<x,y>来替换原来顶点x的入边仍为顶点x的入边，原来顶点x的出边改为顶点y的出边。连接顶点x和顶点y只有一条边<x，y>，其边容量为原顶点x的顶点容量。36最大网络流的变换与应用3.二分图的最大匹配问题二分图的概念设G＝(V,E)是一个无向图。如果顶点集合V可分割为两个互不相交的子集X和Y，并且图中每条边(v,w)所关联的两个顶点v和w分属于这两个不同的顶点集，则称图G为一个二分图。二分图的匹配设G＝(V,E)是一个二分图。如果ME，且M中任何两条边都不与同一个顶点相关联，则称M是G的一个匹配。二分图的最大匹配。37最大网络流的变换与应用将二分图的最大匹配问题转换为网络的最大流问题（1）增加一个源s’利—个汇t’。（2）从s’向X的每一个顶点都增加一条有向边；从Y的每一个顶点都增加一条到t’的有向边。（3）原图G中的每—条都改为相应的由X指向Y的有向边；（4）置所有边的容量为1。38最大网络流的变换与应用4.带下界约束的最大流在给定网络中，对于边(x,y)，不仅仅有边流量的上界约束，即容量约束cap(x,y)，还有边流量的下界约束caplow(x.y)。在这种情况下，对可行流flow的容量约束相应地改变为:两个阶段求解第1阶段先找满足约束条件的可行流第2阶段将找到的可行流扩展成最大流。

39最大网络流的变换与应用第1阶段先找满足约束条件的可行流一个等价的循环可行流问题变换方法在原网络中增加一条容量充分大的边从汇点指向源点，这条边将从源点流到汇点的流量再送回到源点构成一个循环流。原网络有可行流当且仅当新网络有循环可行流。40最大网络流的变换与应用设flow是新网络的一个循环可行流，则(1)对于有:顶点x的流出量-顶点x的流入量=0

(2)对于，有将其转化为一般网络的最大流问题。转化方法对且边(x,y)既有边容量上界约束，也有边容量下界约束，在循环网络中添加相应的源点s和汇点t，添加两条有向边(x,t)、(s,y)，边上的容量均为caplow(x,y)。41将其转化为单源单汇的最大流问题4243447.3最小费用流问题1网络流的费用网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：2涉及流的费用的残余网络对于G中的任一条边<x，y>：对应于G*中的<x，y>，则设置G*中<x，y>的单位流量费用为cost(x,y)；对应于G*中的<y，x>，则设置G*中<y，x>的单位流量费用为-cost(x,y)。453最小费用最大流问题给定网络G，要求G的一个最大流flow，使流的总费用最小。4负费用圈对于一个给定的网络G、其上的可行流flow及流的费用，残余网络中的负费用圈是指所有边的单位流量费用之和为负的圈最小费用最大流问题的最优性定理网络G的最大流flow是G的一个最小费用最大流的充分必要条件是flow所对应的残余网络中没有负费用圈46最小费用流的消圈算法步骤0：用最大流算法构造最大流flow。步骤1：如果残余网络中不存在负费用圈，则计算结束，已经找到最小费用流；否则转步骤2。步骤2：沿找到的负费用圈增流，并转步骤1。算法主要包括两个过程找负费用圈沿负费用圈增流47找负费用圈的方法步骤1：初始化数组st中的元素全为0；数组wt[s]=0，其它均为无穷大；队列Q为空；N=0。步骤2：节点s入队，令m=顶点个数+1，m也入队；步骤3：检查队列是否为空，如果为空，则残余网络中没有负费用圈，算法结束；如果不空，则转步骤4；步骤4：取出队首元素v；步骤5：如果v=m，判断N是否大于m，如果N大于m，则残余网络中没有负费用圈，算法结束；否则，N++，将m入队，转步骤4；如果vm，转步骤6；步骤6：残余网络中如果不存在以v为弧尾且未检查的弧，转步骤3；否则对其中一条以v为弧尾且未检查的弧，转步骤7；步骤7：取出弧的弧头w；步骤8；计算wt[v]+cost(v,w)，记其值为p;步骤9：如果p大于等于wt[w]，转步骤6；否则wt[w]=p，st[w]=v；步骤10：利用st找出包含节点w的负费用圈，如果找到返回w，算法结束；反之将w入队；转步骤6。48沿负费用圈增流的方法如果找到负费用圈，则沿负费用圈增流，设增量为d。增流方法沿负费用圈方向的边容量减去d，如果边的容量等于0，则取消该方向的边；逆负费用圈方向的边容量加上d。49例题：在下图中找负费用圈50步骤1：初始化。初始化数组st中的元素均为0；wt[1]=0，其它均为；队列为空；N=0；m=6+1=7;步骤2：让节点1和m入队；数组st、wt及队列Q的数据如下图所示。51步骤3：取出队首元素1。检查以1为弧尾的所有弧。对于弧<1，2>，记w=2。计算p=wt[1]+cost[1][2]=0+1=1。由于p<wt[2]，所以wt[2]=1，st[2]=1；然后找以2为始点和终点的圈，结果未找到，将节点2入队。对于弧<1，3>，记w=3。计算p=wt[1]+cost[1][3]=0+7=7。由于p<wt[3]，所以wt[3]=7，st[3]=1；然后找以3为始点和终点的圈，结果未找到，将节点3入队。数组st、wt及队列Q的数据如图所示。52步骤5：取出队首元素，即m=7；N++；m入队；步骤6：取队首元素2。检查以2为弧尾的所有弧。对于弧<2，1>，记w=1。计算p=wt[2]+cost[2][1]=1+(-1)=0。由于p等于wt[1]，所以无需执行任何操作；对于弧<2，4>，记w=4。计算p=wt[2]+cost[2][4]=1+4=5。由于p<wt[4]，所以wt[4]=5，st[4]=2；然后找以4为始点和终点的圈，结果未找到，将节点4入队。对于弧<2，5>，记w=5。计算p=wt[2]+cost[2][5]=1+5=6。由于p<wt[5]，所以wt[5]=6，st[5]=2；然后找以5为始点和终点的圈，结果未找到，将节点5入队。数组st、wt及队列Q的数据如图所示。53步骤7：取队首元素3。检查以3为弧尾的所有弧。对于弧<3，1>，记w=1。计算p=wt[3]+cost[3][1]=7+(-7)=0。由于p等于wt[1]，所以无需执行任何操作；对于弧<3，2>，记w=2。计算p=wt[3]+cost[3][2]=7+1=8。由于p>wt[2]，所以无需执行任何操作;对于弧<3，4>，记w=4。计算p=wt[3]+cost[3][4]=7+3=10。由于p>wt[4]，所以无需执行任何操作；队列Q的数据所示。54步骤7：取出队首元素，即m=7；N++；m入队；步骤8：取队首元素4。检查以4为弧尾的所有弧。对于弧<4，2>，记w=2。计算p=wt[4]+cost[4][2]=5+(-4)=1。由于p等于wt[2]，所以无需执行任