最優(yōu)化理論小結(jié)

學(xué)號：20131221447姓名：施林紅最優(yōu)化理論方法小結(jié)轉(zhuǎn)眼間研一的第一學(xué)期就要結(jié)束了，經(jīng)過三個月的學(xué)習(xí)，我對《最優(yōu)化理論與方法》這門課也有了一定的認(rèn)識與了解。下面是我對這門課的小結(jié)。1.線性規(guī)劃線性規(guī)劃的規(guī)范形式如下TOC\o"1-5"\h\zmaxz=cx+cxHbcx1122nns.t.ax+axHHax<b1111221nn1ax+axHHax<b2112222nn2ax+axHHax<bm11m22mnnmx,x…，x>012,n稱以下形式為標(biāo)準(zhǔn)形式maxz=cx+cxHHcx1122nns.t.ax+axHHax=b1111221nn1ax+axHHax=b2112222nn2ax+axHHax=bm11m22mnnmx,x…，x>012，n其中z為目標(biāo)函數(shù)，xj(j=l‘2,?…,n)為決策變量，cj為價值系數(shù)’(j=1,2,m)為右端項，a為約束系數(shù)。從線性規(guī)劃的標(biāo)準(zhǔn)形式可知，其具有四個特點：目標(biāo)最大化、?j約束為等式、決策變量均非負(fù)、右端項非負(fù)。單純形算法單純形算法的基本思想是有選擇的取基本可行解，即從可行域的一個極點出發(fā)，沿著可行域的邊界移到另一個相鄰的極點，要求新極點的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差。下面是以我自己的理解對單純形算法的步驟所做的歸納：列出初始單純形表2）算出檢驗數(shù)b。j3）確定旋入、旋出變量。先確定旋入變量，旋入變量是取檢驗數(shù)最大所在的那一列對應(yīng)的決策變量；旋出變量是將單純形表中b所在的那一列的各項值除以旋入變量所在列的對應(yīng)值（必須大于0）即得到0，取最小的0值，其對應(yīng)的決策變量作為旋出變量。4）對（b,x,x,x）組成的矩陣作初等行變換，知道選入變量之前所在的的列變?yōu)樾?2n出變量之前所在的列對應(yīng)的值即可。5）如此反復(fù)迭代，直到檢驗數(shù)全為非正則停止。6）從表中得到最優(yōu)解x*和最優(yōu)目標(biāo)值z*。對偶單純形算法對偶單純性算法的基本思想是從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶可行解（檢驗數(shù)均非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負(fù)分量，如果有小于零的分量則進(jìn)行迭代，求另一基本解，此基本解對應(yīng)著另一個基本可行解（檢驗數(shù)非正）。如果得到的基本解的分量均非負(fù)，則該基本解為最優(yōu)解。下面是以我自己的理解對單純形算法的步驟所做的歸納：1）建立初始對偶單純形表，此表要求檢驗數(shù)行各元素一定非正，原規(guī)劃的基本可行解可以有小于零的分量。2）若基本解的所有分量皆非負(fù)，則得到原規(guī)劃的最優(yōu)解，停止計算。若基本解有小于零的的分量b，且b所在行的各系數(shù)a..>0，則原規(guī)劃沒有可行解；若b所在行的iiiji各系數(shù)存在a..<0，則確定最小的x為出基變量，并計算0=min寫a<q[-確r-IarrIarjrk定x為進(jìn)基變量。k3）如此反復(fù)迭代，直至基本解非負(fù)，檢驗數(shù)全為非正則停止。靈敏度分析線性規(guī)劃模型中的參數(shù)常常是估計量，所以在對問題求解之后，需要對這些估計量進(jìn)行

分析，以決定是否需要對所求解進(jìn)行調(diào)整。周圍環(huán)境的變化也會使參數(shù)發(fā)生變化，這些參數(shù)

的變化很可能影響以求得的最優(yōu)值，因此在解決實際問題時，一般要研究最優(yōu)解對數(shù)據(jù)變化

反應(yīng)的程度，以使決策者全面的考慮問題，這就是靈敏度分析所要研究的一部分內(nèi)容。靈敏

度分析考慮價值系數(shù)，資源系數(shù)，約束條件系數(shù)，增加新變量，增加約束條件等的變化對其

的影響。價值系數(shù)的變化有兩種情況，一是非基變量系數(shù)的變化，二是基變量系數(shù)的變化。非基變量系數(shù)的變化。當(dāng)非基變量系數(shù)C變化Ac時，只影響與c有關(guān)的一個檢驗數(shù)H的變化,kkkk對其它的b.沒有影響，變化后的檢驗數(shù)b=◎+Ac，變化后的某一價值系數(shù)為jkkkc<c-b，c-b為c的變化上限。當(dāng)c變化超過此上限時，最優(yōu)解將發(fā)生變化，應(yīng)kkkkkkk求出新檢驗數(shù)h的值，取x為進(jìn)基變量，繼續(xù)迭代求新的解。基變量系數(shù)c變化Ac時，kkll它的變化使n-m非基變量的檢驗數(shù)都發(fā)生變化。為使最優(yōu)解保持不變Aci應(yīng)滿足max]~a'>0><Aca'jI1Iij丿<min~la'<0

a'jImax]~a'>0><Aca'jI1Iij丿<min~la'<0

a'jIj當(dāng)Ac1超過此范圍時’應(yīng)求出n-m個檢驗數(shù)叮選擇其中大于零的檢驗數(shù)對應(yīng)的變量為進(jìn)基變量，繼續(xù)迭代，求新的最優(yōu)解。右端一常數(shù)的變化會影響解的可行性，但不會引起檢驗數(shù)符號變化，由丁B-1b知，會引起最優(yōu)解數(shù)值的變化。最優(yōu)解的變化可以分為以下兩種：一是B-ib>0，即最優(yōu)基B不變（影子價格不變，也就是對偶問題的最優(yōu)解不變）；二是B-"中出現(xiàn)負(fù)分量，這將使最優(yōu)基變化，若最優(yōu)基不變（影子價格不變），這只需要將變化后的b代入B-ib的表r達(dá)式重新計算即可，若B-"中出現(xiàn)負(fù)分量，則只需通過迭代求解新的最優(yōu)基和最優(yōu)解。為使最優(yōu)基不變Ab應(yīng)該滿足J土|?rmax］門iIpIpirir<0〉，當(dāng)Ab超過此范圍時，將r使最優(yōu)解中某個分量小于零，是最優(yōu)基發(fā)生變化。此時可利用對偶單純形法繼續(xù)迭代求新的最優(yōu)解。當(dāng)約束條件中當(dāng)只有一個系數(shù)a變化，并且其為非基變量X的系數(shù)時,ijja的變化只影ij響一個檢驗數(shù)b，為使最優(yōu)解保持不變，改變量Aa.應(yīng)滿足Aa>bjjijijy*i(y*i>0)Aa<罕（y*<0）其中y*為對偶最優(yōu)解的y的第i個分量。ijy*iii增加一個新變量X，其相應(yīng)的目標(biāo)函數(shù)系數(shù)為c，檢驗數(shù)為b

n+in+in+i若b<0,則n+i最優(yōu)解不變，否則在單純形表中加入X歹U,繼續(xù)進(jìn)行單純形法迭代。n+i當(dāng)增加一個約束條件時，現(xiàn)將最優(yōu)解代入該約束式，若滿足該約束條件，則最優(yōu)解不變。

否則將約束條件考慮進(jìn)去，增加一個新行和一個新列（引入松弛變量或人工變量），并通過初

等變換使新表中含有各單位向量，此時相應(yīng)的新基變量的值必小于0，利用對偶單純形算法繼續(xù)迭代求解。2.無約束最優(yōu)化方法無約束最優(yōu)化問題，是指G)問題中S=Rn的情況，為了簡便，記無約束最優(yōu)化問題為(f)minf(x)，其中，f:R”tR。2.1最速下降法最速下降法是求解無約束問題的古老而又基本的方法，在下降算法的模型中，方向取負(fù)梯度方向d(k)=-Vf(x(k))，采用精確的一位搜索，即得到最速下降法。最速下降法的基本思想是從當(dāng)前點x出發(fā)，取函數(shù)f(X)在點x處下降最快的方向作kk為我們的搜索方向。設(shè)f:RnTR，在x可微，Vf(X)豐0，那么，d_Vf(x)是問題_IVf(x)11(p」minf'(x;d)的最優(yōu)解，d是f在在x點的最速下降方向。[s.t.|d|<1最速下降法的流程圖如下：圖2-1最速下降法流程圖其特點是全局最優(yōu)，線性收斂,易產(chǎn)生扭擺現(xiàn)象而造成早停?當(dāng)x(k)距最優(yōu)點較遠(yuǎn)時,速度快，而接近最優(yōu)點時,速度下降.適用于精度要求不高或用于對復(fù)雜函數(shù)尋找一個好的初始點。2.2牛頓法由于最速下降法在最初幾步迭代中函數(shù)值下降很快，但愈接近極值點下降的愈慢。因此，應(yīng)尋找使目標(biāo)函數(shù)下降更快的方法。牛頓法就是一種收斂很快的方法，其基本思路是利用二次函數(shù)近似目標(biāo)函數(shù)，把這個二次函數(shù)的極小點作為新的迭代點。牛頓法的流程圖如下：圖2-2牛頓法流程圖牛頓法的特點是二階收斂，局部收斂。當(dāng)