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

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　單純形法的綜述及其應(yīng)用</p><p>　　所在學(xué)院 </p><p>　　專(zhuān)業(yè)班級(jí) 數(shù)學(xué)與應(yīng)用數(shù)學(xué)

2、 </p><p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱(chēng) </p><p>　　完成日期 年 月 </p><p>　　摘要：?jiǎn)渭冃畏ㄊ墙饩€(xiàn)性規(guī)劃問(wèn)題的一種重要方法，也是最主要的算法，本文

3、首先介紹單純形法的歷史背景，然后主要闡述了單純形法的一些基本計(jì)算步驟，指出單純形法在解決線(xiàn)性規(guī)劃問(wèn)題時(shí)一般形式、最簡(jiǎn)單單純形表的結(jié)構(gòu)，并通過(guò)一些具體的題目說(shuō)明單純形法的基本要點(diǎn)．另外，介紹了解一般線(xiàn)性規(guī)劃問(wèn)題中引入人工變量的方法，即大M法和兩階段法．以及一些改進(jìn)的計(jì)算方法和計(jì)算機(jī)算法．最后，介紹了單純形法在一些實(shí)際的線(xiàn)性規(guī)劃問(wèn)題中的應(yīng)用．</p><p>　　關(guān)鍵詞：線(xiàn)性規(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 線(xiàn)性規(guī)劃問(wèn)題解的概念1</p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、p>　　又因，所以可得到一個(gè)初始基可行解</p><p><b>　?。?lt;/b></p><p>　　2.4 最優(yōu)性檢驗(yàn)與解的判別</p><p>　　對(duì)于線(xiàn)性規(guī)劃問(wèn)題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解和無(wú)可行解四種情況．</p><p>　　代入目標(biāo)函數(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>　　若 為對(duì)應(yīng)于B的一個(gè)基可行解，且對(duì)一切有，則為最優(yōu)解，稱(chēng)為檢驗(yàn)數(shù)．</p><p>　　2.無(wú)窮多最優(yōu)解判別定理</p><p>　　若為一個(gè)可行解，對(duì)于一切有，又存在某個(gè)非基變量的檢驗(yàn)數(shù)，則線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解．</p><p><b>　　3.無(wú)界解判別定理</b&g

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

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

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

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

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

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

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

37、表1．</p><p><b>　　表1</b></p><p>　　在表1左上角是表示目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)．在列填入初始基變量的價(jià)值系數(shù)，它們都為零，各非基變量的檢驗(yàn)數(shù)為</p><p>　?。?）因?yàn)闄z驗(yàn)數(shù)都大于零，而且有正分量存在，轉(zhuǎn)入下一步：</p><p>　?。?），對(duì)應(yīng)的變量為換入變量，計(jì)算</

38、p><p>　　它所對(duì)應(yīng)的為換出變量．所在的列和所在的行交叉[2]為主元素．</p><p>　?。?）以[2]為主元素進(jìn)行初等行變換，使變換為,在列中將替換，得到新表2．</p><p><b>　　表2</b></p><p>　　得到新基，目標(biāo)函數(shù)的取值．</p><p>　?。?）檢查表2的所

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

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

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

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

43、這樣得到一個(gè)新的線(xiàn)性規(guī)劃問(wèn)題（記為）．</p><p>　　只要人工變量取正，不可能實(shí)現(xiàn)最大值，因?yàn)橹邪≈悼扇我庑〉捻?xiàng)．更準(zhǔn)確的說(shuō)，問(wèn)之間有下列關(guān)系．</p><p><b>　　設(shè)</b></p><p>　　若有最優(yōu)解，則與是的最優(yōu)解．</p><p>　　若有最優(yōu)解與，則是的最優(yōu)解；如果最優(yōu)解中，則無(wú)可行解．&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

61、整個(gè)迭代過(guò)程中，始終保持原問(wèn)題的可行性即，達(dá)到最優(yōu)解時(shí)檢驗(yàn)數(shù)為止，而也就是，即，所以原始單純形法實(shí)質(zhì)就是在保證原問(wèn)題可行的條件下向?qū)ε紗?wèn)題可行的方向迭代．而對(duì)偶單純形法在整個(gè)迭代過(guò)程中，始終保持對(duì)偶問(wèn)題的的可行性即，也始終保持所有檢驗(yàn)數(shù)，最后達(dá)到最優(yōu)解時(shí)即滿(mǎn)足原問(wèn)題的可行性為止，所以對(duì)偶單純形法實(shí)質(zhì)就是保證對(duì)偶問(wèn)題可行的條件下向原問(wèn)題可行的方向迭代．</p><p>　　對(duì)偶單純形法與原始單純形法相比有以下兩個(gè)顯

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

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

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

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

66、使求解過(guò)程比較簡(jiǎn)便且可靠性高[15]．</p><p><b>　　主要程序?yàn)椋?lt;/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ù)，是一個(gè)的矩陣，它的值需要在matlab 的工作空間中人工輸入.．程序返回值為，如果有無(wú)界解, 則返回值為0 , 否則為一個(gè)的矩陣.．從該矩陣可以分析得出所需要的結(jié)果, 包括最優(yōu)解以及目標(biāo)函數(shù)的極值．子程序1的主要作用是將計(jì)算矩陣進(jìn)行標(biāo)準(zhǔn)化．子程序2的作用是尋找主元素( f 值) 及主元素所在

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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