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

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

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

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

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

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

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

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

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

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

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

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