線性規(guī)劃模型的應(yīng)用與靈敏度分析

1、中國(guó)石油大學(xué)勝利學(xué)院本科畢業(yè)設(shè)計(jì)(論文）摘 要線性規(guī)劃是解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最少或獲得的利益最大。它的研究對(duì)象是有一定的人力、財(cái)力、資源條件下，如何合理安排使用，效益最高；某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使之最省。它要解決的問(wèn)題的目標(biāo)可以用數(shù)值指標(biāo)反映，對(duì)于要實(shí)現(xiàn)的目標(biāo)有多種方案可以選擇，有影響決策的若干約束條件。本文主要介紹了線性規(guī)劃模型在實(shí)際生活中的應(yīng)用，其中包括解線性方程組的各種方法，如圖解法、單純形法、以及對(duì)偶單純形法等等，以及簡(jiǎn)單介紹了有關(guān)靈敏度分析的方法。由于許多問(wèn)題僅僅利用線性規(guī)劃的方法還不足以解決，因此用到了對(duì)偶理論，也因此引出了對(duì)偶單純形法。對(duì)偶規(guī)

2、劃是線性規(guī)劃問(wèn)題從另一個(gè)角度進(jìn)行研究，是線性規(guī)劃理論的進(jìn)一步深化，也是線性規(guī)劃理論整體的一個(gè)不可分割的組成部分。靈敏度分析是對(duì)線性規(guī)劃結(jié)果的再發(fā)掘，是對(duì)線性規(guī)劃理論的充要應(yīng)用，本文以實(shí)例驗(yàn)證靈敏度分析的實(shí)際應(yīng)用。 關(guān)鍵詞：線性規(guī)劃；單純形法；對(duì)偶單純形法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.

3、Its object of 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 a

4、chieve a variety 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

5、of using the sensitivity 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, simplex method and dual simplex method, etc., and simp

6、ly introduces 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 simplex method. The dual programming is linear programming problem from another Angle, is the further deepenin

7、g of linear programming 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；Simplex method；The dual simplex method 目 錄前

8、言線性規(guī)劃模型的應(yīng)用與靈敏度分析1第一章 線性規(guī)劃問(wèn)題11. 線性規(guī)劃及靈敏度分析簡(jiǎn)介12. 線性規(guī)劃模型應(yīng)用的發(fā)展13. 線性規(guī)劃模型研究的問(wèn)題24. 線性規(guī)劃模型的應(yīng)用24.1問(wèn)題24.2線性規(guī)劃方法的特點(diǎn)及局限性24.3線性規(guī)劃模型的基本結(jié)構(gòu)34.4線性規(guī)劃模型的一般形式34.4線性規(guī)劃的性質(zhì)5第二章 求解線性規(guī)劃的方法61. 圖解法62. 單純行法72.1 單純行法的基本思路72.2 單純形法的求解步驟112.3 單純形法的求解過(guò)程小結(jié)122.3.1人造基、初始基本可行解122.3.2最優(yōu)解判別定理：142.3.3單純行過(guò)程的兩種方法143. 單純行法143.1對(duì)偶問(wèn)題的提出143.2

9、線性規(guī)劃的對(duì)偶理論153.3對(duì)偶單純形法的步驟154. 單純行表15第三章 靈敏度分析171. 邊際值(影子價(jià))172. 價(jià)值向量的靈敏度分析183. 靈敏度的應(yīng)用19第四章 應(yīng)用設(shè)計(jì)實(shí)例191. 目標(biāo)函數(shù)系數(shù)靈敏度分析192. 右邊值敏感性分析19結(jié) 論22參考文獻(xiàn)23致 謝24前 言線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。1947年，當(dāng)時(shí)正在美國(guó)空軍擔(dān)任數(shù)學(xué)顧問(wèn)的Dantzig在最優(yōu)規(guī)劃的科學(xué)計(jì)算中提出“如何使規(guī)劃過(guò)程機(jī)械化”問(wèn)題，并著手建立數(shù)學(xué)模型。他從改造投入產(chǎn)出模型入手，逐步研究，形成了“單純形法”，并于1953年提出“改進(jìn)單純形法”，以解決計(jì)算機(jī)求解過(guò)程中的舍入誤差問(wèn)題。之后，線性規(guī)劃理論

10、逐步趨于成熟，在實(shí)用中日益廣泛和深入。 通過(guò)設(shè)計(jì)該課題，可以加深對(duì)運(yùn)籌學(xué)、最優(yōu)化、線性規(guī)劃、非線性規(guī)劃以及MATLAB的認(rèn)識(shí)，提高對(duì)這些知識(shí)的綜合應(yīng)用水平，提高利用靈敏度分析解決各種線性規(guī)劃問(wèn)題的能力。本文章主要介紹了線性規(guī)劃在實(shí)際生活中的應(yīng)用，包括解線性方程組的各種方法，包括圖解法，單純形法，大M法，二階段法以及對(duì)偶單純形法，以及簡(jiǎn)要介紹了有關(guān)靈敏度分析的方法。由于線性方程組是解決各種應(yīng)用問(wèn)題的主要工具， 而有許多問(wèn)題僅僅利用線性規(guī)劃的解決方法還不足以解決問(wèn)題，還用到了對(duì)偶理論，也因此引出了對(duì)偶單純形法。 本課題當(dāng)前的研究方向有：LP的內(nèi)點(diǎn)算法，它通過(guò)非線性規(guī)劃解決線性問(wèn)題，其成功是對(duì)數(shù)學(xué)思

11、想的革新；算法復(fù)雜度，評(píng)價(jià)算法好壞應(yīng)從平均工作量出發(fā)；大型問(wèn)題的分解算法、近似算法。線性規(guī)劃的應(yīng)用正在不斷擴(kuò)大，企業(yè)成功確實(shí)通過(guò)提高生產(chǎn)和有效使用資源的競(jìng)爭(zhēng)過(guò)程來(lái)達(dá)到。線性規(guī)劃模型的應(yīng)用與靈敏度分析第一章 線性規(guī)劃問(wèn)題1. 線性規(guī)劃及靈敏度分析簡(jiǎn)介線性規(guī)劃(Linear Programming)問(wèn)題, 簡(jiǎn)稱LP問(wèn)題,是運(yùn)籌學(xué)中最基本, 也是最重要的內(nèi)容, 被廣泛地應(yīng)用于軍事決策、企業(yè)管理、工程設(shè)計(jì)、交通運(yùn)輸?shù)阮I(lǐng)域. 特別是經(jīng)濟(jì)領(lǐng)域應(yīng)用更為廣泛, 有資料稱, 在對(duì)500家有相當(dāng)效益的公司所作的評(píng)述中, 有85%的公司都曾應(yīng)用了線性規(guī)劃。靈敏度分析對(duì)于決策者的重要性不言而喻，在真實(shí)世界里，周?chē)沫h(huán)

12、境、條件是在不斷變化的。2. 線性規(guī)劃模型應(yīng)用的發(fā)展線性規(guī)劃及其通用解法單純形法是由美國(guó)G.B.Dantzig在1947年研究空軍軍事規(guī)劃提出來(lái)的。法國(guó)數(shù)學(xué)家傅里葉和瓦萊普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家康托羅維奇在生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書(shū)中提出線性規(guī)劃問(wèn)題，也未引起重視1。1947年美國(guó)數(shù)學(xué)家丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法單純形法，為這門(mén)學(xué)科奠定了基礎(chǔ)。1947年美國(guó)數(shù)學(xué)家諾伊曼提出對(duì)偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力2。1951年美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章拱丫€性規(guī)劃應(yīng)用

13、到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年萊姆基提出對(duì)偶單純形法，1954年加斯和薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問(wèn)題，1956年塔克提出互補(bǔ)松弛定理，1960年丹齊克和沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究3。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)式算法理論。5

14、0年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大4。3. 線性規(guī)劃模型研究的問(wèn)題建立線性規(guī)劃模型線性規(guī)劃研究的問(wèn)題主要有兩類:一類是當(dāng)一項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，盡量做到以最少的人力、物力等資源去完成；另一類是在人力、物力等資源確定的情況下，如何安排使用這些資源，使創(chuàng)造的價(jià)值最多，其實(shí)質(zhì)是解決稀缺資源在有競(jìng)爭(zhēng)環(huán)境中如何進(jìn)行最優(yōu)分配的問(wèn)題，即尋求整個(gè)問(wèn)題的某個(gè)整體指標(biāo)最優(yōu)的問(wèn)題4。4. 線性規(guī)劃模型的應(yīng)用 4.1問(wèn)題 a.目標(biāo)函數(shù)最優(yōu)化單一目標(biāo)，多重目標(biāo)問(wèn)題如何處理？ b.實(shí)現(xiàn)目標(biāo)的多種方法，若實(shí)現(xiàn)目標(biāo)只有一種方法不存在規(guī)劃問(wèn)題。 c.生產(chǎn)條件的約束資源是有限的，資源無(wú)限不存在規(guī)劃問(wèn)題。 4.2線性規(guī)劃方法

15、的特點(diǎn)及局限性 特點(diǎn)： a.可以使研究對(duì)象具體化、數(shù)量化?？梢詫?duì)所研究的技術(shù)經(jīng)濟(jì)問(wèn)題做出明確的結(jié)論； b.線性； c.允許出現(xiàn)生產(chǎn)要素的剩余量； d.有一套完整的運(yùn)算程序；局限性： a. 線性規(guī)劃它是以價(jià)格不變和技術(shù)不變?yōu)榍疤釛l件的，不能處理涉及到時(shí)間因素的問(wèn)題。因此，線性規(guī)劃只能以短期計(jì)劃為基礎(chǔ)。 b.在生產(chǎn)活動(dòng)中，投入產(chǎn)出的關(guān)系不完全是線性關(guān)系，由于在一定的技術(shù)條件下，報(bào)酬遞減規(guī)律起作用，所以要滿足線性假定是不可能的。在線性規(guī)劃解題中，常常把投入產(chǎn)出的非線性關(guān)系轉(zhuǎn)化為線性關(guān)系來(lái)處理，以滿足線性的假定性，客觀上產(chǎn)生誤差。 c.線性規(guī)劃本身只是一組方程式，并不提供經(jīng)濟(jì)概念，它不能代替人們對(duì)現(xiàn)實(shí)

16、經(jīng)濟(jì)問(wèn)題的判斷。 4.3線性規(guī)劃模型的基本結(jié)構(gòu)(1)決策變量 未知數(shù)。它是通過(guò)模型計(jì)算來(lái)確定的決策因素。又分為實(shí)際變量求解的變量和計(jì)算變量，計(jì)算變量又分松弛變量（上限）和人工變量（下限）。 (2)目標(biāo)函數(shù)經(jīng)濟(jì)目標(biāo)的數(shù)學(xué)表達(dá)式。目標(biāo)函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個(gè)極值問(wèn)題。 (3)約束條件實(shí)現(xiàn)經(jīng)濟(jì)目標(biāo)的制約因素。它包括：生產(chǎn)資源的限制（客觀約束條件）、生產(chǎn)數(shù)量、質(zhì)量要求的限制（主觀約束條件）、特定技術(shù)要求和非負(fù)限制。 4.4線性規(guī)劃模型的一般形式極大值模型 (1-1) (1-2) (1-3) 其簡(jiǎn)縮形式為 極小值模型 (1-4) (1-5) (1-6)其簡(jiǎn)縮形式為 模型的簡(jiǎn)縮形式可

17、用向量表示 例1 生產(chǎn)安排模型，某工廠生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表所示。III資源總量設(shè)備128/臺(tái)時(shí)原材料A4016/千克原材料B0412/千克該工廠生產(chǎn)一單位產(chǎn)品I可獲利2元，生產(chǎn)產(chǎn)品II可獲利3元，問(wèn)如何安排生產(chǎn)獲利最大？解：本問(wèn)題是目標(biāo)最大化問(wèn)題：(1)決策變量，設(shè)x1, x2為產(chǎn)品I、II的生產(chǎn)數(shù)量；(2)目標(biāo)函數(shù)，2x1+3x2；(3)約束條件， 設(shè)備限制： x1+2x2 8 原材料A限制： 4x1 16 原材料B限制： 4x2 12 基本要求：x10 ， x20 該模型記為如下形式 maxZ=2x1+3x2 s.t.x1+2x

18、2 84x1 164x2 12 x1 ，x2 0其中max表示本問(wèn)題是最大值問(wèn)題（用min表示最小值問(wèn)題）， s.t.(subject to的縮寫(xiě))表示約束條件。這就是一個(gè)線性規(guī)劃模型5。 4.4線性規(guī)劃的性質(zhì)定理1 線性規(guī)劃問(wèn)題的可行解X是基可行解的充要條件是X的非零分量對(duì)應(yīng)的系數(shù)矩陣A的列向量線性無(wú)關(guān)6。定理2 若一個(gè)線性規(guī)劃問(wèn)題有可行解，則它必有基本可行解7。定理3 若可行域有界，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)達(dá)到最優(yōu)。 第2章 求解線性規(guī)劃的方法1. 圖解法圖解法是求解線性規(guī)劃模型的一種重要方法，線性規(guī)劃中一些重要的性質(zhì)、概念和求解思想都來(lái)源于此。當(dāng)只有兩個(gè)決策變量時(shí)，

19、可以用圖解法求解。它具有簡(jiǎn)單直觀的特點(diǎn)。為了給后面的線性問(wèn)題的基本理論提供較直觀的幾何說(shuō)明，先介紹線性規(guī)劃問(wèn)題的圖解法8。圖解法的求解步驟如下：第一步，根據(jù)約束畫(huà)出可行域，先以決策變量為坐標(biāo)，建立直角坐標(biāo)系，再根據(jù)各約束條件，作出可行域。第二步，作出一條目標(biāo)函數(shù)等值線，并確定增值方法。第三步，沿等值線的法線方向值增大方向移動(dòng)，從而找到最大值。圖解法得出線性規(guī)劃的幾種情況：表2-1 解旳幾種情況解旳幾種情況約束條件圖形特點(diǎn)方程特點(diǎn)唯一解一般圍成有限區(qū)域，最優(yōu)值只在一個(gè)頂點(diǎn)達(dá)到無(wú)窮多解在圍成的的區(qū)域邊界上，至少有兩個(gè)頂點(diǎn)處達(dá)到優(yōu)解目標(biāo)和某一約束方程成比例無(wú)可行解（無(wú)解）圍不成區(qū)域有矛盾方程無(wú)界解(

20、無(wú)解）圍成無(wú)界區(qū)域，且無(wú)有限最優(yōu)解缺少一必要條件的方程例：Min Z=10x1+20x2 2. 單純形法單純形法是美國(guó)數(shù)學(xué)家G.B.Dantzig于1947年首先提出的。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是n維向量空間nR中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到9。它的原理涉及到較多的數(shù)學(xué)理論上的推導(dǎo)和證明，我們?cè)诖藘H介紹這種方法的具體操作步驟及每一步的經(jīng)濟(jì)上的含義。為更好地說(shuō)明問(wèn)題，我們?nèi)越Y(jié)合實(shí)例介紹這種方法。 單純形法（simplex methods），求解線性規(guī)劃的通用方法。 2.1單純形法的基本思路單純形法的基本思路是：根據(jù)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型，從可行域中某個(gè)基本可行解

21、（一個(gè)頂點(diǎn)）開(kāi)始，轉(zhuǎn)換到另一個(gè)基本可行解（頂點(diǎn)），并且當(dāng)目標(biāo)函數(shù)達(dá)到最大值時(shí)，問(wèn)題就得到了解決，其基本思路的框架圖如下圖2-1。圖2-1.單純行法的基本思路用單純行法討論例1的求解解：已知例1的標(biāo)準(zhǔn)型為 （2-1） （2-2）約束條件（2-2）的系數(shù)矩陣 顯然，x3，x4，x5的系數(shù)列向量 （2-3）是線性獨(dú)立的，因而這些向量構(gòu)成一個(gè)基 (2-4)對(duì)應(yīng)于B的基變量為x3,x4,x5，從約束條件（2-2）中可以看到 （2-5）當(dāng)令非基變量這時(shí)得到一個(gè)基本可行解X（0） （2-6）將式(2-3)代入目標(biāo)函數(shù)(2-1)得到 （2-7）這個(gè)基本可行解表示：工廠沒(méi)有安排生產(chǎn)產(chǎn)品；資源都沒(méi)有被利用，所以工

22、廠的利潤(rùn)Z=0。分析目標(biāo)函數(shù)的表達(dá)式(2-7)可以看到：非基變量x1,x2的系數(shù)都是正數(shù)，因此將非基變量變?yōu)榛兞?，目?biāo)函數(shù)的值就可能增大，從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品或，就可以使工廠的利潤(rùn)指標(biāo)增加，所以只要在目標(biāo)函數(shù)(2-7)的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，就需要將非基變量與某個(gè)基變量進(jìn)行對(duì)換，一般選擇正系數(shù)最大的那個(gè)非基變量x2為換入變量，將它換入到基變量中區(qū)，同時(shí)還有確定基變量中有一個(gè)要換出來(lái)成為非基變量，可按以下方法來(lái)確定換出變量。現(xiàn)分析式(2-5)，當(dāng)將x2定為換入變量后，必須從x3,x4,x5中換出一個(gè)，并保證其余的都是非負(fù)，即x3,x4,x5。

23、當(dāng)x1=0，由式(2-5)得到 （2-8）可以看出，只有選擇 （2-9） 時(shí)，才能使式(2-8)成立。以上數(shù)學(xué)模型說(shuō)明了每生產(chǎn)一件產(chǎn)品，需要用掉的各種資源數(shù)為(2,0,4)。這些資源中的薄弱環(huán)節(jié)確定了產(chǎn)品的產(chǎn)量。原材料B的數(shù)量決定產(chǎn)品的產(chǎn)量只能是x2=12/4=3件。為了求得以x3，x4，x2為基變量的一個(gè)基本可行解和進(jìn)一步分析問(wèn)題，需將方程(2-5)中x2的位置對(duì)換。得到 （2-10）用高斯消去法求解，得到以非基變量表示的基變量 （2-11）代入目標(biāo)函數(shù)得到 (2-12) 令非基變量得到并得另一個(gè)基本可行解。從目標(biāo)函數(shù)的表達(dá)式(2-12)中可以看到，非基變量的系數(shù)是正的，說(shuō)明目標(biāo)函數(shù)的值還可

24、以增大，還不是最優(yōu)解。于是用上述方法，確定換入、換出變量，繼續(xù)迭代，再得到另外一個(gè)基本可行解。再經(jīng)過(guò)一次迭代，得到一個(gè)基本可行解。而這時(shí)得到的目標(biāo)函數(shù)的表達(dá)式是 （2-13）再分析目標(biāo)函數(shù)(2-13),可知所有非基變量的系數(shù)都是負(fù)數(shù)，這說(shuō)明若要用剩余資源就必須支付附加費(fèi)用。所以當(dāng)時(shí)，即不再利用這些資源時(shí)，目標(biāo)函數(shù)達(dá)到最大值，那么是最優(yōu)解。這說(shuō)明當(dāng)產(chǎn)品生產(chǎn)4件，產(chǎn)品生產(chǎn)2件，工廠才能得到最大利潤(rùn)。通過(guò)上例，可以了解利用單純形法求解線性規(guī)劃問(wèn)題的思路。 2.2單純形法的求解步驟 線性規(guī)劃問(wèn)題的求解有以下幾個(gè)步驟： (1)確定初始基本可行解。為了確定初始基本可行解，首先要找出初始可行解。設(shè)一線性規(guī)劃

25、問(wèn)題為 （2-14）可分為兩種情況討論。若中存在一個(gè)單位基，則將其作為初始可行基 （2-15）若中不存在一個(gè)單位基，則人為地構(gòu)造一個(gè)單位初始基。(2)檢驗(yàn)最優(yōu)解。得到初始基本可行解后，要檢驗(yàn)該解是否為最優(yōu)解。如果是最優(yōu)解，則停止運(yùn)算；否則轉(zhuǎn)入（3）基變換。下面給出最優(yōu)性判別定理。一般情況下，經(jīng)過(guò)迭代后可以得到以非基變量表示基變量的表達(dá)式 （） （2-16） 將式(2-11)代入式(2-10)的目標(biāo)函數(shù)，整理后得 （2-17）令 （ （2-18） 于是 （2-19）再令 （2-20）則得到以非基變量表示目標(biāo)函數(shù)的表達(dá)式 （2-21） (3)基變換。若初始基本可行解不是最優(yōu)解，又不能判別無(wú)界時(shí)，由

26、目標(biāo)函數(shù)(2-10)的約束條件可看到，當(dāng)某些增加則目標(biāo)函數(shù)值還可能增加這時(shí)就要將其中某個(gè)非基變量換到基變量中去（稱為換入變量），同時(shí)，某個(gè)基變量要換成非基變量（稱為換出變量），隨之會(huì)得到一個(gè)新的基本可行解。從一個(gè)基本可行解到另一個(gè)基本可行解的變換，就是進(jìn)行一次基變換。從幾何意義上就是從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)向另一個(gè)頂點(diǎn)。 (4)迭代。在確定了換入變量和換出變量后，要把和的位置進(jìn)行對(duì)換，就是說(shuō)要把對(duì)應(yīng)的系數(shù)列向量變成單位列向量。這可以通過(guò)對(duì)約束方程組的增廣矩陣進(jìn)行初等行變換來(lái)實(shí)現(xiàn)，變換結(jié)果得一新的基本可行解。 2.3單純形法的求解過(guò)程小結(jié) 2.3.1人造基、初始基本可行解 (1)若從線性規(guī)劃問(wèn)題的P

27、j中能直接觀察到存在m個(gè)線性獨(dú)立的單位向量，經(jīng)過(guò)重新安排次序便得到一個(gè)可行基。 (2)“”標(biāo)準(zhǔn)化的方法，引入非負(fù)的松弛變量重新對(duì)及編號(hào)，經(jīng)整理則可得到下列方程 顯然得到一個(gè)單位陣我們就將B作為可行基。 我們就將B作為可行基。將每個(gè)等式進(jìn)行移項(xiàng)得 令由等式可得 得到一個(gè)初始基本可行解 2.3.2最優(yōu)性檢驗(yàn)得到初始可行解后，要檢驗(yàn)一下是否是最優(yōu)解，如果是則停止迭代，如果不是，則繼續(xù)迭代。但每次迭代后都要檢驗(yàn)是否是最優(yōu)解，為此需要建立一個(gè)判別準(zhǔn)則。一般情況下，經(jīng)過(guò)迭代后式變成 將上式代入目標(biāo)函數(shù)，整理后得 2.3.3最優(yōu)解判別定理：若 為對(duì)應(yīng)于B的基本可行解，且對(duì)于一切有X（0）為最優(yōu)解。無(wú)有限最優(yōu)

28、解判別定理：若為對(duì)應(yīng)于B的基本可行解，有一個(gè)并且對(duì)于一切i=1,2,3,m有那么該線性規(guī)劃沒(méi)有有限最優(yōu)解。 a.換入變量的確定 則對(duì)應(yīng)的為換入變量 b.換出變量的確定為換入變量。 2.3.4單純形法過(guò)程的兩種方法在單純形迭代過(guò)程中，要求人工變量逐步從基變量被替換出，變?yōu)榉腔兞浚@有兩種方法：大M法和兩階段法10。3. 對(duì)偶單純形法對(duì)偶規(guī)劃是線性規(guī)劃問(wèn)題從另一個(gè)角度進(jìn)行研究，是線性規(guī)劃理論的進(jìn)一步深化，也是線性規(guī)劃理論的進(jìn)一步深化，也是線性規(guī)劃理論整體的一個(gè)不可分割. 3.1對(duì)偶問(wèn)題的提出每個(gè)線性規(guī)劃都有另一個(gè)線性規(guī)劃（對(duì)偶問(wèn)題）與它密切相關(guān)，對(duì)偶理論揭示了原問(wèn)題與對(duì)偶問(wèn)題的內(nèi)在聯(lián)系11。考慮

29、到對(duì)偶模型的約束與原問(wèn)題模型的變量相對(duì)應(yīng)，變量則是與原問(wèn)題模型的約束相對(duì)應(yīng)。原問(wèn)題是最小化，則可將對(duì)偶問(wèn)題看做原問(wèn)題12。 3.2線性規(guī)劃的對(duì)偶理論定理2-1(對(duì)稱性定理) 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。定理2-2(弱對(duì)偶定理) 設(shè)X和Y分別是原問(wèn)題P和對(duì)偶問(wèn)題D的可行解，則有13。定理2-3(對(duì)偶原理) 定理2-4(互補(bǔ)松弛定理) 如果X和Y分別為P和D的可行解，它們分別為P和D的最優(yōu)解的充要條件是 3.3對(duì)偶單純形法的步驟對(duì)偶單純形法是用對(duì)偶理論求解原問(wèn)題的一種方法，而不是求解對(duì)偶問(wèn)題解的單純形法。與對(duì)偶單純形法相對(duì)應(yīng)，已有的單純形法稱原始單純形法14。（1） 建立初始單純形表，計(jì)算檢驗(yàn)數(shù)行（2

30、） 先確定換出變量-解答列中的負(fù)元素一般選最小的負(fù)元素對(duì)應(yīng)的基變量出基；（3） 將主元素進(jìn)行換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解15。4. 單純形表表2-2 單純形表也可以反映線性規(guī)劃在現(xiàn)實(shí)生活中的運(yùn)用初單純形表實(shí)際活動(dòng)松弛活動(dòng)比值x1x2x3x4x5R0x382300060x4161210040x51240010-目標(biāo)系數(shù)行23000檢驗(yàn)數(shù)行023000第二單純形表實(shí)際活動(dòng)松弛活動(dòng)比值x1x2x3x4x5R0x362010030x421210020x5164001043x2304001-檢驗(yàn)數(shù)行20000903000

31、第三單純形表實(shí)際活動(dòng)松弛活動(dòng)比值x1x2x3x4x5R0x32001-2042x1212010-0x58000-4143x230100012檢驗(yàn)數(shù)行000-201323020第三章 靈敏度分析靈敏度分析是研究與分析一個(gè)系統(tǒng)(或模型)的狀態(tài)或輸出變化對(duì)系統(tǒng)參數(shù)或周?chē)鷹l件變化的敏感程度的方法。在最優(yōu)化方法中經(jīng)常利用靈敏度分析來(lái)研究原始數(shù)據(jù)不準(zhǔn)確或發(fā)生變化時(shí)最優(yōu)解的穩(wěn)定性。通過(guò)靈敏度分析還可以決定哪些參數(shù)對(duì)系統(tǒng)或模型有較大的影響。因此，靈敏度分析幾乎在所有的運(yùn)籌學(xué)方法中以及在各種方案進(jìn)行評(píng)價(jià)時(shí)都是很重要的16。1. 邊際值(影子價(jià)) 是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)趇個(gè)約束行的右端項(xiàng)減少一個(gè)單位時(shí)，目標(biāo)函

32、數(shù)的變化量機(jī)會(huì)成本 因此機(jī)會(huì)成本的另外表達(dá)形式關(guān)于影子價(jià)的一些說(shuō)明影子價(jià)是資源最優(yōu)配置下資源的理想價(jià)格，資源的影子價(jià)與資源的緊缺度有關(guān)；松弛變量增加一個(gè)單位等于資源減少一個(gè)單位；剩余變量增加一個(gè)單位等于資源增加一個(gè)單位；資源有剩余，在最優(yōu)解中就有對(duì)應(yīng)松弛變量存在，且其影子價(jià)為0；影子價(jià)為0，資源并不一定有剩余。2. 價(jià)值向量的靈敏度分析價(jià)值向量(即目標(biāo)函數(shù)系數(shù))的靈敏度分析分為原最終單純形表中jc與非基變量和基變量對(duì)應(yīng)兩種情況來(lái)討論17。（1） 若是非基變的系數(shù)，則其對(duì)應(yīng)的最終單純形表中的檢驗(yàn)數(shù)為當(dāng)變化，要保證最終單純形表的最優(yōu)解不變，必有保證最終單純形表最優(yōu)解不變，可得的允許變化值（2）若是

33、基變量的系數(shù)，應(yīng)有,當(dāng)變化時(shí)，就引起的變化這時(shí)若要求原最優(yōu)解不變，必須滿足。于是得到可變化的范圍是3. 靈敏度的應(yīng)用 (1)投入產(chǎn)出法中靈敏度分析可以用來(lái)研究采取某一項(xiàng)重大經(jīng)濟(jì)政策后將會(huì)對(duì)國(guó)民經(jīng)濟(jì)的各個(gè)部門(mén)產(chǎn)生怎樣的影響。 (2)方案評(píng)價(jià)中靈敏度分析 可以用來(lái)確定評(píng)價(jià)條件發(fā)生變化時(shí)備選方案的價(jià)值是否會(huì)發(fā)生變化或變化多少。第4章 應(yīng)用設(shè)計(jì)實(shí)例某農(nóng)戶計(jì)劃用12公頃耕地生產(chǎn)玉米，大豆和地瓜，可投入48個(gè)勞動(dòng)日，資金360元。生產(chǎn)玉米1公頃，需6個(gè)勞動(dòng)日，資金36元，可獲凈收入200元；生產(chǎn)1公頃大豆，需6個(gè)勞動(dòng)日，資金24元，可獲凈收入150元；生產(chǎn)1公頃地瓜需2個(gè)勞動(dòng)日，資金18元，可獲凈收入12

34、00元，問(wèn)怎樣安排才能使總的凈收入最高。設(shè)種玉米，大豆和地瓜的數(shù)量分別為x1、x2和x3公頃，根據(jù)問(wèn)題建立線性規(guī)劃問(wèn)題模型如下： Max Z=200x1+150x2+100x3 x1+x2+x312 6x1+6x2+2x348 (4-1) 36x1+24x2+183360 (4-2) x10，x20，x301. 目標(biāo)函數(shù)系數(shù)靈敏度分析表4-1 目標(biāo)系數(shù)的允許變動(dòng)范圍活動(dòng)目標(biāo)系數(shù)可減上限可增上限可變范圍玉米種植x1大豆種植x2地瓜種植x320015010050 無(wú)窮大100/310050100150300-200200/3200 當(dāng)僅有一種目標(biāo)系數(shù)在允許范圍內(nèi)變動(dòng)時(shí)，最優(yōu)方案不會(huì)變動(dòng)，但最優(yōu)目標(biāo)

35、值會(huì)隨之變化。2. 右邊值敏感性分析由線性規(guī)劃的原理可知，影子價(jià)格不變的條件是最優(yōu)解的松弛變量矩陣與右邊值矩陣的乘積大于和等于0，即：當(dāng)右邊值發(fā)生變化時(shí)，如耕地變化，此時(shí)，影子價(jià)格不變的條件是 得到 6+3/210 6-1/210 -414 36-910因此耕地影子價(jià)格不變的耕地?cái)?shù)量范圍為：8，16得到 61/420 6+1/420 -2428 36-9/220因此勞動(dòng)力影子價(jià)格不變的勞動(dòng)力數(shù)量范圍為：24，56得到 60 3 36 3630因此資金影子價(jià)格不變的資金數(shù)量范圍為：324，-表4-2 常數(shù)項(xiàng)的允許變動(dòng)范圍資源現(xiàn)有數(shù)量可減上限可增上限可變范圍影子價(jià)格耕地124481650勞動(dòng)48248245625資金36036+324+0常數(shù)項(xiàng)的允許變動(dòng)范圍這一結(jié)果也還有另外一種意義，即它給出了資源影子價(jià)格（邊際產(chǎn)出率）的有效范圍。對(duì)耕地而言，當(dāng)投入使用的數(shù)量在8-16公頃之間變化時(shí)，其邊際產(chǎn)出率都是50元，即每增加或減少1公頃耕地，農(nóng)戶將增加或減少50元凈