線性規(guī)劃理論及其應(yīng)用【信息科學(xué)與技術(shù)專業(yè)】【畢業(yè)設(shè)計(jì)+文獻(xiàn)綜述+開(kāi)題報(bào)告】

1、<p>　　本科畢業(yè)論文（設(shè)計(jì)）</p><p><b>　?。ā?0 　屆）</b></p><p>　　線性規(guī)劃理論及其應(yīng)用</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級(jí) 信息與計(jì)算科學(xué) </p>

2、<p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要:線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，并應(yīng)用到社會(huì)各個(gè)方面。本文首先介紹了線性規(guī)劃理論產(chǎn)生

3、的背景和意義，以及它的發(fā)展過(guò)程和發(fā)展方向。接著敘述了解決線性規(guī)劃問(wèn)題的方法及其算法。我們通過(guò)分析問(wèn)題建立數(shù)學(xué)模型，使用適當(dāng)方法求出最優(yōu)解，并對(duì)其進(jìn)行分析得到該問(wèn)題的最優(yōu)值。最后運(yùn)用線性規(guī)劃理論來(lái)解決相關(guān)實(shí)際問(wèn)題，即它被應(yīng)用的過(guò)程。</p><p>　　關(guān)鍵詞:線性規(guī)劃；數(shù)學(xué)模型；單純形法</p><p>　　The Theoretical analysis and Application

4、of Linear Programming</p><p>　　Abstract:Linear programming is an important branch of operations research, and it’s applied to all aspects of the society． In this paper the background and sense of the linear

5、programming theory, the development history and direction of linear programming theory are introduced． Then the methods and algorithms of solving the linear programming problems are described．We can build a mathematical

6、model by analyzing the problem,obtain an optinum solution in the proper way and analyze the solution to </p><p>　　Keywords: Linear programming; Mathematical models; Simplex method </p><p><b&

7、gt;　　目錄</b></p><p><b>　　1.緒論1</b></p><p>　　1.1線性規(guī)劃理論的背景1</p><p>　　1.2線性規(guī)劃理論的意義1</p><p>　　2.線性規(guī)劃理論概述3</p><p>　　2.1線性規(guī)劃的發(fā)展過(guò)程及其現(xiàn)狀3

8、</p><p>　　2.2線性規(guī)劃的發(fā)展方向3</p><p>　　3.線性規(guī)劃的具體實(shí)現(xiàn)5</p><p>　　3.1線性規(guī)劃的基本步驟和基本原則5</p><p>　　3.2線性規(guī)劃的模型建立和一般形式5</p><p>　　3.3線性規(guī)劃的解法6</p><p>　　

9、3.3.1 單純形法6</p><p>　　3.3.2 對(duì)偶單純形法7</p><p>　　3.4靈敏度分析8</p><p>　　3.5線性規(guī)劃的其他算法和問(wèn)題9</p><p>　　4.線性規(guī)劃的應(yīng)用11</p><p>　　4.1線性規(guī)劃應(yīng)用的現(xiàn)實(shí)意義11</p><p&g

10、t;　　4.2線性規(guī)劃的應(yīng)用實(shí)例11</p><p>　　5.線性規(guī)劃的軟件實(shí)現(xiàn)13</p><p>　　5.1線性規(guī)劃在LINDO中的實(shí)現(xiàn)13</p><p>　　5.2線性規(guī)劃在MATLAB中的實(shí)現(xiàn)15</p><p><b>　　6.結(jié)論20</b></p><p>　　

11、致謝錯(cuò)誤!未定義書(shū)簽。</p><p><b>　　參考文獻(xiàn)21</b></p><p><b>　　緒論</b></p><p><b>　　線性規(guī)劃理論的背景</b></p><p>　　線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法成熟的一個(gè)重要分支,它是輔助人

12、們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過(guò)兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料。二是生產(chǎn)組織與計(jì)劃的改進(jìn)，即合理安排人力物力資源。線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好。一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大化或最小化的問(wèn)題，最大化問(wèn)題是要在一個(gè)集合上使一個(gè)函數(shù)達(dá)到最大，

13、最小化問(wèn)題是要在一個(gè)集合上使一個(gè)函數(shù)達(dá)到最小。統(tǒng)稱為線性規(guī)劃問(wèn)題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，線性規(guī)劃的應(yīng)用越來(lái)越廣泛。它已成為人們?yōu)楹侠砝糜邢拶Y源制定最佳決策的有力工具。[1][2]</p><p><b>　　線性規(guī)劃理論的意義</b></p><p&g

14、t;　　隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，線性規(guī)劃的應(yīng)用越來(lái)越廣泛。它已成為人們合理利用有限資源制定最佳決策的有力工具。隨著經(jīng)濟(jì)全球化的不斷發(fā)展，企業(yè)面臨更加激烈的市場(chǎng)競(jìng)爭(zhēng)。企業(yè)必須不斷提高盈利水平，增強(qiáng)其獲利能力，在生產(chǎn)、銷售、新產(chǎn)品研發(fā)等一系列過(guò)程中只有自己的優(yōu)勢(shì)，提高企業(yè)效率，降低成本，形成企業(yè)的核心競(jìng)爭(zhēng)力，才能在激烈的競(jìng)爭(zhēng)中立于不敗之地。過(guò)去很多企業(yè)在生產(chǎn)、運(yùn)輸、市場(chǎng)營(yíng)銷等方面沒(méi)有利用線性規(guī)劃進(jìn)行合理的配置，從而增加了企業(yè)的生產(chǎn)，使企

15、業(yè)的利潤(rùn)不能達(dá)到最大化。在競(jìng)爭(zhēng)日益激烈的今天，如果還按照過(guò)去的方式，是難以生存的，所以就有必要利用線性規(guī)劃的知識(shí)對(duì)戰(zhàn)略計(jì)劃、生產(chǎn)，銷售各個(gè)環(huán)節(jié)進(jìn)行優(yōu)化從而降低生產(chǎn)成本，提高企業(yè)的效率。在各類經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問(wèn)題：在生產(chǎn)條件不變的情況下，如何通過(guò)統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，組織生產(chǎn)過(guò)程，使總的經(jīng)濟(jì)效益最好。這樣的問(wèn)題常常可以化成或近似地化成所謂的“線性規(guī)劃” (Linear Pmgramming，簡(jiǎn)記為

16、LP)問(wèn)題。線性規(guī)劃是應(yīng)用分析、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以</p><p><b>　　線性規(guī)劃理論概述</b></p><p>　　線性規(guī)劃的發(fā)展過(guò)程及其現(xiàn)狀</p><p>　　法國(guó)數(shù)學(xué)家 J.- B.- J.傅里葉和 C.瓦萊－普森分別于1832和1911年獨(dú)立地提出線

17、性規(guī)劃的想法，但未引起注意。 </p><p>　　1939年蘇聯(lián)數(shù)學(xué)家Л.В.康托羅維奇在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書(shū)中提出線性規(guī)劃問(wèn)題，也未引起重視。 </p><p>　　1947年美國(guó)數(shù)學(xué)家G.B.丹奇克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法──單純形法，為這門(mén)學(xué)科奠定了基礎(chǔ)。 </p><p>　　1947年美國(guó)數(shù)學(xué)家J.von諾伊曼

18、提出對(duì)偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。 </p><p>　　1951年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。 </p><p>　　50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對(duì)偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃

19、的靈敏度分析和參數(shù)規(guī)劃問(wèn)題，1956年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。 </p><p>　　線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問(wèn)題。 </p><p>　　1

20、979年蘇聯(lián)數(shù)學(xué)家L. G. Khachian提出解線性規(guī)劃問(wèn)題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。 </p><p>　　1984年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問(wèn)題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。[3][4]</p><p&g

21、t;<b>　　線性規(guī)劃的發(fā)展方向</b></p><p>　　線性規(guī)劃在軍事、工農(nóng)業(yè)、交通和城鎮(zhèn)規(guī)劃等領(lǐng)域中得到廣泛的應(yīng)用。實(shí)際問(wèn)題有的是很大的，大到具有幾萬(wàn)、幾十萬(wàn)甚至上百萬(wàn)的變量和成千上萬(wàn)的約束條件。有的問(wèn)題雖小些，一般也有幾百幾千的變量和成百上千的約束條件。顯然解這類問(wèn)題都離不開(kāi)計(jì)算機(jī)。常用的計(jì)算機(jī)軟件有LINGO,LINDO,MATLAB等。</p><p>

22、;　　線性規(guī)劃理論與大系統(tǒng)分析理論相結(jié)合，以解決經(jīng)濟(jì)、社會(huì)、生態(tài)、和政治因素交織在一起的復(fù)雜社會(huì)系統(tǒng)問(wèn)題，或者解決設(shè)計(jì)、工藝、質(zhì)量、生產(chǎn)計(jì)劃、大型試驗(yàn)、技術(shù)改造、成本價(jià)格、市場(chǎng)營(yíng)銷等因素交織在一起的企業(yè)管理中的復(fù)雜問(wèn)題，是線性規(guī)劃理論的主要方向之一。</p><p>　　在大系統(tǒng)理論中，對(duì)于一些含有幾個(gè)層級(jí)的系統(tǒng)（系統(tǒng)含有分系統(tǒng)，分系統(tǒng)又含有子系統(tǒng)，子系統(tǒng)又含有更小的子系統(tǒng)等），通常采用遞階分析的方法進(jìn)行分解和分

23、析。從系統(tǒng)觀點(diǎn)考慮問(wèn)題的多學(xué)科優(yōu)化理論和方法的研究與應(yīng)用，已經(jīng)成為線性規(guī)劃理論的重要發(fā)展方向之一 。我國(guó)的現(xiàn)代化建設(shè)進(jìn)程中，眾多大系統(tǒng)工程（如三峽工程、載人航天工程）中，也大量的采用了系統(tǒng)工程的一些科學(xué)方法，并取得了顯著的成效。反過(guò)來(lái)，實(shí)踐的發(fā)展又不斷地催生新的理論，或者不斷地開(kāi)拓已有應(yīng)用范圍，不斷地創(chuàng)新理論和方法，是所有學(xué)科發(fā)展的生命力源泉之所在，線性規(guī)劃理論的發(fā)展也不例外。[5][6][7]</p><p>

24、<b>　　線性規(guī)劃的具體實(shí)現(xiàn)</b></p><p>　　線性規(guī)劃的基本步驟和基本原則</p><p>　　線性規(guī)劃問(wèn)題的基本步驟[8]</p><p>　?。?）提出并抽象問(wèn)題</p><p><b>　?。?）建立數(shù)學(xué)模型</b></p><p><b>　　

25、（3）求解</b></p><p><b>　?。?）檢驗(yàn)解</b></p><p>　?。?）解的靈敏度分析</p><p><b>　?。?）解的回歸</b></p><p>　　線性規(guī)劃方法的運(yùn)用原則[8]</p><p><b>　?。?）合作原

26、則</b></p><p><b>　?。?）打破常規(guī)原則</b></p><p><b>　?。?）相互滲透原則</b></p><p>　?。?）客觀獨(dú)立性原則</p><p><b>　?。?）包容性原則</b></p><p><

27、;b>　?。?）平衡性原則</b></p><p>　　線性規(guī)劃的模型建立和一般形式</p><p>　　線性規(guī)劃的模型建立[1][2][9]</p><p>　　從實(shí)際問(wèn)題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟； </p><p>　　1．根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量； </p><p>　　2

28、．由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)； </p><p>　　3．由決策變量所受的限制條件確定決策變量所要滿足的約束條件。 </p><p>　　所建立的數(shù)學(xué)模型具有以下特點(diǎn)： </p><p>　　1、每個(gè)模型都有若干個(gè)決策變量，其中為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。</p><p>　

29、　2、目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問(wèn)題可以是最大化或最小化，二者統(tǒng)稱為最優(yōu)化。 </p><p>　　3、約束條件也是決策變量的線性函數(shù)。 </p><p>　　當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。</p><p>　　線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的一般形式[2]</p><p&g

30、t;　?。?）列出約束條件及目標(biāo)函數(shù) </p><p>　?。?）畫(huà)出約束條件所表示的可行域 </p><p>　　（3）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值</p><p><b>　　線性規(guī)劃的解法</b></p><p>　　求解線性規(guī)劃問(wèn)題的基本方法是單純形法，現(xiàn)在已有單純形法的標(biāo)準(zhǔn)軟件，可在電子計(jì)算機(jī)上求解約束

31、條件和決策變量數(shù)達(dá) 10000個(gè)以上的線性規(guī)劃問(wèn)題。為了提高解題速度，又有改進(jìn)單純形法、對(duì)偶單純形法、原始對(duì)偶方法、分解算法和各種多項(xiàng)式時(shí)間算法。對(duì)于只有兩個(gè)變量的簡(jiǎn)單的線性規(guī)劃問(wèn)題，也可采用圖解法求解。這種方法僅適用于只有兩個(gè)變量的線性規(guī)劃問(wèn)題。它的特點(diǎn)是直觀而易于理解，但實(shí)用價(jià)值不大。通過(guò)圖解法求解可以理解線性規(guī)劃的一些基本概念。</p><p>　　3.3.1 單純形法</p><p&g

32、t;　　單純形法是求解線性規(guī)劃問(wèn)題的一般方法，原則上它適用于任何線性規(guī)劃問(wèn)題。這是丹齊克在1947年提出來(lái)的。 它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是維向量空間中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。大量的實(shí)際表明,這是一種行之有效的解法。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換

33、,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。</p><p>　　單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問(wèn)題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問(wèn)題無(wú)解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更

34、優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問(wèn)題的最優(yōu)解。⑤若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。下面把單純形法的計(jì)算步驟及迭代過(guò)程歸結(jié)如下圖：</p><p><b>　　并得出單純形表：</b></p><p>　　這樣就可以得出一般線性規(guī)劃問(wèn)題的解。</p><p>

35、　　有關(guān)單純形法的進(jìn)一步討論，當(dāng)線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式后約束條件的系數(shù)矩陣中含有單位矩陣，以此作初始基，用人工變量法（大M法）求解。用大M法處理人工變量，在用手工計(jì)算求解時(shí)不會(huì)碰到麻煩，但用電子計(jì)算機(jī)求解時(shí)，由于計(jì)算機(jī)取值時(shí)的誤差，有可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為了克服這個(gè)困難，可以對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)階段來(lái)計(jì)算，稱兩階段法。[1][2]</p><p>　　3.3.2 對(duì)偶單純形法</p&g

36、t;<p>　　每一個(gè)線性規(guī)劃問(wèn)題都有另一個(gè)與其相互關(guān)聯(lián)的問(wèn)題，這個(gè)新問(wèn)題具有非常重要的性質(zhì)，用這些性質(zhì)可以更加有效地獲得原來(lái)問(wèn)題的解。為區(qū)別起見(jiàn)，我們稱原來(lái)的問(wèn)題為原問(wèn)題，稱與原問(wèn)題相關(guān)聯(lián)的問(wèn)題為對(duì)偶問(wèn)題。</p><p><b>　　1．對(duì)偶理論　</b></p><p>　　以如下線性規(guī)劃問(wèn)題及其對(duì)偶問(wèn)題：</p><p>

37、　　這里表示原問(wèn)題，表示對(duì)偶問(wèn)題。</p><p><b>　　2．對(duì)偶單純形法</b></p><p>　　對(duì)偶單純形算法可以概括如下：</p><p>　　(1)找出原問(wèn)題的一個(gè)基，構(gòu)成起始對(duì)偶基可行解，是對(duì)所有的有</p><p>　　構(gòu)成原始對(duì)偶單純形法表；</p><p>　　(2)假如

38、,則當(dāng)前的解是最優(yōu)解，停止計(jì)算。否則選擇樞行，其，</p><p><b>　　例如選擇你最小者：</b></p><p>　　(3)假如對(duì)所有列，則對(duì)偶問(wèn)題無(wú)界，原問(wèn)題無(wú)解，停止計(jì)算。否則選擇樞列；</p><p>　　（4）以為樞元素變換對(duì)偶單純形表，然后轉(zhuǎn)達(dá)步驟（2）。[6]</p><p><b>　　

39、靈敏度分析</b></p><p>　　靈敏度分析一詞的含義是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度的分析。靈敏度分析意義很大。其一，很多實(shí)際問(wèn)題中數(shù)據(jù)常常是不夠精確的，很多是估計(jì)出來(lái)的，因此調(diào)整數(shù)據(jù)是常事。其二，當(dāng)一個(gè)用于決策的問(wèn)題得出最優(yōu)解后，決策者為了通觀全局，常常要研究其中某些因素（數(shù)據(jù)）的改變對(duì)當(dāng)前最優(yōu)決策所造成的影響。其三，當(dāng)作多種方案比較時(shí)，這些不同方案常常是某些數(shù)據(jù)不同而已。靈

40、敏度分析的步驟可歸納如下：[4][6]</p><p>　　1.將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表來(lái)。具體方法是，按照下列公式計(jì)算出由參數(shù)，，的變化而引起的最終單純形表上有關(guān)數(shù)字的變化。</p><p>　　2．檢查原問(wèn)題是否仍為可行解。</p><p>　　3．檢查對(duì)偶問(wèn)題是否仍為可行解。</p><p>　　4．按下表所列情況得出結(jié)論

41、或決定繼續(xù)計(jì)算的步驟。</p><p>　　線性規(guī)劃的其他算法和問(wèn)題</p><p><b>　　1．分解算法[1]</b></p><p>　　分解算法是一種處理大型問(wèn)題的方法，它把一個(gè)大型問(wèn)題分解成若干個(gè)規(guī)模較小的問(wèn)題來(lái)求解，這種方法不僅可以減少存儲(chǔ)量，也能減少計(jì)算量。因?yàn)榫€性規(guī)劃的計(jì)算量對(duì)于約束條件的個(gè)數(shù)m很敏感，統(tǒng)計(jì)表明，計(jì)算量大約與成

42、正比，因此，若把一個(gè)大型問(wèn)題轉(zhuǎn)化為求解若干個(gè)小型問(wèn)題，由于每個(gè)小型問(wèn)題的約束條件個(gè)數(shù)較少，可使總的計(jì)算量大大減少。</p><p>　　2．Karmarkar 算法[6]</p><p>　　1984年N。Karmarkar提出了一個(gè)屬于多項(xiàng)式時(shí)間算法的內(nèi)點(diǎn)法，并證明其計(jì)算復(fù)雜性是0，這是一種能解決大型線性規(guī)劃問(wèn)題的強(qiáng)有力的算法。它的應(yīng)用十分廣泛，如應(yīng)用這一系統(tǒng)規(guī)模的多項(xiàng)式時(shí)間算法用于電力

43、系統(tǒng)，可以使實(shí)時(shí)電價(jià)計(jì)算等問(wèn)題變的簡(jiǎn)單。</p><p>　　3．整數(shù)線性規(guī)劃問(wèn)題</p><p>　　在線性規(guī)劃問(wèn)題中，當(dāng)某些變量（或全部變量）取整數(shù)值時(shí)，該規(guī)劃問(wèn)題就稱為整數(shù)規(guī)劃問(wèn)題。整數(shù)規(guī)劃可以看成是線性規(guī)劃問(wèn)題中對(duì)變量進(jìn)行整數(shù)約束的一種特殊形式，因此，可以認(rèn)為，整數(shù)規(guī)劃問(wèn)題一般要比相應(yīng)的線性規(guī)劃問(wèn)題約束得更緊。整數(shù)規(guī)劃中，如果所有的變量都要求取整數(shù)值，則稱此規(guī)劃問(wèn)題為純整數(shù)規(guī)劃；如

44、果部分變量要求取整數(shù)值，則稱此規(guī)劃問(wèn)題為混合整數(shù)規(guī)劃；如果要求變量的取值為0或1，則稱此規(guī)劃問(wèn)題為0-1規(guī)劃。</p><p>　　4．影子價(jià)格與影子成本[10]</p><p>　　根據(jù)線性規(guī)劃問(wèn)題對(duì)偶變量和影子價(jià)格的經(jīng)濟(jì)意義，給出了影子成本的概念，討論了影子成本與對(duì)偶價(jià)格的關(guān)系。通過(guò)靈敏度分析給出了影子成本的動(dòng)態(tài)表示，并進(jìn)一步闡明了影子價(jià)格和影子成本的惟一性以及影子成本在經(jīng)濟(jì)管理中的應(yīng)

45、用。</p><p>　　5．有界變量線性規(guī)劃問(wèn)題</p><p>　　實(shí)際應(yīng)用中的許多線性規(guī)劃問(wèn)題，其決策變量具有上、下界限制。這類問(wèn)題稱為有界變量線性規(guī)劃問(wèn)題。它的一般數(shù)學(xué)模型可寫(xiě)為</p><p><b>　　，</b></p><p><b>　　，</b></p><p

46、><b>　　,</b></p><p>　　其中，分別為的下界和上界；認(rèn)為階矩陣，，并設(shè)的秩為。</p><p><b>　　線性規(guī)劃的應(yīng)用</b></p><p>　　線性規(guī)劃應(yīng)用的現(xiàn)實(shí)意義</p><p>　　隨著經(jīng)濟(jì)全球化的不斷發(fā)展，企業(yè)面臨更加激烈的市場(chǎng)競(jìng)爭(zhēng)。企業(yè)必須不斷提高盈利水平

47、，增強(qiáng)其獲利能力，在生產(chǎn)、銷售、新產(chǎn)品研發(fā)等一系列過(guò)程中只有自己的優(yōu)勢(shì)，提高企業(yè)效率，降低成本，形成企業(yè)的核心競(jìng)爭(zhēng)力，才能在激烈的競(jìng)爭(zhēng)中立于不敗之地。過(guò)去很多企業(yè)在生產(chǎn)、運(yùn)輸、市場(chǎng)營(yíng)銷等方面沒(méi)有利用線性規(guī)劃進(jìn)行合理的配置，從而增加了企業(yè)的生產(chǎn)，使企業(yè)的利潤(rùn)不能達(dá)到最大化。在競(jìng)爭(zhēng)日益激烈的今天，如果還按照過(guò)去的方式，是難以生存的，所以就有必要利用線性規(guī)劃的知識(shí)對(duì)戰(zhàn)略計(jì)劃、生產(chǎn)，銷售各個(gè)環(huán)節(jié)進(jìn)行優(yōu)化從而降低生產(chǎn)成本，提高企業(yè)的效率。在各類經(jīng)

48、濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問(wèn)題：在生產(chǎn)條件不變的情況下，如何通過(guò)統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，組織生產(chǎn)過(guò)程，使總的經(jīng)濟(jì)效益最好。這樣的問(wèn)題常?？梢曰苫蚪频鼗伤^的“線性規(guī)劃” (Linear Pmgramming，簡(jiǎn)記為L(zhǎng)P)問(wèn)題。線性規(guī)劃是應(yīng)用分析、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)有效管理。利用線性規(guī)劃我們可以解決很多問(wèn)題。如：在不違反一定

49、資源限制下，組織安排生產(chǎn)，獲得最好的經(jīng)濟(jì)效</p><p><b>　　線性規(guī)劃的應(yīng)用實(shí)例</b></p><p>　　數(shù)學(xué)與經(jīng)濟(jì)的結(jié)合由來(lái)已久。從經(jīng)濟(jì)學(xué)作為一門(mén)學(xué)科的發(fā)展看，數(shù)學(xué)在其中的位置越來(lái)越重要，它不僅幫助人們?cè)诮?jīng)營(yíng)中獲利，而且給予人們以能力，包括直觀思維、邏輯思維、精確計(jì)算等等，以至于今天，不懂?dāng)?shù)學(xué)就無(wú)法研究經(jīng)濟(jì)。前蘇聯(lián)數(shù)學(xué)家坎托羅維奇因?qū)ξ镔Y最優(yōu)調(diào)撥理論的

50、貢獻(xiàn)獲1975年諾貝爾獎(jiǎng)，他被公認(rèn)為最優(yōu)規(guī)劃理論的創(chuàng)始人，經(jīng)濟(jì)數(shù)學(xué)理論的奠基人。坎托羅維奇創(chuàng)造的線性規(guī)劃方法被廣泛地應(yīng)用于經(jīng)濟(jì)領(lǐng)域并為經(jīng)濟(jì)發(fā)展作出了卓越貢獻(xiàn)。[12]</p><p>　　線性規(guī)劃作為運(yùn)籌學(xué)的一個(gè)重要分支，在經(jīng)濟(jì)管理中有著極其廣泛的應(yīng)用，比如設(shè)計(jì)一個(gè)物流網(wǎng)絡(luò)的問(wèn)題。[13]以下是一些常用的應(yīng)用舉例。</p><p>　　1．線性規(guī)劃在薪酬管理中的應(yīng)用[14]</p&g

51、t;<p>　　知識(shí)經(jīng)濟(jì)時(shí)代，現(xiàn)代化的大型企業(yè)或企業(yè)集團(tuán)不斷涌現(xiàn)，大企業(yè)的內(nèi)部管理模式更加復(fù)雜，必須提高企業(yè)內(nèi)部的控制力、執(zhí)行力、及對(duì)市場(chǎng)變化能夠快速做出的反應(yīng)能力。線性規(guī)劃是人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法，通過(guò)在薪酬管理宏觀和微觀兩方面的應(yīng)用，提高企業(yè)管理水平，實(shí)現(xiàn)最佳經(jīng)濟(jì)效益。</p><p>　　2．線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用[15]</p><p>　　在企業(yè)生產(chǎn)

52、過(guò)程中，生產(chǎn)計(jì)劃安排直接影響到企業(yè)的經(jīng)濟(jì)效益，而解決生產(chǎn)計(jì)劃問(wèn)題的有效方法之一就是建立線性規(guī)劃模型，線性規(guī)劃為企業(yè)制定生產(chǎn)計(jì)劃提供了一種簡(jiǎn)單又科學(xué)的方法，具有一定的實(shí)用價(jià)值。</p><p>　　3．線性規(guī)劃在服裝生產(chǎn)任務(wù)分配中的應(yīng)用[16]</p><p>　　針對(duì)不確定條件下實(shí)際的服裝生產(chǎn)任務(wù)分配問(wèn)題，采用線性規(guī)劃優(yōu)化的方法予以解決。為此，建立了服裝生產(chǎn)任務(wù)分配的數(shù)學(xué)模型，在保證交貨期

53、的前提下，將線性規(guī)劃法對(duì)生產(chǎn)任務(wù)進(jìn)行優(yōu)化分配，使加工成本最小。生產(chǎn)實(shí)例表明，所提出的優(yōu)化方法能夠使服裝生產(chǎn)系統(tǒng)得到整體優(yōu)化，表明其有效性和可行性。</p><p>　　4．線性規(guī)劃在企業(yè)成本控制中的應(yīng)用[17]</p><p>　　企業(yè)成本由原材料，制造費(fèi)用等要素構(gòu)成，通過(guò)構(gòu)建企業(yè)成本構(gòu)成的數(shù)學(xué)模型及約束條件，求解使企業(yè)成本總體最低的最優(yōu)解，同時(shí)解釋各要素變化對(duì)企業(yè)利潤(rùn)的影響程度，為企業(yè)成

54、本控制指明方向。</p><p>　　5．線性規(guī)劃在飲料的生產(chǎn)銷售模型中的應(yīng)用[18]</p><p>　　應(yīng)用運(yùn)籌學(xué)中的線性規(guī)劃原理，研究了在給定務(wù)件下，按某一衡量指標(biāo)來(lái)尋找安排的最優(yōu)方案問(wèn)題．且研究了工廠安排合理的生產(chǎn)計(jì)劃、管理資源和人力資源，使得企業(yè)在有限的資本情況下，獲得總費(fèi)用最少或者總收益最大問(wèn)題．根據(jù)該實(shí)際情況將問(wèn)題簡(jiǎn)單化為飲料的生產(chǎn)銷售問(wèn)題，建立了線性規(guī)劃的數(shù)學(xué)模型．用MAT

55、LAB軟件進(jìn)行了模型求解．使得求解過(guò)程簡(jiǎn)便且得到的結(jié)果較準(zhǔn)確．通過(guò)模型檢驗(yàn)，進(jìn)一步改進(jìn)了模型，使其更加符合實(shí)際．最后將該模型推廣到了更加廣泛的情形。</p><p><b>　　線性規(guī)劃的軟件實(shí)現(xiàn)</b></p><p>　　線性規(guī)劃在LINDO中的實(shí)現(xiàn)</p><p>　?。ㄉa(chǎn)計(jì)劃問(wèn)題）已知某工廠計(jì)劃生產(chǎn)I，II，III三種產(chǎn)品，各產(chǎn)品需要

56、在A、B、C設(shè)備上加工，有關(guān)數(shù)據(jù)如下 ，試問(wèn)答：</p><p>　　現(xiàn)問(wèn)如何發(fā)揮生產(chǎn)能力，使生產(chǎn)盈利最大？</p><p>　　顯然此問(wèn)題是在設(shè)備有效臺(tái)時(shí)（每月）受到限制的情形下來(lái)尋求發(fā)揮生產(chǎn)能力，使生產(chǎn)盈利最大，其決策方案是決定I，II，III各自的產(chǎn)量為多少才最佳？現(xiàn)在，在上面的問(wèn)題中，若記為生產(chǎn)I產(chǎn)品的產(chǎn)量；為生產(chǎn)II產(chǎn)品的產(chǎn)量；為生產(chǎn)III產(chǎn)品的產(chǎn)量；為生產(chǎn)盈利。則上面的生產(chǎn)計(jì)劃

57、問(wèn)題可抽象地歸納為一個(gè)數(shù)學(xué)模型：</p><p>　　打開(kāi)LINDO軟件出現(xiàn)一個(gè)名為“untitled”空白文件,這就是輸入數(shù)據(jù)的地方，如下圖：</p><p>　　按LINDO的規(guī)則歸納上述數(shù)學(xué)模型為： </p><p>　　并輸入在LINDO的空白文件中，得到：</p><p>　　然后點(diǎn)擊工具條上的按鈕即可，運(yùn)行結(jié)果：</p>

58、;<p>　　由此可知，當(dāng)I產(chǎn)品的產(chǎn)量為24，II產(chǎn)品的產(chǎn)量為24，III產(chǎn)品的產(chǎn)量為5時(shí)生產(chǎn)盈利最大，生產(chǎn)盈利最大為134.5。</p><p>　　線性規(guī)劃在MATLAB中的實(shí)現(xiàn)</p><p>　　（啤酒配方問(wèn)題）某啤酒廠希望用原料摻水的辦法生產(chǎn)一種復(fù)合標(biāo)準(zhǔn)的低成本啤酒。其標(biāo)準(zhǔn)要求為：酒精含量為3．1%；發(fā)酵前平均相對(duì)密度在1．034-1．040之間；顏色在8-10單位

59、之間；每升混合物之中，蛇麻子脂的含量在20-25之間。現(xiàn)在采用水和4種不同成分的原料進(jìn)行混合，不同的原料有不同的性質(zhì)，如下表所示。</p><p>　　設(shè)計(jì)變量是混合時(shí)每種原料所占總體積的百分比，以分別表示水、原料1-原料4各自的百分比。優(yōu)化目標(biāo)是使得成本最小，由上表最后一行可知目標(biāo)函數(shù)為</p><p>　　由于諸變量在總體積中所占的百分比，所以可用以下的等式約束限定變量范圍：</

60、p><p>　　從酒精含量的這一要求出發(fā)有：</p><p>　　為滿足相對(duì)密度要求我們有兩個(gè)不等式約束</p><p>　　需要通過(guò)以下不等式控制它的顏色：</p><p>　　最后，蛇麻子脂含量的要求決定了它的邊界條件：</p><p>　　打開(kāi)MATLAB程序就直接進(jìn)入主窗口“Command Window” ，如圖：

61、</p><p>　　然后根據(jù)上述數(shù)學(xué)模型編一個(gè)程序：</p><p>　　f=[0,44,50,64,90];</p><p>　　A=[-1,-1.03,-1.043,-1.05,-1.064;1,1.03,1.043,1.05,1。064;0,11,9,8,7;0,-11,-9,-8,-7;0,30,20,28,30;0,-30,-20,-28,-30];&l

62、t;/p><p>　　b=[-1.034;1.040;10;-8;25;-20];</p><p>　　Aeq=[1,1,1,1,1;0,2.5,3.7,4.5,5.8];</p><p>　　beq=[1;3.10];</p><p>　　options=optimset('Diagnostics','on',&

63、#39;largescale','off');</p><p>　　[x,fval]=linprog(f,A,b,Aeq,beq,[0,0,0,0,0]',[1,1,1,1,1]',[1,1,1,1,1],options)</p><p>　　并輸入到下面的窗口中，得到</p><p>　　按工具欄中，即可得到結(jié)果</p

64、><p>　　即水、原料1、原料2、原料3、原料4占總體積的百分比分別為9.84%、19.67%、70。49%、0%、0%時(shí)生產(chǎn)該啤酒成本最低，最低成本為43.9016元。</p><p><b>　　結(jié)論</b></p><p>　　本文首先介紹了線性規(guī)劃理論產(chǎn)生的背景、意義及發(fā)展的過(guò)程、現(xiàn)狀和方向，讓大家對(duì)線性規(guī)劃有了初步認(rèn)識(shí)。然后又介紹了線性

65、規(guī)劃的理論和方法及其應(yīng)用。通過(guò)建立的數(shù)學(xué)模型，利用單純形法、對(duì)偶單純形法、分解算法和Karmarkar 算法等對(duì)薪酬管理問(wèn)題、運(yùn)輸問(wèn)題、整數(shù)線性規(guī)劃問(wèn)題和服裝生產(chǎn)任務(wù)分配中的應(yīng)用等多種問(wèn)題求解，然后通過(guò)靈敏度的分析來(lái)確定最優(yōu)解和最優(yōu)值，生產(chǎn)計(jì)劃問(wèn)題和啤酒配方問(wèn)題分別通過(guò)LINDO和MATLAB進(jìn)行軟件實(shí)現(xiàn)。線性規(guī)劃在企業(yè)營(yíng)銷策劃、產(chǎn)品生產(chǎn)計(jì)劃、物流管理、理財(cái)與投資、認(rèn)識(shí)管理等很多的領(lǐng)域得到廣泛和有效的利用，并且對(duì)社會(huì)中各種活動(dòng)的規(guī)劃以及

66、生產(chǎn)的策劃起到指導(dǎo)作用，給社會(huì)帶來(lái)了極大的方便。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 張干宗線性規(guī)劃[M].第二版.武漢:武漢大學(xué)出版社,2008,6:1-39.</p><p>　　[2] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].第三版.北京:清華大學(xué)出版社,2007,4:1-10.</p><p&

67、gt;　　[3] Leonid Nison Vaserstein,Christopher Cattelier Byrne. Introduction to Linear Programming[M].Beijing:China Machine Press,2005,6:1-18.</p><p>　　[4] 運(yùn)籌學(xué)編寫(xiě)組.運(yùn)籌學(xué)[M] .第三版.北京:清華大學(xué)出版社,2005,6:1-2.</p>

68、<p>　　[5] 高紅衛(wèi).實(shí)用線性規(guī)劃工具[M].北京:科學(xué)出版社,2007:15-15.</p><p>　　[6] 胡清淮,魏一鳴.線性規(guī)劃及其應(yīng)用[M].北京:科學(xué)出版社,2004:253-256.</p><p>　　[7] 劉春艷.線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用[J].電力學(xué)報(bào).2008,23（6）：460-462.</p><p>　　[8] 高

69、紅衛(wèi).線性規(guī)劃方法應(yīng)用詳解[M].北京:科學(xué)出版社,2004:14-16.</p><p>　　[9] 江道琪,何建坤，陳松華.實(shí)用線性規(guī)劃方法及其支持系統(tǒng)[M].北京：清華大學(xué)出版社,2006：2-8.</p><p>　　[10] 楊桂元.影子價(jià)格與影子成本[J].運(yùn)籌與管理.2005,14（5）：41-45.</p><p>　　[11] 戶孝俊.線性規(guī)劃在現(xiàn)

70、實(shí)生活中的應(yīng)用[J].理論研究.2009,7：206-207.</p><p>　　[12] 聶天霞.線性規(guī)劃在經(jīng)濟(jì)發(fā)展中的作用[J].鄭州鐵路職業(yè)技術(shù)學(xué)院學(xué)報(bào).2009,21(3):20-22.</p><p>　　[13] Mi Lim Lee, Jae-Gon Kim and Yeong-Dae Kim. Linear programming and Lagrangian relax

71、ation heuristics for designing a material flow network on a block layout[J].International Journal of Production Research.15 September 2009, Vol.47, No. 18:187-182.</p><p>　　[14] 許紅艷.線性規(guī)劃在薪酬管理中的應(yīng)用[J].現(xiàn)代經(jīng)濟(jì)信息.2

72、009,8：139-140.</p><p>　　[15] 孫庭鋒.淺析線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用[J].商業(yè)經(jīng)濟(jì).2006,3：18-20.</p><p>　　[16] 凌雪.基于線性規(guī)劃的服裝生產(chǎn)任務(wù)分配研究[J].江蘇紡織A版.2009,11：57-58.</p><p>　　[17] 尹紹群.基于線性規(guī)劃的企業(yè)成本控制研究[J].現(xiàn)代經(jīng)濟(jì)信息.2010

73、,3：58-59.</p><p>　　[18] 姜新.飲料的生產(chǎn)銷售模型[J].科技信息.2010,10：178-179.</p><p><b>　　文獻(xiàn)綜述</b></p><p>　　線性規(guī)劃理論及其應(yīng)用 </p><p>　　一、前言部分[1] [2]</p><p>　　線性規(guī)劃是運(yùn)籌

74、學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過(guò)兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料.二是生產(chǎn)組織與計(jì)劃的改進(jìn)，即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好.一般地，求線性目標(biāo)函數(shù)在線性約束條件下的

75、最大化或最小化的問(wèn)題，最大化問(wèn)題是要在一個(gè)集合上使一個(gè)函數(shù)達(dá)到最大，最小化問(wèn)題是要在一個(gè)集合上使一個(gè)函數(shù)達(dá)到最小。統(tǒng)稱為線性規(guī)劃問(wèn)題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，線性規(guī)劃的應(yīng)用越來(lái)越廣泛。它已成為人們?yōu)楹侠砝糜邢拶Y源制定最佳決策的有力工具。</p><p><b>　　二、主題部分<

76、/b></p><p>　　2.1線性規(guī)劃理論發(fā)展過(guò)程及方向</p><p>　　2.1.1線性規(guī)劃發(fā)展過(guò)程[3][4]</p><p>　　法國(guó)數(shù)學(xué)家 J.- B.- J.傅里葉和 C.瓦萊－普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。 </p><p>　　1939年蘇聯(lián)數(shù)學(xué)家Л.В.康托羅維奇在《生產(chǎn)組織

77、與計(jì)劃中的數(shù)學(xué)方法》一書(shū)中提出線性規(guī)劃問(wèn)題，也未引起重視。 </p><p>　　1947年美國(guó)數(shù)學(xué)家G.B.丹奇克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法──單純形法，為這門(mén)學(xué)科奠定了基礎(chǔ)。 </p><p>　　1947年美國(guó)數(shù)學(xué)家J.von諾伊曼提出對(duì)偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。 </p><p>　　

78、1951年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。 </p><p>　　50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對(duì)偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問(wèn)題，1956年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。 <

79、/p><p>　　線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問(wèn)題。 </p><p>　　1979年蘇聯(lián)數(shù)學(xué)家L. G. Khachian提出解線性規(guī)劃問(wèn)題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。 </p>

80、<p>　　1984年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問(wèn)題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。 </p><p>　　2.1.2線性規(guī)劃理論的發(fā)展方向[5][6][7]</p><p>　　線性規(guī)劃在軍事、工農(nóng)業(yè)、交通和城

81、鎮(zhèn)規(guī)劃等領(lǐng)域中得到廣泛的應(yīng)用。實(shí)際問(wèn)題有的是很大的，大到具有幾萬(wàn)、幾十萬(wàn)甚至上百萬(wàn)的變量和成千上萬(wàn)的約束條件。有的問(wèn)題雖小些，一般也有幾百幾千的變量和成百上千的約束條件。顯然解這類問(wèn)題都離不開(kāi)計(jì)算機(jī)。常用的計(jì)算機(jī)軟件有LINGO,LINDO,MATLAB等。</p><p>　　線性規(guī)劃理論與大系統(tǒng)分析理論相結(jié)合，以解決經(jīng)濟(jì)、社會(huì)、生態(tài)、和政治因素交織在一起的復(fù)雜社會(huì)系統(tǒng)問(wèn)題，或者解決設(shè)計(jì)、工藝、質(zhì)量、生產(chǎn)計(jì)劃、

82、大型試驗(yàn)、技術(shù)改造、成本價(jià)格、市場(chǎng)營(yíng)銷等因素交織在一起的企業(yè)管理中的復(fù)雜問(wèn)題，是線性規(guī)劃理論的主要方向之一。</p><p>　　在大系統(tǒng)理論中，對(duì)于一些含有幾個(gè)層級(jí)的系統(tǒng)（系統(tǒng)含有分系統(tǒng)，分系統(tǒng)又含有子系統(tǒng)，子系統(tǒng)又含有更小的子系統(tǒng)等），通常采用遞階分析的方法進(jìn)行分解和分析。從系統(tǒng)觀點(diǎn)考慮問(wèn)題的多學(xué)科優(yōu)化理論和方法的研究與應(yīng)用，已經(jīng)成為線性規(guī)劃理論的重要發(fā)展方向之一 。我國(guó)的現(xiàn)代化建設(shè)進(jìn)程中，眾多大系統(tǒng)工程（如

83、三峽工程、載人航天工程）中，也大量的采用了系統(tǒng)工程的一些科學(xué)方法，并取得了顯著的成效。反過(guò)來(lái)，實(shí)踐的發(fā)展又不斷地催生新的理論，或者不斷地開(kāi)拓已有應(yīng)用范圍，不斷地創(chuàng)新理論和方法，是所有學(xué)科發(fā)展的生命力源泉之所在，線性規(guī)劃理論的發(fā)展也不例外。</p><p>　　2.2線性規(guī)劃的具體實(shí)現(xiàn)</p><p>　　2.2.1 線性規(guī)劃問(wèn)題的基本步驟[8]</p><p>　　

84、（1）提出并抽象問(wèn)題</p><p><b>　?。?）建立數(shù)學(xué)模型</b></p><p><b>　　（3）求解</b></p><p><b>　?。?）檢驗(yàn)解</b></p><p>　　（5）解得靈敏度分析</p><p><b>　

85、?。?）解得回歸</b></p><p>　　2.2.2 線性規(guī)劃方法的運(yùn)用原則[8]</p><p><b>　?。?）合作原則</b></p><p><b>　?。?）打破常規(guī)原則</b></p><p><b>　?。?）相互滲透原則</b></p&g

86、t;<p>　?。?）客觀獨(dú)立性原則</p><p><b>　　（5）包容性原則</b></p><p><b>　?。?）平衡性原則</b></p><p>　　2.2.3 線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的一般形式[2]</p><p>　?。?）列出約束條件及目標(biāo)函數(shù) </p>

87、;<p>　?。?）畫(huà)出約束條件所表示的可行域 </p><p>　?。?）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值</p><p>　　2.2.4 線性規(guī)劃的模型建立[1][2][9]</p><p>　　從實(shí)際問(wèn)題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟； </p><p>　　1.根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量； </p

88、><p>　　2.由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)； </p><p>　　3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。 </p><p>　　所建立的數(shù)學(xué)模型具有以下特點(diǎn)： </p><p>　　1、每個(gè)模型都有若干個(gè)決策變量，其中為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。<

89、/p><p>　　2、目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問(wèn)題可以是最大化或最小化，二者統(tǒng)稱為最優(yōu)化。 </p><p>　　3、約束條件也是決策變量的線性函數(shù)。 </p><p>　　當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。</p><p>　　2.2.5線性規(guī)劃的解法</p&g

90、t;<p>　　求解線性規(guī)劃問(wèn)題的基本方法是單純形法，現(xiàn)在已有單純形法的標(biāo)準(zhǔn)軟件，可在電子計(jì)算機(jī)上求解約束條件和決策變量數(shù)達(dá) 10000個(gè)以上的線性規(guī)劃問(wèn)題。為了提高解題速度，又有改進(jìn)單純形法、對(duì)偶單純形法、原始對(duì)偶方法、分解算法和各種多項(xiàng)式時(shí)間算法。對(duì)于只有兩個(gè)變量的簡(jiǎn)單的線性規(guī)劃問(wèn)題，也可采用圖解法求解。這種方法僅適用于只有兩個(gè)變量的線性規(guī)劃問(wèn)題。它的特點(diǎn)是直觀而易于理解，但實(shí)用價(jià)值不大。通過(guò)圖解法求解可以理解線性規(guī)劃

91、的一些基本概念。</p><p>　　2.2.5.1單純形法[1][2]</p><p>　　單純形法是求解線性規(guī)劃問(wèn)題的一般方法，原則上它適用于任何線性規(guī)劃問(wèn)題。這是丹齊克在1947年提出來(lái)的. 它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是維向量空間中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。大量的實(shí)際表明,這是一種行之有效的解法.單純形法的基本思

92、想是：先找出一個(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>　　單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問(wèn)題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛

93、盾，則問(wèn)題無(wú)解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問(wèn)題的最優(yōu)解。⑤若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。下面把單純形法的計(jì)算步驟及迭代過(guò)程歸結(jié)如下圖：</p><p><b>　　并得出單純形表：</

94、b></p><p>　　這樣就可以得出一般線性規(guī)劃問(wèn)題的解。</p><p>　　有關(guān)單純形法的進(jìn)一步討論，當(dāng)線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式后約束條件的系數(shù)矩陣中含有單位矩陣，以此作初始基，用人工變量法（大法）求解。用大法處理人工變量，在用手工計(jì)算求解時(shí)不會(huì)碰到麻煩，但用電子計(jì)算機(jī)求解時(shí)，由于計(jì)算機(jī)取值時(shí)的誤差，有可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為了克服這個(gè)困難，可以對(duì)添加人工變量后的線性規(guī)劃問(wèn)

95、題分兩個(gè)階段來(lái)計(jì)算，稱兩階段法。</p><p>　　2.2.5.2 對(duì)偶單純形法[6]</p><p>　　每一個(gè)線性規(guī)劃問(wèn)題都有另一個(gè)與其相互關(guān)聯(lián)的問(wèn)題，這個(gè)新問(wèn)題具有非常重要的性質(zhì)，用這些性質(zhì)可以更加有效地獲得原來(lái)問(wèn)題的解。為區(qū)別起見(jiàn)，我們稱原來(lái)的問(wèn)題為原問(wèn)題，稱與原問(wèn)題相關(guān)聯(lián)的問(wèn)題為對(duì)偶問(wèn)題。</p><p><b>　　1.對(duì)偶理論</b&

96、gt;</p><p>　　以如下的線性規(guī)劃問(wèn)題和其對(duì)偶問(wèn)題：</p><p>　　這里表示原問(wèn)題，表示對(duì)偶問(wèn)題。</p><p><b>　　2.對(duì)偶單純形法</b></p><p>　　對(duì)偶單純形算法可以概括如下：</p><p>　　(1)找出原問(wèn)題的一個(gè)基，構(gòu)成起始對(duì)偶基可行解，是對(duì)所有的

97、有</p><p>　　構(gòu)成原始對(duì)偶單純形法表；</p><p>　　(2)假如,則當(dāng)前的解是最優(yōu)解，停止計(jì)算。否則選擇樞行，其，</p><p><b>　　例如選擇你最小者：</b></p><p>　　(3)假如對(duì)所有列，則對(duì)偶問(wèn)題無(wú)界，原問(wèn)題無(wú)解，停止計(jì)算。否則選擇樞列；</p><p>

98、　?。?）以為樞元素變換對(duì)偶單純形表，然后轉(zhuǎn)達(dá)步驟（2）。</p><p>　　2.2.5.3 靈敏度分析[2][6]</p><p>　　靈敏度分析一詞的含義是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度的分析。靈敏度分析意義很大。其一，很多實(shí)際問(wèn)題中數(shù)據(jù)常常是不夠精確的，很多是估計(jì)出來(lái)的，因此調(diào)整數(shù)據(jù)是常事。其二，當(dāng)一個(gè)用于決策的問(wèn)題得出最優(yōu)解后，決策者為了通觀全局，常常要研究其中某

99、些因素（數(shù)據(jù)）的改變對(duì)當(dāng)前最優(yōu)決策所造成的影響。其三，當(dāng)作多種方案比較時(shí)，這些不同方案常常是某些數(shù)據(jù)不同而已。靈敏度分析的步驟可歸納如下：</p><p>　　1.將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表來(lái)。具體方法是，按照下列公式計(jì)算出由參數(shù)，，的變化而引起的最終單純形表上有關(guān)數(shù)字的變化。</p><p>　　2. 檢查原問(wèn)題是否仍為可行解。</p><p>　　3

100、. 檢查對(duì)偶問(wèn)題是否仍為可行解。</p><p>　　4. 按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。</p><p>　　2.2.6 線性規(guī)劃的其他算法和問(wèn)題[1][6]</p><p><b>　　1.分解算法</b></p><p>　　分解算法是一種處理大型問(wèn)題的方法，它把一個(gè)大型問(wèn)題分解成若干個(gè)規(guī)模較小的問(wèn)題

101、來(lái)求解，這種方法不僅可以減少存儲(chǔ)量，也能減少計(jì)算量。因?yàn)榫€性規(guī)劃的計(jì)算量對(duì)于約束條件的個(gè)數(shù)m很敏感，統(tǒng)計(jì)表明，計(jì)算量大約與成正比，因此，若把一個(gè)大型問(wèn)題轉(zhuǎn)化為求解若干個(gè)小型問(wèn)題，由于每個(gè)小型問(wèn)題的約束條件個(gè)數(shù)較少，可使總的計(jì)算量大大減少。</p><p>　　2. Karmarkar 算法</p><p>　　1984年N.Karmarkar提出了一個(gè)屬于多項(xiàng)式時(shí)間算法的內(nèi)點(diǎn)法，并證明其計(jì)

102、算復(fù)雜性是0，這是一種能解決大型線性規(guī)劃問(wèn)題的強(qiáng)有力的算法。它的應(yīng)用十分廣泛，如應(yīng)用這一系統(tǒng)規(guī)模的多項(xiàng)式時(shí)間算法用于電力系統(tǒng)，可以使實(shí)時(shí)電價(jià)計(jì)算等問(wèn)題變的簡(jiǎn)單。</p><p>　　3.整數(shù)線性規(guī)劃問(wèn)題</p><p>　　在線性規(guī)劃問(wèn)題中，當(dāng)某些變量（或全部變量）取整數(shù)值時(shí)，該規(guī)劃問(wèn)題就稱為整數(shù)規(guī)劃問(wèn)題。整數(shù)規(guī)劃可以看成是線性規(guī)劃問(wèn)題中對(duì)變量進(jìn)行整數(shù)約束的一種特殊形式，因此，可以認(rèn)為，整

103、數(shù)規(guī)劃問(wèn)題一般要比相應(yīng)的線性規(guī)劃問(wèn)題約束得更緊。整數(shù)規(guī)劃中，如果所有的變量都要求取整數(shù)值，則稱此規(guī)劃問(wèn)題為純整數(shù)規(guī)劃；如果部分變量要求取整數(shù)值，則稱此規(guī)劃問(wèn)題為混合整數(shù)規(guī)劃；如果要求變量的取值為0或1，則稱此規(guī)劃問(wèn)題為0-1規(guī)劃。</p><p>　　4.影子價(jià)格與影子成本[10]</p><p>　　根據(jù)線性規(guī)劃問(wèn)題對(duì)偶變量和影子價(jià)格的經(jīng)濟(jì)意義，給出了影子成本的概念，討論了影子成本與對(duì)偶

104、價(jià)格的關(guān)系。通過(guò)靈敏度分析給出了影子成本的動(dòng)態(tài)表示，并進(jìn)一步闡明了影子價(jià)格和影子成本的惟一性以及影子成本在經(jīng)濟(jì)管理中的應(yīng)用。</p><p>　　5. 有界變量線性規(guī)劃問(wèn)題</p><p>　　實(shí)際應(yīng)用中的許多線性規(guī)劃問(wèn)題，其決策變量具有上、下界限制。這類問(wèn)題稱為有界變量線性規(guī)劃問(wèn)題。它的一般數(shù)學(xué)模型可寫(xiě)為</p><p><b>　　，</b>

105、;</p><p><b>　　，</b></p><p><b>　　,</b></p><p>　　其中，分別為的下界和上界；認(rèn)為階矩陣，，并設(shè)的秩為.</p><p>　　2.3 線性規(guī)劃理論的應(yīng)用</p><p>　　2.3.1 線性規(guī)劃在企業(yè)中運(yùn)用的必要性[11]&

106、lt;/p><p>　　隨著經(jīng)濟(jì)全球化的不斷發(fā)展，企業(yè)面臨更加激烈的市場(chǎng)競(jìng)爭(zhēng)。企業(yè)必須不斷提高盈利水平，增強(qiáng)其獲利能力，在生產(chǎn)、銷售、新產(chǎn)品研發(fā)等一系列過(guò)程中只有自己的優(yōu)勢(shì)，提高企業(yè)效率，降f氐成本，形成企業(yè)的核心競(jìng)爭(zhēng)力，才能在激烈的競(jìng)爭(zhēng)中立于不敗之地。過(guò)去很多企業(yè)在生產(chǎn)、運(yùn)輸、市場(chǎng)營(yíng)銷等方面沒(méi)有利用線性規(guī)劃進(jìn)行合理的配置，從而增加了企業(yè)的生產(chǎn)，使企業(yè)的利潤(rùn)不能達(dá)到最大化。在競(jìng)爭(zhēng)日益激烈的今天，如果還按照過(guò)去的方式，

107、是難以生存的，所以就有必要利用線性規(guī)劃的知識(shí)對(duì)戰(zhàn)略計(jì)劃、生產(chǎn)，銷售各個(gè)環(huán)節(jié)進(jìn)行優(yōu)化從而降低生產(chǎn)成本，提高企業(yè)的效率。在各類經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問(wèn)題：在生產(chǎn)條件不變的情況下，如何通過(guò)統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，組織生產(chǎn)過(guò)程，使總的經(jīng)濟(jì)效益最好。這樣的問(wèn)題常?？梢曰苫蚪频鼗伤^的“線性規(guī)劃” (Linear Pmgramming，簡(jiǎn)記為L(zhǎng)P)問(wèn)題。線性規(guī)劃是應(yīng)用分析、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)

108、、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)有效管理。利用線性規(guī)劃我們可以解決很多問(wèn)題。如：在不違反一定資源限制下，組織安排生產(chǎn)，獲得最好的經(jīng)濟(jì)</p><p>　　2.3.2 線性規(guī)劃的應(yīng)用實(shí)例</p><p>　　數(shù)學(xué)與經(jīng)濟(jì)的結(jié)合由來(lái)已久。從經(jīng)濟(jì)學(xué)作為一門(mén)學(xué)科的發(fā)展看，數(shù)學(xué)在其中的位置越來(lái)越重要，它不僅幫助人們?cè)诮?jīng)營(yíng)中獲利，而且給予人們以能力，包括直觀思維、邏輯思維

109、、精確計(jì)算等等，以至于今天，不懂?dāng)?shù)學(xué)就無(wú)法研究經(jīng)濟(jì)。前蘇聯(lián)數(shù)學(xué)家坎托羅維奇因?qū)ξ镔Y最優(yōu)調(diào)撥理論的貢獻(xiàn)獲1975年諾貝爾獎(jiǎng)，他被公認(rèn)為最優(yōu)規(guī)劃理論的創(chuàng)始人，經(jīng)濟(jì)數(shù)學(xué)理論的奠基人?？餐辛_維奇創(chuàng)造的線性規(guī)劃方法被廣泛地應(yīng)用于經(jīng)濟(jì)領(lǐng)域并為經(jīng)濟(jì)發(fā)展作出了卓越貢獻(xiàn)。[12]</p><p>　　線性規(guī)劃作為運(yùn)籌學(xué)的一個(gè)重要分支，在經(jīng)濟(jì)管理中有著極其廣泛的應(yīng)用，比如設(shè)計(jì)一個(gè)物流網(wǎng)絡(luò)的問(wèn)題。[13]以下是一些常用的應(yīng)用舉例。&l

110、t;/p><p>　　1.線性規(guī)劃在薪酬管理中的應(yīng)用[14]</p><p>　　知識(shí)經(jīng)濟(jì)時(shí)代，現(xiàn)代化的大型企業(yè)或企業(yè)集團(tuán)不斷涌現(xiàn)，大企業(yè)的內(nèi)部管理模式更加復(fù)雜，必須提高企業(yè)內(nèi)部的控制力、執(zhí)行力、及對(duì)市場(chǎng)變化能夠快速做出的反應(yīng)能力。線性規(guī)劃是人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法，通過(guò)在薪酬管理宏觀和微觀兩方面的應(yīng)用，提高企業(yè)管理水平，實(shí)現(xiàn)最佳經(jīng)濟(jì)效益。</p><p>　　2

111、.線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用[15]</p><p>　　在企業(yè)生產(chǎn)過(guò)程中，生產(chǎn)計(jì)劃安排直接影響到企業(yè)的經(jīng)濟(jì)效益，而解決生產(chǎn)計(jì)劃問(wèn)題的有效方法之一就是建立線性規(guī)劃模型，線性規(guī)劃為企業(yè)制定生產(chǎn)計(jì)劃提供了一種簡(jiǎn)單又科學(xué)的方法，具有一定的實(shí)用價(jià)值。</p><p>　　3.線性規(guī)劃在服裝生產(chǎn)任務(wù)分配中的應(yīng)用[16]</p><p>　　針對(duì)不確定條件下實(shí)際的服裝生產(chǎn)任

112、務(wù)分配問(wèn)題，采用線性規(guī)劃優(yōu)化的方法予以解決。為此，建立了服裝生產(chǎn)任務(wù)分配的數(shù)學(xué)模型，在保證交貨期的前提下，將線性規(guī)劃法對(duì)生產(chǎn)任務(wù)進(jìn)行優(yōu)化分配，使加工成本最小。生產(chǎn)實(shí)例表明，所提出的優(yōu)化方法能夠使服裝生產(chǎn)系統(tǒng)得到整體優(yōu)化，表明其有效性和可行性。</p><p>　　4.線性規(guī)劃在企業(yè)成本控制中的應(yīng)用[17]</p><p>　　企業(yè)成本由原材料，制造費(fèi)用等要素構(gòu)成，通過(guò)構(gòu)建企業(yè)成本構(gòu)成的數(shù)學(xué)

113、模型及約束條件，求解使企業(yè)成本總體最低的最優(yōu)解，同時(shí)解釋各要素變化對(duì)企業(yè)利潤(rùn)的影響程度，為企業(yè)成本控制指明方向。</p><p>　　5.線性規(guī)劃在飲料的生產(chǎn)銷售模型中的應(yīng)用[18]</p><p>　　應(yīng)用運(yùn)籌學(xué)中的線性規(guī)劃原理，研究了在給定務(wù)件下，按某一衡量指標(biāo)來(lái)尋找安排的最優(yōu)方案問(wèn)題．且研究了工廠安排合理的生產(chǎn)計(jì)劃、管理資源和人力資源，使得企業(yè)在有限的資本情況下，獲得總費(fèi)用最少或者總