華中科技大學工程優(yōu)化設(shè)計線性及二次規(guī)劃

工程優(yōu)化設(shè)計內(nèi)容提要工程優(yōu)化問題建模優(yōu)化數(shù)學理論一維搜索方法無約束問題直接搜索方法無約束問題間接接搜索方法約束問題直接搜索方法線性規(guī)劃與二次規(guī)劃問題求解約束問題間接搜索方法啟發(fā)式算法優(yōu)化軟件系統(tǒng)線性規(guī)劃與二次規(guī)劃線性規(guī)劃問題是一類優(yōu)化問題,其約束函數(shù)和目標函數(shù)均為線性.(1)基本理論1.線性規(guī)劃的標準形式一般形式:minf(x)=cTx=c1x1+c2x2+…+cnxns.t.h(x)=Hx=h1x1+h2x2+…+hnxn=0g(x)=Gx=g1x1+g2x2+…+gnxn

0

xRn,hiRp,giRq一.線性規(guī)劃線性規(guī)劃與二次規(guī)劃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]線性規(guī)劃與二次規(guī)劃Ax=0,A=[BN]=[],BRmm

BNxT=[xB,xN

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

]=[-B-1N,I]

xN+[B-1b,0]線性規(guī)劃與二次規(guī)劃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]因此,xN自由變化,x=f(xN)

為所有可行解的顯式表達.2.1基本解

令

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

xT=[B-1b0]0

為基本可行解.2.3基本解個數(shù)隨著B的構(gòu)成列不同,可得不同的基本解,從n列中選取m列的選擇方案有Cnm=n!/[m!(n-m)!]個.除去|B|=0的情況,基本解個數(shù)最多是Cnm.線性規(guī)劃與二次規(guī)劃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)基本解,但非可行線性規(guī)劃與二次規(guī)劃3.解的幾何意義3.1可行域是超多面體.3.2等高線是超平面.3.3最優(yōu)解在頂點處.3.4頂點個數(shù)有限.3.5頂點是基本可行解.f=6f=0f=-5線性規(guī)劃與二次規(guī)劃4.單純形法(1)算法基本思想因為最優(yōu)解在頂點上,基本可行解為頂點,所以,優(yōu)化搜索可以沿著可行域的邊界,從一個頂點到另一個頂點的方式進行,每一步使目標函數(shù)值減小.由于頂點個數(shù)有限,在有限步內(nèi)可達到最優(yōu)解.1.1最優(yōu)性檢查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線性規(guī)劃與二次規(guī)劃1.1最優(yōu)性檢查xT=[xB

xN]=[B-1b-B-1NxN,xN]f(x)=cTx=cBTxB+cNTxN=cBT[B-1b-B-1NxN]+cNTxN=cBTB-1b+(cNT-cBTB-1N)xN所以,在x=xk時,xk為一基本可行解,即xk=(Bk-1b0)T.f(xk)=cBTBk-1b,當xk沿著xN>0方向變化時,其可行變化方向為Dk=(-Bk-1Nk,I)T,即x=xk+xNDk

,且f(x)=f(xk)+(cNT-cBTBk-1Nk)xN這樣,如果cNT-cBTBk-1Nk0,xN0使f(x)增加,于是,xk是最優(yōu)解.

Skip線性規(guī)劃與二次規(guī)劃1.1最優(yōu)性檢查xT=[xB

xN]=[B-1b-B-1NxN,xN]f(x)=cTx=cBTxB+cNTxN=cBT[B-1b-B-1NxN]+cNTxN=cBTB-1b+(cNT-cBTB-1N)xN這樣,如果cNT-cBTBk-1Nk0,xN0使f(x)增加,于是,xk是最優(yōu)解.

xxk=[Bk-1b,0]1.2基本可行解更新f(x)=f(xk)+(cNT-cBTBk-1Nk)xN=f(xk)+cTxN,c=[c1,c2,…,cp,…,cn]T取cp<0,使f(x)下降.x=xk+[-Bk-1Nk,I]TxN=[Bk-1b0]+[-Bk-1Nk,I]TxN所以,xN變化后,xB=Bk-1b-Bk-1NkxN

設(shè)xN=[0…0xp0…0]T,則xB=Bk-1b-Bk-1NkxN=bk-xpApk,

bk=Bk-1b,Apk=Bk-1Nk[0…010…0]T=Bk-1Nkep由xB=bk-xpApk0,得出xp的搜索步長:xp=bqk/aqpk=min{bjk/ajpk,ajpk>0,jBk},得:xk+1=xk+xpdk,dk=(-Apk,0,…,0,1,0,…,0)T.ajpk<0時,xp不受限制(xBk+1xNk+1)=Txk+1,T為行交換陣,xBk+1為xk+1中非零部分,

xNk+1為xk+1中零部分,這樣得到A中新B和N的下標集合.

Skip1.2基本可行解更新f(x)=f(xk)+(cNT-cBTBk-1Nk)xN=f(xk)+cTxN,c=[c1,c2,…,cp,…,cn]T取cp<0,使f(x)下降.xN=[0…0

xp0…0]T,f(x)=

f(xk)+cpxpx=[Bk-1b-Bk-1NkxN,xN]=[Bk-1b,0]+[-Bk-1NkxN,xN]=xk

+

[-Bk-1NkxN,xN]:=xk+xpdkxk=[Bk-1b,0]dkxk+1=xk+xpdkxN=[0…0

xp0…0]T

=xp[0…010…0]T=xpepdk=[-Bk-1Nkep,0…1…0]1.2基本可行解更新xk=[****,0000]dkxpxk+1=[**0*,0*00]xk+1=xk+xpdk隨xp增加,x3k+1最先變?yōu)榱鉿k+1=[**0*,0*00]出基本變量入基本變量(2)算法流程1.給定一個初始基本可行解,記k=1.2.計算cNk=cNk-NkTBk-1cBk.3.最優(yōu)性檢驗:計算cpk=mn{cjk

|jNk},如果cpk0,則x(k)為最優(yōu)解,停止.否則,選xp為入基變量.4.確定出基本變量:dk=Bk-1Nkep=

bk=Bk-1b=,

若對所有jBk,dkj0,則問題有無界最優(yōu)解;否則,出基變量是滿足下式的q:-bqk/dkj=min{-bjk/dkj,dkj<0,jBk}.5.交換Bk中Aq和Nk中Ap,得新Bk+1和Nk+1,k=k+1,轉(zhuǎn)步驟2.線性規(guī)劃與二次規(guī)劃(3)單純形法的表計算形式線性規(guī)劃與二次規(guī)劃基變量xBxN右端項負函數(shù)值0cNT-cBTB-1N-cBTB-1bxBIB-1NB-1bxB+B-1NxN=B-1bf(x)=cTx=cBTxB+cNTxN

=cBTB-1b+(cNT-cBTB-1N)xN結(jié)束條件:

cNT-cBTB-1N0最優(yōu)解:

x*=(xB,0)T=(B-1b,0)T最優(yōu)值:f(x*)=cBTB-1b在xN中找到下一個進入基變量的分量,在xB中找到下一個出基變量的分量.通過消去法更新表中內(nèi)容,使對于新的xB

和xN

上表仍保持各項數(shù)據(jù)的相應(yīng)意義.表中數(shù)據(jù)項意義:表操作:終止狀態(tài):(3)單純形法的表計算形式—舉例線性規(guī)劃與二次規(guī)劃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.計算bj/ajp:{3/1,2/1,16/1}->min=2/1->

即選出分量q=4.pqx1不變，x2變化引起x4變化(3)單純形法的表計算形式—舉例線性規(guī)劃與二次規(guī)劃基變量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變?yōu)榛兞?3)單純形法的表計算形式—舉例線性規(guī)劃與二次規(guī)劃基變量x1x2x3x4x5右端項-f-800306x3

101-101x2-210102x5600-1114cB0-30更新f系數(shù):c新=c舊-cBTAi,Ai為列向量基變量x1x2x3x4x5右端項-f-8p00306x3q1(1/1)q01-101x2-210102x56(14/6)00-1114第一輪完(3)單純形法的表計算形式—舉例線性規(guī)劃與二次規(guī)劃基變量x1x2x3x4x5右端項-f-8p00306x1

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

101-101x2012-104x500-6518cB-800更新f系數(shù):c新=c舊-cBTAi,Ai為列向量第二輪完(3)單純形法的表計算形式—舉例線性規(guī)劃與二次規(guī)劃基變量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)單純形法的表計算形式—舉例線性規(guī)劃與二次規(guī)劃基變量x1x2x3x4x5右端項-f0020122x110-1/501/513/5x2014/501/528/5x4

00-6/511/58/5cB00-5更新f系數(shù):c新=c舊-cBTAi,Ai為列向量第三輪完因為c=(00201)0,所以,結(jié)束,-f=22,f=-22.線性規(guī)劃與二次規(guī)劃min -2x1-3x2s.t. -x1+x2+x3=3 -2x1+x2+x4=2 4x1+x2

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

基變量x1x2x3x4x5右端項-f-2-30000C1-111003C2-210102C34100116min 3x1-2x2s.t. -x1+x23 -2x1+x22 4x1+x216 x10,x20

初始基本變量(4)初值取法問題:單純形法要求從一個基本可行解開始搜索,怎樣找到第一基本可行解,即為初值問題.條件:

xT=[B-1b0]0

為基本可行解.(4)初值取法線性規(guī)劃與二次規(guī)劃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)初值取法線性規(guī)劃與二次規(guī)劃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).如果原問題有可行解,則輔助問題最優(yōu)值為零;如果輔助問題最優(yōu)值大于零,原問題無解.第二階段:當達到輔助問題的最優(yōu)解,基本變量都變?yōu)閤i,它們可作為原問題初始值.輔助問題(4)初值取法線性規(guī)劃與二次規(guī)劃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,充分大的正實數(shù).初始基本變量為(x3,a1,a2).當基本變量都變?yōu)閤i后,剔除目標函數(shù)和約束中有關(guān)ai,的項,繼續(xù)迭代.輔助問題線性規(guī)劃與二次規(guī)劃線性規(guī)劃問題是一類優(yōu)化問題,其約束函數(shù)為線性,目標函數(shù)是二次.(1)等式約束二次規(guī)劃問題二.二次規(guī)劃minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTxbi,iIminq(x)=(1/2)xTGx+gTxs.t.ATx=b線性規(guī)劃與二次規(guī)劃(1)等式約束二次規(guī)劃問題ATx=b,ABTxB+ANTxN=bxB=AB-T(b-ANTxN)一.直接消去法線性規(guī)劃與二次規(guī)劃(1)等式約束二次規(guī)劃問題二.Lagrange法解上述方程即得:x*,*.1.與K-T條件一致2.對于凸二次規(guī)劃，K-T條件是充分條件線性規(guī)劃與二次規(guī)劃(1)一般凸二次規(guī)劃問題的有效集方法minq(x)=(1/2)xTGx+gTxs.t.aiTx=bi,iE

aiTxbi,iI一.算法思想從初始可行點x0開始,不斷向新的可行解轉(zhuǎn)移,其思路與線性規(guī)劃中單純形方法相似.有效約束集

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

}因為x0可行,所以w0=E{i|aiTx0=bi,iI},

并且aiTx0>bi,iw0G

正定線性規(guī)劃與二次規(guī)劃(1)一般二次規(guī)劃問題的有效集方法終止條件

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條件(對于凸二次規(guī)劃問題,K-T條件是極值的充分條件),即:(注意:I.等式約束不需要i*>0;II.當iw0時,可取i*=0)對于凸二次規(guī)劃，K-T條件是充分條件線性規(guī)劃與二次規(guī)劃條件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如果得上述問題最優(yōu)解為p=0,即x=x0+p=x0為子問題最優(yōu)解.條件1滿足.線性規(guī)劃與二次規(guī)劃條件2判斷:

直接將x0代入aiTxbi

,

iw0.即可驗證.由于每一步迭代已保證x0為原問題可行點,所以,此判斷可免.條件3判斷:

將x0代入求出i*.如果i*0,iIw0,即條件3滿足.對原問題來說,K-T條件是:=00實數(shù)線性規(guī)劃與二次規(guī)劃可行點轉(zhuǎn)移更新:

(1)當條件3不滿足時.即存在j*<0,jIw0,則在子問題中去掉約束ajTx=bj,重新計算局部最優(yōu)解.f大f小P1P2a1a2f1>0,2>0f大f小P1P2a1a2f1>0,2<0x1去掉約束P2有利于極小點向頂點x1轉(zhuǎn)移.(2)條件2始終保證滿足.即每一步假設(shè)x0是可行點,所以條件2始終滿足.線性規(guī)劃與二次規(guī)劃可行點轉(zhuǎn)移更新:

(3)當條件1不滿足時.即p*0時,將x0轉(zhuǎn)移到x1=x