線性規(guī)劃的單純形算法課程設計論文

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

2、、 單純性方法簡介.1 1.1 單純性方法提出.1 1.2 單純性方法的基本思想和步驟.1 1.2.1 基本思想.1 1.2.2 計算步驟.1 二、問題的提出與分析.1 2.1 問題提出.1 2.2 問題分析.2 三、程序設計.2 3.1 算法設計.2 3.2 算法框圖.3 3.3 程序編制.4 四、結果分析.6 4.1 設計結果.6 4.2 進一步討論和驗證.8 五、結束語.8 5.1 設計的優(yōu)缺點.8 5.2 收獲與總結.9 參考文獻.10 附 錄.11 1、單純性方法簡介 1.1 單純性方法提出 單純形法，求解線性規(guī)劃問題的通用方法。單純形是美國數(shù)學家 g.b.丹齊克于 1947 年首先

3、提出來的,這是 20 世紀數(shù)學界最重大的成果之一。由于這一方法的有效性， 幾十年來一直在幾乎所有的領域得到廣泛應用。 它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n 維向量空間 rn 中的多面凸集，其最 優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。 1.2 單純性方法的基本思想和步驟 1.2.1 基本思想 單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu) 解；若不是，則按照一定法則轉換到另一改進的基本可行解，再鑒別；若仍不是，則 再轉換，按此重復進行。因基本可行解的個數(shù)有限，故經有限次轉換必能得出問題的 最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。 1

4、.2.2 計算步驟 1、對于一般的的線性規(guī)劃，將其化為標準型； 2、求出初始基本可行解； 3、先檢驗其最優(yōu)性； 4、如果不是最優(yōu)的，則從取負值的非基變量中選取一個最負確定為入基變量； 5、選好入基變量后，再在基變量中選取一個出基變量； 6、選好入基變量和出基變量后，進行高斯消去，得到新的可行解； 7、重復以上過程，直至找到最優(yōu)解。 、 二、問題的提出與分析 2.1 問題提出 本文運用單純性算法求解下列問題： max 321 453xxxz s.ts.t 120032 21 xx 80042 32 xx 2000523 321 xxx 0, 321 xxx 并編寫 matlab 程序求解。 2.

5、2 問題分析 在用單純性算法解決現(xiàn)行規(guī)劃問題時，我們通?？疾鞓藴市维F(xiàn)行規(guī)劃問題，其標準形 如下： xcxf t )(min 0,. .xbaxts 現(xiàn)在將本文所討論的線性規(guī)劃化為標準線性規(guī)劃的形式： min 321 453xxxzy s.t. 120032 421 xxx 80042 532 xxx 2000523 6321 xxxx 其中4, 5, 3c a=2 3 0 1 0 0 0 2 4 0 1 0 3 2 5 0 0 1 2000,800,1200b ，6 , 5 , 4 b x3 , 2 , 1 n x 三、程序設計 3.1 算法設計 1、解，求得，令，計算目標函數(shù)值,以 bbxb

6、bbxb 1 0 n x bbx cf 記的第 i 個分量；)m, 2 , 1(ibibb 1 2、計算單純性乘子 w，,得到,對于非基變量，計算判別系數(shù) b cwb 1 bcw b ，令，r 為非基變量集合，若判別系數(shù) iibiii cpbccz 1 ii ri k cz max ，則得到一個最基本可行解，運算結束；否則，轉到下一步0 k 3、解，得到；若，即的每一個分量均非正數(shù)，則停止計算， kk pba kk pba 1 0 k a k a 問題不存在有限最優(yōu)解，否則，進行步驟 4; 4、確定下標 r，使，為出基變量，為入基變量，用 0min rk rk i rk r a a b a b

7、 r b x k x 替換，得到新的基矩陣 b，返回步驟 1。 k p r b p 3.2 算法框圖 是是 否否 是是 否否 開始 初始可行解b 令 1 ,0, bnbb xb bb xfc x 計算單純形乘子，計算判別數(shù)（非基變 1 b wc b, ijj wpcjr 量）令max, kj jr 0? k 得到最優(yōu)解 解方程，得到。 kk pba kk pba 1 ?0 k a 不存在有限最優(yōu)解 確定下標，是r 0min rk rk i rk r a a b a b 3.3 程序編制 a=input(a=); b=input(b=); c=input(c=); format rat m,n=

8、size(a); e=1:m;e=e; f=n-m+1:n;f=f; d=e,f; x=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=max(panbieshu); fprintf(b./(ba(:,%d)為,k); b./(ba(:,k) if(z0.000000001) flag=0; 為進基變量，用替換，得到新的基矩陣 k x k p r b p b fprintf( 已找

9、到最優(yōu)解!n); xb=(bb); f=cb*xb; for i=1:n mark=0; for j=1:m if (d(j,2)=i) mark=1; x(i)=xb(d(j,1); end end if mark=0 x(i)=0; end end fprintf(基向量為:); x fprintf(目標函數(shù)值為:) ; f else if(ba(:,k)0) r=i; end end fprintf(x(%d)進基，x(%d)退基n,k,d(r,2); b(:,r)=a(:,k); cb(r)=c(k); d(r,2)=k; end end end end 四、結果分析 4.1 設計結果

10、 在命令窗口中輸入： a=2,3,0,1,0,0;0,2,4,0,1,0;3,2,5,0,0,1 b=1200,800,2000 0 , 0 , 0 , 4, 5, 3c 得到如下結果: 我們可以看到，程序經過 4 次換基迭代，得到目標函數(shù)的最優(yōu)值為-2600，即目標函數(shù) 的最小值為-2600。從而，原問題的最大值為 2600。 4.2 進一步討論和驗證 對于 matlab 程序的正確性與軟件運行的可行性。由于計算量并不是很大，我們通過 單純性表進行手工計算。經過幾次換基迭代，我們選取的入基變量和出基變量與以上 軟件運行過程得到的結果完全相同。由此，我們可以認定目標函數(shù)的最小值為-2600，

11、即原問題的最大值為 2600。 五、結束語 5.1 設計的優(yōu)缺點 設計優(yōu)點： 1、設計的程序是根據(jù)課本的步驟編寫的； 2、程序的編制能得到正確結果； 3、編制的程序得到的結果中具體體現(xiàn)每一步的出基變量與入基變量，清晰明了； 設計缺點： 1、不能直觀的反應迭代步數(shù)，如若迭代次數(shù)過多，則想要了解迭代步數(shù)則比較麻煩； 2、不能給出完整的單純性表。 5.2 收獲與總結 通過本次課程論文設計，讓我對單純性法有了進一步的了解，明確了它的具體思想理論，算法 步驟。此外，通過此次課程設計，初次接觸了 matlab 軟件，讓我對 matlab 軟件有了初步的 了解，此次論文的完成，主要是通過根據(jù)算法設計，編制 matlab 程序，通過 matlab 軟件對 模型求解。因此，此次設計的最大問題在于怎樣設計算法程序，但這對于我們來說難度還是比較大， 所以，此次的單純性算法程序直接利用網上給出的算