1、-摘 要線性規劃是解決稀缺資源最優分配的有效方法，使付出的費用最少或獲得的利益最大。它的研究對象是有一定的人力、財力、資源條件下，如何合理安排使用，效益最高；*項任務確定后，如何安排人、財、物，使之最省。它要解決的問題的目標可以用數值指標反映，對于要實現的目標有多種方案可以選擇，有影響決策的假設干約束條件。本文主要介紹了線性規劃模型在實際生活中的應用，其中包括解線性方程組的各種方法，如圖解法、單純形法、以及對偶單純形法等等，以及簡單介紹了有關靈敏度分析的方法。由于許多問題僅僅利用線性規劃的方法還缺乏以解決，因此用到了對偶理論，也因此引出了對偶單純形法。對偶規劃是線性規劃問題從另一個角度進展研究

2、，是線性規劃理論的進一步深化，也是線性規劃理論整體的一個不可分割的組成局部。靈敏度分析是對線性規劃結果的再開掘，是對線性規劃理論的充要應用，本文以實例驗證靈敏度分析的實際應用。 關鍵詞：線性規劃；單純形法；對偶單純形法. z-ABSTRCTLinear programming is an effective method to solve the optimal allocation of scarce resources, make the cost of pay or receive at least the interests of the largest. Its object of

3、study is the human and financial resources, resource conditions, how to reasonably arrange to use, benefit is supreme; A task is determined, how to arrange people, goods, and make it the most provinces. It to the target can be used to solve the problem of the numerical indicators, to achieve a varie

4、ty of solutions to choose from, have an impact on the decision of some constraint conditions. Through the subject design, can deepen the operations research, optimization method, linear programming, nonlinear programming, to improve the integrated use of knowledge, improve the ability of using the s

5、ensitivity analysis to solve various practical problems. This article mainly introduces the application of linear programming model in real life, including the various methods of solving linear equations, as shown in figure method, simple* method and dual simple* method, etc., and simply introduces

6、the method of sensitivity analysis. Due to many problems just by using the method of linear programming is not enough to solve, so use the duality theory, thus raises the dual simple* method. The dual programming is linear programming problem from another Angle, is the further deepening of linear pr

7、ogramming theory, linear planning theory as a whole is also an integral part of. Sensitivity analysis is to discover, the result of the linear programming is the charge to application of linear programming theory.Keywords: linear programming；Simple* method；The dual simple* method. z-目 錄前言線性規劃模型的應用與靈

8、敏度分析1第一章 線性規劃問題11. 線性規劃及靈敏度分析簡介12. 線性規劃模型應用的開展13. 線性規劃模型研究的問題24. 線性規劃模型的應用24.1問題24.2線性規劃方法的特點及局限性24.3線性規劃模型的根本構造34.4線性規劃模型的一般形式34.4線性規劃的性質5第二章 求解線性規劃的方法61. 圖解法62. 單純行法72.1 單純行法的根本思路72.2 單純形法的求解步驟112.3 單純形法的求解過程小結122.3.1人造基、初始根本可行解122.3.2最優解判別定理：142.3.3單純行過程的兩種方法143. 單純行法143.1對偶問題的提出143.2線性規劃的對偶理論153

9、.3對偶單純形法的步驟154. 單純行表15第三章 靈敏度分析171. 邊際值(影子價)172. 價值向量的靈敏度分析183. 靈敏度的應用19第四章 應用設計實例191. 目標函數系數靈敏度分析192. 右邊值敏感性分析19結 論22參考文獻23致 24. z-前 言線性規劃是運籌學的一個重要分支。1947年，當時正在美國空軍擔任數學參謀的Dantzig在?最優規劃的科學計算?中提出“如何使規劃過程機械化問題，并著手建立數學模型。他從改造投入產出模型入手，逐步研究，形成了“單純形法，并于1953年提出“改良單純形法，以解決計算機求解過程中的舍入誤差問題。之后，線性規劃理論逐步趨于成熟，在實用

10、中日益廣泛和深入。通過設計該課題，可以加深對運籌學、最優化、線性規劃、非線性規劃以及MATLAB的認識，提高對這些知識的綜合應用水平，提高利用靈敏度分析解決各種線性規劃問題的能力。本文章主要介紹了線性規劃在實際生活中的應用，包括解線性方程組的各種方法，包括圖解法，單純形法，大M法，二階段法以及對偶單純形法，以及簡要介紹了有關靈敏度分析的方法。由于線性方程組是解決各種應用問題的主要工具， 而有許多問題僅僅利用線性規劃的解決方法還缺乏以解決問題，還用到了對偶理論，也因此引出了對偶單純形法。本課題當前的研究方向有：LP的點算法，它通過非線性規劃解決線性問題，其成功是對數學思想的革新；算法復雜度，評價

11、算法好壞應從平均工作量出發；大型問題的分解算法、近似算法。線性規劃的應用正在不斷擴大，企業成功確實通過提高生產和有效使用資源的競爭過程來到達。. z-線性規劃模型的應用與靈敏度分析第一章 線性規劃問題1. 線性規劃及靈敏度分析簡介線性規劃(Linear Programming)問題, 簡稱LP問題,是運籌學中最根本, 也是最重要的容, 被廣泛地應用于軍事決策、企業管理、工程設計、交通運輸等領域. 特別是經濟領域應用更為廣泛, 有資料稱, 在對500家有相當效益的公司所作的評述中, 有85%的公司都曾應用了線性規劃。靈敏度分析對于決策者的重要性不言而喻，在真實世界里，周圍的環境、條件是在不斷變化

12、的。2. 線性規劃模型應用的開展線性規劃及其通用解法單純形法是由美國在1947年研究空軍軍事規劃提出來的。法國數學家傅里葉和瓦萊普森分別于1832和1911年獨立地提出線性規劃的想法，但未引起注意。1939年聯數學家康托羅維奇在?生產組織與方案中的數學方法?一書中提出線性規劃問題，也未引起重視1。1947年美國數學家丹齊克提出線性規劃的一般數學模型和求解線性規劃問題的通用方法單純形法，為這門學科奠定了根底。1947年美國數學家諾伊曼提出對偶理論,開創了線性規劃的許多新的研究領域，擴大了它的應用圍和解題能力2。1951年美國經濟學家庫普曼斯把線性規劃應用到經濟領域，為此與康托羅維奇一起獲1975

13、年諾貝爾經濟學獎。50年代后對線性規劃進展大量的理論研究，并涌現出一大批新的算法。例如，1954年萊姆基提出對偶單純形法，1954年加斯和薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題，1956年塔克提出互補松弛定理，1960年丹齊克和沃爾夫提出分解算法等。線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的算法研究3。1984年美國貝爾實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法。用這種方法求解線性規劃問題在變量個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式算法理論。50年代后線性規劃的應用圍不斷擴大4。3. 線性

14、規劃模型研究的問題建立線性規劃模型線性規劃研究的問題主要有兩類:一類是當一項任務確定后，如何統籌安排，盡量做到以最少的人力、物力等資源去完成；另一類是在人力、物力等資源確定的情況下，如何安排使用這些資源，使創造的價值最多，其實質是解決稀缺資源在有競爭環境中如何進展最優分配的問題，即尋求整個問題的*個整體指標最優的問題4。4. 線性規劃模型的應用4.1問題a.目標函數最優化單一目標，多重目標問題如何處理.b.實現目標的多種方法，假設實現目標只有一種方法不存在規劃問題。 c.生產條件的約束資源是有限的，資源無限不存在規劃問題。4.2線性規劃方法的特點及局限性 特點：a.可以使研究對象具體化、數量化

15、。可以對所研究的技術經濟問題做出明確的結論；b.線性；c.允許出現生產要素的剩余量；d.有一套完整的運算程序；局限性：a. 線性規劃它是以價格不變和技術不變為前提條件的，不能處理涉及到時間因素的問題。因此，線性規劃只能以短期方案為根底。b.在生產活動中，投入產出的關系不完全是線性關系，由于在一定的技術條件下，報酬遞減規律起作用，所以要滿足線性假定是不可能的。在線性規劃解題中，常常把投入產出的非線性關系轉化為線性關系來處理，以滿足線性的假定性，客觀上產生誤差。c.線性規劃本身只是一組方程式，并不提供經濟概念，它不能代替人們對現實經濟問題的判斷。 4.3線性規劃模型的根本構造(1)決策變量 未知數

16、。它是通過模型計算來確定的決策因素。又分為實際變量求解的變量和計算變量，計算變量又分松弛變量上限和人工變量下限。 (2)目標函數經濟目標的數學表達式。目標函數是求變量的線性函數的極大值和極小值這樣一個極值問題。 (3)約束條件實現經濟目標的制約因素。它包括：生產資源的限制客觀約束條件、生產數量、質量要求的限制主觀約束條件、特定技術要求和非負限制。4.4線性規劃模型的一般形式極大值模型 (1-1) (1-2) (1-3)其簡縮形式為 極小值模型 (1-4) (1-5) (1-6)其簡縮形式為 模型的簡縮形式可用向量表示 例1 生產安排模型，*工廠生產I、II兩種產品，生產單位產品所需的設備臺時及

17、A、B兩種原材料的消耗，如表所示。III資源總量設備128/臺時原材料A4016/千克原材料B0412/千克該工廠生產一單位產品I可獲利2元，生產產品II可獲利3元，問如何安排生產獲利最大.解：本問題是目標最大化問題：(1)決策變量，設*1, *2為產品I、II的生產數量；(2)目標函數，2*1+3*2；(3)約束條件，設備限制： *1+2*2 8原材料A限制： 4*1 16原材料B限制： 4*2 12根本要求：*10 ， *20 該模型記為如下形式 ma*Z=2*1+3*2s.t.*1+2*2 84*1 164*2 12*1 ，*2 0其中ma*表示本問題是最大值問題用min表示最小值問題，

18、 s.t.(subject to的縮寫)表示約束條件。這就是一個線性規劃模型5。4.4線性規劃的性質定理1 線性規劃問題的可行解*是基可行解的充要條件是*的非零分量對應的系數矩陣A的列向量線性無關6。定理2 假設一個線性規劃問題有可行解，則它必有根本可行解7。定理3 假設可行域有界，線性規劃問題的目標函數一定可以在其可行域的頂點到達最優。第2章 求解線性規劃的方法1. 圖解法圖解法是求解線性規劃模型的一種重要方法，線性規劃中一些重要的性質、概念和求解思想都來源于此。當只有兩個決策變量時，可以用圖解法求解。它具有簡單直觀的特點。為了給后面的線性問題的根本理論提供較直觀的幾何說明，先介紹線性規劃問

19、題的圖解法8。圖解法的求解步驟如下：第一步，根據約束畫出可行域，先以決策變量為坐標，建立直角坐標系，再根據各約束條件，作出可行域。第二步，作出一條目標函數等值線，并確定增值方法。第三步，沿等值線的法線方向值增大方向移動，從而找到最大值。圖解法得出線性規劃的幾種情況：表2-1 解旳幾種情況解旳幾種情況約束條件圖形特點方程特點唯一解一般圍成有限區域，最優值只在一個頂點到達無窮多解在圍成的的區域邊界上，至少有兩個頂點處到達優解目標和*一約束方程成比例無可行解無解圍不成區域有矛盾方程無界解(無解圍成無界區域，且無有限最優解缺少一必要條件的方程例：Min Z=10*1+20*22. 單純形法單純形法是美

20、國數學家于1947年首先提出的。它的理論根據是：線性規劃問題的可行域是n維向量空間nR中的多面凸集，其最優值如果存在必在該凸集的*頂點處到達9。它的原理涉及到較多的數學理論上的推導和證明，我們在此僅介紹這種方法的具體操作步驟及每一步的經濟上的含義。為更好地說明問題，我們仍結合實例介紹這種方法。 單純形法simple* methods，求解線性規劃的通用方法。 2.1單純形法的根本思路單純形法的根本思路是：根據線性規劃問題的標準型，從可行域中*個根本可行解一個頂點開場，轉換到另一個根本可行解頂點，并且當目標函數到達最大值時，問題就得到了解決，其根本思路的框架圖如以下圖2-1。圖2-1.單純行法的

21、根本思路用單純行法討論例1的求解解：例1的標準型為2-12-2約束條件2-2的系數矩陣顯然，*3，*4，*5的系數列向量 2-3是線性獨立的，因而這些向量構成一個基(2-4)對應于B的基變量為*3,*4,*5，從約束條件2-2中可以看到2-5當令非基變量這時得到一個根本可行解*02-6將式(2-3)代入目標函數(2-1)得到2-7這個根本可行解表示：工廠沒有安排生產產品；資源都沒有被利用，所以工廠的利潤Z=0。分析目標函數的表達式(2-7)可以看到：非基變量*1,*2的系數都是正數，因此將非基變量變為基變量，目標函數的值就可能增大，從經濟意義上講，安排生產產品或，就可以使工廠的利潤指標增加，所

22、以只要在目標函數(2-7)的表達式中還存在有正系數的非基變量，這表示目標函數值還有增加的可能，就需要將非基變量與*個基變量進展對換，一般選擇正系數最大的那個非基變量*2為換入變量，將它換入到基變量中區，同時還有確定基變量中有一個要換出來成為非基變量，可按以下方法來確定換出變量。現分析式(2-5)，當將*2定為換入變量后，必須從*3,*4,*5中換出一個，并保證其余的都是非負，即*3,*4,*5。當*1=0，由式(2-5)得到 2-8可以看出，只有選擇 2-9 時，才能使式(2-8)成立。以上數學模型說明了每生產一件產品，需要用掉的各種資源數為(2,0,4)。這些資源中的薄弱環節確定了產品的產量

23、。原材料B的數量決定產品的產量只能是*2=12/4=3件。為了求得以*3，*4，*2為基變量的一個根本可行解和進一步分析問題，需將方程(2-5)中*2的位置對換。得到 2-10用高斯消去法求解，得到以非基變量表示的基變量 2-11代入目標函數得到 (2-12) 令非基變量得到并得另一個根本可行解。從目標函數的表達式(2-12)中可以看到，非基變量的系數是正的，說明目標函數的值還可以增大，還不是最優解。于是用上述方法，確定換入、換出變量，繼續迭代，再得到另外一個根本可行解。再經過一次迭代，得到一個根本可行解。而這時得到的目標函數的表達式是 2-13再分析目標函數(2-13),可知所有非基變量的系

24、數都是負數，這說明假設要用剩余資源就必須支付附加費用。所以當時，即不再利用這些資源時，目標函數到達最大值，則是最優解。這說明當產品生產4件，產品生產2件，工廠才能得到最大利潤。通過上例，可以了解利用單純形法求解線性規劃問題的思路。 2.2單純形法的求解步驟 線性規劃問題的求解有以下幾個步驟： (1)確定初始根本可行解。為了確定初始根本可行解，首先要找出初始可行解。設一線性規劃問題為 2-14可分為兩種情況討論。假設中存在一個單位基，則將其作為初始可行基 2-15假設中不存在一個單位基，則人為地構造一個單位初始基。(2)檢驗最優解。得到初始根本可行解后，要檢驗該解是否為最優解。如果是最優解，則停

25、頓運算；否則轉入3基變換。下面給出最優性判別定理。一般情況下，經過迭代后可以得到以非基變量表示基變量的表達式 2-16將式(2-11)代入式(2-10)的目標函數，整理后得 2-17令 2-18于是2-19再令2-20則得到以非基變量表示目標函數的表達式2-21 (3)基變換。假設初始根本可行解不是最優解，又不能判別無界時，由目標函數(2-10)的約束條件可看到，當*些增加則目標函數值還可能增加這時就要將其中*個非基變量換到基變量中去稱為換入變量，同時，*個基變量要換成非基變量稱為換出變量，隨之會得到一個新的根本可行解。從一個根本可行解到另一個根本可行解的變換，就是進展一次基變換。從幾何意義上

26、就是從可行域的一個頂點轉向另一個頂點。 (4)迭代。在確定了換入變量和換出變量后，要把和的位置進展對換，就是說要把對應的系數列向量變成單位列向量。這可以通過對約束方程組的增廣矩陣進展初等行變換來實現，變換結果得一新的根本可行解。 2.3單純形法的求解過程小結2.3.1人造基、初始根本可行解 (1)假設從線性規劃問題的Pj中能直接觀察到存在m個線性獨立的單位向量，經過重新安排次序便得到一個可行基。 (2)“標準化的方法，引入非負的松弛變量重新對及編號，經整理則可得到以下方程顯然得到一個單位陣我們就將B作為可行基。 我們就將B作為可行基。將每個等式進展移項得 令由等式可得 得到一個初始根本可行解

27、2.3.2最優性檢驗得到初始可行解后，要檢驗一下是否是最優解，如果是則停頓迭代，如果不是，則繼續迭代。但每次迭代后都要檢驗是否是最優解，為此需要建立一個判別準則。一般情況下，經過迭代后式變成將上式代入目標函數，整理后得2.3.3最優解判別定理：假設 為對應于B的根本可行解，且對于一切有*0為最優解。無有限最優解判別定理：假設為對應于B的根本可行解，有一個并且對于一切i=1,2,3,m有則該線性規劃沒有有限最優解。 a.換入變量確實定 則對應的為換入變量 b.換出變量確實定為換入變量。2.3.4單純形法過程的兩種方法在單純形迭代過程中，要求人工變量逐步從基變量被替換出，變為非基變量，這有兩種方法

28、：大M法和兩階段法10。3. 對偶單純形法對偶規劃是線性規劃問題從另一個角度進展研究，是線性規劃理論的進一步深化，也是線性規劃理論的進一步深化，也是線性規劃理論整體的一個不可分割.3.1對偶問題的提出每個線性規劃都有另一個線性規劃對偶問題與它密切相關，對偶理論提醒了原問題與對偶問題的在聯系11。考慮到對偶模型的約束與原問題模型的變量相對應，變量則是與原問題模型的約束相對應。原問題是最小化，則可將對偶問題看做原問題12。3.2線性規劃的對偶理論定理2-1(對稱性定理) 對偶問題的對偶是原問題。定理2-2(弱對偶定理) 設*和Y分別是原問題P和對偶問題D的可行解，則有13。定理2-3(對偶原理)

29、定理2-4(互補松弛定理) 如果*和Y分別為P和D的可行解，它們分別為P和D的最優解的充要條件是3.3對偶單純形法的步驟對偶單純形法是用對偶理論求解原問題的一種方法，而不是求解對偶問題解的單純形法。與對偶單純形法相對應，已有的單純形法稱原始單純形法14。（1） 建立初始單純形表，計算檢驗數行（2） 先確定換出變量-解答列中的負元素一般選最小的負元素對應的基變量出基；（3） 將主元素進展換基迭代旋轉運算、樞運算)，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續以上步驟，直至求出最優解15。4. 單純形表表2-2 單純形表也可以反映線性規劃在現實生活中的運用初單純形表實際活動松弛活動比

30、值*1*2*3*4*5R0*382300060*4161210040*51240010-目標系數行23000檢驗數行023000第二單純形表實際活動松弛活動比值*1*2*3*4*5R0*362010030*421210020*5164001043*2304001-檢驗數行20000903000第三單純形表實際活動松弛活動比值*1*2*3*4*5R0*32001-2042*1212010-0*58000-4143*230100012檢驗數行000-201323020第三章 靈敏度分析靈敏度分析是研究與分析一個系統(或模型)的狀態或輸出變化對系統參數或周圍條件變化的敏感程度的方法。在最優化方法中經

31、常利用靈敏度分析來研究原始數據不準確或發生變化時最優解的穩定性。通過靈敏度分析還可以決定哪些參數對系統或模型有較大的影響。因此，靈敏度分析幾乎在所有的運籌學方法中以及在各種方案進展評價時都是很重要的16。1. 邊際值(影子價) 是指在最優解的根底上，當第i個約束行的右端項減少一個單位時，目標函數的變化量時機本錢 因此時機本錢的另外表達形式關于影子價的一些說明影子價是資源最優配置下資源的理想價格，資源的影子價與資源的緊缺度有關；松弛變量增加一個單位等于資源減少一個單位；剩余變量增加一個單位等于資源增加一個單位；資源有剩余，在最優解中就有對應松弛變量存在，且其影子價為0；影子價為0，資源并不一定有

32、剩余。2. 價值向量的靈敏度分析價值向量(即目標函數系數)的靈敏度分析分為原最終單純形表中jc與非基變量和基變量對應兩種情況來討論17。（1） 假設是非基變的系數，則其對應的最終單純形表中的檢驗數為當變化，要保證最終單純形表的最優解不變，必有保證最終單純形表最優解不變，可得的允許變化值2假設是基變量的系數，應有,當變化時，就引起的變化這時假設要求原最優解不變，必須滿足。于是得到可變化的圍是3. 靈敏度的應用 (1)投入產出法中靈敏度分析可以用來研究采取*一項重大經濟政策后將會對國民經濟的各個部門產生怎樣的影響。 (2)方案評價中靈敏度分析 可以用來確定評價條件發生變化時備選方案的價值是否會發生

33、變化或變化多少。第4章 應用設計實例*農戶方案用12公頃耕地生產玉米，大豆和地瓜，可投入48個勞動日，資金360元。生產玉米1公頃，需6個勞動日，資金36元，可獲凈收入200元；生產1公頃大豆，需6個勞動日，資金24元，可獲凈收入150元；生產1公頃地瓜需2個勞動日，資金18元，可獲凈收入1200元，問怎樣安排才能使總的凈收入最高。設種玉米，大豆和地瓜的數量分別為*1、*2和*3公頃，根據問題建立線性規劃問題模型如下：Ma* Z=200*1+150*2+100*3*1+*2+*312 6*1+6*2+2*348 (4-1) 36*1+24*2+183360 (4-2)*10，*20，*301.

34、 目標函數系數靈敏度分析表4-1 目標系數的允許變動圍活動目標系數可減上限可增上限可變圍玉米種植*1大豆種植*2地瓜種植*320015010050 無窮大100/310050100150300-200200/3200 當僅有一種目標系數在允許圍變動時，最優方案不會變動，但最優目標值會隨之變化。2. 右邊值敏感性分析由線性規劃的原理可知，影子價格不變的條件是最優解的松弛變量矩陣與右邊值矩陣的乘積大于和等于0，即：當右邊值發生變化時，如耕地變化，此時，影子價格不變的條件是得到 6+3/210 6-1/210 -414 36-910因此耕地影子價格不變的耕地數量圍為：8，16得到 61/420 6+1/420 -2428 36-9/220因此勞動力影子價格不變的勞動力數量圍為：24，56得到 60 3 36 3630因此資金影子價格不變的資金數量圍為：324，-表4-2 常數項的允許變動圍資源現有數量可減上限可增上限可變圍影子價格耕地124481650勞動48248245625資金36036+324+0常數項的允許變動圍這一結果也還有另外一種意義，即它給出了資源影子價格