最优化方法线性规划.ppt

《最优化方法线性规划.ppt》由会员分享，可在线阅读，更多相关《最优化方法线性规划.ppt（50页珍藏版）》请在三一办公上搜索。

1、线性规划,数学教研室石鸿雁,引言,线性规划是数学规划的一个重要分支，历史比较悠久，理论比较成熟，方法较为完善。线性规划的思想最早可以追溯到1939年，当时的苏联数学家、经济学家（康特罗维奇）在生产组织与计划中的数学方法一书中提出了类似线性规划的模型，以解决下料问题和运输问题，并给出了“解决乘数法”的求解方法。然而，他们的长期工作未被人们知道。由于战争的需要，美国的经济学家T.C.Koopmans（库普曼斯）重新独立的研究运输问题，并很快看到了线性规划在经济学中应用的意义。在这之后，线性规划也被广泛地应用于军事、经济等方面。由于他们在这方面的突出贡献，康特罗维奇和库普曼斯联合得到1975年诺贝尔

2、经济学奖。,引言,对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他在1947年提出了求解线性规划的单纯形法（Simple Method），并同时给出了许多很有价值的理论，为线性规划奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法，1954年Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。在1976年，R.G.Bland 提出避免出现循环的方法后，使线性规划的理论更加完善。但在1972年，V.Klee和G.Minmty构造了一个例子，发现单纯形法的迭代次数是指数次运算，不是好方法并不是多项式算法（多项式算法被认为是好算法），这对单纯形法

3、提出了挑战。,引言,1979年，前苏联青年数学家（哈奇扬）提出了一种新算法椭圆算法，是一个多项式算法，这一结果在全世界引起了极大轰动，被认为是线性规划理论上的历史突破。然而在实际计算中，椭球算法的计算量与单纯形算法差不多，因此，椭球算法并不实用。1984年，在美国的贝尔实验室工作的印度数学家N.Karmarkar(卡玛卡尔)又提出了一个多项式算法Karmarkar 算法，Karmarkar算法本质上属于内点法，这种算法不仅在理论上优于单纯形算法，而且也显示出对求解大规模线性规划问题的巨大潜力。此外，1980年前后，形成求解线性规划的有效集法（active set method），在理论上有效集

4、法与单纯形法是等价的，但解决问题的侧重点不同，因此各有优缺点，起着相互补充的作用。,引言,由于很多非常重要的实际问题都是线性的，即使不是至少能够用线性函数很好地近似，所以线性规划的研究是很有价值的。另一方面，线性规划方面的工作与非线性规划领域相比更为成熟。目前，线性规划方法的发展已被用来求解非线性模型，所以掌握线性规划的理论和解法是本课程的重要目标之一。,线性规划（LP）,A1,A2,B1,B2,B3,工地,运价（元/万块）,砖厂,50 60 70,60 110 160,1947年 美国数学家 Dantzig 单纯形法 理论基础,1979年 苏联数学家 哈奇安 椭球法 理论上的突破,1984年

5、 美国数学家 Karmarkar Karmarkar算法 大规模,1.问题与模型,1.1.数学模型,例1.设有A1，A2两个砖厂，产量分别为23万块和27万块砖，供应三个工地B1，B2，B3，其需求量分别为17万块、18万块和15万块，而自产地到各工地的运价见表，问应如何调运，才能使总运费最小？,圆桌 0.18 0.08 6,衣柜 0.09 0.28 10,产品 利润,木 料,第一种 第二种,解 设xij 表示 Ai运往Bj的运量（万块）,minS=50 x11+60 x12+70 x13+60 x21+110 x22+160 x23,S.t.x11+x12+x13=23,x21+x22+x2

6、3=27,x11+x21=17,x12+x22=18,x13+x23=15,xij0,i=1,2、j=1,2,3,例2.某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3,第二种有56m3，生产圆桌和衣柜所需木料如下表。每生产一个桌子可获利润6元，生产衣柜可获利润10元。木料厂在现有木料的条件下，圆桌和衣柜各生产多少，才能使利润最大？,解设生产圆桌x1个，衣柜x2个,max S=6x1+10 x2,s.t.0.18x1+0.09x272,0.08x1+0.28x256,x1,x20,线性规划问题：约束条件及目标函数均为未知量的线性函数，求目标函数的最大或最小值问题。,.2图解法（只

7、限于两个变量）,max S=c1x1+c2x2 s.t.a11x1+a12x2b1 a21x1+a22x2b2 x1,x20,在平面上取一直角坐标系，它的两个坐标分别是x1,x2,把满足第一个方程的x1,x2看作平面的一个点，那么这个点应在什么地方呢？平面被直线a11x1+a12x2=b1 划分为两个半平面，这个点一定在两个半平面的某一个上面。所有满足约束条件的点就构成一个区域K。现在，我们就是要在K中找一点（x10,x20），使目标函数达到最大。,a21x1+a22x2=b2,a11x1+a12x2=b1,c1x1+c2x2=h,A,显然，把h作为参数的方程c1x1+c2x2=h 表示一平行

8、直线束，在K中任意取一点(x10,x20)，h=c1x1+c2x2=c1x10+c2x20 就表示这个直线束中通过（x10,x20）的一条直线。所以，我们要在K中找一点（x10,x20）使c1x10+c2x20为最大，就变成在直线束中找一条直线，这条直线既通过K中某一点，又使原点到这条直线的距离沿正法线方向达到最大。,x2,x1,O,那么，怎样找这条直线呢？让直线c1x1+c2x2=h 沿着它的正法线（梯度）方向移动，移动到刚刚开始要离开K的时候，这时的直线仍与K相交，也就是还通过K的点.,总结：求最大，沿正法线方向移动。求最小，沿负法线方向移动。,例1.max S=-x1+x2 s.t.2x

9、1+x22 x1-2x22 x1+x25 x1,x20,法线方向：,A(1,4)是S达到最大值的点。,x1+x2=5,-2x1+x2=2,x1-2x2=2,A,例2min S=-2x1+x2 s.t.x1+x21 x1-3x2-3 x1,x20,负法线方向：,O,x1,x2,最小值为负无穷,x1-3x2=-3,x1+x2=1,例3Max S=3x1+x2 s.t.x1+x25-x1+x20 6x1+2x221 x1,x20,法线方向，此问题有无穷多个解.,O,x1,x2,例4Max S=3x1+x2 s.t.x1-x2-1 x1+x2-1 x1,x20此问题无可行解。,O,x1,x2,-1,1

10、,-1,6x1+2x2=21,x1+x2=5,-x1+x2=0,x2,x1,O,可在某一顶点上取得。,总结：两个变量的线性规划问题的解有4种情况。1有唯一的最优解 2有最优解，但不唯一（有无穷多个）3有可行解，但无最优解 4无可行解,3标准形式,min=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj0;j=1,2,n bi0;i=1,2,m,化一般问题为标准形式：,(一)若ak1x1+ak2x2+aknxnbk,加一变量xn+k0（松驰变量），改写为 ak1x1+ak2x2

11、+aknxn+xn+k=bk,若ak1x1+ak2x2+aknxnbk,减一变量xn+k0(剩余变量），改写为 ak1x1+ak2x2+aknxn-xn+k=bk,(二)若目标函数为max=c1x1+c2x2+cnxn,min=-=-(c1x1+c2x2+cnxn),（三）若xj0，令xj=xj-xj”,xj0,xj”0,利用矩阵和向量的符号，线性规划问题可以写为,a11 a12 a1n am1 am2 amn,B=,X=,b1b2bm,x1x2xn,p1jp2jpmj,Pj=,min=CX s.t.AX=b X0,min=CX s.t.xjPj=b X0,C=(c1,c2,cn),A=,mn

12、.秩(A)=m,4 线性规划问题的解,可行解：满足约束条件的解,最优解：使目标函数达到最大的可行解,基:若B是A中m*m阶非奇异子矩阵，(|B|0)，则称B是一个基，相应于B的变量称为基变量。,B被称为一个基，由于B是由m个线性无关列组成，这m个线性无关的列向量可以作为Em空间的一个基。,基本解：令非基变量取零，则得唯一解，称为基本解。,基本可行解：所有变量非负的基本解。,可行基：对应于基可行解的基。,例.Min Z=2x1+x2 s.t.x1+x2+x3=5-x1+x2+x4=0 6x1+2x2+x5=21 xj0,j=1,2,5,1 1 1 0 0A=-1 1 0 1 0 6 2 0 0

13、1,由于，因此P3,P4,P5是一个基，对应的x3,x4,x5为基变量。,1p3=0 0,0p4=1 0,0P5=0 1,令x1=x2=0,则得x3=5,x4=0,x5=21,x0=(0,0,5,0,21)T是,1 0 00 1 00 0 1,对应于基B=的一个基本解。因xi0,x0为基本可行解。,另外，向量P1=，P2=,P3=线性无关，因此P1,P2,P3为一个基，对应的x1,x2,x3为基变量。令x4=x5=0,得 x1=21/8,x2=21/8,x3=-2/8则x=(21/8,21/8,-2/8,0,0)T也是基本解，但其不是可行解。,1 1 1-1 1 06 2 0,又向量P2，P3

14、，P5线性无关，为一组基，x2，x3，x5为对应的基变量，令x1=x4=0，则x2=0，x3=5，x5=21，所以X2=（0，0，5，0，21）T也是一基本可行解，但是退化的。,2.线性规划问题的几何意义,2.1基本概念,凸集：设k为n维欧氏空间的一点集，任取X,YK,若连接X,Y的线段仍属于K,则称K为凸集。即任取,01 X+(1-)YK称K为凸集。,顶点（极点）：设K是凸集，XK,若X不能用不同的两点 X(1)K,X2)K的线性组合表示为 X=X(1)+(1-)X(2)(01)则称X为极点。,2.2基本定理,定理1.线性规划问题的可行解的集合为凸集。,定理2.可行域k的点X是顶点的充分必要

15、条件为X是基本可行解。,定理3.若可行域有界，最优解可以在极点上达到。,单纯形法的基本思想,由线性规划的基本定理知道：一个线性规划问题若有最优解，一定有最优基本可行解，而且基本可行解的个数是有限个。因此求线性规划问题的直观想法是：把所有的基本可行解都找出来，并求其相应的目标函数值，经过比较，即可求出最优解。当线性规划问题的阶数n与维数m很小时，这种方法（枚举法）是可行的，如，时，需要计算的基本可行解的个数不会超过20，是可行的。但当n和m都较大时，计算量迅速增长，以至成为不可能，如，时，需要计算的基本可行解的个数有可能达到70个；而当，时，要求计算的基本可行解的个数有可能达到252个；因此需要

16、寻求其它的计算量小的方法，于是单纯形法应运而生。,3.单纯形法,先找一个基本可行解，判断它是否为最优解。若不是，确定一个规则，从一个基本可行解转移得另一个基本可行解，同时使目标函数值减少，这样经过有限次迭代，可求出最优基本可行解或判断该线性规划问题解无界,3.1 举例,例 求min=2x1+5x2 s.t.x14 x2 3x1+2x2 8 x1 0,x2 0,解化为标准形式 min=2x1+5x2+0 x3+0 x4+0 x5,s.t.x1+x3=4 x2+x4=3 x1+2x2+x5=8 xj0,j=1,2,5,思路：,1.选定一基本可行解；,2.判断现行解是否为最优；（将目标函数中基变量用

17、非基变量代换）；,3.若不是最优解，则从一基本可行解变换到另一基本可行解。（选一非基变量进基，并选择一基变量出基），使目标有所增大，返回2。,系数矩阵A为:,1 0 1 0 0A=0 1 0 1 0 1 2 0 0 1,P3,P4,P5构成一个基，对应的基变量为x3,x4,x5,令非基变量x1,x2取零，则得一基本可行解（0,0,4,3,8）T,令x2增加（由于目标函数中的x2系数较大），而x1仍保持为零，并使原基变量之一变为非基变量。,x1=0时，x3=4 0 x4=3-x2 0 x5=8-2x20,将基变量关于非基变量解出,x3=4-x1 x2=3-x4 x5=8-x1-2(3-x4)=2

18、-x1+2x4,并将目标函数中的基变量用非基变量代替,=2x1+5(3-x4)=15+2x1-5x4,这时，得一基本可行解（0,3,4,0,2）T，目标函数值为15.,其仍然不是最优解.,令x1增加，使原基变量之一为零,x4=0时 x3=4-x10 x2=3 0 x5=2-x10,x1=2时,x5=0,用非基变量表示基变量,x1=2+2x4-x5 x2=3-x4 x3=2-2x4+x5,用非基变量替换目标函数中的基变量，得,=15+2(2+2x4-x5)-5x4=19-x4-2x5,这时得到最优解（2,3,2,0,0）T，max=19.,从一个基本可行解向另一个基本可行解的迭代过程，相当于从一

19、个极点向另一邻接极点的过渡。,(0,3),(2,3),(4,2),(4,0),x1,x2,0,.,.,.,3.2 初始基本可行解的确定,1.若线性规划问题 min=CX s.t.AX=b X0系数矩阵A中存在一单位矩阵B，则B为一个可行基。,2.若约束条件是“”形式的不等式，则可以通过标准化的方法，引入m个非负的松驰变量,AX+IXS=b X0,XS0,3.若约束条件是“”形式或等式约束不存在单位矩阵的情况，则采用人造基方法（见后面）,3.3最优性检验,以矩阵形式表示单纯形的迭代过程,min=CX s.t.AX=b X0,A=(B,N),X=(XB,XN)T,C=(CB,CN)，则上式可写为,

20、min=CBXB+CNXN s.t.BXB+NXN=b XB,XN0,将基变量用非基变量表示 XB=B-1b-B-1NXN代入目标函数，得,=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XN,XB=B-1b,XN=0为一基本可行解。,1.最优解判别定理：若 X(0)=(B-1b,0)T为对应于基B的基本可行解，且CN-CBB-1N 0,则X(0)为最优解。,证对一切可行解X,CX=CB B-1b+（CN-CBB-1N）XN CB B-1b,所以，X(0)=(B-1b,0)T为最优解。,若把上面的矩阵形式表示为方程组，则,则上面的判别定理表示为：若X(0)=(b

21、1,b2,bm,0,0)T为对应于基B的基本可行解，且对于一切j=m+1,2,n,j0，则X(0)为最优解。,2.无穷多最优解判别定理：,若X(0)=(b1,b2,bm,0,0)T为一基本可行解，对于一切j=m+1,n,有j0,又存在某个非基变量xm+k的检验数m+k=0,则线性规划问题有无穷多最优解。,证只需将非基变量xm+k换入基变量中，找到一个新的基本可行解X（1），因m+k=0，知z=z0，故X（1）也是最优解，由2.2定理3可知，X(0)、X（1）连线上所有点都是最优解。,3.无界解判别定理：,若X(0)=(b1,b2,bm,0,0)T为一基可行解，且有一个m+k 0,并且对i=1,

22、2,m,有ai,m+k0,那么该线性规划问题没有有限最优解。,证取xm+k为进基变量，令xm+k增加，并取其余非基变量为零，则得,令xm+k=0，显然，这时目标函数值为 z=z0+m+k+（+）故没有有限最优解。,4 基变换,1.换入变量的确定,一般取j0中的最大者 max(j0)=k对应的xk为换入变量。,2.换出变量的确定,5 迭代（旋转运算）,4.单纯形法的计算步骤,基变量 b x1 x2 xm xm+1 xn x1 b1 1 0 0 a1m+1 a1n x2 b2 0 1 0 a2m+1 a2n xm bm 0 0 1 amm+1 amn c1 c2 cm cm+1 cn,基变量 b

23、x1 x2 xm xm+1 xn x1 b1 1 0 0 a1m+1 a1n x2 b2 0 1 0 a2m+1 a2n xm bm 0 0 1 amm+1 amn 0 0 0 m+1 n,初始单纯形表,4.1单纯形表,4.2计算步骤,步骤：,1.找出初始基本可行解，建立初始单纯形表；,2.检验各非基变量的检验数j，若所有j0，则已得最优解，停止。否则，转3,3.在所有j0中若有一k对应的Pk 0，则此问题无界，停止计算；否则，转4,4.根据max(j0)=k确定进基变量xk，根据规则计算,确定离基变量xl，得主元alk，转5,5.进行基变换，得新的单纯形表，返回2,例1 min=2x1+5x

24、2 s.t.x14 x23 x1+2x28 x1,x20,解 标准化：min=2x1+5x2 s.t.x1+x3=4 x2+x4=3 x1+2x2+x5=8 xj0,j=1,2,5,XB b x1 x2 x3 x4 x5 x3 4 1 0 1 0 0-x4 3 0 1 0 1 0 3 x5 8 1 2 0 0 1 4 0 2 5 0 0 0,x3 4 1 0 1 0 0 4 x2 3 0 1 0 1 0-x5 2 1 0 0-2 1 2 2 0 0 5 0,x3 2 0 0 1 2-1 x2 3 0 1 0 1 0 x1 2 1 0 0-2 1 0 0 0 1-2,最优解为(2,3,2,0,0

25、)T，max=19,例2min z=3x1+x2+3x3 s.t.2x1+x2+x32 x1+2x2+3x35 2x1+2x2+x36 xi0,i=1,2,3解 标准化后，写出单纯形表,XB b x1 x2 x3 x4 x5 x6 x4 2 2 1 1 1 0 0 1 x5 5 1 2 3 0 1 0 5/2 x6 6 2 2 1 0 0 1 3 0 3 1 3 0 0 0,x2 2 2 1 1 1 0 0 2 x5 1-3 0 1-2 1 0 1/2 x6 2-2 0-1-2 0 1-2 1 0 2-1 0 0,XB b x1 x2 x3 x4 x5 x6 x2 1 5 1 0 3-1 0

26、1/5 x3 1-3 0 1-2 1 0-x6 3-5 0 0-4 1 1-7 0 0 3-2 0,x1 1/5 1 1/5 0 3/5-1/5 0 x3 8/5 0 3/5 0-1/5 2/5 0 x6 4 0 1 1-1 0 1-27/5 0-7/5 0-6/5-3/5 0,最优解为(1/5,0,8/5,0,0,4)T min=27/5,5.单纯形法的进一步讨论 5.1人工变量法 若线性规划问题的约束条件 a11x1+a1nxn=b1 am1x1+amnxn=bm不存在单位矩阵。我们可以强行为约束条件加入一单位矩阵 a11x1+a1nxn+xn+1=b1 a21x1+a2nxn+xn+2=

27、b2 am1x1+amnxn+xn+m=bm xj0,j=1,2,m+n xn+1,xn+m称为人工变量。因为人工变量必须为零，所以若经过基变量的逐步转换，最优解中不存在人工变量,则原问题有解；若最优解中还存在人工变量，则原问题无解。1.大M法 我们引入一个很大的正系数(+M)，把规划问题变为下列形式(*)max=c1x1+c2x2+cnxn-M（xn+1+xn+2+xn+m）s.t.a11x1+a1nxn+xn+1=b1 a21x1+a2nxn+xn+2=b1 am1x1+amnxn+xn+m=b1 xj0,j=1,2,m+n M为充分大的正数。定理：应用单纯形法求解(*)(1)如果获得最优

28、解,则当,i=1,2,m都成立时，为(LP)之最优解；否则(LP)的可行解不存在；,(2)如果(*)目标值无下界，且在迭代过程中最后得到的基本可行解，则当,i=1,2,m都成立时,(LP)也无下界；否则(LP)的可行解不存在。例.max=3x1+2x1+x3-x4 s.t.3x1+2x2+x3=15 5x1+x2+2x3=20 x1+2x2+x3+x4=10 x1,x2,x3,x40解引入人工变量把原问题变成下列形式 max=3x1+2x1+x3-x4-M(x5+x6)s.t.3x1+2x2+x3+x5=15 5x1+x2+2x3+x6=20,x1+2x2+x3+x4=10 xi0,i=1,2

29、,6 3 2 1-1-M-M XB b x1 x2 x3 x4 x5 x6 x5 15 3 2 1 0 1 0 x6 20 5 1 2 0 0 1 x4 10 1 2 1 1 0 0 8M+2 3M+2 3M+2 0 0 0 x5 3 0 7/5-1/5 0 1-3/5 x1 4 1 1/5 2/5 0 0 1/5 x4 6 0 9/5 3/5 1 0-1/5 0 7/5M-M/5 0 0-8/5M+16/5+2/5-4/5,XB b x1 x2 x3 x4 x5 x6 x2 15/7 0 1-1/7 0 7/5-3/7 x1 25/7 1 0 3/7 0-1/7 2/7 x4 15/7 0

30、0 6/7 1-9/7 5/7 0 0 6/7 0-M-2/7-M+5/7 x2 5/2 0 1 0 1/6 1/2-1/4 x1 5/2 1 0 0-1/2 1/2-1/14 x3 5/2 0 0 1 7/6-3/2 6/5 0 0 0-1-M+1-M最优解为(5/2,5/2,5/2,0,0,0)T,max=15,原问题的解为(5/2,5/2,5/2,0)T,max=15.2.两阶段法 第一阶段：首先判断原问题是否存在基本可行解，在有基本可行解的情况下，求出一基本可行解。,(*)min=xn+1+xn+m s.t.a11x1+a1nxn+xn+1=b1 am1x1+amnxn+xn+m=bm

31、 xj0,j=1,2,m 结论：若原问题有解，则min=0 若(*)问题min=0,原问题有解，相反，若 min0,则原问题无解。由此问题可得一基本可行解，第二阶段：若第一阶段已判断出原问题有解，这时原问题已得一基本可行解。则可删去xn+1,xn+m,而把原问题的目标函数 代入求max。例.max=3x1+2x1+x3-x4 s.t 3x1+2x2+x3=15 5x1+x2+2x3=20 x1+2x2+x3+x4=10 x1,x2,x3,x40,解第一阶段 max=-x5-x6 s.t.3x1+2x2+x3+x5=15 5x1+x2+2x3+x6=20 x1+2x2+x3+x4=10 x1,x

32、2,x3,x40单纯形表为：,0 0 0 0-1-1 XB b x1 x2 x3 x4 x5 x6 x5 15 3 2 1 0 1 0 x6 20 5 1 2 0 0 1 x4 10 1 2 1 1 0 0 8 3 3 0 0 0,XB b x1 x2 x3 x4 x5 x6 x5 3 0 7/5-1/5 0 1-3/5 x1 4 1 1/5 2/5 0 0 1/5 x4 6 0 9/5 3/5 1 0-1/5 0 7/5-1/5 0 0-8/5 x2 15/7 0 1-1/7 0 7/5-3/7 x1 25/7 1 0 3/7 0-1/7 2/7 x4 15/7 0 0 6/7 1-9/7

33、5/7 0 0 0 0 0-1-1第二阶段：3 2 1-1 XB b x1 x2 x3 x4 x2 15/7 0 1-1/7 0 x1 25/7 1 0 3/7 0 x4 15/7 0 0 6/7 1 0 0 6/7 0,XB b x1 x2 x3 x4 x2 5/2 0 1 0 1/6 x1 5/2 1 0 0-1/2 x3 5/2 0 0 1 7/6 0 0 0-1最优解为x1=x2=x3=5/2,x4=0.5.2退化 若用规则确定换出变量时，有时存在两个以上的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。当出现退化解时，会出现循环。1974年勃兰特(Bland)提出了一种简便规则：(1)选取j0中下标最小的非基变量xk为换入变量k=min(j|j0)(2)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量换出变量。,