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

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

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

3、的背景和意義，以及它的發(fā)展過程和發(fā)展方向。接著敘述了解決線性規(guī)劃問題的方法及其算法。我們通過分析問題建立數(shù)學(xué)模型，使用適當(dāng)方法求出最優(yōu)解，并對其進(jìn)行分析得到該問題的最優(yōu)值。最后運用線性規(guī)劃理論來解決相關(guān)實際問題，即它被應(yīng)用的過程。</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ā)展過程及其現(xiàn)狀3

8、</p><p>　　2.2線性規(guī)劃的發(fā)展方向3</p><p>　　3.線性規(guī)劃的具體實現(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 對偶單純形法7</p><p>　　3.4靈敏度分析8</p><p>　　3.5線性規(guī)劃的其他算法和問題9</p><p>　　4.線性規(guī)劃的應(yīng)用11</p><p>　　4.1線性規(guī)劃應(yīng)用的現(xiàn)實意義11</p><p&g

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、;b>　?。?）平衡性原則</b></p><p>　　線性規(guī)劃的模型建立和一般形式</p><p>　　線性規(guī)劃的模型建立[1][2][9]</p><p>　　從實際問題中建立數(shù)學(xué)模型一般有以下三個步驟； </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é)模型具有以下特點： </p><p>　　1、每個模型都有若干個決策變量，其中為決策變量個數(shù)。決策變量的一組值表示一種方案，同時決策變量一般是非負(fù)的。</p><p>　

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45、用。</p><p>　　5．有界變量線性規(guī)劃問題</p><p>　　實際應(yīng)用中的許多線性規(guī)劃問題，其決策變量具有上、下界限制。這類問題稱為有界變量線性規(guī)劃問題。它的一般數(shù)學(xué)模型可寫為</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)實意義</p><p>　　隨著經(jīng)濟全球化的不斷發(fā)展，企業(yè)面臨更加激烈的市場競爭。企業(yè)必須不斷提高盈利水平

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

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

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

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

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

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

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

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

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

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

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

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

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

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

61、</p><p>　　然后根據(jù)上述數(shù)學(xué)模型編一個程序：</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%時生產(chǎn)該啤酒成本最低，最低成本為43.9016元。</p><p><b>　　結(jié)論</b></p><p>　　本文首先介紹了線性規(guī)劃理論產(chǎn)生的背景、意義及發(fā)展的過程、現(xiàn)狀和方向，讓大家對線性規(guī)劃有了初步認(rèn)識。然后又介紹了線性

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

66、生產(chǎn)的策劃起到指導(dǎo)作用，給社會帶來了極大的方便。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 張干宗線性規(guī)劃[M].第二版.武漢:武漢大學(xué)出版社,2008,6:1-39.</p><p>　　[2] 胡運權(quá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] 運籌學(xué)編寫組.運籌學(xué)[M] .第三版.北京:清華大學(xué)出版社,2005,6:1-2.</p>

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

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

70、實生活中的應(yīng)用[J].理論研究.2009,7：206-207.</p><p>　　[12] 聶天霞.線性規(guī)劃在經(jīng)濟發(fā)展中的作用[J].鄭州鐵路職業(yè)技術(shù)學(xué)院學(xué)報.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)濟信息.2

72、009,8：139-140.</p><p>　　[15] 孫庭鋒.淺析線性規(guī)劃在企業(yè)生產(chǎn)計劃中的應(yīng)用[J].商業(yè)經(jīng)濟.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)濟信息.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ī)劃是運籌

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

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

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

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

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

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

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

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

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

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

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

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

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

87、;<p>　?。?）畫出約束條件所表示的可行域 </p><p>　?。?）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值</p><p>　　2.2.4 線性規(guī)劃的模型建立[1][2][9]</p><p>　　從實際問題中建立數(shù)學(xué)模型一般有以下三個步驟； </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é)模型具有以下特點： </p><p>　　1、每個模型都有若干個決策變量，其中為決策變量個數(shù)。決策變量的一組值表示一種方案，同時決策變量一般是非負(fù)的。<

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

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

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

92、想是：先找出一個基本可行解，對它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。</p><p>　　單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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