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

1、中國石油大學勝利學院本科畢業(yè)設(shè)計（論文）線性規(guī)劃模型的應用與靈敏度分析第一章 線性規(guī)劃問題1. 線性規(guī)劃簡介及發(fā)展線性規(guī)劃（linear programming）是運籌學中研究最早、發(fā)展最快、應用廣泛、方法成熟的一個重要分支，它是輔助人們進行科學管理的一種數(shù)學方法，研究線性約束條件下線性目標函數(shù)的極值問題的數(shù)學理論和方法，英文縮寫為lp。它是運籌學的一個重要分支，廣泛應用于軍事作戰(zhàn)、經(jīng)濟分析、經(jīng)營管理和工程技術(shù)等方面，為合理利用有限的人力、物力、財力等資源做出的最優(yōu)決策，提供科學的依據(jù)。線性規(guī)劃及其通用解法單純形法是由美國g.b.dantzig在1947年研究空軍軍事規(guī)劃提出來的。法國數(shù)學家傅

2、里葉和瓦萊普森分別于1832和1911年獨立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學家康托羅維奇在生產(chǎn)組織與計劃中的數(shù)學方法一書中提出線性規(guī)劃問題，也未引起重視1。1947年美國數(shù)學家丹齊克提出線性規(guī)劃的一般數(shù)學模型和求解線性規(guī)劃問題的通用方法單純形法，為這門學科奠定了基礎(chǔ)。1947年美國數(shù)學家諾伊曼提出對偶理論,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴大了它的應用范圍和解題能力2。1951年美國經(jīng)濟學家?guī)炱章拱丫€性規(guī)劃應用到經(jīng)濟領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟學獎。50年代后對線性規(guī)劃進行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年萊姆基提出對偶單純形

3、法，1954年加斯和薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，1956年塔克提出互補松弛定理，1960年丹齊克和沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究3。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如mpsx，opheie，umpire等，可以很方便地求解幾千個變量的線性規(guī)劃問題。1979年蘇聯(lián)數(shù)學家提出解線性規(guī)劃問題的橢球算法，并證明它是多項式時間算法。1984年美國貝爾電話實驗室的印度數(shù)學家n.卡馬卡提出解線性規(guī)劃問題的新的多項式時間算法。用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用

4、時間的1/50。現(xiàn)已形成線性規(guī)劃多項式算法理論。50年代后線性規(guī)劃的應用范圍不斷擴大。 建立線性規(guī)劃模型線性規(guī)劃研究的問題主要有兩類:一類是當一項任務確定后，如何統(tǒng)籌安排，盡量做到以最少的人力、物力等資源去完成；另一類是在人力、物力等資源確定的情況下，如何安排使用這些資源，使創(chuàng)造的價值最多，其實質(zhì)是解決稀缺資源在有競爭環(huán)境中如何進行最優(yōu)分配的問題，即尋求整個問題的某個整體指標最優(yōu)的問題4。2. 線性規(guī)劃的數(shù)學模型2.1 線性規(guī)劃問題例1-1某工廠在計劃期內(nèi)要安排生產(chǎn)兩種產(chǎn)品,，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺數(shù)及a,b兩種原材料的消耗量，見表1-1。該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可

5、獲利3元，問應如何安排生產(chǎn)計劃使該工廠獲得的利潤最大？有關(guān)資料如下表1-1產(chǎn)品、資源信息產(chǎn)品資源限量設(shè)備/臺128原材料a/kg4016原材料b/kg0412用數(shù)學語言來描述生產(chǎn)計劃的安排，建立數(shù)學模型。解：設(shè)x,x分別表示在計劃期內(nèi)產(chǎn)品,的生產(chǎn)量，在滿足資源限量的條件下，它們必須同時滿足下列條件。 對設(shè)備有效臺數(shù)： 對原材料a： 對原材料b： 該工廠的生產(chǎn)目標是在不超過所有資源限量的條件下，確定生產(chǎn)量x,x，使該得到的利潤最大。若用z表示總利潤，則有 綜合上述，該生產(chǎn)計劃問題可用數(shù)學模型表示為 (1-1)這就是一個線性規(guī)劃模型5。2.2 線性規(guī)劃問題的數(shù)學模型線性規(guī)劃數(shù)學模型是由一組含有等式

6、或者不等式的代數(shù)方程以及一個具有求極值關(guān)系的目標函數(shù)表達式構(gòu)成的符合抽象數(shù)學模型。下面介紹建立實際問題線性規(guī)劃模型的基本步驟。（1） 確定決策變量。這是很關(guān)鍵的一步，決策變量選取得當，不僅會使線性規(guī)劃的數(shù)學模型建得容易，而且求解比較方便。 （2） 找出所有限制條件，并用決策變量的線性等式或不等式來表示，從而得到約束條件。一般可用表格形式列出所有的限制數(shù)據(jù)，然后根據(jù)所列出的數(shù)據(jù)寫出相應的約束條件，以避免遺漏或重復所規(guī)定的限制要求。 （3） 把實際問題所要達到的目的用決策變量的線性函數(shù)來表示，得到目標函數(shù)，并確定是求最大值還是最小值。 （4） 根據(jù)實際問題添加非負約束。 線性規(guī)劃的數(shù)學表達式成為線

7、性規(guī)劃的數(shù)學模型，一般形式為 (1-2) s.t. (1-3)其中，式(1-2)稱為目標函數(shù)，(1-3)式稱為約束條件。2.3 線性規(guī)劃的性質(zhì)定理1 線性規(guī)劃問題的可行解x是基可行解的充要條件是x的非零分量對應的系數(shù)矩陣a的列向量線性無關(guān)6。定理2 若一個線性規(guī)劃問題有可行解，則它必有基本可行解7。定理3 若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。證明：設(shè)是可行域的頂點，若不是頂點，且目標函數(shù)在處達到最優(yōu)（標準型是）。因為不是頂點，所以d的頂點線性表示為 (1-4)在所有頂點中必然能找到某個頂點，使是所有中最大者，并且將代替式（1-5）中所有的，這就得到，由此得到

8、，根據(jù)假設(shè)最大值，所以只能有，即目標函數(shù)在頂點處也達到最大值。有時目標函數(shù)可能在多個頂點處達到最大值，這時在這些頂點的凸集合上也達到最大值，稱這種線性規(guī)劃問題有無窮多最優(yōu)解。由以上的討論可知，為了尋求線性規(guī)劃問題的最優(yōu)解，只從其有限數(shù)目的基本可行解中去尋找基礎(chǔ)最優(yōu)解就可以了。盡管如此，當數(shù)m,n較大時，用此種方法求其最優(yōu)解也是不可行的8。第二章 求解線性規(guī)劃的方法1. 圖解法圖解法是求解線性規(guī)劃模型的一種重要方法，線性規(guī)劃中一些重要的性質(zhì)、概念和求解思想都來源于此。當只有兩個決策變量時，可以用圖解法求解。它具有簡單直觀的特點。為了給后面的線性問題的基本理論提供較直觀的幾何說明，先介紹線性規(guī)劃問

9、題的圖解法8。我們把滿足約束條件和非負約束條件的一組解叫做可行解，所有可行解組成的集合稱為可行域。圖解法的求解步驟如下：第一步，根據(jù)約束畫出可行域，先以決策變量為坐標，建立直角坐標系，再根據(jù)各約束條件，作出可行域。第二步，作出一條目標函數(shù)等值線，并確定增值方法。第三步，沿等值線的法線方向值增大方向移動，從而找到最大值。圖解法得出線性規(guī)劃的幾種情況：表2-1 解的幾種情況解的幾種情況約束條件圖形特點方程特點惟一解一般圍成有限區(qū)域，最優(yōu)值只在一個頂點達到-無窮多解在圍成的區(qū)域邊界上，至少有兩個頂點處達到最優(yōu)目標和某一約束方程成比例無可行解（無解）圍不成區(qū)域有矛盾方程無界解（無解）圍成無界區(qū)域，且無

10、有限最優(yōu)值缺少一必要條件的方程2. 單純形法2.1 單純形法的發(fā)展單純形法（simplex methods），求解線性規(guī)劃的通用方法。單純形法是美國數(shù)學家g.b.dantzig于1947年首先提出的。簡單的說就是一種數(shù)學迭代方法，求解基本過程是從一個基本可行解跳到另一個基本可行解的逐步替代，從而使目標函數(shù)不斷得到改善。它的理論根據(jù)是：線性規(guī)劃問題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點處達到9。2.1.1 單純形法的基本思路單純形法的基本思路是：根據(jù)線性規(guī)劃問題的標準型，從可行域中某個基本可行解（一個頂點）開始，轉(zhuǎn)換到另一個基本可行解（頂點），并且當目標函數(shù)達到最

11、大值時，問題就得到了解決，其基本思路的框架圖如下圖2-1。給出一個初始基本可行解是否最優(yōu) 否 是從當前基可行解出發(fā)，尋求一個能使目標函數(shù)值活的改善的新的基本可行解寫出最優(yōu)解 圖2-1 單純形法的基本思路例2-1 用單純形法討論例1-1的求解。解：已知例1.1的標準型為： (2-1) (2-2) 約束條件(2-2)的系數(shù)矩陣 顯然，的系數(shù)列向量 ， (2-3)是線性獨立的，因而這些向量構(gòu)成一個基 (2-4)對應于的基變量為,，從約束條件(2-2)中可以看到 (2-5)當令非基變量，這時得到一個基本可行解 (2-6)將式(2-3)代入目標函數(shù)(2-1)得到 (2-7)這個基本可行解表示：工廠沒有安

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

13、2-5)得到 (2-8)從式(2-8)中可以看出，只有選擇 (2-9)時，才能使式(2-8)成立。因為當時，基變量，所以可用去替代。以上數(shù)學模型說明了每生產(chǎn)一件產(chǎn)品，需要用掉的各種資源數(shù)為(2,0,4)。這些資源中的薄弱環(huán)節(jié)確定了產(chǎn)品的產(chǎn)量。原材料b的數(shù)量決定產(chǎn)品的產(chǎn)量只能是件。為了求得以為基變量的一個基本可行解和進一步分析問題，需將方程(2-5)中的位置對換。得到 (2-10)用高斯消去法求解，得到以非基變量表示的基變量 (2-11)再將式(1-12)代入目標函數(shù)(1-6)得到 (2-12)令非基變量，得到，并得另一個基本可行解。從目標函數(shù)的表達式(2-12)中可以看到，非基變量的系數(shù)是正的

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

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

16、始基本可行解不是最優(yōu)解，又不能判別無界時，由目標函數(shù)(2-10)的約束條件可看到，當某些，增加則目標函數(shù)值還可能增加，這時就要將其中某個非基變量換到基變量中去（稱為換入變量），同時，某個基變量要換成非基變量（稱為換出變量），隨之會得到一個新的基本可行解。從一個基本可行解到另一個基本可行解的變換，就是進行一次基變換。從幾何意義上就是從可行域的一個頂點轉(zhuǎn)向另一個頂點。（4） 迭代。在確定了換入變量和換出變量后，要把和的位置進行對換，就是說要把對應的系數(shù)列向量變成單位列向量。這可以通過對約束方程組的增廣矩陣進行初等行變換來實現(xiàn)，變換結(jié)果得一新的基本可行解。然后轉(zhuǎn)入（2）。2.2 單純形法的進一步討論

17、對于一般的線性規(guī)劃問題，在用單純形法求解之前，總是先化為標準型。如果在系數(shù)矩陣中有一個單位陣，則可以作為初始可行基。如果約束條件的系數(shù)矩陣中不存在單位矩陣，則可以通過添加人工變量的方法，在標準型的約束方程的系數(shù)矩陣中人為地構(gòu)造一個單位陣，從而獲得初始可行基，再作進一步迭代。在單純形迭代過程中，要求人工變量逐步從基變量被替換出，變?yōu)榉腔兞?，這有兩種方法：大m法和兩階段法10。人工變量法的基本思想：對于線性規(guī)劃問題，有時候很難找出初始基本可行解，這時可以考慮加入人工變量的方法來解決問題。基本原理對于標準型的線性規(guī)劃問題： (2-22)給每個約束方程硬性加入一個人工變量之后得到： (2-23)這樣

18、，就可以以為基變量，得到問題的初始基本可行解。在求解的過程中，通過迭代不斷地將這些人工變量從基變量中迭代出去，使人工變量均等于0，從而求得原始問題的最優(yōu)解。若不能把人工變量完全迭代出去，則表明原始問題無可行解。下面介紹人工變量的兩種方法。（1） 大m法在目標函數(shù)求最大值的線性規(guī)劃問題中，設(shè)人工變量在目標函數(shù)中的系數(shù)為-m，m為任意大的正數(shù)。只要人工變量不為零，目標函數(shù)最大值就是一個任意小的數(shù)。（2） 兩階段法第一階段：建立一個輔助線性規(guī)劃，并求解，以判斷原線性規(guī)劃是否存在可行解。所有人工變量都變成非基變量，目標函數(shù)最小值為0，原問題存在基可行解。轉(zhuǎn)到第二階段。若目標函數(shù)大于0，至少有一個人工變

19、量不能從基變量中轉(zhuǎn)出，由于它取正值，原問題沒有可行解。停止。第二階段：在第一階段最優(yōu)表格中去掉人工變量，將目標函數(shù)系數(shù)換成原問題的目標函數(shù)系數(shù)，接下去用單純形法計算，直到得到最優(yōu)解為止。3單純形法對偶規(guī)劃是線性規(guī)劃問題從另一個角度進行研究，是線性規(guī)劃理論的進一步深化，也是線性規(guī)劃理論的進一步深化，也是線性規(guī)劃理論整體的一個不可分割的組成部分。3.1 對偶問題的提出每個線性規(guī)劃都有另一個線性規(guī)劃（對偶問題）與它密切相關(guān)，對偶理論揭示了原問題與對偶問題的內(nèi)在聯(lián)系11。3.2 對偶問題的數(shù)學模型及對偶關(guān)系原問題p的標準形式： (2-24)對偶問題d的標準形式： (2-25)當我們討論對偶問題時，它必

20、定是與原問題成對出現(xiàn)的；同時，原問題與對偶問題之間沒有嚴格的界限，它們互為對偶：一個是原問題，則另一個就為對偶問題。表2-1給出了線性規(guī)劃原問題與對偶問題的對應關(guān)系，該表也可以看做是一個線性規(guī)劃原問題轉(zhuǎn)化為對偶問題的一般規(guī)律。其中，對于變量與約束間關(guān)系的理解，必須考慮到對偶模型的約束與原問題模型的變量相對應，變量則是與原問題模型的約束相對應。如原問題是最小化，則可將對偶問題看做原問題12。表2-1 原問題模型與對偶問題模型的對應關(guān)系原問題(或?qū)ε紗栴})對偶問題(或原問題)目標函數(shù)最大化()目標函數(shù)最小化()個變量個約束約束條件的資源向量（右端項）目標函數(shù)的價格向量（系數(shù)）個約束個變量目標函數(shù)的

21、價格向量約束條件的資源向量變量約束約束變量例2-2 試求下列線性規(guī)劃問題的對偶問題。 (2-26)解：設(shè)對應于約束條件(2-14)的對偶變量分別為 則由表2-1中原問題與對偶問題的對應關(guān)系，可以直接寫出上述線性規(guī)劃問題的對偶問題，有 (2-27)3.3 線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論包括以下幾個主要的基本定理：定理2-1(對稱性定理) 對偶問題的對偶是原問題。這一定理的內(nèi)涵顯而易見，證明從略。定理2-2(弱對偶定理) 設(shè)和分別是原問題p和對偶問題d的可行解，則必有13。定理2-3(對偶原理) 原問題p與對偶問題d存在如下對應關(guān)系：(1) p有最優(yōu)解的充要條件是d有最優(yōu)解。(2) 若p無界

22、則d不可行，若d無界則p不可行。(3) 若和分別是p和d的可行解，則它們分別為p和d的最優(yōu)解的充要條件是。原問題與對偶問題的對應關(guān)系見表2-2。表2-2 原問題與對偶問題解的對應關(guān)系對應關(guān)系對偶問題有最優(yōu)解無界無可行解原問題有最優(yōu)解一定不可能不可能無界不可能不可能一定無可行解不可能一定可能定理2-4(互補松弛定理) 如果和分別為p和d的可行解，它們分別為p和d的最優(yōu)解的充要條件是和。互補松弛定理也稱松緊定理，它描述了線性規(guī)劃問題達到最優(yōu)時，原問題(或?qū)ε紗栴})的變量取值和對偶問題(或原問題)約束的松緊性之間的對應關(guān)系。我們知道，在一對互為對偶的線性規(guī)劃問題中，原問題的變量和對偶問題的約束是一一

23、對應的，原問題的約束和對偶問題的變量也是一一對應的。當線性規(guī)劃問題達到最優(yōu)時，我們不僅可以同時得到原問題與對偶問題的最優(yōu)解，而且還可以得到變量與約束之間的一種對應關(guān)系?；パa松弛定理即揭示了這一點。3.4 對偶單純形法的思路對偶單純形法是用對偶理論求解原問題的一種方法，而不是求解對偶問題解的單純形法。與對偶單純形法相對應，已有的單純形法稱原始單純形法14。對偶單純形法適應求解：（1）使用條件：檢驗數(shù)全部0； 解答列至少一個元素小于零。 （2）實施對偶單純形法的基本原則在保持對偶可行的前提下進行基變換每一次迭代過程中取出基變量中的一個負分量作為換出變量去替換某個非基變量(作為換入變量)，使原始問題

24、的非可行解向可行解靠近。（3） 計算步驟 建立初始單純形表，計算檢驗數(shù)行。 基變換。先確定換出變量解答列中的負元素(一般選最小的負元素)對應的基變量出基；即 (2-28)相應的行為主元行。然后確定換入變量原則是：在保持對偶可行的前提下，減少原始問題的不可行性。如果 (2-29)(最小比值原則)，則選為換入變量，相應的列為主元列，主元行和主元列交叉處的元素為主元素。 將主元素進行換基迭代(旋轉(zhuǎn)運算、樞運算)，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解15。例2-3 用對偶單純形法解下列線性規(guī)劃問題 (2-30)解：先將這個問題化成標準型 (2-31)再建立

25、這個問題的初始單純形表，并進行迭代計算，見下表。表2-3 初始單純形表-3-90000-2-1-11000-3-1-40100-3-1-70010-3-9000-3/-1-9/-1-表2-4 單純形表（第一步迭代）-3-9000-3211-1000-30-3-1100-30-6-10160-6-300-6/-3-3/-1-表2-5 單純形表（第二次迭代）-3-9000-35/310-4/31/30-91/3011/3-1/3001001-21800-1-20-0-1-2-最優(yōu)解是目標函數(shù)最優(yōu)值為。第三章 靈敏度分析靈敏度分析是研究與分析一個系統(tǒng)(或模型)的狀態(tài)或輸出變化對系統(tǒng)參數(shù)或周圍條件變化

26、的敏感程度的方法。在最優(yōu)化方法中經(jīng)常利用靈敏度分析來研究原始數(shù)據(jù)不準確或發(fā)生變化時最優(yōu)解的穩(wěn)定性。通過靈敏度分析還可以決定哪些參數(shù)對系統(tǒng)或模型有較大的影響。因此，靈敏度分析幾乎在所有的運籌學方法中以及在各種方案進行評價時都是很重要的16。1邊際值(影子價)首先以()為例。邊際值(影子價)是指在最優(yōu)解的基礎(chǔ)上，當?shù)趥€約束行的右端項減少一個單位時，目標函數(shù)的變化量 (3-1) (3-2)機會成本 (3-3)因此 (3-4)機會成本的另外表達形式 (3-5)關(guān)于影子價的一些說明影子價是資源最優(yōu)配置下資源的理想價格，資源的影子價與資源的緊缺度有關(guān)；松弛變量增加一個單位等于資源減少一個單位；剩余變量增加

27、一個單位等于資源增加一個單位；資源有剩余，在最優(yōu)解中就有對應松弛變量存在，且其影子價為0；影子價為0，資源并不一定有剩余。2價值向量的靈敏度分析價值向量(即目標函數(shù)系數(shù))的靈敏度分析分為原最終單純形表中與非基變量和基變量對應兩種情況來討論17。（1） 若是非基變量的系數(shù)，則其對應的最終單純形表中的檢驗數(shù)為 (3-6)或 (3-7)當變化，要保證最終單純形表的最優(yōu)解不變，必有 (3-8)保證最終單純形表最優(yōu)解不變，可得的允許變化值 (3-9)（2） 若是基變量的系數(shù)，應有,當變化時，就引起的變化，這時 (3-10)若要求原最優(yōu)解不變，必須滿足。于是得到 當 (3-11) (3-12)所以，可變化

28、的范圍是 (3-13)3靈敏度的應用（1）投入產(chǎn)出法中靈敏度分析可以用來研究采取某一項重大經(jīng)濟政策后將會對國民經(jīng)濟的各個部門產(chǎn)生怎樣的影響。（2）方案評價中靈敏度分析可以用來確定評價條件發(fā)生變化時備選方案的價值是否會發(fā)生變化或變化多少。第四章 應用實例某廠生產(chǎn)甲乙兩種口味的飲料，每百箱甲飲料需用原料6千克，工人10名，可獲利10萬元；每百箱乙飲料需用原料5千克，工人20名，可獲利9萬元。今工廠共有原料60千克，工人150名，又由于其他條件所限甲飲料產(chǎn)量不超過800箱。問如何安排生產(chǎn)計劃，即兩種飲料各生產(chǎn)多少使獲利最大.進一步討論：1)若投資0.8萬元可增加原料1千克，問應否作這項投資。2)若每

29、100箱甲飲料獲利可增加1萬元，問應否改變生產(chǎn)計劃。解：分別設(shè)在利潤最大的時候生產(chǎn)甲和乙的數(shù)量分別為：、百箱，則相應的甲和乙的原料數(shù)、工人數(shù)、利潤分別為：、；、；、。根據(jù)題設(shè)條件可以得出線性規(guī)劃模型為：目標函數(shù)為： (4-1)約束條件為： s.t. (4-2)編寫m文件yuqian1.m如下：c=-10 -9;a=6 5;10 20;1 0;b=60;150;8;aeq=; beq=;vlb=0;0; vub=;x,fval=linprog(c,a,b,aeq,beq,vlb,vub)計算結(jié)果為：x = 6.4286 4.2857fval = -102.8571所以最后應該生產(chǎn)的甲和乙分別為：

30、6.4286、4.2857百箱，保留兩位小數(shù)，應為6.42百箱和4.28百箱，相應的最大利潤為：102.72萬元。下面進一步討論：(1) 若投資0.8萬元可增加原料1千克，問應否作這項投資。當增加1千克原料時的線性規(guī)劃模型如下。目標函數(shù)： ； (4-3)約束條件： s.t. (4-4)編寫m文件yuqian2.m如下：c=-10 -9;a=6 5;10 20;1 0;b=61;150;8;aeq=; beq=;vlb=0;0; vub=;x,fval=linprog(c,a,b,aeq,beq,vlb,vub)計算結(jié)果為：x = 6.7143 4.1429fval = -104.4286這說明

31、應該生產(chǎn)的甲和乙分別為：6.7143、4.1429百箱，保留兩位小數(shù)，應為6.71百箱和4.14百箱。相應的利潤增加為：104.36-102.72=1.64>0.8。說明此時應該做這項投資。(2) 若每100箱甲飲料獲利可增加1萬元，問應否改變生產(chǎn)計劃。此時相應的線性規(guī)劃模型的目標函數(shù)為： ； (4-5)約束條件： s.t. (4-6)編寫m文件yuqian3.m如下：c=-11 -9;a=6 5;10 20;1 0;b=60;150;8;aeq=; beq=;vlb=0;0; vub=;x,fval=linprog(c,a,b,aeq,beq,vlb,vub)運行結(jié)果為：x = 8.0000 2.4000fval = -109.6000即相應的利潤為：109.6000>102.8571，說明應該改變生產(chǎn)計劃。結(jié) 論本文主要介紹了線性規(guī)劃的應用及靈敏度分析，包括解線性規(guī)劃問題的各種方法：圖解法，單純形法，大m法，兩階段法以及對偶單純形法等，以及簡單介紹了有關(guān)靈敏度分析的各種問題。通過對本論文的學習研究，除了能夠?qū)懗鼍€性規(guī)劃問題的各種模型并對它進行分析求解，還能夠?qū)懗鋈我庖粋€線性規(guī)劃問題的對偶理論，并能應用對偶單純形法解決相應的線性規(guī)劃問題，同時能對線性規(guī)劃的求解結(jié)果進行多種