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

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

2、 z.目 錄 TOC o 1-5 h z u HYPERLINK l _Toc24242 一、 單純性方法簡介 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計算步驟 PAGEREF _Toc14838 1 HYPERLI

3、NK l _Toc10125 二、問題的提出與分析 PAGEREF _Toc10125 1 HYPERLINK l _Toc16512 2.1問題提出 PAGEREF _Toc16512 1 HYPERLINK l _Toc6386 2.2問題分析 PAGEREF _Toc6386 2 HYPERLINK l _Toc3182 三、程序設計 PAGEREF _Toc3182 2 HYPERLINK l _Toc18292 3.1算法設計 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設計結(jié)果 PAGEREF _Toc22331 6 HYPERLINK l _Toc11558 4.2 進一步討論和驗證 PAGEREF _Toc11558 8 HYPERLINK l _Toc2159 五、完畢語 PAGEREF _Toc2159 8 HYPERLINK l _Toc9257 5.1設計的優(yōu)缺點 PAGEREF _Toc9257 8 HYPERLINK

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

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

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

8、別系數(shù)，令，R為非基變量集合，假設判別系數(shù)，則得到一個最根本可行解，運算完畢；否則，轉(zhuǎn)到下一步解，得到；假設，即的每一個分量均非正數(shù)，則停頓計算，問題不存在有限最優(yōu)解，否則，進展步驟4;確定下標r，使，為出基變量，為入基變量，用替換，得到新的基矩陣B，返回步驟1。3.2算法框圖開場初始可行解令計算單純形乘子，計算判別數(shù)非基變量令是得到最優(yōu)解解方程，得到。否是不存在有限最優(yōu)解確定下標，是否為進基變量，用替換，得到新的基矩陣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(目標函數(shù)值為:) ; felseif(BA(:,k)0) & (b1(i)/(A(i,k)+eps)temp ) temp=b1(i)/A(i,k); r=i;endend fprintf(*(%d)進基，*(%d)退基n,k,D(r,2); B(:,r)=A(:,k); cB(r)=c(k); D(r,2)=k; endendendend四、結(jié)果分析4.1設計結(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)過4次換基迭代，得到目標函數(shù)的最優(yōu)值為-2600，即目標函數(shù)的最小值為-2600。從而，原問題的最大值為2600。4.2 進一步討論和驗證 對于MATLAB程序的正確性與軟件運行的可行性。由于計算量并不是很大，我們通過單純性表進展手工計算。經(jīng)過幾次換基迭代，我們選取的入基變量和出基變量與以上軟件運行過程得到的結(jié)果完全一樣。由此，我們可以認定目標函數(shù)的最小值為-2600，即原問題的最大值為2600。五、完畢語5.1設計的優(yōu)缺點設計優(yōu)點：設計的程序是根據(jù)課本的步驟編寫的；程序的編制能得到正確結(jié)果；編制的程序得到的結(jié)

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