第7章线性规划问题与网络流精选PPT.ppt
第7章线性规划问题与网络流1第1页，本讲稿共52页学习要点学习要点理解线性规划算法模型掌握解线性规划问题的单纯形算法 理解网络与网络流的基本概念掌握网络最大流的增广路算法掌握网络最小费用流的消圈算法第8章 线性规划与网络流2第2页，本讲稿共52页线性规划问题和单纯形算法线性规划问题和单纯形算法线性规划问题及其表示线性规划问题及其表示一般线性规划问题可表示为如下形式：s.t.3第3页，本讲稿共52页变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解可行解。所有可行解构成的集合称为线性规划问题的可行区域可行区域。使目标函数取得极值的可行解称为最优解最优解。在最优解处目标函数的值称为最优值最优值。有些情况下可能不存在最优解。根本没有可行解，可行区域为空集；目标函数没有极值，目标函数值无界。4第4页，本讲稿共52页标准线性规划问题描述5第5页，本讲稿共52页将一般线性规划问题转化为标准型规划问题的方法 一般线性规划形式中目标函数如果是求极小值的，即 那么，令 ，则，。右端常数项如果小于零，则不等式两边同乘以（-1），将其变成大于零；同时改变不等号的方向，保证恒等变形。如2x1+x26，2x1x26。约束条件为大于等于约束时，则在不等式左边减去一个新的非负变量将不等式约束改为等式约束。如3x12x212，3x12x2x312，x30；约束条件为小于等于约束时，则在左边加上一个新的非负变量将不等式约束改为等式约束。如x12x28，x12x2x38，x30；无约束的决策变量x，即可正可负的变量，则引入两个新的非负变量x和x”，令x=-x-x”，其中x0，x”0，将x代入线性规划模型。决策变量x小于等于0时，令xx，显然x0，将x代入线性规划模型。在(3)(6)中引入的新的非负变量称为松弛变量。6第6页，本讲稿共52页标准型线性规划问题的单纯形算法 单纯形法是指1947年数学家George Dantzing(乔治丹捷格)发明的一种求解线性规划模型的一般性方法。约束标准型线性规划问题为了便于讨论，先考察一类特殊的标准形式的线性规划问题。在这类问题中，每个等式约束条件中均至少含有一个正系数的变量，且这个变量只出现在一个约束条件中。将每个约束条件中这样的变量作为非0变量来求解该约束方程。这类特殊的标准形式线性规划问题称为约束标准型线性规划问题。7第7页，本讲稿共52页基本概念：基本变量：每个约束条件中的系数为正且只出现在一个约束条件中的变量。非基本变量：除基本变量外的变量全部为非基本变量。基本可行解：满足标准形式约束条件的可行解称为基本可行解。由此可知，如果令n-m个非基本变量等于0，那么根据约束条件求出m个基本变量的值，它们组成的一组可行解为一个基本可行解。8第8页，本讲稿共52页线性规划基本定理定理定理1（最优解判别定理）若目标函数中关于非基本变量的所有系数（以下称检验数）小于等于0，则当前基本可行解就是最优解。定理定理2（无穷多最优解判别定理）若目标函数中关于非基本变量的所有检验数小于等于0，同时存在某个非基本变量的检验数等于0，则线性规划问题有无穷多个最优解。定理定理3（无界解定理）如果某个检验数cj大于0，而xj对应的列向量中所有基本变量的系数a1j,a2j,amj都小于等于0，则该线性规划问题有无界解。9第9页，本讲稿共52页约束标准型线性规划问题的单纯形算法步骤1：找出基本变量和非基本变量，将目标函数由非基本变量表示，建立初始单纯形表如表7-1所示。表7-1 初始单纯形表110第10页，本讲稿共52页步骤2；判别、检查目标函数的所有系数，即检验数cj(j=1,2,n)。（1）如果所有的cj0，则已获得最优解，算法结束。（2）若在检验数cj中，有些为正数，但其中某一正的检验数所对应的列向量的各分量均小于等于0，则线性规划问题无界，算法结束。（3）若在检验数cj中，有些为正数且它们所对应的列向量中有正的分量，则转步骤3。（3）若在检验数cj中，有些为正数且它们所对应的列向量中有正的分量，则转步骤3。步骤3：选入基变量。在所有cj0的检验数中选取值最大的一个，记为ce，其对应的非基变量为xe，对应的列向量为a1e,a2e,ameT，称为入基列。11第11页，本讲稿共52页步骤4：选离基变量。选取“常数列元素/入基列元素”正比值的最小者所对应的基本变量为离基变量，即 ，选取基本变量xk为离基变量。步骤5：换基变换（转轴变换）。在单纯形表上将入基变量和离基变量互换位置，并按照式如下公式进行各元素的变换后得到一张新的单纯形表。转步骤2。12第12页，本讲稿共52页对应入基列位置元素=-原入基列元素/交叉位置元素（不包括交叉位置）。对应离基行位置元素=原离基行元素/交叉位置元素（不包括交叉位置）。交叉位置元素=原交叉位置元素的倒数。目标函数的值=原目标函数的值+同行画线位置元素同列画线位置元素/交叉位置的元素。其它位置的元素=原对应位置的元素-同行画线位置元素同列画线位置元素/交叉位置的元素13第13页，本讲稿共52页例题1解：将线性规划问题转化为约束标准型如下：令14第14页，本讲稿共52页由约束标准形式可知：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=915第15页，本讲稿共52页由表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。练习：16第16页，本讲稿共52页两阶段单纯形算法一般线性规划问题转化为标准形式的线性规划问题后，每个约束条件中不一定都含有基本变量。在这种情况下，可在每个约束条件表达式的左端添加一个非负变量zi(i=1,2,m)，将其转化为约束标准型的线性规划问题。添加的非负变量zi称为人工变量。形式如下：17第17页，本讲稿共52页第一阶段：用辅助目标函数代替原来的目标函数。辅助目标函数：。选择人工变量作为基本变量，其它变量作为非基本变量，构造初始单纯形表。然后，运行该算法，当所有人工变量均变成非基本变量时，辅助目标函数达到最大值，第一阶段算法结束；如果所有人工变量无法全部变成非基本变量，则原线性规划问题无解。第二阶段：将第一阶段得到的最后一张单纯形表中的所有人工变量所在的列全部划掉，剩下的就只含有xi的约束标准型线性规划问题，此时的目标函数由辅助目标函数改为原来的目标函数，用剩下的单纯形表作为第二阶段的初始单纯形表，再次运行约束标准型单纯形算法，即得线性规划问题的解。18第18页，本讲稿共52页8.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)上的流量流量。19第19页，本讲稿共52页（3）可行流可行流满足下述条件的流flow称为可行流可行流：(3.1)容量约束：容量约束：对每一条边(v,w)E，0flow(v,w)cap(v,w)。(3.2)平衡约束：平衡约束：对于中间顶点：流出量=流入量。即对每个vV(vs,t)有：顶点v的流出量顶点v的流入量=0，即对于源s：s的流出量s的流入量=源的净输出量f，即对于汇t：t的流入量t的流出量的=汇的净输入量f，即式中f 称为这个可行流的流量，即源的净输出量(或汇的净输入量)。20第20页，本讲稿共52页（4）边流边流对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边饱和边；flow(v,w)0的边称为非零流边非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边弱流边。（5）最大流最大流最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：0flow(v,w)cap(v,w)，(v,w)E；且21第21页，本讲稿共52页（6）流的费用流的费用在实际应用中，与网络流有关的问题，不仅涉及流量，而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：22第22页，本讲稿共52页（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)。23第23页，本讲稿共52页（8）向前边和向后边）向前边和向后边设P是网络G中联结源s和汇t的一条路。定义路的方向是从s到t。将路P上的边分成2类：一类边的方向与路的方向一致，称为向前边向前边。向前边的全体记为P+。另一类边的方向与路的方向相反，称为向后边向后边。向后边的全体记为P-。24第24页，本讲稿共52页（9）增广路设flow是一个可行流，P是从s到t的一条路，若P满足下列条件：在P的所有向前边(v,w)上，flow(v,w)0，即P-中的每一条边都是非零流。则称P为关于可行流flow的一条可增广路。25第25页，本讲稿共52页增广路定理：增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。增广路算法增广路算法（1）初始化为0流（2）找关于当前可行流的可增广路，若找到，转3；否则，当前可行流为网络的最大流。（3）沿增广路增流。因此，增广路算法主要包括两个过程：找增广路和沿增广路增流。26第26页，本讲稿共52页可采用标号法找可增广路。对网络中的每个节点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)-flow(v，w)；对于边，flow(w，v)0，则w的标号为(-v，maxl(w)，maxl(w)=minmaxl(v)，flow(w，v)。步骤3：不断重复步骤2，直到已经不存在已标号未检查的点或标到了汇点结束。如果不存在已标号未检查的点，则说明不存在关于当前可行流的可增广路，当前流就是最大流。如果标到了汇点，则找到了一条可增广路，需要沿着该可增广路进行增流，转过程（2）。沿增广路增流具体方法 27第27页，本讲稿共52页例题用增广路算法找出如下图所示的网络及可行流的最大流，其中，顶点1为源点，顶点6为汇点，边上的权为（cap，flow）。28第28页，本讲稿共52页标号法找增广路 沿着增广路增流 29第29页，本讲稿共52页标号法找增广路 沿着增广路增流 30第30页，本讲稿共52页标号法找增广路 沿着增广路增流 31第31页，本讲稿共52页标号法找增广路，当前流为最大流 32第32页，本讲稿共52页最大网络流的变换与应用 多源多汇的网络流问题多源多汇的最大流问题可以转化为单源单汇的最大流问题。具体做法是：在原网络的基础上，增加一个虚源s和一个虚汇t。从s向原网络中的源点分别引一条有向边，每一条有向边的流量等于与其相连的源点（非虚源）的流出量，容量为无穷大；从原网络中的汇点分别向虚汇引一条有向边，每一条有向边的流量等于与其相连的汇点的流入量，容量为无穷大。这样，新网络的最大流就对应于原网络的最大流。33第33页，本讲稿共52页示例：34第34页，本讲稿共52页网络的顶点容量约束流经某顶点的流量不能超过该顶点给定的约束值 变换方法：只要将有顶点容量约束的顶点x用一条边来替换，原来顶点x的入边仍为顶点x的入边，原来顶点x的出边改为顶点y的出边。连接顶点x和顶点y只有一条边，其边容量为原顶点x的顶点容量。示例 35第35页，本讲稿共52页8.3 最小费用流问题最小费用流问题1 网络流的费用网络流的费用网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：2涉及流的费用的残余网络涉及流的费用的残余网络对于G中的任一条边：对应于G*中的，则设置G*中的单位流量费用为cost(x,y)；对应于G*中的，则设置G*中的单位流量费用为-cost(x,y)。36第36页，本讲稿共52页3最小费用最大流问题最小费用最大流问题给定网络G，要求G的一个最大用流flow，使流的总费用最小。4负费用圈负费用圈对于一个给定的网络G、其上的可行流flow及流的费用，残余网络中的负费用圈是指所有边的单位流量费用之和为负的圈 最小费用最大流问题的最优性定理最小费用最大流问题的最优性定理网络G的最大流flow是G的一个最小费用最大流的充分必要条件是flow所对应的残余网络中没有负费用圈 37第37页，本讲稿共52页最小费用流的消圈算法最小费用流的消圈算法 步骤步骤0：用最大流算法构造最大流flow。步骤步骤1：如果残量网络中不存在负费用圈，则计算结束，已经找到最小费用流；否则转步骤2。步骤步骤2：沿找到的负费用圈增流，并转步骤1。算法主要包括两个过程算法主要包括两个过程找负费用圈找负费用圈沿负费用圈增流沿负费用圈增流38第38页，本讲稿共52页找负费用圈的方法找负费用圈的方法步骤步骤1：初始化数组：初始化数组st中的元素全为中的元素全为0；数组；数组wts=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；计算；计算wtv+cost(v,w)，记其值为，记其值为p;步骤步骤9：如果：如果p大于等于大于等于wtw，转步骤，转步骤6；否则；否则wtw=p，stw=v；步骤步骤10：利用：利用st找出包含节点找出包含节点w的负费用圈，如果找到返回的负费用圈，如果找到返回w，算法结，算法结束；反之将束；反之将w入队；转步骤入队；转步骤6。39第39页，本讲稿共52页沿负费用圈增流的方法如果找到负费用圈，则沿负费用圈增流，设增量为d。增流方法沿负费用圈方向的边容量减去d，如果边的容量等于0，则取消该方向的边；逆负费用圈方向的边容量加上d。40第40页，本讲稿共52页例题：在下图中找负费用圈41第41页，本讲稿共52页步骤1：初始化。初始化数组st中的元素均为0；wt1=0，其它均为；队列为空；N=0；m=6+1=7;步骤2：让节点1和m入队；数组st、wt及队列Q的数据如下图所示。42第42页，本讲稿共52页步骤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的数据如图所示。43第43页，本讲稿共52页步骤5：取出队首元素，即m=7；N+；m入队；步骤6：取队首元素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的数据如图所示。44第44页，本讲稿共52页步骤7：取队首元素3。检查以3为弧尾的所有弧。对于弧，记w=1。计算p=wt3+cost31=7+(-7)=0。由于p等于wt1，所以无需执行任何操作；对于弧，记w=2。计算p=wt3+cost32=7+1=8。由于pwt2，所以无需执行任何操作;对于弧，记w=4。计算p=wt3+cost34=7+3=10。由于pwt4，所以无需执行任何操作；队列Q的数据所示。45第45页，本讲稿共52页步骤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为始点和终点的圈，结果未找到，将节点5入队。对于弧，记w=6。计算p=wt4+cost46=5+6=11。由于pwt6，所以wt6=11，st6=4；然后找以6为始点和终点的圈，结果未找到，将节点6入队。数组st、wt及队列Q的数据如图7-30所示。46第46页，本讲稿共52页步骤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。由于pwt6，所以wt6=4，st6=5；然后找以6为始点和终点的圈，结果未找到，将节点6入队；数组st、wt及队列Q的数据如图7-31所示。47第47页，本讲稿共52页步骤10：取出队首元素，即m=7；N+；m入队；步骤11：取队首元素5。检查以5为弧尾的所有弧。与步骤9类似，数组st、wt及队列Q的数据如图7-32所示。48第48页，本讲稿共52页步骤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所示。49第49页，本讲稿共52页沿负费用圈增流重复上述过程，直到没有负费用圈为止即为最小费用流50第50页，本讲稿共52页练习：找出下图所示的最小费用流51第51页，本讲稿共52页答案：找到的最小费用流答案：找到的最小费用流52第52页，本讲稿共52页
