自由模板最優(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 四、結果分析 PAGEREF _Toc14149 6 HYPERLINK l _Toc22331 4.1設計結果 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 收獲與總結 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)解；假設不是，則按照一定法則轉換到另一改良的根本可行解，再鑒別；假設仍不是，則再轉換，按此重復進展。因根本可行解的個數(shù)有限，故經(jīng)有限次轉換必能得出問題的最優(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ù)，則得到一個最根本可行解，運算完畢；否則，轉到下一步解，得到；假設，即的每一個分量均非正數(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四、結果分析4.1設計結果在命令窗口中輸入： A=2,3,0,1,0,0;0,2,4,0,1,0;3,

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

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