自由模板最優(yōu)化方法課程論文

1、. - - . 可修編. . z. - - . 可修編. *理工學(xué)院最優(yōu)化方法課程論文題目：線性規(guī)劃的單純形算法姓 名：專 業(yè)：統(tǒng)計(jì)學(xué)班 級(jí)：2011級(jí)1班學(xué) 號(hào)：完成日期：2014年6月27日*理工學(xué)院理學(xué)院二O一 四 年 六 月-. z.摘 要線性規(guī)劃是運(yùn)籌學(xué)中研究較早、開(kāi)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)展科學(xué)管理的一種數(shù)學(xué)方法。是研究線性約束條件下線性目標(biāo)函數(shù)的極值問(wèn)題的數(shù)學(xué)理論和方法。為了得到線性目標(biāo)函數(shù)的極值，我們有多重方法。本文采用單純性算法求解線性規(guī)劃問(wèn)題，并通過(guò)Matlab軟件編寫程序進(jìn)展求解。關(guān)鍵詞：線性規(guī)劃 單純性算法 Matlab編程. - -.

2、 z.目 錄 TOC o 1-5 h z u HYPERLINK l _Toc24242 一、 單純性方法簡(jiǎn)介 PAGEREF _Toc24242 1 HYPERLINK l _Toc17343 1.1 單純性方法提出 PAGEREF _Toc17343 1 HYPERLINK l _Toc31101 1.2單純性方法的根本思想和步驟 PAGEREF _Toc31101 1 HYPERLINK l _Toc16127 1.2.1根本思想 PAGEREF _Toc16127 1 HYPERLINK l _Toc14838 1.2.2計(jì)算步驟 PAGEREF _Toc14838 1 HYPERLI

3、NK l _Toc10125 二、問(wèn)題的提出與分析 PAGEREF _Toc10125 1 HYPERLINK l _Toc16512 2.1問(wèn)題提出 PAGEREF _Toc16512 1 HYPERLINK l _Toc6386 2.2問(wèn)題分析 PAGEREF _Toc6386 2 HYPERLINK l _Toc3182 三、程序設(shè)計(jì) PAGEREF _Toc3182 2 HYPERLINK l _Toc18292 3.1算法設(shè)計(jì) PAGEREF _Toc18292 2 HYPERLINK l _Toc29221 3.2算法框圖 PAGEREF _Toc29221 3 HYPERLINK

4、 l _Toc18999 3.3程序編制 PAGEREF _Toc18999 4 HYPERLINK l _Toc14149 四、結(jié)果分析 PAGEREF _Toc14149 6 HYPERLINK l _Toc22331 4.1設(shè)計(jì)結(jié)果 PAGEREF _Toc22331 6 HYPERLINK l _Toc11558 4.2 進(jìn)一步討論和驗(yàn)證 PAGEREF _Toc11558 8 HYPERLINK l _Toc2159 五、完畢語(yǔ) PAGEREF _Toc2159 8 HYPERLINK l _Toc9257 5.1設(shè)計(jì)的優(yōu)缺點(diǎn) PAGEREF _Toc9257 8 HYPERLINK

5、 l _Toc14895 5.2 收獲與總結(jié) PAGEREF _Toc14895 9 HYPERLINK l _Toc9903 參考文獻(xiàn) PAGEREF _Toc9903 10 HYPERLINK l _Toc22250 附錄 PAGEREF _Toc22250 11-. z. - - . 可修編. 單純性方法簡(jiǎn)介1.1 單純性方法提出單純形法，求解線性規(guī)劃問(wèn)題的通用方法。單純形是美國(guó)數(shù)學(xué)家G.B.丹齊克于1947年首先提出來(lái)的,這是20世紀(jì)數(shù)學(xué)界最重大的成果之一。由于這一方法的有效性，幾十年來(lái)一直在幾乎所有的領(lǐng)域得到廣泛應(yīng)用。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是 n維向量空間Rn中的多面凸

6、集，其最優(yōu)值如果存在必在該凸集的*頂點(diǎn)處到達(dá)。頂點(diǎn)所對(duì)應(yīng)的可行解稱為根本可行解。1.2單純性方法的根本思想和步驟1.2.1根本思想單純形法的根本思想是：先找出一個(gè)根本可行解，對(duì)它進(jìn)展鑒別，看是否是最優(yōu)解；假設(shè)不是，則按照一定法則轉(zhuǎn)換到另一改良的根本可行解，再鑒別；假設(shè)仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)展。因根本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。1.2.2計(jì)算步驟 1、對(duì)于一般的的線性規(guī)劃，將其化為標(biāo)準(zhǔn)型； 2、求出初始根本可行解； 3、先檢驗(yàn)其最優(yōu)性； 4、如果不是最優(yōu)的，則從取負(fù)值的非基變量中選取一個(gè)最負(fù)確定為入基變量； 5、選好入基變量后，再在

7、基變量中選取一個(gè)出基變量； 6、選好入基變量和出基變量后，進(jìn)展高斯消去，得到新的可行解； 7、重復(fù)以上過(guò)程，直至找到最優(yōu)解。、二、問(wèn)題的提出與分析2.1問(wèn)題提出本文運(yùn)用單純性算法求解以下問(wèn)題：Ma* s.t 并編寫MATLAB程序求解。2.2問(wèn)題分析在用單純性算法解決現(xiàn)行規(guī)劃問(wèn)題時(shí)，我們通常考察標(biāo)準(zhǔn)形現(xiàn)行規(guī)劃問(wèn)題，其標(biāo)準(zhǔn)形如下：現(xiàn)在將本文所討論的線性規(guī)劃化為標(biāo)準(zhǔn)線性規(guī)劃的形式：Min S.t. 其中 A=2 3 0 1 0 0 0 2 4 0 1 0 3 2 5 0 0 1，三、程序設(shè)計(jì)3.1算法設(shè)計(jì)解，求得，令，計(jì)算目標(biāo)函數(shù)值,以記的第i個(gè)分量；計(jì)算單純性乘子w，,得到,對(duì)于非基變量，計(jì)算判

8、別系數(shù)，令，R為非基變量集合，假設(shè)判別系數(shù)，則得到一個(gè)最根本可行解，運(yùn)算完畢；否則，轉(zhuǎn)到下一步解，得到；假設(shè)，即的每一個(gè)分量均非正數(shù)，則停頓計(jì)算，問(wèn)題不存在有限最優(yōu)解，否則，進(jìn)展步驟4;確定下標(biāo)r，使，為出基變量，為入基變量，用替換，得到新的基矩陣B，返回步驟1。3.2算法框圖開(kāi)場(chǎng)初始可行解令計(jì)算單純形乘子，計(jì)算判別數(shù)非基變量令是得到最優(yōu)解解方程，得到。否是不存在有限最優(yōu)解確定下標(biāo)，是否為進(jìn)基變量，用替換，得到新的基矩陣3.3程序編制A=input(A=);b=input(b=);c=input(c=);format ratm,n=size(A);E=1:m;E=E; F=n-m+1:n;F=

9、F;D=E,F; *=zeros(1,n); if(nm) fprintf(不符合要求需引入松弛變量) flag=0;else flag=1; B=A(:,n-m+1:n); cB=c(n-m+1:n); while flag w=cB/B; panbieshu=w*A-c z,k=ma*(panbieshu); fprintf(b./(BA(:,%d)為,k); b./(BA(:,k)if(z0.000000001) flag=0; fprintf( 已找到最優(yōu)解!n); *B=(Bb); f=cB*B; for i=1:n mark=0;for j=1:mif (D(j,2)=i) mar

10、k=1; *(i)=*B(D(j,1); endendif mark=0 *(i)=0; endend fprintf(基向量為:); * fprintf(目標(biāo)函數(shù)值為:) ; felseif(BA(:,k)0) & (b1(i)/(A(i,k)+eps)temp ) temp=b1(i)/A(i,k); r=i;endend fprintf(*(%d)進(jìn)基，*(%d)退基n,k,D(r,2); B(:,r)=A(:,k); cB(r)=c(k); D(r,2)=k; endendendend四、結(jié)果分析4.1設(shè)計(jì)結(jié)果在命令窗口中輸入： A=2,3,0,1,0,0;0,2,4,0,1,0;3,

11、2,5,0,0,1 b=1200,800,2000得到如下結(jié)果:我們可以看到，程序經(jīng)過(guò)4次換基迭代，得到目標(biāo)函數(shù)的最優(yōu)值為-2600，即目標(biāo)函數(shù)的最小值為-2600。從而，原問(wèn)題的最大值為2600。4.2 進(jìn)一步討論和驗(yàn)證 對(duì)于MATLAB程序的正確性與軟件運(yùn)行的可行性。由于計(jì)算量并不是很大，我們通過(guò)單純性表進(jìn)展手工計(jì)算。經(jīng)過(guò)幾次換基迭代，我們選取的入基變量和出基變量與以上軟件運(yùn)行過(guò)程得到的結(jié)果完全一樣。由此，我們可以認(rèn)定目標(biāo)函數(shù)的最小值為-2600，即原問(wèn)題的最大值為2600。五、完畢語(yǔ)5.1設(shè)計(jì)的優(yōu)缺點(diǎn)設(shè)計(jì)優(yōu)點(diǎn)：設(shè)計(jì)的程序是根據(jù)課本的步驟編寫的；程序的編制能得到正確結(jié)果；編制的程序得到的結(jié)

12、果中具體表達(dá)每一步的出基變量與入基變量，清晰明了；設(shè)計(jì)缺點(diǎn)：不能直觀的反響迭代步數(shù)，如假設(shè)迭代次數(shù)過(guò)多，則想要了解迭代步數(shù)則比擬麻煩；不能給出完整的單純性表。5.2 收獲與總結(jié) 通過(guò)本次課程論文設(shè)計(jì)，讓我對(duì)單純性法有了進(jìn)一步的了解，明確了它的具體思想理論，算法步驟。此外，通過(guò)此次課程設(shè)計(jì)，初次接觸了MATLAB軟件，讓我對(duì)MATLAB軟件有了初步的了解，此次論文的完成，主要是通過(guò)根據(jù)算法設(shè)計(jì)，編制MATLAB程序，通過(guò)MATLAB軟件對(duì)模型求解。因此，此次設(shè)計(jì)的最大問(wèn)題在于怎樣設(shè)計(jì)算法程序，但這對(duì)于我們來(lái)說(shuō)難度還是比擬大，所以，此次的單純性算法程序直接利用網(wǎng)上給出的算法程序進(jìn)展設(shè)計(jì)。但網(wǎng)上的很多程序也存在很多問(wèn)題，需要在