华科大工程优化设计课件07线性规划与二次规划

线性规划与二次规划线性规划问题是一类优化问题,其约束函数和目标函数均为线性.一般形式:minf(x)=cTx=c1x1+c2x2+…+cnxns.t.h(x)=Hx=h1x1+h2x2+…+hnxn=0g(x)=Gx=g1x1+g2x2+…+gnxn

0

xRn,hi

Rp,gi

Rq线性规划线性规划-举例线性规划-举例Ti张力l

可删去线性规划-举例Wi,wi

是已知量。线性规划与二次规划线性规划问题是一类优化问题,其约束函数和目标函数均为线性.(1)基本理论1.线性规划的标准形式一般形式:minf(x)=cTx=c1x1+c2x2+…+cnxns.t.h(x)=Hx=h1x1+h2x2+…+hnxn=0g(x)=Gx=g1x1+g2x2+…+gnxn

0

xRn,hi

Rp,gi

Rq一.线性规划线性规划与二次规划2.基本可行解标准形式:minf(x)=cTx=c1x1+c2x2+…+cnxns.t.Ax=a1x1+a2x2+…+anxn=b

x0,xRn,ARmn

Ax=0,A=[BN]=[],BRmm

BN方阵,|B|0N不一定是方阵Ax=BxB+NxN=b,xB=B-1(b-NxN)=B-1b-B-1NxNxT=[xB

xN]=[B-1b-B-1NxN,xN]=[-B-1NI]

xN+[B-1b0]线性规划与二次规划xT=[xB

xN]=[-B-1NI]

xN+[B-1b0]因此,xN自由变化,x=f(xN)

为所有可行解的显式表达.2.1基本解

令

xN=0,xT=[B-1b0]为基本解.2.2基本可行解

xT=[B-1b0]0

为基本可行解.2.3基本解个数随着B的构成列不同,可得不同的基本解,从n列中选取m列的选择方案有Cnm=n!/[m!(n-m)!]个.除去|B|=0的情况,

基本解个数最多是Cnm.线性规划与二次规划3.解的几何意义min 3x1-2x2s.t. -x1+x23 -2x1+x22 4x1+x216 x10,x20

min 3x1-2x2s.t. -x1+x2+x3=3 -2x1+x2+x4=2 4x1+x2

+x5=16 xi0,i=1,2,…,5

f=6f=0f=-5(1,4)(13/5,28/5)(7/3,20/3)(x1=0,x2=0)(1,4)(13/5,28/5)(7/3,20/3)(x1=0,x2=16)基本解,但非可行线性规划与二次规划3.解的几何意义3.1可行域是超多面体.3.2等高线是超平面.3.3最优解在顶点处.3.4顶点个数有限.3.5顶点是基本可行解.f=6f=0f=-5线性规划与二次规划4.单纯形法(1)算法基本思想因为最优解在顶点上,基本可行解为顶点,所以,优化搜索可以沿着可行域的边界,从一个顶点到另一个顶点的方式进行,每一步使目标函数值减小.由于顶点个数有限,在有限步内可达到最优解.1.1最优性检查xT=[xB

xN]=[B-1b-B-1NxN,xN]f(x)=cTx=cBTxB+cNTxN=cBT[B-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

xN1.2基本可行解更新f(x)=c0+cTxN,c=[c1,c2,…,cp,…,cN]T取cp<0,使f(x)下降.x=[B-1b0]+[-B-1N,I]TxN所以,xN变化后,xB=B-1b-B-1NxN

设xN=[0…0xp0…0]T=xpep,则xB=B-1b-B-1NxN=b’–xpa’,b’=B-1b,a’=B-1Nep由xB=b’-xpa’0,得出xp的搜索步长:xp=bq/aq=min{bjp/ajp,ajp>0,jB};最先到零：xj=bjp-xpajp=0

写成一维搜索格式是:Xk+1=Xk+xpdk,dk=(-a’,0,…,0,1,0,…,0)T.ajp<0时,xp不受限制x=[B-1b-B-1NxN,xN]=[B-1b,0]+[-B-1NxN,xN]=Xk

+

[-B-1NxN,xN]=Xk+xpdkXk=[B-1b,0]dkXk+1=Xk+xpdkxN=[0…0

xp0…0]T

=xp[0…010…0]T=xpepdk=[-B-1Nep,0…1…0]如果dk分量全非负,有无界最优解;否则,最优解受Xk+xpdk>=0约束.1.2基本可行解更新Xk=[****,0000]dkxpXk+1=[**0*,0*00]Xk+1=Xk+xpdk随xp增加,x3k+1最先变为零xk+1=[**0*,0*00]出基本变量入基本变量(2)算法流程1.给定一个初始基本可行解x(1)=[B1-1b,0],记k=1.2.计算cNk=cNk-NkTBk-1cBk.3.最优性检验:计算cpk=min{cjk

|jNk},如果cpk0,则x(k)为最优解,停止.否则,选xkp为入基变量.4.确定出基本变量:dk=Bk-1Nkep=

x(k)=Bk-1b=,

若对所有jBk,dkj

0,则问题有无界最优解;否则,出基变量是满足下式的q:-xkq/dkq=min{-xkj/dkj,dkj<0,jBk}.5.交换Bk中Aq和Nk中Ap,得新Bk+1和Nk+1,k=k+1,转步骤2.线性规划与二次规划算法分析1.算法简单明了,有限步结束.2.初始值需要是基本可行解.3.在Step2计算cNk=cNk-NkTBk-1cBk时,需要求Bk的逆.线性规划与二次规划单纯形方法用逐步消去法替代Bk求逆.

为什么叫单纯形算法？标准形式:minf(x)=cTx=c1x1+c2x2+…+cnxns.t.Ax=a1x1+a2x2+…+anxn=b

x0,xRn,ARmn

标准形式中的约束定义的可行域是“n维空间中n-m维单纯形”,

即为n维空间中m维线性流形与第一象限的交。x1x2x3x1x2x3n=3;m=1n=3;m=2所以，前述算法是在n维空间中n-m维单纯形顶点上搜索。(3)单纯形法的表计算形式线性规划与二次规划基变量xBxN-f右端项-f0cNT-cBTB-1N1-cBTB-1bxBIB-1N0B-1b(>0)xB+B-1NxN=B-1bf(x)=cTx=cBTxB+cNTxN

=cBTB-1b+(cNT-cBTB-1N)xN表中数据项意义:0*xB+(cNT-cBTB-1N)xN

–f

=-cBTB-1b线性规划与二次规划基变量xBxN-f右端项-f0cN1cxBIN0b(>0)xB+NxN

=b表中数据项意义:0*xB+cNTxN

–f

=c线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-f00cN-pcp(<0)1cxq10nTa1(>0)0b1(>0)xB-q0IN’np0b’(>0)xB+NxN

=b表中数据项意义:0*xB+cNTxN

–f

=c线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-f00cN-pcp1cxq1/a10nT/a110b1/a1(>0)xB-q0IN’np0b’xB+NxN

=b表中数据项意义:0*xB+cNTxN

–f

=c线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-f00cN-pcp1cxqa0mT10b2xB-q0IN’np0b’xB+NxN

=b表中数据项意义:0*xB+cNTxN

–f

=c线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-f00cN-pcp1cxqa0mT10b2xB-q-anpIN’-npmT00b’-b2npxB+NxN

=b表中数据项意义:0*xB+cNTxN

–f

=c线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-f00cN-pcp1cxqa0mT10b2xB-qa”IN”00b”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-cpmT]xN-p

–f

=c-cpb2线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-f-cpa0cN-p-cpmT01c-cpb2xqa0mT10b2xB-qa”IN”00b”xB+NxN

=b表中数据项意义:

-cpaxq+[cN-pT-cpmT]xN-p

–f

=c-cpb2线性规划与二次规划基变量xqxB-qxN-pxp-f右端项-fcq’0cN-p’01c’xpa0mT10b2xB-qa”IN”00b”xB+NxN

=b表中数据项意义:

-cpaxq+[cN-pT-cpmT]xN-p

–f

=c-cpb2线性规划与二次规划基变量xBxN-f右端项-f0cNT-cBTB-1N1-cBTB-1bxBIB-1N0B-1bxB+B-1NxN=B-1bf(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=16 xi0,i=1,2,…,5

基变量x1x2x3x4x5右端项-f-2-30000x3-111003x4-210102x54100116cN中最负量为-3,即选入分量p=2.计算xj/ajp:{3/1,2/1,16/1}->min=2/1->

即选出分量q=4.注意:d=-B-1Nep,所以dj=-ajppqx1不变，x2变化引起x4变化(3)单纯形法的表计算形式—举例线性规划与二次规划基变量x1x2x3x4x5右端项-f-2-30000x3101-101x2-210102x5600-1114相减相减2进,4出基变量x1x2x3x4x5右端项-f-2-30000x3

101-101x2-210102x5600-1114cB0-30将

cB=(c3,c2,c5)=(0,-3,0)移至表前.用消元法将x2变为基变量(3)单纯形法的表计算形式—举例线性规划与二次规划基变量x1x2x3x4x5右端项-f-800306x3

101-101x2-210102x5600-1114cB0-30更新f系数:c新=c旧-cBTAi,Ai为列向量基变量x1x2x3x4x5右端项-f-8p00306x3q1(1/1)q01-101x2-210102x56(14/6)00-1114第一轮完(3)单纯形法的表计算形式—举例线性规划与二次规划基变量x1x2x3x4x5右端项-f-8p00306x1

101-101x2012-104x500-6518cB-800基变量x1x2x3x4x5右端项-f008-5014x1

101-101x2012-104x500-6518cB-800更新f系数:c新=c旧-cBTAi,Ai为列向量第二轮完(3)单纯形法的表计算形式—举例线性规划与二次规划基变量x1x2x3x4x5右端项-f008-5p014x1101-101x2012-104x5q00-65(8/5)q18基变量x1x2x3x4x5右端项-f008-5014x110-1/501/513/5x2014/501/528/5x4

00-6/511/58/5cB00-5(3)单纯形法的表计算形式—举例线性规划与二次规划基变量x1x2x3x4x5右端项-f0020122x110-1/501/513/5x2014/501/528/5x4

00-6/511/58/5cB00-5更新f系数:c新=c旧-cBTAi,Ai为列向量第三轮完因为c=(00201)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=16 xi0,i=1,2,…,5

基变量x1x2x3x4x5右端项-f-2-30000x3-111003x4-210102x54100116min 3x1-2x2s.t. -x1+x23 -2x1+x22 4x1+x216 x10,x20

初始基本变量(4)初值取法问题:单纯形法要求从一个基本可行解开始搜索,怎样找到第一基本可行解,即为初值问题.条件:

xT=[B-1b0]0

为基本可行解.线性规划-举例s.t.s.t.s.t.线性规划-举例x1x2x3x4x5x6-fb”线性规划-举例线性规划-举例线性规划-举例x1x2x3x4-fb”Whenx3->+∞,f->-∞.线性规划-举例s.t.线性规划-举例x1x2x3x5x4-fb”但是，x1

取其它正数时，仍有最小值f=-20！线性规划-举例f(4)初值取法线性规划与二次规划4.1二阶段法min-x1s.t.2x1+3x2=72x1-3x264x1+x24x10,x20min-x1s.t.2x1+3x2=72x1-3x2+x3=64x1+x2-x4=4xi0,i=1,2,3,4标准化后,难以确定基变量条件:

xT=[B-1b0]0

为基本可行解.x=(0,7/3,13,-5/3)因为x4<0,所以x为非可行基本解.(4)初值取法线性规划与二次规划4.1二阶段法min-x1s.t.2x1+3x2+a1=72x1-3x2+x3=64x1+x2-x4+a2=4xi0,i=1,2,3,4,ai0,i=1,2.x3可作为基变量将原问题拓展为下列问题.mina1+a2s.t.2x1+3x2+a1=72x1-3x2+x3=64x1+x2-x4+a2=4xi0,i=1,2,3,4,ai0,i=1,2.第一阶段:初始基本变量为(x3,a1,a2).如果原问题有可行解,则辅助问题最优值为零;如果辅助问题最优值大于零,原问题无解.第二阶段:当达到辅助问题的最优解,基本变量都变为xi,它们可作为原问题初始值.辅助问题(4)初值取法线性规划与二次规划4.2大M方法min-x1+M(a1+a2)s.t.2x1+3x2+a1=72x1-3x2+x3=64x1+x2-x4+a2=4xi0,i=1,2,3,4,ai0,i=1,2.M>0,充分大的正实数.初始基本变量为(x3,a1,a2).当基本变量都变为xi后,剔除目标函数和约束中有关ai,的项,继续迭代.辅助问题线性规划与二次规划mins.t.线性规划与二次规划先消去y1、y2的系数！相同时，任意取一个。线性规划与二次规划x1x2x3x4x5y1y2b”y2y1线性规划与二次规划线性规划与二次规划线性规划与二次规划线性规划与二次规划线性规划与二次规划或用[x,fval,exitflag,output]=linprog(f,A,b,Aeq,beq,lb,[],[],optimset('LargeScale','off','Simplex','on','Display','iter'))大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod大型线性规划问题

Karmarkar’sInteriorPointMethod二次规划二次规划问题是一类优化问题,其约束函数为线性,目标函数是二次.二次规划minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTx

bi,iI二次规划-举例资源成本成品售价ui

资源用量xi成品销售量二次规划-举例总成本总营业额总利润二次规划-举例FindMinimizeSubjectto线性规划与二次规划二次规划问题是一类优化问题,其约束函数为线性,目标函数是二次.(1)等式约束二次规划问题二.二次规划minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTx

bi,iIminq(x)=(1/2)xTGx+gTxs.t.ATx=b线性规划与二次规划(1)等式约束二次规划问题ATx=b,ABTxB+ANTxN=bxB=AB-T(b-ANTxN)一.直接消去法线性规划与二次规划(1)等式约束二次规划问题二.Lagrange法解上述方程即得:x*,

*.1.与K-T条件一致2.对于凸二次规划，K-T条件是充分条件线性规划与二次规划(1)一般凸二次规划问题的有效集方法minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTx

bi,iIG

正定线性规划与二次规划(1)一般凸二次规划问题的有效集方法minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTx

bi,iIG

正定对于凸二次规划问题,G正定,可行域为凸多边形.先以无约束问题,求出xu;如果xu满足约束,xu即为原约束问题的解;否则,原问题的解在边界上,用下列有效集方法求解.线性规划与二次规划(1)一般凸二次规划问题的有效集方法minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTx

bi,iI一.算法思想从初始可行点x0开始,不断向新的可行解转移,其思路与线性规划中单纯形方法相似.有效约束集

w0=w(x0)={iIE|aiTx0=bi

}因为x0可行,所以w0=E

{i|aiTx0=bi,iI},

并且aiTx0>bi,iw0G

正定线性规划与二次规划(1)一般二次规划问题的有效集方法终止条件

x0是下列等式约束问题的解aiTx0>bi,iw0,

w0=E

{i|aiTx0=bi,iI},minq(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)=(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+g0Tps.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条件是:

=0

0

实数线性规划与二次规划可行点转移更新:

(1)当条件3不满足时.即存在

j*<0,jIw0,则在子问题中去掉约束ajTx=bj,重新计算局部最优解