线性规划与网络流精品文稿.ppt
《线性规划与网络流精品文稿.ppt》由会员分享,可在线阅读,更多相关《线性规划与网络流精品文稿.ppt(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、线性规划与网络流线性规划与网络流1第1页,本讲稿共47页8.1 线性规划问题和单纯形算法线性规划问题和单纯形算法w线性规划问题及其表示线性规划问题及其表示w线性规划问题可表示为如下形式:s.t.2第2页,本讲稿共47页w变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解可行解。w所有可行解构成的集合称为线性规划问题的可行区域可行区域。w使目标函数取得极值的可行解称为最优解最优解。w在最优解处目标函数的值称为最优值最优值。w有些情况下可能不存在最优解。w通常有两种情况:w(1)根本没有可行解,即给定的约束条件之间是相互排斥的,可行区域为空集;w(2)目标函数没有极值,也
2、就是说在n 维空间中的某个方向上,目标函数值可以无限增大,而仍满足约束条件,此时目标函数值无界。3第3页,本讲稿共47页w这个问题的解为(x1,x2,x3,x4)=(0,3.5,4.5,1);最优值为16。4第4页,本讲稿共47页线性规划基本定理线性规划基本定理 w约束条件(8.2)-(8.5)中n个约束以等号满足的可行解称为线性规划问题的基本可行解基本可行解。w若nm,则基本可行解中至少有n-m个分量为0,也就是说,基本可行解中最多有m个分量非零。w线性规划基本定理:线性规划基本定理:如果线性规划问题有最优解,则必有一基本可行最优解。w上述定理的重要意义在于,它把一个最优化问题转化为一个组合
3、问题,即在(8.2)-(8.5)式的m+n个约束条件中,确定最优解应满足其中哪n个约束条件的问题。w由此可知,只要对各种不同的组合进行测试,并比较每种情况下的目标函数值,直到找到最优解。wDantzig于1948年提出了线性规划问题的单纯形算法。w单纯形算法的特点是:w(1)只对约束条件的若干组合进行测试,测试的每一步都使目标函数的值增加;w(2)一般经过不大于m或n次迭代就可求得最优解。5第5页,本讲稿共47页约束标准型线性规划问题的单纯形算法约束标准型线性规划问题的单纯形算法 w当线性规划问题中没有不等式约束(8.2)和(8.4)式,而只有等式约束(8.3)和变量非负约束(8.5)时,称该
4、线性规划问题具有标准形式标准形式。w为便于讨论,不妨先考察一类更特殊的标准形式线性规划问题。这一类线性规划问题中,每一个等式约束中,至少有一个变量的系数为正,且这个变量只在该约束中出现。w在每一约束方程中选择一个这样的变量,并以它作为变量求解该约束方程。这样选出来的变量称为左端变量或基本变基本变量量,其总数为m个。剩下的n-m个变量称为右端变量或非基本变量非基本变量。w这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题约束标准型线性规划问题。w虽然约束标准型线性规划问题非常特殊,但是对于理解线性规划问题的单纯形算法是非常重要的。w稍后将看到,任意一个线性规划问题可以转换为约束标准型线性
5、规划问题。6第6页,本讲稿共47页x2x3x5z0-13-2x173-12x412-240 x610-4387第7页,本讲稿共47页w任何约束标准型线性规划问题,只要将所有非基本变量都置为0,从约束方程式中解出满足约束的基本变量的值,可求得一个基本可行解。w单纯形算法的基本思想就是从一个基本可行解出发,进行一系列的基本可行解的变换。w每次变换将一个非基本变量与一个基本变量互调位置,且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。w基本可行解x=(7,0,0,12,0,10)。w单纯形算法的第单纯形算法的第1步:步:选出使目标函数增加的非基本变量作为入基变量入基变量。w查看单纯
6、形表的第1行(也称之为z行)中标有非基本变量的各列中的值。w选出使目标函数增加的非基本变量作为入基变量。wz行中的正系数非基本变量都满足要求。w在上面单纯形表的z行中只有1列为正,即非基本变量相应的列,其值为3。w选取非基本变量x3作为入基变量。w单纯形算法的第单纯形算法的第2步:步:选取离基变量离基变量。w在单纯形表中考察由第1步选出的入基变量所相应的列。w在一个基本变量变为负值之前,入基变量可以增到多大。8第8页,本讲稿共47页w如果入基变量所在的列与基本变量所在行交叉处的表元素为负数,那么该元素将不受任何限制,相应的基本变量只会越变越大。w如果入基变量所在列的所有元素都是负值,则目标函数
7、无界,已经得到了问题的无界解。w如果选出的列中有一个或多个元素为正数,要弄清是哪个数限制了入基变量值的增加。w受限的增加量可以用入基变量所在列的元素(称为主元素)来除主元素所在行的“常数列”(最左边的列)中元素而得到。所得到数值越小说明受到限制越多。w应该选取受到限制最多的基本变量作为离基变量,才能保证将入基变量与离基变量互调位置后,仍满足约束条件。w上例中,惟一的一个值为正的z行元素是3,它所在列中有2个正元素,即4和3。wmin12/4,10/3=4,应该选取x4为离基变量;w入基变量x3取值为3。w单纯形算法的第单纯形算法的第3步:转轴变换步:转轴变换。w转轴变换的目的是将入基变量与离基
8、变量互调位置。w给入基变量一个增值,使之成为基本变量;w修改离基变量,让入基变量所在列中,离基变量所在行的元素值减为零,而使之成为非基本变量。9第9页,本讲稿共47页w解离基变量所相应的方程,将入基变量x3用离基变量x4表示为w再将其代入其他基本变量和所在的行中消去x3,w代入目标函数得到w形成新单纯形表x2x4x5z91/2-3/4-2x1105/21/22x33-1/21/40 x61-5/2-3/4810第10页,本讲稿共47页w单纯形算法的第单纯形算法的第4步:步:转回并重复第1步,进一步改进目标函数值。w不断重复上述过程,直到z行的所有非基本变量系数都变成负值为止。这表明目标函数不可
9、能再增加了。w在上面的单纯形表中,惟一的值为正的z行元素是非基本变量x2相应的列,其值为1/2。w因此,选取非基本变量x2作为入基变量。w它所在列中有惟一的正元素5/2,即基本变量x1相应行的元素。w因此,选取x1为离基变量。w再经步骤3的转轴变换得到新单纯形表。w新单纯形表z行的所有非基本变量系数都变成负值,求解过程结束。w整个问题的解可以从最后一张单纯形表的常数列中读出。w目标函数的最大值为11;w最优解为:x*=(0,4,5,0,0,11)。x1x4x5z11-1/5-4/5-12/5x245/21/104/5x351/53/102/5x6111-1/21011第11页,本讲稿共47页1
10、2第12页,本讲稿共47页13第13页,本讲稿共47页14第14页,本讲稿共47页15第15页,本讲稿共47页w为了进一步构造标准型约束,还需要引入m个人工变量人工变量,记为zi。w至此,原问题已经变换为等价的约束标准型线性规划问题。w对极小化线性规划问题,只要将目标函数乘以-1即可化为等价的极大化线性规划问题。16第16页,本讲稿共47页一般线性规划问题的一般线性规划问题的2阶段单纯形算法阶段单纯形算法 w引入人工变量后的线性规划问题与原问题并不等价,除非所有zi都是0。w为了解决这个问题,在求解时必须分2个阶段进行。w第一阶段用一个辅助目标函数 替代原来的目标函数。w这个线性规划问题称为原
11、线性规划问题所相应的辅助线性规划问题。w对辅助线性规划问题用单纯形算法求解。w如果原线性规划问题有可行解,则辅助线性规划问题就有最优解,且其最优值为0,即所有zi都为0。w在辅助线性规划问题最后的单纯形表中,所有zi均为非基本变量。w划掉所有zi相应的列,剩下的就是只含xi和yi的约束标准型线性规划问题了。w单纯形算法第一阶段的任务就是构造一个初始基本可行解。w单纯形算法第二阶段的目标是求解由第一阶段导出的问题。w此时要用原来的目标函数进行求解。w如果在辅助线性规划问题最后的单纯形表中,zi不全为0,则原线性规划问题没有可行解,从而原线性规划问题无解。17第17页,本讲稿共47页退化情形的处理
12、退化情形的处理 w用单纯形算法解一般的线性规划问题时,可能会遇到退化的情形,即在迭代计算的某一步中,常数列中的某个元素的值变成0,使得相应的基本变量取值为0。w如果选取退化的基本变量为离基变量,则作转轴变换前后的目标函数值不变。在这种情况下,算法不能保证目标函数值严格递增,因此,可能出现无限循环。w考察下面的由Beale在1955年提出的退化问题的例子。w按照2阶段单纯形算法求解该问题将出现无限循环。18第18页,本讲稿共47页wBland提出避免循环的一个简单易行的方法。wBland提出在单纯形算法迭代中,按照下面的2个简单规则就可以避免循环。w规则1:设 ,取xe为入基变量。w规则2:设
13、w取xk为离基变量。w算法leave(col)已经按照规则2选取离基变量。w选取入基变量的算法enter(objrow)中只要加一个break语句即可。19第19页,本讲稿共47页20第20页,本讲稿共47页21第21页,本讲稿共47页8.2 最大网络流问题最大网络流问题w1 基本概念和术语基本概念和术语w w(1)网络网络wG是一个简单有向图,G=(V,E),V=1,2,n。w在V中指定一个顶点s,称为源源和另一个顶点t,称为汇汇。w有向图G的每一条边(v,w)E,对应有一个值cap(v,w)0,称为边的容量容量。w这样的有向图G称作一个网络网络。w(2)网络流网络流w网络上的流流是定义在网
14、络的边集合E上的一个非负函数flow=flow(v,w),并称flow(v,w)为边(v,w)上的流量流量。22第22页,本讲稿共47页w(3)可行流可行流w满足下述条件的流flow称为可行流可行流:w(3.1)容量约束:容量约束:对每一条边(v,w)E,0flow(v,w)cap(v,w)。w(3.2)平衡约束:平衡约束:w对于中间顶点:流出量=流入量。w即对每个vV(vs,t)有:顶点v的流出量顶点v的流入量=0,即w对于源s:s的流出量s的流入量=源的净输出量f,即w对于汇t:t的流入量t的流出量的=汇的净输入量f,即w式中f 称为这个可行流的流量,即源的净输出量(或汇的净输入量)。w可
15、行流总是存在的。w例如,让所有边的流量flow(v,w)=0,就得到一个其流量f=0的可行流(称为0流)。23第23页,本讲稿共47页w(4)边流边流w对于网络G的一个给定的可行流flow,将网络中满足flow(v,w)=cap(v,w)的边称为饱和边饱和边;flow(v,w)0的边称为非零流边非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时,称为弱流边弱流边。w(5)最大流最大流w最大流问题即求网络G的一个可行流flow,使其流量f达到最大。即flow满足:w0flow(v,w)cap(v,w),(v,w)E;且w(6)流的费用流的费用w在实际应用中,与网络流有关的问题,不仅涉及流
16、量,而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外,还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow,其费用定义为:24第24页,本讲稿共47页w(7)残流网络残流网络w对于给定的一个流网络G及其上的一个流flow,网络G关于流flow的残流网络G*与G有相同的顶点集V,而网络G中的每一条边对应于G*中的1条边或2条边。w设(v,w)是G的一条边。w当flow(v,w)0时,(w,v)是G*中的一条边,该边的容量为cap*(w,v)=flow(v,w);w当flow(v,w)cap(v,w)时,(v,w)是G*中的一条边,该边的容量为w
17、cap*(v,w)=cap(v,w)-flow(v,w)。w按照残流网络的定义,当原网络G中的边(v,w)是一条零流边时,残流网络G*中有唯一的一条边(v,w)与之对应,且该边的容量为cap(v,w)。w当原网络G中的边(v,w)是一条饱和边时,残流网络G*中有唯一的一条边(w,v)与之对应,且该边的容量为cap(v,w)。w当原网络G中的边(v,w)是一条弱流边时,残流网络G*中有2条边(v,w)和(w,v)与之对应,这2条边的容量分别为cap(v,w)-flow(v,w)和flow(v,w)。w残流网络是设计与网络流有关算法的重要工具。25第25页,本讲稿共47页增广路算法增广路算法 w1
18、 算法基本思想算法基本思想w设P是网络G中联结源s和汇t的一条路。定义路的方向是从s到t。w将路P上的边分成2类:w一类边的方向与路的方向一致,称为向前边向前边。向前边的全体记为P+。w另一类边的方向与路的方向相反,称为向后边向后边。向后边的全体记为P-。w设flow是一个可行流,P是从s到t的一条路,若P满足下列条件:w(1)在P的所有向前边(v,w)上,flow(v,w)0,即P-中的每一条边都是非零流边。w则称P为关于可行流flow的一条可增广路。w可增广路是残流网络中一条容量大于0的路。w将具有上述特征的路P称为可增广路是因为可以通过修正路P上所有边流量flow(v,w)将当前可行流改
19、进成一个流值更大的可行流。26第26页,本讲稿共47页w增流的具体做法是:w(1)不属于可增广路P的边(v,w)上的流量保持不变;w(2)可增广路P上的所有边(v,w)上的流量按下述规则变化:w在向前边(v,w)上,flow(v,w)+d;w在向后边(v,w)上,flow(v,w)-d。w按下面的公式修改当前的流。w其中d称为可增广量,可按下述原则确定:d取得尽量大,又要使变化后的流仍为可行流。w按照这个原则,d既不能超过每条向前边(v,w)的cap(v,w)-flow(v,w),也不能超过每条向后边(v,w)的flow(v,w)。w因此d应该等于向前边上的cap(v,w)-flow(v,w)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 网络 精品 文稿
限制150内