單純形法的綜述及其應用[畢業(yè)論文]

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　　（20 屆）</b></p><p>　　單純形法的綜述及其應用</p><p>　　所在學院 </p><p>　　專業(yè)班級 數(shù)學與應用數(shù)學

2、 </p><p>　　學生姓名 學號 </p><p>　　指導教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要：單純形法是解線性規(guī)劃問題的一種重要方法，也是最主要的算法，本文

3、首先介紹單純形法的歷史背景，然后主要闡述了單純形法的一些基本計算步驟，指出單純形法在解決線性規(guī)劃問題時一般形式、最簡單單純形表的結構，并通過一些具體的題目說明單純形法的基本要點．另外，介紹了解一般線性規(guī)劃問題中引入人工變量的方法，即大M法和兩階段法．以及一些改進的計算方法和計算機算法．最后，介紹了單純形法在一些實際的線性規(guī)劃問題中的應用．</p><p>　　關鍵詞：線性規(guī)劃；最優(yōu)解；單純形法；人工變量</

4、p><p>　　Review of the Simplex Method and Its Application</p><p>　　Abstract：The simplex method is an important method and also is the primary algorithms in solving the linear program problem. This t

5、ext introduced the historical background of simplex method and mainly discussed some basic calculation steps of the simplex method, pointed out the common form and the simplest structure of simplex tableau about the simp

6、lex method in solving linear program problem, and introduced the basic points of the simplex method by some idiographic topics. Then the text introdu</p><p>　　Key words: Linear Programming; Optimum Solution;

7、 Simplex Method; Artificial Variables</p><p><b>　　目 錄</b></p><p><b>　　1 前 言1</b></p><p>　　2 單純形法的原理1</p><p>　　2.1 線性規(guī)劃問題解的概念1</p>

8、<p>　　2.2 單純形法的計算步驟2</p><p>　　2.3 初始基可行解的確定3</p><p>　　2.4 最優(yōu)性檢驗與解的判別5</p><p>　　3 單純形法的計算6</p><p>　　3.1 單純形表的計算步驟6</p><p>　　3.1.1 單純形表6<

9、;/p><p>　　3.1.2 計算步驟7</p><p>　　3.2 人工變量10</p><p>　　3.2.1 大M法10</p><p>　　3.2.2 兩階段法13</p><p>　　3.3 單純形法的改進的計算方法16</p><p>　　3.3.1 基于矩陣初等

10、變換初始可行解得算法16</p><p>　　3.3.2 對偶單純形法18</p><p>　　4 單純形法的計算機算法21</p><p>　　5 單純形法的應用22</p><p>　　5.1 單純形法在企業(yè)資源配置中的應用23</p><p>　　5.2 單純形法在城市軌道列車惰行點搜索中的應

11、用24</p><p>　　6 總 結25</p><p>　　致 謝錯誤!未定義書簽。</p><p><b>　　參考文獻26</b></p><p><b>　　1 前 言</b></p><p>　　線性規(guī)劃(Linear Programming,簡

12、寫LP)是運籌學的一個重要分支，早在20世紀30年代末，前蘇聯(lián)著名的數(shù)學家康托洛維奇就提出了線性規(guī)劃的數(shù)學模型．它是研究較早、理論較完善、應用最廣泛的一個科學．它所研究的問題主要包括兩個方面：一是在一項任務確定后，如何以最低成本（如人力、物力、資源和時間等）去完成這一任務；二是如何在現(xiàn)有資源條件下進行組織和安排，以產生最大收益．因此，線性規(guī)劃是一組變量的值，使它滿足一組線性式子，并且是一個線性函數(shù)的最大值（最小值）的數(shù)學方法．線性規(guī)劃不

13、僅僅是一種數(shù)學理論和方法，而且已成為現(xiàn)代管理工作中幫助管理者作出科學決策的重要手段[1]．線性規(guī)劃也是運籌學的一個基本分支，越來越來受到人們的重視．特別是計算機的發(fā)展和普及，線性規(guī)劃如虎添翼，計算能力得到飛速提高，使得它的應用領域更加廣泛[2]．</p><p>　　而后于1947 年由美國數(shù)學家G. B. Duntzg提出一般線性規(guī)劃問題的求解方法——單純形法，它是線性規(guī)劃(Linear Programming

14、,簡寫LP) 問題的通用解法．為線性規(guī)劃的理論與計算奠定了基礎．更使線性規(guī)劃得以迅速的發(fā)展，可用計算機來處理成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃問題，在工業(yè)、農業(yè)、商業(yè)、運輸業(yè)以及決策分析部門都可以發(fā)揮作用．從范圍來看，小到一個班級的計劃安排，大到整個部門，以至國民經(jīng)濟計劃的最優(yōu)化方案分析，它都有用武之地．線性規(guī)劃具有適應性強、應用面廣、計算技術比較簡單的特點[1]．從而使得線性規(guī)劃的應用領域更加的廣泛．線性規(guī)劃這一學科也因此開始形

15、成并迅速地發(fā)展起來．</p><p>　　單純形方法與經(jīng)典分析的方法很不相同，它利用了矩陣的初等變換，通過部分枚舉的方法來尋求線性規(guī)劃問題的最優(yōu)基可行解，從而求得值．由于這種方法運算簡單又有規(guī)則，且適用性廣泛．所以它的應用迅速得到發(fā)展，根據(jù)它而編制的程序已在一些計算機上開發(fā)實現(xiàn)．值得指出的是，盡管單純形法避開了經(jīng)典極值問題常用的微分法，但是單純形法的最優(yōu)性條件仍可用微分法導出[3]．</p><

16、;p>　　本文主要在于介紹單純形法的歷史背景，基本計算方法，改進的計算方法，以及單純形法的應用．目的在于對單純形法的歷史背景，計算方法等進行綜述，并總結單純形法在生活各個領域的應用，單純形法是求解線性規(guī)劃問題很有效的方法，通過對單純形法的進一步了解，最后提出一些實際問題利用單純法進行分析求解．</p><p>　　2 單純形法的原理</p><p>　　由于越來越多的領域借助于線性

17、規(guī)劃來做出最優(yōu)決策，所以完善線性規(guī)劃理論及其有效解法已成為重要研究課題．單純形法作為求解線性規(guī)劃問題較實用而有效的算法已在實際中得到廣泛應用．</p><p>　　2.1 線性規(guī)劃問題解的概念</p><p>　　LP問題的一般形式[4]</p><p>　　線性規(guī)劃問題的標準型為[2]</p><p><b>　　其矩陣形式為&

18、lt;/b></p><p><b>　　其中，，決策向量．</b></p><p>　　為約束條件中的系數(shù)矩陣, 即</p><p>　　本文除了介紹線性規(guī)劃問題的一般形式、標準形式和矩陣形式以外還列舉了一些定義.</p><p>　　定義1[5]：設矩陣的秩為，矩陣是中的一個階滿秩子方陣，則為一個基矩陣．矩陣中

19、剩余元素組成的子陣為,即.把的分量相應地分成兩部分，記成和，的分量與的列對應，稱為基變量；的分量與中的列對應，稱為非基變量．在約束中令所有的非基變量取值為零時，得到解，稱為相應于的基本解．</p><p>　　定義2[5]：基本解得基變量都取非負值時，即滿足的基本解為基本可行解．</p><p>　　定義3[6]：滿足式（1）各約束條件的解稱為可行解.全部可行解的集合稱為可行域.目標函數(shù)達

20、到最大值的可行解稱為最優(yōu)解.</p><p>　　定義4[6]：設為約束方程組的階系數(shù)矩陣，設(),其秩為，為矩陣中的一個階的滿秩子矩陣，稱為線性規(guī)劃問題的一個基.不失一般性，設</p><p>　　中每一個向量稱為基向量；與基向量對應的變量稱為基變量.基變量以外的的變量稱為非基變量.</p><p>　　定義5[6]：在約束方程組中，令所有非基變量</p&g

21、t;<p><b>　　.</b></p><p>　　此時約束方程組有唯一解.將此解加上非基變量?。暗闹担?，稱為線性規(guī)劃問題的基本解.基本解總數(shù)不超過個.</p><p>　　2.2 單純形法的計算步驟</p><p>　　我們利用單純形法來求解它．它的理論根據(jù)是：線性規(guī)劃問題的可行域是n維向量空間Rn中的多面凸集，其最優(yōu)值

22、如果存在，必在該凸集的某頂點處達到．頂點所對應的可行解稱為基本可行解．單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是，則再轉換,按此重復進行．因基本可行解的個數(shù)有限，故經(jīng)有限次轉換必能得出問題的最優(yōu)解．如果問題無最優(yōu)解也可用此法判別．</p><p>　　現(xiàn)在把單純形法的的計算步驟歸納如下：</p><

23、;p>　　第一步：對于一個已知的可行基，寫出B對應的典式以及對應的基可行解，．</p><p>　　第二步：檢查檢驗數(shù)，如果所有檢驗數(shù) （j=1,2,…,n）則便是最優(yōu)解，計算結束，否則轉下一步．</p><p>　　第三步：如果有檢驗數(shù)，而，則問題無最優(yōu)解，計算結束，否則轉下一步．</p><p>　　第四步：如果有檢驗數(shù)，且中有正數(shù)，則取為進基變量（若

24、有多個正檢驗數(shù)，可任選一個，一般來說選取最大的檢驗數(shù)有利于提高迭代效率），并求最小比值 </p><p>　　由此來確定為離基變量（若上述最小比值同時在幾個比值上達到，則選取其中下標最小的變量為離基變量），然后用代換得新基，再接下一步．</p><p>　　第五步：求出新基的典式（計算或直接通過初等行變換來實現(xiàn)）以及對應的基可行解，</p><p>　　然后，以取代

25、B，取代，返回第二步[7]．</p><p>　　2.3 初始基可行解的確定</p><p><b>　　若線性規(guī)劃問題</b></p><p><b>　　目標函數(shù) </b></p><p>　　從中一般能找到一初始可行基</p><p>　　對于所有的約束條件是形式的不

26、等式，可以利用化為標準型的方法，在每一個約束條件的左端加上一個松弛變量．經(jīng)過整理，重新對進行編號，則可得下列方程式</p><p><b>　　得到矩陣 </b></p><p><b>　　以作為可行基，可得</b></p><p><b>　　令，可得</b></p><

27、p>　　又因，所以可得到一個初始基可行解</p><p><b>　?。?lt;/b></p><p>　　2.4 最優(yōu)性檢驗與解的判別</p><p>　　對于線性規(guī)劃問題的求解結果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況．</p><p>　　代入目標函數(shù)，整理后得</p><

28、p><b>　　令</b></p><p><b>　　于是</b></p><p><b>　　再令</b></p><p><b>　　則</b></p><p><b>　　.</b></p><p&g

29、t;　　1.最優(yōu)解的判別定理</p><p>　　若 為對應于B的一個基可行解，且對一切有，則為最優(yōu)解，稱為檢驗數(shù)．</p><p>　　2.無窮多最優(yōu)解判別定理</p><p>　　若為一個可行解，對于一切有，又存在某個非基變量的檢驗數(shù)，則線性規(guī)劃問題有無窮多最優(yōu)解．</p><p><b>　　3.無界解判別定理</b&g

30、t;</p><p>　　若為一個可行解，有一個，并對,有，那么該線性規(guī)劃問題具有無界解[8]．</p><p>　　3 單純形法的計算</p><p>　　通常，在求解LP模型時，常用基本單純形表、大M法、兩階段法等，所以本文具體介紹了求解線性規(guī)劃的單純形法的一些計算方法．根據(jù)對模型中是否存在單位基矩陣、存在怎么樣的基矩陣等特征的判斷來選擇方法或判斷解的存在與否

31、等情況．這就是說，在求解線性規(guī)劃的單純形法中，初始基(矩陣)的確定是一個基本問題．通常使用大M法和兩階段法，通過人工構造，人為地在系數(shù)矩陣中形成一個單位矩陣作為初始基，再進行單純形法的迭代[9]．</p><p>　　3.1 單純形表的計算步驟</p><p>　　3.1.1 單純形表</p><p>　　線性規(guī)劃式(1-1)、式（1-2）和相應的基可行解，檢驗

32、數(shù)等內容可以用表1-1來表示</p><p><b>　　表1-1示例</b></p><p>　　表1-1稱為單純形表，它的右半部第二行指明各個變量的位置，第一行是它們的價值系數(shù)，其下面m行是（1-2）的系數(shù)矩陣，它包括一個m階單位陣．左半部3列中，是式（1-2）的右端常數(shù)，列依次標明各方程的基變量，是相應的價值系數(shù)．表的最后一行稱為檢驗數(shù)，填寫各個變量的檢驗數(shù)．單

33、純性表的主要部分是約束方程組的增廣矩陣和檢驗數(shù)行．應注意的是，系數(shù)矩陣中必須包含一個m階單位陣．</p><p>　　單純形表的便利之處首先在于，從表中可以直接讀出基可行解；相應的目標函數(shù)值列與b列元數(shù)乘積之和：其次，每個變量（包括基變量在內）的檢驗數(shù)等于減去列元數(shù)與表中的系數(shù)列向量元數(shù)成績之和：．更有益的是，單純形法的全部分析和計算過程，可以比較方便地在單純形表中完成[10]．</p><p

34、>　　3.1.2 計算步驟</p><p>　　第一步：將數(shù)學模型化為規(guī)范型，找出初始可行基，確定初始基本可行解，建立初始單純形表．</p><p>　　第二步：檢驗各非基變量的檢驗數(shù)，，若所有的則已得到最優(yōu)解，可停止計算；否則轉入下一步．</p><p>　　第三步：在所有的中，若有一個（即對均有），則此問題無解，停止計算；否則轉入下一步．</p&g

35、t;<p>　　第四步：根據(jù)，確定為換入變量，按規(guī)則計算</p><p>　　可以確定為換出變量，轉入下一步．</p><p>　　第五步：以為主元素進行迭代（即用高斯消去法或稱為旋轉運算）把所對應的列向量</p><p><b>　　第行</b></p><p>　　將列中的換為，得到新的單純形表．重復第

36、二步到第五步一直到最優(yōu)解為止．</p><p><b>　　例1:</b></p><p>　　用單純形表計算求解．</p><p>　　解：（1）化成標準型</p><p>　　取松弛變量為基變量，對應的單位矩陣為基．得到初始基可行解</p><p>　　將有關數(shù)字填入表中，得到初始單純形表，見

37、表1．</p><p><b>　　表1</b></p><p>　　在表1左上角是表示目標函數(shù)中各變量的價值系數(shù)．在列填入初始基變量的價值系數(shù)，它們都為零，各非基變量的檢驗數(shù)為</p><p>　　（2）因為檢驗數(shù)都大于零，而且有正分量存在，轉入下一步：</p><p>　?。?），對應的變量為換入變量，計算</

38、p><p>　　它所對應的為換出變量．所在的列和所在的行交叉[2]為主元素．</p><p>　　（4）以[2]為主元素進行初等行變換，使變換為,在列中將替換，得到新表2．</p><p><b>　　表2</b></p><p>　　得到新基，目標函數(shù)的取值．</p><p>　　（5）檢查表2的所

39、有，有；所以為換入變量．重復（2）~（4）的計算步驟，得到表3．</p><p><b>　　表3</b></p><p>　　最后一行的所有檢驗數(shù)都為負數(shù)或零，這表示目標函數(shù)已不可能再增大，于是得到最優(yōu)解</p><p><b>　　3.2 人工變量</b></p><p>　　利用單純性表求解

40、線性規(guī)劃的前提是，已知初始基可行解，及約束方程組的系數(shù)矩陣A中包含m階單位陣．不是所有的例題都是約束全為“”型、松弛變量正好構成初始基變量或者從方程組中容易看出初始基變量．一般情況下，往往難以看出哪些變量可以沖當這個角色．任意選擇m個變量進行試探，顯然不是好的方法．通常的做法是引入人工變量，人為地構造一組初始變量．具體的處理方法有大M法和兩階段法兩種不同的形式．</p><p>　　3.2.1 大M法</

41、p><p>　　為了解線性規(guī)劃問題 需要一個初始基可行解，為此常常借助于大M法或兩階段法．</p><p>　　大M法：在一個線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對目標函數(shù)取值不受影響，為此假定人工變量在目標函數(shù)中的系數(shù)為（-M）（M為任意大的正數(shù)），這樣目標函數(shù)要實現(xiàn)最大化時，必須把人工變量從基變量換出．否則目標函數(shù)不可能實現(xiàn)最大化．</p><p>

42、;　　例2：求下列線性規(guī)劃問題的最優(yōu)解．</p><p>　　解 ：引入松弛變量，把問題化為標準形式的線性規(guī)劃（簡稱）．</p><p>　　給后兩個方程分別添加人工變量，使得約束方程組化為</p><p>　　變量構成初始變量．但是只有，新約束方程組才與原來的方程組等價.為了迫使轉化為0，在目標函數(shù)中令的系數(shù)是任.意大正數(shù)M的相反數(shù)-M（如果求最小值，應取為M）.

43、這樣得到一個新的線性規(guī)劃問題（記為）．</p><p>　　只要人工變量取正，不可能實現(xiàn)最大值，因為中包含取值可任意小的項．更準確的說，問之間有下列關系．</p><p><b>　　設</b></p><p>　　若有最優(yōu)解，則與是的最優(yōu)解．</p><p>　　若有最優(yōu)解與，則是的最優(yōu)解；如果最優(yōu)解中，則無可行解．&

44、lt;/p><p>　　下面列表求的最優(yōu)解．</p><p>　　故得最優(yōu)解為；因此原線性規(guī)劃問題無可行解．</p><p>　　3.2.2 兩階段法</p><p>　　在許多線性規(guī)劃問題中，引進松弛變量化成標準形式后，約束條件方程組的系數(shù)矩陣并不含m階單位矩陣，這樣就給單純形解法的換基迭代帶來了困難，為了很快找到第一個可行基，在利用單純形法

45、求解時，首先要在線性規(guī)劃問題中引入人工變量，把問題變?yōu)榧s束方程組的系數(shù)矩陣中含有單位陣，用以作為人造基，然后再按照單純形法進行換基迭代，求得最優(yōu)解或判定無最優(yōu)解．這種方法就稱為兩階段法．</p><p>　　第一階段：不考慮原問題是否存在基可行解；給原線性規(guī)劃問題加入人工變量，并構造僅含人工變量的目標函數(shù)和要求實現(xiàn)最小化．如</p><p><b>　?。?lt;/b>&l

46、t;/p><p>　　然后用單純形法求解上述模型，若得到，這說明原問題存在基可行解，可以進行第二段計算．否則原問題無可行解，應停止計算．</p><p>　　第二階段：將第一階段計算得到的最終表，除去人工變量．將目標函數(shù)行的系數(shù)，換原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表．</p><p>　　繼續(xù)討論例題2中的線性規(guī)劃問題的求解問題．</p>&l

47、t;p>　　兩階段法是另一種處理人工變量的方法．它的第一階段是先解決輔助問題：</p><p>　　當單純性法求解時，若最優(yōu)解中人工變量全為0，，人工變量全部退出基，說明各方程的基變量時非人工變量，從而得到問題的基可行解．刪去最優(yōu)表中人工變量各列，把目標函數(shù)系數(shù)換成原來的z的系數(shù)，即得的初始表．然后解決問題．若最優(yōu)解中人工變量不全為0，則無可行解[11]．</p><p><b

48、>　　的計算過程如表</b></p><p>　　最優(yōu)解中人工變量不全為0，停止計算無法進行第二階段，則無可行解．再來看下面一個例題．</p><p>　　例3：求下列線性規(guī)劃問題的最優(yōu)解．</p><p><b>　?。?lt;/b></p><p>　　解 ：先在上述線性規(guī)劃問題的約束方程中加入人工變量，

49、給出第一階段模型為：．</p><p>　　最優(yōu)表中，人工變量已全部退出基．去掉最優(yōu)表中兩列，把目標函數(shù)系數(shù)換成z的系數(shù)，繼續(xù)第二階的計算．</p><p><b>　　最后的的最優(yōu)解，．</b></p><p>　　大法與兩階段法都是從尋求線性規(guī)劃問題的一個初始可行基引入的．從形式上看，它們是兩種不同的方法，但在本質上是一致．</p&g

50、t;<p>　　3.3 單純形法的改進的計算方法</p><p>　　3.3.1 基于矩陣初等變換初始可行解得算法</p><p>　　通常使用大M法和兩階段法，通過人工構造，人為地在系數(shù)矩陣中形成一個單位矩陣作為初始基，再進行單純形法的迭代．這樣，往往無意中擾亂了思想主線，增加了計算量．特別對于人工計算顯得運算操作繁雜而偏離了主體，在理解和教學中常常帶來不便．通過對單純

51、形法求解法的實質的分析和認識，提出了基于矩陣初等變換初始可行基的獲得方法，進而得到基于單純形法的求解線性規(guī)劃模型的直接方法使單純法的運用簡單明白．</p><p>　　利用這種確定初始可行基的方法求解線性規(guī)劃問題時，首先，對線性規(guī)劃模型（2）的系數(shù)增廣矩陣進行上述的初等行變換而得到階的初始可行基，接著，將所得初始可行基安排入單純形表，然后，進行單純形表的表上作業(yè)程序．這樣做的優(yōu)點不僅在于可以給出初始可行基，而且可

52、以方便地發(fā)現(xiàn)不獨立的約束，并將其提前剔除，以減少單純形法的計算量．具體步驟為:</p><p>　　步驟1 對增廣矩陣施行一系列的初等行變換，并始終保持可行性(即：列非負)，直到中含有單位矩陣；這里需要注意的是當變換到可以使某一行元素全部為時，說明約束方程組不獨立，可以降維為，那么，所得到的單位矩陣也就是階的，并非一定要得到的階的單位矩陣作為基．</p><p>　　步驟2 將步驟1的結果

53、安排到一個單純形表中，并以中的單位矩陣的列所相應的變量為基變量而得到初始單純形表．</p><p>　　步驟3 在步驟2的所得的單純形表上按照通常的單純形表上作用法進行求解．</p><p>　　需要說明的是，在步驟1中完全可以不用第一類初等行變換(交換任兩行的位置)，而只用第二、三類初等行變換就可以實現(xiàn)．該方法的優(yōu)勢在于思想清晰，方法簡明，計算量減?。?lt;/p><p&

54、gt;　　有了初始可行基，就可從這個可行基相應的基本可行解出發(fā)進行換基迭代，從而，求得目標函數(shù)的最優(yōu)解或判斷其無最優(yōu)解[9]．</p><p><b>　　例4：求解</b></p><p>　　解：首先，對系數(shù)增廣矩陣作保持可行性的初等行變換：</p><p>　　然后，安排初始單純形表并進行單純形求解如下：</p><p

55、>　　于是，得到最優(yōu)解及最優(yōu)值．</p><p>　　此方法的優(yōu)勢在于思路清晰，方法簡明．在運用單純形法時只要借助于線性代數(shù)的初等行變換及在以單位陣為初始基的單純形法就可以順利地求解任何線性規(guī)劃模型，不需要判斷選擇兩階段法或大M法等．</p><p>　　3.3.2 對偶單純形法</p><p>　　對偶單純形法的思路，則是保持其對偶變量的解為可行解，即．然

56、后從原問題的一個基解（此時基解不一定為基可行解）出發(fā)，然后檢驗其是否為基可行解，若是基可行解，則得最優(yōu)解，否則進行迭代（基變換），迭代過程中保持其對偶變量的解為可行解（），得到一個新的基解，再判斷、迭代，直到求得最優(yōu)解[12]．具體步驟為：</p><p>　　第一步：根據(jù)線性規(guī)劃對偶可行問題，列出初始單純形表．檢驗列的數(shù)字，若都為非負，檢驗數(shù)都為非正，則以得到最優(yōu)解，停止計算．若檢驗列數(shù)字時，至少還有一個負分量

57、，同時在檢驗數(shù)中至少還有一個檢驗數(shù)保持非正，那么進行第二步；</p><p>　　第二步：確定換出變量．按所確定對應的基變量為換出變量；</p><p>　　第三步：確定換入變量．在單純形表中檢查所在的行的各系數(shù)，若所有，則無可行解，停止計算：若存在，計算</p><p>　　按最小比值法則所對應的列的非基變量為換入變量；</p><p>　

58、　第四步：以為主元素，按原來的單純形法在表中進行迭代運算；</p><p>　　第五步：重復第一至第四步[13]．</p><p>　　例5：用對偶單純形法求解線性規(guī)劃問題</p><p><b>　　．</b></p><p>　　解：第一步，把原問題變形為</p><p>　　第二步，初始單純

59、形表．</p><p>　　第三步，確定出基變量和進基變量．</p><p>　　因為，所以為出基變量；由最小比值法知</p><p>　　則為進基變量，主元素為“-7”．</p><p>　　第四步，進行迭代得到</p><p>　　第五步，由新的單純形表，計算檢驗數(shù)，確定新的出基變量和進基變量，繼續(xù)迭代，知道求出最

60、優(yōu)解．</p><p>　　因為，所以為出基變量；由最小比值法知</p><p>　　則為進基變量，主元素為“-13/7”,迭代得到</p><p>　　原問題的解轉變成了可行解，且對應的對偶問題的解任可行（即檢驗數(shù)為非正），因此原問題的最優(yōu)解為</p><p>　　對偶單純形法與原始單純形法兩種求解原問題的方法的主要區(qū)別在于：原始單純形法在

61、整個迭代過程中，始終保持原問題的可行性即，達到最優(yōu)解時檢驗數(shù)為止，而也就是，即，所以原始單純形法實質就是在保證原問題可行的條件下向對偶問題可行的方向迭代．而對偶單純形法在整個迭代過程中，始終保持對偶問題的的可行性即，也始終保持所有檢驗數(shù)，最后達到最優(yōu)解時即滿足原問題的可行性為止，所以對偶單純形法實質就是保證對偶問題可行的條件下向原問題可行的方向迭代．</p><p>　　對偶單純形法與原始單純形法相比有以下兩個顯

62、著的優(yōu)點．</p><p>　?。?）初始解時非可行解．當檢驗數(shù)都非正時，可以進行基變換，這時不需要引進人工變量，簡化了計算．</p><p>　?。?）對于變量個數(shù)多于約束方程個數(shù)的線性規(guī)劃問題，采用對偶單純形法計算量少．因此對于變量較少、約束較多的線性規(guī)劃問題，可用對偶單純形法求解[4]．</p><p>　　4 單純形法的計算機算法</p>&

63、lt;p>　　利用數(shù)學計算工具來解決單純形法中計算的難題，其應用價值和推廣價值是可觀的，不僅可以提高計算速度，而且可以大大提高計算的準確性．</p><p><b>　　求解思路：</b></p><p>　　首先把它變?yōu)槿缦?左式) 標準形式: </p><p>　　然后對進行標準化, 記,如果是只有一個分量為1的單位向量，那么把第一行

64、中的通過矩陣變換，變成0，標準化完成.．標準化的目的是將第一行中的系數(shù)變?yōu)闄z驗數(shù), 其中非基變量系數(shù)均為0，基變量的系數(shù)則未必為0．</p><p>　　接著對進行變換, 首先在矩陣的第一行第1到第個分量中找出一個最大數(shù)，如果這個最大數(shù)不大于0，則不用進行再次迭代，直接得到最終變換矩陣．反之，用記下最大數(shù)所對應的列．然后進行判斷：如果的第列的第2至第個數(shù)全都小于或等于0，那么此線性規(guī)劃問題無界，迭代結束．反之，用

65、的最后一列的第2至第個分量分別除以第列對應的數(shù)，如果碰到除數(shù)小于或等于0 則跳過. 在所得結果中找出最小的那個數(shù)，用j記下該數(shù)所對應的行．于是得到主元素 接下來是對第 行進行行變換，將P( j , k) 變?yōu)?．然后對其他行進行行變換，使矩陣的第k 列的其他分量都變?yōu)? ，于是第一輪變換結束．接下來回到變換過程的開始，重復迭代過程至到跳出迭代過程為止，最后對結果矩陣進行智能分析．其中需要人工進行的步聚是構造計算矩陣和分析迭代結果兩步，以

66、使求解過程比較簡便且可靠性高[15]．</p><p><b>　　主要程序為：</b></p><p><b>　　主程序 </b></p><p><b>　　子程序1 </b></p><p><b>　　子程序2 </b></p>

67、;<p><b>　　子程序3 </b></p><p>　　注：主程序只需輸入?yún)?shù)，是一個的矩陣，它的值需要在matlab 的工作空間中人工輸入.．程序返回值為，如果有無界解, 則返回值為0 , 否則為一個的矩陣.．從該矩陣可以分析得出所需要的結果, 包括最優(yōu)解以及目標函數(shù)的極值．子程序1的主要作用是將計算矩陣進行標準化．子程序2的作用是尋找主元素( f 值) 及主元素所在

68、的行( i 值) 和列( j 值) ．子程序3根據(jù)主元素進行矩陣變換, 即先將主元素變?yōu)? ， 然后對其他行進行行變換， 使a 矩陣的第j 列的其他分量都變?yōu)?．</p><p>　　5 單純形法的應用</p><p>　　各種資源的最優(yōu)配置已成為當今節(jié)約型社會的研究熱點．它廣泛應用于國防、科技、工業(yè)、農業(yè)、交通運輸、環(huán)境工程、教育、經(jīng)濟及社會科學等領域，是指在一定的人力、物力、財力等資

69、源條件下，如何合理利用這些資源完成最多任務或得到最大效益的方法．線性規(guī)劃的資源最優(yōu)配置是研究在一組線性約束之下，目標線性函數(shù)的最小值或最大值問題[5]．</p><p>　　一個經(jīng)濟、管理問題凡滿足一下條件時，才能建立線性規(guī)劃的模型．</p><p>　?。?）要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；</p><p>　?。?）存在多種方案及有關數(shù)據(jù)；

70、</p><p>　?。?）要求達到的目的是在一定約束條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來描述．</p><p>　　一般滿同時足上面幾個條件的實際生活中的難解問題都可以用線性規(guī)劃問題來解決．所以越來越多的領域借助于線性規(guī)劃來做出最優(yōu)的決策．</p><p>　　5.1 單純形法在企業(yè)資源配置中的應用</p><p>　　單純形

71、法在實際中的應用最常使用于資源的配置．</p><p>　　人力、時間和物質資源的優(yōu)化配置問題是制定企業(yè)生產計劃時考慮的重要問題，線性規(guī)劃模型可以考慮各類資源的變動對其造成的影響并尋求最佳方案.</p><p>　　在企業(yè)生產和經(jīng)濟管理等領域中，人們常會遇到這樣的問題，如何從一切可能的方案中選擇最好、最優(yōu)的方案，在數(shù)學上把這類問題稱為最優(yōu)化問題．如何解決這類問題，在當今商品經(jīng)濟的環(huán)境下，是

72、一個關系到國計民生的重要問題．</p><p>　　線性規(guī)劃是理論和方法都比較成熟，并具有廣泛應用價值的一個運籌學分支．如果一個問題的限制條件可以寫成某些決策變量的線性方程組或線性不等式組，目標可以寫成決策變量的線性函數(shù)，那么這個問題的數(shù)學模型就是線性規(guī)劃問題．線性規(guī)劃法是研究如何將有限的人力、物力、設備、資金等資源進行最優(yōu)計劃和分配的理論方法．</p><p>　　線性規(guī)劃模型受到重視和

73、得到廣泛應用的現(xiàn)實表明，盡管經(jīng)濟系統(tǒng)是非常復雜的，但應用線性模型仍然能夠描述和解決大量的實際問題．對象限定的那些可以用線性規(guī)劃模型描述，其數(shù)學描述如下：</p><p>　　對于求取一些變量，使之即滿足線性約束條件，又使具有線性特征的目標函數(shù)取得極值的一類最優(yōu)化問題．線性規(guī)劃模型建立需具備以下條件：一是最優(yōu)目標．問題所要達到的目標能用線性函數(shù)來描述，且能夠使用極值；二是約束條件．達到目標的條件是有一定限制的，這些

74、限制可以用決策變量的線性等式或線性不等式來表示．三是選擇條件．有多種方案可供選擇，以便從中找出最優(yōu)方案[16]．</p><p><b>　　案例：</b></p><p>　　某車間生產A和B兩種儀器，對于生產A和B所需的原料分別為2個和3個單位，而所需的工時分別為4個和2個單位，目前可以用的原料為100個單位，工時為120個單位，并且已知每生產一臺A和B可以獲得的

75、利潤分別為6元和4元，應當安排生產A和B各多少臺，才能獲得最大的利潤？</p><p>　　分析：設應該安排生產的A和B的數(shù)量分別為臺、臺，則問題是求解最大值函數(shù)(目標函數(shù))：</p><p>　　編寫MATLAB程序</p><p>　　即最優(yōu)解為：，生產的A和B的數(shù)量相同即可獲得最大利潤．</p><p>　　線性規(guī)劃是企業(yè)生產過程中決策

76、制定的理論依據(jù)，決策的合理與否直接影響到企業(yè)的經(jīng)濟效益，線性規(guī)劃函數(shù)中各要素以及各變量的變化對分析造成的影響，通過單純形法案例進行了計算，針對大型、復雜的模型，需要選擇更為有效的手段來進行計算．</p><p>　　企業(yè)管理是一種典型的復雜系統(tǒng)，利用模型描述這類系統(tǒng)是一件非常困難的工作，為此建模和求解過程中對研究對象做出一些簡化是非常必要的，這也是各類線性模型受到重視和廣泛應用的原因之一．</p>

77、<p>　　5.2 單純形法在城市軌道列車惰行點搜索中的應用</p><p>　　能源緊缺是人類社會面臨的重要問題．現(xiàn)代城市軌道交通系統(tǒng)通過軌道上方的直流接觸網(wǎng)供電，因電動車組往往牽引功率巨大，需消耗大量電能，因此，有效利用牽引能源至關重要．單列車牽引策略優(yōu)化對于節(jié)約牽引能耗具有極其重要意義.在文獻[17-18]討論了單純形優(yōu)化算法在城市軌道交通列車惰行點搜索方面的應用，列車運行因受多重因素影響，確定

78、必要的惰行起點在實際情況的約束下并不容易．通過分析列車站內運行惰行點搜索特點、約束條件及尋解空間等．詳細介紹了二維空間中單純形法尋找合適列車惰行點的實現(xiàn)過程．借助于單列車仿真系統(tǒng)的幫助，通過問題的尋優(yōu)結果分析，研究了這種啟發(fā)式搜索方法在確定惰行點方面的可行性和性能表現(xiàn)．</p><p>　　借助于單純形法在城市勒道交通列車站問運行惰行點搜索方面的應用，在綜合考慮運行時間和能量消耗不同要求的情況下，應用該搜索方法得

79、到的惰行點可以為優(yōu)化列車運行提供滿意解．啟發(fā)式的搜索方法，通過較低的迭代次數(shù)，為列車運行的惰行點搜索提供了解決方案．然而，在站間運行時，首先要關注兩站之間的距離有沒有足夠的空間容納多個惰行點，從而合理選擇惰行點數(shù)量．從應用角度看，根據(jù)整條線路的總運行時間搜索多個站點間的惰行點，會使搜索更復雜．這將在今后進一步研究[17]．</p><p><b>　　6 總 結</b></p>

80、;<p>　　線性規(guī)劃是運籌學的一個重要分支，早在20世紀30年代末，前蘇聯(lián)著名的數(shù)學家康托洛維奇就提出了線性規(guī)劃的數(shù)學模型，越來越來受到人們的重視．而后于1947 年由美國數(shù)學家G. B. Duntzg提出一般線性規(guī)劃問題的求解方法——單純形法，它是線性規(guī)劃問題的通用解法．從而使得線性規(guī)劃的應用領域更加的廣泛．線性規(guī)劃這一學科也因此開始形成并迅速地發(fā)展起來．單純形方法與經(jīng)典分析的方法很不相同，在文獻[19-20]介紹它利

81、用了矩陣的初等變換，通過部分枚舉的方法來尋求線性規(guī)劃問題的最優(yōu)基可行解，從而求得值．由于這種方法運算簡單又有規(guī)則，且適用性廣泛．所以它的應用迅速得到發(fā)展，根據(jù)它而編制的程序已在一些計算機上開發(fā)實現(xiàn)．值得指出的是，盡管單純形法避開了經(jīng)典極值問題常用的微分法，但是單純形法的最優(yōu)性條件仍可用微分法導出[21]．</p><p><b>　　參考文獻</b></p><p>

82、　　[1]焦寶聰,陳蘭平.運籌學的思想方法及應用[M].北京.北京大學出版社.2008-2.</p><p>　　[2]賀學海.單純形法解決LP問題的研究[J].沈陽師范大學報(自然科學版).2010,28(1):14-16.</p><p>　　[3]毛東明,許風.單純形法最優(yōu)性條件的經(jīng)典證明[J].遼東學刊(自然科學版).1994,(3):12-14.</p><p

83、>　　[4]田學民.利用單純形法解線性規(guī)劃問題的機理[J].中國科技論文在線,2010.</p><p>　　[5]王東雷.基于單純算法的優(yōu)化設計與實現(xiàn)[J].安徽農業(yè)科學.2007,35(36):11727-11728.</p><p>　　[6]蔡海濤等.運籌學[M].湖南長沙.國防科技大學出版社.2003-10.</p><p>　　[7]張干宗.線性規(guī)

84、劃[M].武漢.武漢大學出版社.2004-3.</p><p>　　[8]甘應愛,田豐,李梅生等.運籌學[M].北京.清華大學出版社.2005-6.</p><p>　　[9]申卯興,許進.求解線性規(guī)劃的單純形法的直接方法[J].華東科技大學.2007,43(30):94-96.</p><p>　　[10]孫秀梅,皮曉明.線性規(guī)劃[M].哈爾濱.哈爾濱工業(yè)大學出版

85、社.2004.</p><p>　　[11]于春田,李法朝.運籌學[M].北京.科學出版社.2006-2.</p><p>　　[12]盧向南,李俊杰,壽涌毅.應用運籌學[M].杭州.浙江大學出版社.2005-2.</p><p>　　[13]詹明清,朱俊,韓曉明.運籌學[M].廣州.中山大學出版社.2004-8.</p><p>　　[14

86、]徐裕生,張海英.運籌學[M].北京.北京大學出版社.2006-4.</p><p>　　[15]畢春麗,曾強,王榮文.線性規(guī)劃問題中單純形法的計算機求解[J].焦作工學院學報(自然科學版).2002,21(6):472-474.</p><p>　　[16]王樹祥,武新霞,卜少利.線性規(guī)劃在企業(yè)生產計劃中的應用及模型的建立和求解[J].中國電力教育.2007,(21):195-197.&

87、lt;/p><p>　　[17]趙亞輝,朱琴躍.基于單純形法的城軌列車惰行點搜索[J].同濟大學(自然科學版).2010,38(1):81-85.</p><p>　　[18]趙亞輝,謝維達.單純形法在城軌列車惰行點搜索中的應用[J].同濟大學(自然科學版).2009,45(14):217-220.</p><p>　　[19]Hamdy A.Taha.運籌學(英文版)