最优化方法-线性规划.ppt

线性规划,数学教研室 石鸿雁,引言,线性规划是数学规划的一个重要分支，历史比较悠久，理论比较成熟，方法较为完善。线性规划的思想最早可以追溯到1939年，当时的苏联数学家、经济学家（康特罗维奇）在生产组织与计划中的数学方法一书中提出了类似线性规划的模型，以解决下料问题和运输问题，并给出了“解决乘数法”的求解方法。然而，他们的长期工作未被人们知道。 由于战争的需要，美国的经济学家T.C.Koopmans（库普曼斯）重新独立的研究运输问题，并很快看到了线性规划在经济学中应用的意义。在这之后，线性规划也被广泛地应用于军事、经济等方面。由于他们在这方面的突出贡献，康特罗维奇和库普曼斯联合得到1975年诺贝尔经济学奖。,引言,对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他在1947年提出了求解线性规划的单纯形法（Simple Method），并同时给出了许多很有价值的理论，为线性规划奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法，1954年Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。 在1976年， R. G. Bland 提出避免出现循环的方法后，使线性规划的理论更加完善。但在1972年，V. Klee和G .Minmty构造了一个例子，发现单纯形法的迭代次数是指数次运算，不是好方法并不是多项式算法（多项式算法被认为是好算法），这对单纯形法提出了挑战。,引言,1979年，前苏联青年数学家（哈奇扬）提出了一种新算法椭圆算法，是一个多项式算法，这一结果在全世界引起了极大轰动，被认为是线性规划理论上的历史突破。然而在实际计算中，椭球算法的计算量与单纯形算法差不多，因此，椭球算法并不实用。 1984年，在美国的贝尔实验室工作的印度数学家N.Karmarkar (卡玛卡尔)又提出了一个多项式算法Karmarkar 算法，Karmarkar算法本质上属于内点法，这种算法不仅在理论上优于单纯形算法，而且也显示出对求解大规模线性规划问题的巨大潜力。 此外，1980年前后，形成求解线性规划的有效集法（active set method），在理论上有效集法与单纯形法是等价的，但解决问题的侧重点不同，因此各有优缺点，起着相互补充的作用。,引言,由于很多非常重要的实际问题都是线性的，即使不是至少能够用线性函数很好地近似，所以线性规划的研究是很有价值的。 另一方面，线性规划方面的工作与非线性规划领域相比更为成熟。目前，线性规划方法的发展已被用来求解非线性模型，所以掌握线性规划的理论和解法是本课程的重要目标之一。,线性规划（LP）,A1,A2,B1,B2,B3,工地,运价（元/万块）,砖厂,50 60 70,60 110 160,1947年 美国数学家 Dantzig 单纯形法 理论基础,1979年 苏联数学家 哈奇安 椭球法 理论上的突破,1984年 美国数学家 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=50x11+60x12+70x13+60x21+110x22+160x23,S.t. x11+x12+x13=23,x21+x22+x23=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+10x2,s.t. 0.18x1+0.09x272,0.08x1+0.28x256,x1,x20,线性规划问题：约束条件及目标函数均为未知量的线性函数，求目标函数的最大或最小值问题。,.2图解法（只限于两个变量）,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 表示一平行直线束，在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. 2x1+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,-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+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=,b1 b2 bm,x1 x2 xn,p1j p2j pmj,Pj=,min=CX s.t. AX=b X0,min=CX s.t. xjPj=b X0,C=(c1,c2, ,cn),A=,mn.秩(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 0 A= -1 1 0 1 0 6 2 0 0 1,由于 ，因此P3,P4,P5 是一个基，对应的x3,x4,x5为基变量。,1 p3= 0 0,0 p4= 1 0,0 P5= 0 1,令x1=x2=0,则得x3=5,x4=0,x5=21,x0=(0,0,5,0,21)T是,1 0 0 0 1 0 0 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 0 6 2 0,又向量P2 ， P3，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是顶点的充分必要条件为X是基本可行解。,定理3.若可行域有界，最优解可以在极点上达到。,单纯形法的基本思想,由线性规划的基本定理知道：一个线性规划问题若有最优解，一定有最优基本可行解，而且基本可行解的个数是有限个。因此求线性规划问题的直观想法是：把所有的基本可行解都找出来，并求其相应的目标函数值，经过比较，即可求出最优解。 当线性规划问题的阶数n与维数m很小时，这种方法（枚举法）是可行的，如 ， 时，需要计算的基本可行解的个数不会超过20，是可行的。 但当n和m都较大时，计算量迅速增长，以至成为不可能，如 ， 时，需要计算的基本可行解的个数有可能达到70个；而当 ， 时，要求计算的基本可行解的个数有可能达到252个；因此需要寻求其它的计算量小的方法，于是单纯形法应运而生。,3.单纯形法,先找一个基本可行解，判断它是否为最优解。若不是，确定一个规则，从一个基本可行解转移得另一个基本可行解，同时使目标函数值减少，这样经过有限次迭代，可求出最优基本可行解或判断该线性规划问题解无界,3.1 举例,例 求min =2x1+5x2 s.t. x14 x2 3 x1+2x2 8 x1 0,x2 0,解化为标准形式 min =2x1+5x2+0x3+0x4+0x5,s.t. x1 +x3 =4 x2 +x4 =3 x1+2x2 +x5=8 xj0,j=1,2,5,思路：,1.选定一基本可行解；,2.判断现行解是否为最优；（将目标函数中基变量用非基变量代换）；,3.若不是最优解，则从一基本可行解变换到另一基本可行解。（选一非基变量进基，并选择一基变量出基），使目标有所增大，返回2。,系数矩阵A为:,1 0 1 0 0 A= 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-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.,从一个基本可行解向另一个基本可行解的迭代过程，相当于从一个极点向另一邻接极点的过渡。,(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)，则上式可写为,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)=(b1,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,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 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+5x2 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)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 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 =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)如果获得最优解 ,则当 ,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, ,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 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 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,x2,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 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)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量换出变量。,