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

1、學(xué)號(hào)： 姓名：施林紅 最優(yōu)化理論方法小結(jié)轉(zhuǎn)眼間研一的第一學(xué)期就要結(jié)束了，經(jīng)過三個(gè)月的學(xué)習(xí)，我對(duì)最優(yōu)化理論與方法這門課也有了一定的認(rèn)識(shí)與了解。下面是我對(duì)這門課的小結(jié)。1.線性規(guī)劃線性規(guī)劃的規(guī)范形式如下 （1） 稱以下形式為標(biāo)準(zhǔn)形式 （2）其中z為目標(biāo)函數(shù)，（j=1,2,，n）為決策變量, 為價(jià)值系數(shù)，（j=1,2,，m）為右端項(xiàng)，為約束系數(shù)。從線性規(guī)劃的標(biāo)準(zhǔn)形式可知，其具有四個(gè)特點(diǎn)：目標(biāo)最大化、約束為等式、決策變量均非負(fù)、右端項(xiàng)非負(fù)。1.1單純形算法單純形算法的基本思想是有選擇的取基本可行解，即從可行域的一個(gè)極點(diǎn)出發(fā)，沿著可行域的邊界移到另一個(gè)相鄰的極點(diǎn)，要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差

2、。下面是以我自己的理解對(duì)單純形算法的步驟所做的歸納：1） 列出初始單純形表2） 算出檢驗(yàn)數(shù)。3） 確定旋入、旋出變量。先確定旋入變量，旋入變量是取檢驗(yàn)數(shù)最大所在的那一列對(duì)應(yīng)的決策變量；旋出變量是將單純形表中b所在的那一列的各項(xiàng)值除以旋入變量所在列的對(duì)應(yīng)值（必須大于0）即得到，取最小的值，其對(duì)應(yīng)的決策變量作為旋出變量。4） 對(duì)組成的矩陣作初等行變換，知道選入變量之前所在的的列變?yōu)樾鲎兞恐八诘牧袑?duì)應(yīng)的值即可。5） 如此反復(fù)迭代，直到檢驗(yàn)數(shù)全為非正則停止。6） 從表中得到最優(yōu)解和最優(yōu)目標(biāo)值。1.2對(duì)偶單純形算法對(duì)偶單純性算法的基本思想是從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一

3、個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)均非正），所以也可以說是從一個(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ì)算。若基本解有小于零的的分量，且所在行的各系數(shù)，則原規(guī)劃沒有可行解；若所在行的各系數(shù)存在，則確定最小的為出基變量，并計(jì)算確定為進(jìn)基變量。3）如

4、此反復(fù)迭代，直至基本解非負(fù)，檢驗(yàn)數(shù)全為非正則停止。1.3靈敏度分析 線性規(guī)劃模型中的參數(shù)常常是估計(jì)量，所以在對(duì)問題求解之后，需要對(duì)這些估計(jì)量進(jìn)行分析，以決定是否需要對(duì)所求解進(jìn)行調(diào)整。周圍環(huán)境的變化也會(huì)使參數(shù)發(fā)生變化，這些參數(shù)的變化很可能影響以求得的最優(yōu)值，因此在解決實(shí)際問題時(shí)，一般要研究最優(yōu)解對(duì)數(shù)據(jù)變化反應(yīng)的程度，以使決策者全面的考慮問題，這就是靈敏度分析所要研究的一部分內(nèi)容。靈敏度分析考慮價(jià)值系數(shù)，資源系數(shù)，約束條件系數(shù)，增加新變量，增加約束條件等的變化對(duì)其的影響。價(jià)值系數(shù)的變化有兩種情況，一是非基變量系數(shù)的變化，二是基變量系數(shù)的變化。非基變量系數(shù)的變化。當(dāng)非基變量系數(shù)變化時(shí)，只影響與有關(guān)的

5、一個(gè)檢驗(yàn)數(shù)的變化，對(duì)其它的沒有影響，變化后的檢驗(yàn)數(shù)，變化后的某一價(jià)值系數(shù)為-，-為的變化上限。當(dāng)變化超過此上限時(shí)，最優(yōu)解將發(fā)生變化，應(yīng)求出新檢驗(yàn)數(shù)的值，取為進(jìn)基變量，繼續(xù)迭代求新的解。基變量系數(shù)變化時(shí)，它的變化使n-m非基變量的檢驗(yàn)數(shù)都發(fā)生變化。為使最優(yōu)解保持不變應(yīng)滿足，當(dāng)超過此范圍時(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)變化，由知，會(huì)引起最優(yōu)解數(shù)值的變化。最優(yōu)解的變化可以分為以下兩種：一是，即最優(yōu)基B不變（影子價(jià)格不變，也就是對(duì)偶問題的最優(yōu)解不變）；二是中出現(xiàn)負(fù)分量，這將使最優(yōu)基變化，

6、若最優(yōu)基不變（影子價(jià)格不變），這只需要將變化后的代入的表達(dá)式重新計(jì)算即可，若中出現(xiàn)負(fù)分量，則只需通過迭代求解新的最優(yōu)基和最優(yōu)解。為使最優(yōu)基不變應(yīng)該滿足，當(dāng)超過此范圍時(shí)，將使最優(yōu)解中某個(gè)分量小于零，是最優(yōu)基發(fā)生變化。此時(shí)可利用對(duì)偶單純形法繼續(xù)迭代求新的最優(yōu)解。當(dāng)約束條件中當(dāng)只有一個(gè)系數(shù)變化，并且其為非基變量的系數(shù)時(shí)，的變化只影響一個(gè)檢驗(yàn)數(shù)，為使最優(yōu)解保持不變，改變量應(yīng)滿足 其中為對(duì)偶最優(yōu)解的y的第i個(gè)分量。增加一個(gè)新變量，其相應(yīng)的目標(biāo)函數(shù)系數(shù)為，檢驗(yàn)數(shù)為，若0，則最優(yōu)解不變，否則在單純形表中加入列，繼續(xù)進(jìn)行單純形法迭代。當(dāng)增加一個(gè)約束條件時(shí)，現(xiàn)將最優(yōu)解代入該約束式，若滿足該約束條件，則最優(yōu)解不變

7、。否則將約束條件考慮進(jìn)去，增加一個(gè)新行和一個(gè)新列(引入松弛變量或人工變量)，并通過初等變換使新表中含有各單位向量，此時(shí)相應(yīng)的新基變量的值必小于0，利用對(duì)偶單純形算法繼續(xù)迭代求解。2.無約束最優(yōu)化方法無約束最優(yōu)化問題，是指問題中的情況，為了簡(jiǎn)便，記無約束最優(yōu)化問題為，其中，。2.1最速下降法最速下降法是求解無約束問題的古老而又基本的方法，在下降算法的模型中，方向取負(fù)梯度方向，采用精確的一位搜索，即得到最速下降法。最速下降法的基本思想是從當(dāng)前點(diǎn)出發(fā)，取函數(shù)f (x)在點(diǎn)處下降最快的方向作為我們的搜索方向。設(shè)，在可微，那么，是問題的最優(yōu)解，是在在點(diǎn)的最速下降方向。最速下降法的流程圖如下：圖2-1最速下降法流程圖其特點(diǎn)是全局最優(yōu),線性收斂,易產(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)X(k)充分接近x時(shí)，局部函數(shù)可用于正定二次函數(shù)很好地近似，故