《工程优化设计线性及二次规划.ppt》由会员分享，可在线阅读，更多相关《工程优化设计线性及二次规划.ppt（90页珍藏版）》请在三一办公上搜索。
1、工程优化设计,黄正东二0一二年九月,内容提要,工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统,线性规划与二次规划,线性规划问题是一类优化问题,其约束函数和目标函数均为线性.,一般形式:min f(x)=cTx=c1x1+c2x2+cnxn s.t.h(x)=Hx=h1x1+h2x2+hnxn=0 g(x)=Gx=g1x1+g2x2+gnxn 0 xRn,hi Rp,gi Rq,线性规划,线性规划-举例,线性规划-举例,Ti 张力,l 可删去,线性规划-举例,Wi,wi
2、 是已知量。,线性规划与二次规划,线性规划问题是一类优化问题,其约束函数和目标函数均为线性.,(1)基本理论,1.线性规划的标准形式,一般形式:min f(x)=cTx=c1x1+c2x2+cnxn s.t.h(x)=Hx=h1x1+h2x2+hnxn=0 g(x)=Gx=g1x1+g2x2+gnxn 0 xRn,hi Rp,gi Rq,一.线性规划,线性规划与二次规划,2.基本可行解,标准形式:min f(x)=cTx=c1x1+c2x2+cnxn s.t.Ax=a1x1+a2x2+anxn=b x0,xRn,ARmn,Ax=0,A=B N=,BRmm,B,N,方阵,|B|0,N不一定是方阵
3、,Ax=BxB+NxN=b,xB=B-1(b-NxN)=B-1b-B-1NxNxT=xB xN=B-1b-B-1NxN,xN=-B-1N I xN+B-1b 0,线性规划与二次规划,xT=xB xN=-B-1N I xN+B-1b 0因此,xN自由变化,x=f(xN)为所有可行解的显式表达.,2.1 基本解 令 xN=0,xT=B-1b 0 为基本解.2.2 基本可行解 xT=B-1b 00 为基本可行解.2.3 基本解个数 随着B的构成列不同,可得不同的基本解,从n列中 选取m列的选择方案有Cnm=n!/m!(n-m)!个.除去|B|=0的情况,基本解个数最多是Cnm.,线性规划与二次规划,
4、3.解的几何意义,min 3x1-2x2s.t.-x1+x23-2x1+x2 2 4x1+x2 16x10,x20,min 3x1-2x2s.t.-x1+x2+x3=3-2x1+x2+x4=2 4x1+x2+x5=16xi0,i=1,2,5,(x1=0,x2=0),(x1=0,x2=16),基本解,但非可行,线性规划与二次规划,3.解的几何意义,3.1 可行域是超多面体.3.2 等高线是超平面.3.3 最优解在顶点处.3.4 顶点个数有限.3.5 顶点是基本可行解.,f=6,f=0,f=-5,线性规划与二次规划,4.单纯形法,(1)算法基本思想,因为最优解在顶点上,基本可行解为顶点,所以,优化
5、搜索可以沿着可行域的边界,从一个顶点到另一个顶点的方式进行,每一步使目标函数值减小.由于顶点个数有限,在有限步内可达到最优解.,1.1 最优性检查,xT=xB xN=B-1b-B-1NxN,xN,f(x)=cTx=cBTxB+cNTxN=cBTB-1b-B-1NxN+cNTxN=cBTB-1b+(cNT-B-1N)xN,线性规划与二次规划,1.1 最优性检查,f(x)=cBTB-1b+(cNT-cBTB-1N)xN,这样,如果cNT-cBTB-1N0,因为xN0使f(x)增加,于是,当前x是最优解.,设 f(x)=cBTB-1b+(cNT-cBTB-1N)xN=c0+c xN,1.2 基本可行
6、解更新,f(x)=c0+cTxN,c=c1,c2,cp,cNT取cp0,jB;最先到零：xj=bjp-xpajp=0 写成一维搜索格式是:Xk+1=Xk+xpdk,dk=(-a,0,0,1,0,0)T.,ajp0时,xp不受限制,x=B-1b-B-1NxN,xN=B-1b,0+-B-1NxN,xN=Xk+-B-1NxN,xN=Xk+xpdk,xN=0 0 xp 0 0T=xp00 1 00T=xpepdk=-B-1Nep,0 1 0,如果dk分量全非负,有无界最优解;否则,最优解受 Xk+xpdk=0 约束.,1.2 基本可行解更新,Xk=*,0 0 0 0,dk,xp,Xk+1=*0*,0*
7、0 0,Xk+1=Xk+xpdk,随xp增加,x3k+1 最先变为零,xk+1=*0*,0*0 0,出基本变量,入基本变量,(2)算法流程,1.给定一个初始基本可行解x(1)=B1-1b,0,记k=1.2.计算cNk=cNk-NkTBk-1cBk.3.最优性检验:计算cpk=mincjk|jNk,如果cpk0,则x(k)为最优 解,停止.否则,选xkp为入基变量.4.确定出基本变量:dk=Bk-1Nkep=x(k)=Bk-1b=,若对所有jBk,dkj0,则问题有 无界最优解;否则,出基变量是满足下式的q:-xkq/dkq=min-xkj/dkj,dkj0,jBk.5.交换Bk中Aq和Nk中A
8、p,得新Bk+1和Nk+1,k=k+1,转步骤2.,线性规划与二次规划,算法分析,1.算法简单明了,有限步结束.2.初始值需要是基本可行解.3.在Step 2计算cNk=cNk-NkTBk-1cBk时,需要求Bk的逆.,线性规划与二次规划,单纯形方法用逐步消去法替代Bk求逆.,为什么叫单纯形算法？,标准形式:min f(x)=cTx=c1x1+c2x2+cnxn s.t.Ax=a1x1+a2x2+anxn=b x0,xRn,ARmn,标准形式中的约束定义的可行域是“n维空间中n-m维单纯形”,即为n维空间中m维线性流形与第一象限的交。,n=3;m=1,n=3;m=2,所以，前述算法是在n维空间
9、中n-m维单纯形顶点上搜索。,(3)单纯形法的表计算形式,线性规划与二次规划,xB+B-1NxN=B-1b,f(x)=cTx=cBTxB+cNTxN=cBTB-1b+(cNT-cBTB-1N)xN,表中数据项意义:,0*xB+(cNT-cBTB-1N)xN f=-cBTB-1b,线性规划与二次规划,xB+NxN=b,表中数据项意义:,0*xB+cNTxN f=c,线性规划与二次规划,xB+NxN=b,表中数据项意义:,0*xB+cNTxN f=c,线性规划与二次规划,xB+NxN=b,表中数据项意义:,0*xB+cNTxN f=c,线性规划与二次规划,xB+NxN=b,表中数据项意义:,0*x
10、B+cNTxN f=c,线性规划与二次规划,xB+NxN=b,表中数据项意义:,0*xB+cNTxN f=c,线性规划与二次规划,xB+NxN=b,表中数据项意义:,cN-pTxN-p+cpxp f=c,xp=b2-axq-mTxN-p,cN-pTxN-p+cp(b2-axq-mTxN-p)f=c,-cpaxq+cN-pT-cpmTxN-p f=c-cpb2,线性规划与二次规划,xB+NxN=b,表中数据项意义:,-cpaxq+cN-pT-cpmTxN-p f=c-cpb2,线性规划与二次规划,xB+NxN=b,表中数据项意义:,-cpaxq+cN-pT-cpmTxN-p f=c-cpb2,线
11、性规划与二次规划,xB+B-1NxN=B-1b,f(x)=cTx=cBTxB+cNTxN=cBTB-1b+(cNT-cBTB-1N)xN,结束条件:cNT-cBTB-1N0最优解:x*=(xB,0)T=(B-1b,0)T最优值:f(x*)=cBTB-1b,在xN中找到下一个进入基变量的分量,在xB中找到下一个出基变量的分量.通过消去法更新表中内容,使对于新的xB 和xN 上表仍保持各项数据的相应意义.,表操作:,终止状态:,总结：,(3)单纯形法的表计算形式举例,线性规划与二次规划,min-2x1-3x2s.t.-x1+x2+x3=3-2x1+x2+x4=2 4x1+x2+x5=16xi0,i
12、=1,2,5,cN中最负量为-3,即选入分量p=2.计算xj/ajp:3/1,2/1,16/1-min=2/1-即选出分量 q=4.注意:d=-B-1Nep,所以 dj=-ajp,p,q,x1不变，x2变化引起x4变化,(3)单纯形法的表计算形式举例,线性规划与二次规划,相减,相减,2进,4出,将 cB=(c3,c2,c5)=(0,-3,0)移至表前.,用消元法将x2变为基变量,(3)单纯形法的表计算形式举例,线性规划与二次规划,更新f系数:c新=c旧-cBTAi,Ai为列向量,第一轮完,(3)单纯形法的表计算形式举例,线性规划与二次规划,更新f系数:c新=c旧-cBTAi,Ai为列向量,第二
13、轮完,(3)单纯形法的表计算形式举例,线性规划与二次规划,(3)单纯形法的表计算形式举例,线性规划与二次规划,更新f系数:c新=c旧-cBTAi,Ai为列向量,第三轮完,因为c=(0 0 2 0 1)0,所以,结束,-f=22,f=-22.x*=(13/5,28/5,0,8/5,0),线性规划与二次规划,min-2x1-3x2s.t.-x1+x2+x3=3-2x1+x2+x4=2 4x1+x2+x5=16xi0,i=1,2,5,min 3x1-2x2s.t.-x1+x23-2x1+x2 2 4x1+x2 16x10,x20,初始基本变量,(4)初值取法,问题:单纯形法要求从一个基本可行解开始搜
14、索,怎样找到第一基本可行解,即为初值问题.,条件:xT=B-1b 00 为基本可行解.,线性规划-举例,s.t.,s.t.,s.t.,线性规划-举例,x1,x2,x3,x4,x5,x6,-f,b”,线性规划-举例,线性规划-举例,线性规划-举例,x1,x2,x3,x4,-f,b”,When x3-+,f-.,线性规划-举例,s.t.,线性规划-举例,x1,x2,x3,x5,x4,-f,b”,但是，x1 取其它正数时，仍有最小值 f=-20！,线性规划-举例,f,(4)初值取法,线性规划与二次规划,4.1 二阶段法,min-x1s.t.2x1+3x2=7 2x1-3x26 4x1+x24 x1
15、0,x2 0,min-x1s.t.2x1+3x2=7 2x1-3x2+x3=6 4x1+x2-x4=4 xi 0,i=1,2,3,4,标准化后,难以确定基变量,条件:xT=B-1b 00 为基本可行解.,x=(0,7/3,13,-5/3)因为x40,所以x为非可行基本解.,(4)初值取法,线性规划与二次规划,4.1 二阶段法,min-x1s.t.2x1+3x2+a1=7 2x1-3x2+x3=6 4x1+x2-x4+a2=4 xi 0,i=1,2,3,4,ai 0,i=1,2.,x3可作为基变量,将原问题拓展为下列问题.,min a1+a2s.t.2x1+3x2+a1=7 2x1-3x2+x3
16、=6 4x1+x2-x4+a2=4 xi 0,i=1,2,3,4,ai 0,i=1,2.,第一阶段:初始基本变量为(x3,a1,a2).如果原问题有可行解,则辅助问题最优值为零;如果辅助问题最优值大于零,原问题无解.第二阶段:当达到辅助问题的最优解,基本变量都变为xi,它们可作为原问题初始值.,辅助问题,(4)初值取法,线性规划与二次规划,4.2 大M方法,min-x1+M(a1+a2)s.t.2x1+3x2+a1=7 2x1-3x2+x3=6 4x1+x2-x4+a2=4 xi 0,i=1,2,3,4,ai 0,i=1,2.M0,充分大的正实数.,初始基本变量为(x3,a1,a2).当基本变
17、量都变为xi后,剔除目标函数和约束中有关ai,的项,继续迭代.,辅助问题,线性规划与二次规划,min,s.t.,线性规划与二次规划,先消去 y1、y2的系数！,相同时，任意取一个。,线性规划与二次规划,x1,x2,x3,x4,x5,y1,y2,b”,y2,y1,线性规划与二次规划,线性规划与二次规划,线性规划与二次规划,线性规划与二次规划,线性规划与二次规划,或用 x,fval,exitflag,output=linprog(f,A,b,Aeq,beq,lb,optimset(LargeScale,off,Simplex,on,Display,iter),大型线性规划问题Karmarkars
18、Interior Point Method,大型线性规划问题Karmarkars Interior Point Method,大型线性规划问题Karmarkars Interior Point Method,大型线性规划问题Karmarkars Interior Point Method,大型线性规划问题Karmarkars Interior Point Method,大型线性规划问题Karmarkars Interior Point Method,大型线性规划问题Karmarkars Interior Point Method,大型线性规划问题Karmarkars Interior Poin
19、t Method,二次规划,二次规划问题是一类优化问题,其约束函数为线性,目标函数是二次.,二次规划,min q(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE aiTxbi,iI,二次规划-举例,资源成本,成品售价,ui 资源用量,xi 成品销售量,二次规划-举例,总成本,总营业额,总利润,二次规划-举例,Find,Minimize,Subject to,线性规划与二次规划,二次规划问题是一类优化问题,其约束函数为线性,目标函数是二次.,(1)等式约束二次规划问题,二.二次规划,min q(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE aiTxbi,iI,min
20、 q(x)=(1/2)xTGx+gTxs.t.ATx=b,线性规划与二次规划,(1)等式约束二次规划问题,ATx=b,ABTxB+ANTxN=b xB=AB-T(b-ANTxN),一.直接消去法,线性规划与二次规划,(1)等式约束二次规划问题,二.Lagrange法,解上述方程即得:x*,*.,1.与K-T条件一致2.对于凸二次规划，K-T条件是 充分条件,线性规划与二次规划,(1)一般凸二次规划问题的有效集方法,min q(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE aiTxbi,iI,G 正定,线性规划与二次规划,(1)一般凸二次规划问题的有效集方法,min q(x)=(
21、1/2)xTGx+gTxs.t.aiTx=bi,iE aiTxbi,iI,G 正定,对于凸二次规划问题,G正定,可行域为凸多边形.先以无约束问题,求出xu;如果xu满足约束,xu即为原约束问题的解;否则,原问题的解在边界上,用下列有效集方法求解.,线性规划与二次规划,(1)一般凸二次规划问题的有效集方法,min q(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE aiTxbi,iI,一.算法思想,从初始可行点x0开始,不断向新的可行解转移,其思路与线性规划中单纯形方法相似.,有效约束集 w0=w(x0)=iIE|aiTx0=bi,因为x0可行,所以 w0=Ei|aiTx0=bi,
22、iI,并且aiTx0bi,iw0,G 正定,线性规划与二次规划,(1)一般二次规划问题的有效集方法,终止条件 x0是下列等式约束问题的解,aiTx0bi,iw0,w0=Ei|aiTx0=bi,iI,min q(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iw(x0),2.x0是原问题的可行解,即判断是否满足,x0满足原问题的K-T条件(对于凸二次规划问题,K-T条件是 极值的充分条件),即:,(注意:I.等式约束不需要i*0;II.当iw0时,可取i*=0),对于凸二次规划，K-T条件是充分条件,线性规划与二次规划,条件1判断:,p=x-x0,g0=Gx0+gq(x)=q(x0+p
23、)=(1/2)(x0+p)TG(x0+p)+gT(x0+p)=(1/2)pTGp+g0Tp+caiTx=aiT(x0+p)=aiTx0+aiTp=bi,iw0因为,x0为可行点,所以 aiTx0=bi,aiTp=0.解 min(1/2)pTGp+g0Tp s.t.aiTp=0,iw0如果得上述问题最优解为p=0,即x=x0+p=x0为子问题最优解.条件1满足.,线性规划与二次规划,条件2判断:,直接将x0代入aiTxbi,iw0.即可验证.由于每一步迭代已保证x0为原问题可行点,所以,此判断可免.,条件3判断:,将x0代入求出i*.如果i*0,iIw0,即条件3满足.对原问题来说,K-T条件是
24、:,=0,0,实数,线性规划与二次规划,可行点转移更新:,(1)当条件3不满足时.即存在j*0,jIw0,则在子问题中去掉约束ajTx=bj,重新计算局部最优解.,去掉约束P2有利于极小点向顶点x1转移.,(2)条件2始终保证满足.即每一步假设x0是可行点,所以条件2始终满足.,线性规划与二次规划,可行点转移更新:,(3)当条件1不满足时.即p*0时,将x0转移到x1=x0+p,10且x1是可行点,1.由方程aiT(x0+p)=bi计算,意味x1到达某边界.2.aiTp1,可直接取较近处的=1时的x0+p,f(x0+p)更小.,5.当1时,指标为j的约束成为有效,w1=w0-ij,注意:与线性
25、规划不同,二次规划解可不在顶点处.,注意:与线性规划不同,二次规划解可不在顶点处.,可行点转移更新:,p=x-x0,g0=Gx0+gmin(1/2)pTGp+g0Tp s.t.aiTp=0,iw0,(1).在x=x0,w0=i,j时,j 0,移去约束aj,(2).重新计算约束最优解,发现不在原x0处,而是x=x0+p,线性规划与二次规划,二.算法,1.计算可行的初始点x0,置x0处的有效集w0,k=0.2.求解pk:min(1/2)pTGp+gkTp,s.t.aiTp=0,iwk.3.若pk=0,计算i:若i0,iwkI,则停止,x*=xk.否则,j=下标mini|i0,iwkI,xk+1=xk,wk+1=wkj.4.若pk0,计算:xk+1=xk+kpk 若存在j使ajTxk+1=bj,jwk,置wk+1=wkj.否则,即k=1时,wk+1=wk.5.k=k+1,转步2.,线性规划与二次规划,三.算法分析,初始可行点x0的选取,可类似于线性规划.,二次规划的拉格朗日乘子法,二次规划的拉格朗日乘子法,二次规划的拉格朗日乘子法,仅有的非线性项！,二次规划的拉格朗日乘子法,用Simplex法求解时，Lamda 与 Yi 最多保持一个在基本解中。,二次规划,二次规划,总结：,1。线性规划和二次规划是解决一般约束优化问题的重要基础.,线性规划与二次规划,
