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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、的非可行解向可行解靠近。（3） 計算步驟 建立初始單純形表，計算檢驗數行。 基變換。先確定換出變量解答列中的負元素(一般選最小的負元素)對應的基變量出基；即 (2-28)相應的行為主元行。然后確定換入變量原則是：在保持對偶可行的前提下，減少原始問題的不可行性。如果 (2-29)(最小比值原則)，則選為換入變量，相應的列為主元列，主元行和主元列交叉處的元素為主元素。 將主元素進行換基迭代(旋轉運算、樞運算)，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續以上步驟，直至求出最優解15。例2-3 用對偶單純形法解下列線性規劃問題 (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-最優解是目標函數最優值為。第三章 靈敏度分析靈敏度分析是研究與分析一個系統(或模型)的狀態或輸出變化對系統參數或周圍條件變化

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

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

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

29、100箱甲飲料獲利可增加1萬元，問應否改變生產計劃。解：分別設在利潤最大的時候生產甲和乙的數量分別為：、百箱，則相應的甲和乙的原料數、工人數、利潤分別為：、；、；、。根據題設條件可以得出線性規劃模型為：目標函數為： (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)計算結果為：x = 6.4286 4.2857fval = -102.8571所以最后應該生產的甲和乙分別為：

30、6.4286、4.2857百箱，保留兩位小數，應為6.42百箱和4.28百箱，相應的最大利潤為：102.72萬元。下面進一步討論：(1) 若投資0.8萬元可增加原料1千克，問應否作這項投資。當增加1千克原料時的線性規劃模型如下。目標函數： ； (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)計算結果為：x = 6.7143 4.1429fval = -104.4286這說明

31、應該生產的甲和乙分別為：6.7143、4.1429百箱，保留兩位小數，應為6.71百箱和4.14百箱。相應的利潤增加為：104.36-102.72=1.640.8。說明此時應該做這項投資。(2) 若每100箱甲飲料獲利可增加1萬元，問應否改變生產計劃。此時相應的線性規劃模型的目標函數為： ； (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)運行結果為：x = 8.0000 2.4000fval = -109.6000即相應的利潤為：109.6000102.8571，說明應該改變生產計劃。結 論本文主要介紹了線性規劃的應用及靈敏度分析，包括解線性規劃問題的各種方法：圖解法，單純形法，大M法，兩階段法以及對偶單純形法等，以及簡單介紹了有關靈敏度分析的各種問題。通過對本論文的學習研究，除了能夠寫出線性規劃問題的各種模型并對它進行分析求解，還能夠寫出任意一個線性規劃問題的對偶理論，并能應用對偶單純形法解決相應的線性規劃問題，同時能對線性規劃的求解結果進行多種情