修正單純形法求解約束優(yōu)化問(wèn)題

修正單純形法求解約束優(yōu)化問(wèn)題姓名王鐸學(xué)號(hào)2007021271班級(jí) 機(jī)械078日期2010/6/23—.問(wèn)題分析求解約束優(yōu)化問(wèn)題中，假如目標(biāo)函數(shù)和約束條件都是線性的，像這類約束函數(shù)和目標(biāo)函數(shù)都是線性函數(shù)的優(yōu)化問(wèn)題稱作線性規(guī)劃問(wèn)題。從實(shí)際問(wèn)題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟：根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；由決策變量和所在大道目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；有決策變量所受的限制條件確定決策變量所要滿足的約束條件；求解線性規(guī)劃問(wèn)題的基本方法是單純形法，而本文研究的是修正單純形法。1965年由J.A.Nelder等提出。是在基本單純形優(yōu)化法的基礎(chǔ)上，引入了反射、擴(kuò)展與收縮等操作規(guī)則，變固定步長(zhǎng)推移單純形為可變步長(zhǎng)推移單純形，在保證優(yōu)化精度的條件下，加快了優(yōu)化速度。是各種單純形優(yōu)化法在分析測(cè)試中應(yīng)用最廣的一種。二.數(shù)學(xué)模型1、線性規(guī)劃問(wèn)題的formalization問(wèn)題(1.1)稱為線性規(guī)劃問(wèn)題：x=argmin_xc"Txs.t.Ax=bx>=0 (1.1)其中x為n維列向量，A為m*n的矩陣，b和c分別為m,n維的常數(shù)向量。任意一個(gè)線性不等式組約束下求解線性函數(shù)的最大最小值問(wèn)題都可以歸結(jié)到問(wèn)題(1.1)來(lái)。比如A(i,:)x<=b(i)<=>A(i,:)x+y(i)=b(i)y(i)>=0 (1.2)A(i,:)x>=b(i)<=>A(i,:)x-y(i)=b(i)y(i)>=0 (1.3)x<=>_,〃x—x-xx'>=0x">=0 (1.4)2、單純形法設(shè)m<n,即變量個(gè)數(shù)大于約束的個(gè)數(shù)。(否則若m-n，則(1.1)的約束可能唯一確定x,最優(yōu)問(wèn)題就沒有意義，若m>n，則可能符合約束的x不存在，最優(yōu)問(wèn)題同樣沒有意義。)此時(shí)記A-[B,N],B為m*m的方陣，N為m*(n-m)的矩陣，假設(shè)B非奇異，(奇異的情況后面會(huì)討論)則x=[x_B,x_N「T=[B"-b,0「T滿足(1.1)的約束。所有這樣的x(因?yàn)閷?duì)A進(jìn)行列重排可得到不同的B,也就有不同的N)組成的集合稱為問(wèn)題(1.1)的基解。理論基礎(chǔ)：線性規(guī)劃問(wèn)題(1.1)的滿足約束Ax=b,x>=0的所有x的集合F稱為(1.1)的可行解，則有F是凸多邊形，且問(wèn)題(1.1)的最優(yōu)解如果存在必定可以在F的頂點(diǎn)處找到，且F的頂點(diǎn)是基解的子集，也就是說(shuō)，窮舉基解，則必定可以找到(1.1)的最有解單純形法在已知一個(gè)基解的情況下，通過(guò)一個(gè)規(guī)則來(lái)搜索其他基解得到最優(yōu)解，步驟如下：1、 用非基元素x_N通過(guò)約束表出x_B2、 將x代入目標(biāo)函數(shù)c"Tx得到關(guān)于x_N的線形函數(shù)z_0+z"Tx_N3、 任取x_N中系數(shù)z_i<0的項(xiàng)z_ix_i，增加x_i(因?yàn)榇藭r(shí)x_N=0=>c"Tx=z_0,增加x_i可以使c"Tx=z_0+x_iz_i減小)，若z>=0則該解為最優(yōu)解，結(jié)束。(此時(shí)算法得到最優(yōu)解，有關(guān)證明見《線性規(guī)劃》P36定理3.1)4、x_i增加的步長(zhǎng)必須滿足x>=0的約束。此時(shí)x_N不必考慮，因?yàn)閤_N>=0,而x_B用x_N表出，所以選擇的步長(zhǎng)必須保證x_B>=0,若x_B>=0對(duì)任意的l成立，那么，該問(wèn)題無(wú)最優(yōu)解，因?yàn)閘可以任意大，意味著z_0可以任意小)否則選取的最大步長(zhǎng)將使得x_B中的一個(gè)元素x_r變?yōu)?(詳細(xì)過(guò)程如下)，此時(shí)得到了另一個(gè)基解：以x_B\x_r并上x_i為基的基解。這個(gè)基解得到的函數(shù)值_0'=z_0-z_i*l<z_0l為x_i增加的步長(zhǎng)。這樣目標(biāo)函數(shù)就減小了單純形法每次搜索都保證目標(biāo)函數(shù)的非增性。(也有可能不變，這時(shí)采用最小下標(biāo)法避免循環(huán))。詳細(xì)過(guò)程：[B,N][x_B=bx_N]假設(shè)一個(gè)基解已知：Bx_B+Nx_N=b=>x_B=B“-b-B“-Nx_N (1.5)代入c"Tx:z=c"Tx=c_B"TB“-b-c_B“TB“-Nx_N+c_N“Tx_N(1.6)選擇z_i<0的x_i增加其值，所增加的步長(zhǎng)l滿足x_B>=0，(若不存在這樣的z_i，則得到最優(yōu)解，算法結(jié)束)則有x_B=B“-b-B“-Nx_N-(B")(i,:)*l=B“-b-B"-(B"-N)(i,:)*l>=0(若B"-(B"-N)(i,:)<=0則對(duì)任意的l有x_B>=0,此時(shí)該問(wèn)題無(wú)最優(yōu)解)=>l=min((B"-b)(j)/(B"-N)(i,j), j=1,2,...,m}若l=(B"-b)(r)/(B"-N)(i,r)，則x_r=0,x_i=l把x_i添入x_B，把x_r添入x_N，再用上述過(guò)程進(jìn)行計(jì)算3、有效單純形法每次將x_i入基x_r出基時(shí)，B要變動(dòng)，此時(shí)導(dǎo)致無(wú)論用x_N表示x_B(1.5)還是c"Tx(1.6)都要重新計(jì)算一遍B"-，如何利用B變動(dòng)前后的關(guān)系有效計(jì)算(1.5,1.6)就是有效單純形法所要解決的問(wèn)題。假設(shè)變動(dòng)后的B為B'，B"-為已知。因?yàn)锽'x'_B+N'x'_N=b'所以B"-B'x'_B+B"-N'x'_N=B"-b'=>x'_B=(B"-B')"-(B"-b'-B"-N'x'_N)記 A=[A1,A2..,Am,...,An] 則B=[A1,.Ar.,Am],B'=[A1..,Ai,..Am]因此B"-B'=[B"-A1,B"-A2,..,B"-Ai,..B"-Am]=[e1,e2,..B“-Ai,..,em]（e_i為第i分量為1,其余分量為0的向量）(B-B')-=[e1,e2,..B-Ai,..,em]-我們有[1,0,...,a_1r,...0,0"-0,1,...,a_2r,...0,00,0,...,a_mr,...0,1][1,0,...,-a_1r/a_rr,...0,00,1,...,-a_2r/a_rr,...0,00,1,..., 1/a_rr,...0,00,0,...,-a_mr/a_rr,...0,1]因此計(jì)算（B“-B'廣-很快，同理（1.6）也可以同樣處理。4、初始可行解的計(jì)算上面的單純形法假設(shè)初始給定一個(gè)基解。如果沒有給出一個(gè)基解（比如B不可逆），如何獲得第一個(gè)基解就是這里要解決的問(wèn)題。兩階段法：?jiǎn)栴}（1.1）變?yōu)椋簓=argmin_ye“Tys.t.Ax+y=bx,y>=0 (1.7)e為全1的向量，由于Ax+y=[A,I][x,y「T,因此，可取B=I,基解可以證明如果(1.1)存在可行解x0,則x=x0,y=0為(1.7)的最優(yōu)解，mine"Ty=0如果(1.7)的最優(yōu)解為x=x0,y=0，則x0必定是(1.1)的一個(gè)基解(為何不是一般解？，[A,I]秩為m,x,y中至多m項(xiàng)不為0)。若(1.7)的最優(yōu)解中e"Ty〉0則意味著Ax!=b,(1.1)無(wú)解求出基解后做法和前面一樣5、對(duì)偶定理minimizec"Txs.t.Ax>=b,x>=0(1.8)的對(duì)偶問(wèn)題為maximizeb“Tws.t.A"Tw〈=c,w〉=0(1.9)(1.8)稱為原問(wèn)題，(1.9)稱為對(duì)偶問(wèn)題。考察(1.9)的對(duì)偶問(wèn)題，(1.9)等價(jià)于minimize(-b)^Tws.t.(-A“T)w〉二-c,w>=0根據(jù)(1.8,1.9)的關(guān)系，(1.9)的對(duì)偶問(wèn)題為maximize(-c)“Txs.t.(-A)x〈二-b,x>=0就是(1.8),因此(1.8,1.9)互為對(duì)偶問(wèn)題(1.1)等價(jià)于minimizecTxs.t.Ax>=b-Ax>=-bx>=0即minimizecTxs.t.[A[b-A]x〉二-b]x>=0其對(duì)偶問(wèn)題為maximize[b“T,-b“T][w';w〃]s.t.[A"T,—A"T][w';w〃]〈=c[w';w〃]〉二0令W二w'—w〃則maximizebTws.t.A"Tw<=c(1.10)弱對(duì)偶定理：注意Ax>=b,x>=0,A"Tw〈=c,c>=0則c"Tx>=(A“Tw)“Tx=w"TAx>=w“Tb也就是說(shuō)(1.8,1.9)的任意解x,w滿足c"Tx>=b"Tw這就是對(duì)偶定理，下面證明原問(wèn)題有最優(yōu)解時(shí)，對(duì)偶問(wèn)題也一定有最優(yōu)解，假設(shè)線性規(guī)劃問(wèn)題都標(biāo)準(zhǔn)化為(1.1)，最優(yōu)解為x=[x_B,x_N]=[B“-b,0]?？疾靪=B"-Tc_B，根據(jù)z=c"Tx=cB"TB“-b-cB“TB“-NxN+cN“Tx_N(1.6)x_N的系數(shù)全部為正，此時(shí)達(dá)到最優(yōu)，則-cB"TB“-N+cN"T>=0=>c_N-N"Tw>=0=>A"Tw=[B,N「Tw=[B"Tw;N"Tw]〈=[c_B;c_N]=c因此，w也是(1.10)的可行解。進(jìn)一步由x=[x_B,x_N]=[B'b,0]w"Tb=c_B"TB"-b=c"Tx由弱對(duì)偶定理，w"Tb總是小于c"Tx的，因此當(dāng)它們相等時(shí)，w必為對(duì)偶問(wèn)題的最優(yōu)解對(duì)偶定理：原問(wèn)題和對(duì)偶問(wèn)題中若一方有最優(yōu)解，則另一方也有最優(yōu)解，且兩個(gè)問(wèn)題的最優(yōu)值一致。6、靈敏度分析。主要一個(gè)結(jié)論：在(1.1)中b的微小變化不影響最優(yōu)基的選擇，而b的增加將引起c"Tx的增加，其增加的比例dc"Tx/db_i=w_i，b的減小將引起c“Tx的減小。下面說(shuō)明這一點(diǎn)假設(shè)(1.1)變?yōu)閤=argmin_xc"Txs.t.Ax=b+dbx>=0 (1.11)若，此時(shí)仍成立B"-(b+db)〉=0，即x'=[x'_B,x'_N]=[B"-(b+db),0]〉=0則有c_N“T-c_N“TB"-N〉=0，最優(yōu)條件仍舊滿足(就是c"Tx用x_N表出后，所有系數(shù)非負(fù)仍舊成立)，因此B仍為擾動(dòng)之后的最優(yōu)基。流程圖擴(kuò)張V三.計(jì)算程序function[y,A]=danchun(A,x,y)[m,n]=size(A);ifmin(A(1,1:n-1))<0flag=0;elseflag=1;endwhileflag==0[h1,j]=min(A(1,1:n-1));forp=2:mifA(p,j)<=0|A(p,n)==0q(p-1)=inf;elseq(p-1)=A(p,n)./A(p,j);endend[h2,i]=min(q);y⑴=x(j);i=i+1;A(i,:)二A(i,:)./A(i,j