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

1、線性規(guī)劃模型的應(yīng)用與靈敏度分析第一章 線性規(guī)劃問題1. 線性規(guī)劃簡介及發(fā)展線性規(guī)劃（Linear Programming）是運(yùn)籌學(xué)中研究最早、發(fā)展最快、應(yīng)用廣泛、方法成熟的一個重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法，研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法，英文縮寫為LP。它是運(yùn)籌學(xué)的一個重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營管理和工程技術(shù)等方面，為合理利用有限的人力、物力、財力等資源做出的最優(yōu)決策，提供科學(xué)的依據(jù)。線性規(guī)劃及其通用解法單純形法是由美國在1947年研究空軍軍事規(guī)劃提出來的。法國數(shù)學(xué)家傅里葉和瓦萊普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想

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

3、劃問題，1956年塔克提出互補(bǔ)松弛定理，1960年丹齊克和沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究3。由于數(shù)字電子計算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。1979年蘇聯(lián)數(shù)學(xué)家提出解線性規(guī)劃問題的橢球算法，并證明它是多項(xiàng)式時間算法。1984年美國貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問題的新的多項(xiàng)式時間算法。用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性

4、規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。 建立線性規(guī)劃模型線性規(guī)劃研究的問題主要有兩類:一類是當(dāng)一項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，盡量做到以最少的人力、物力等資源去完成；另一類是在人力、物力等資源確定的情況下，如何安排使用這些資源，使創(chuàng)造的價值最多，其實(shí)質(zhì)是解決稀缺資源在有競爭環(huán)境中如何進(jìn)行最優(yōu)分配的問題，即尋求整個問題的某個整體指標(biāo)最優(yōu)的問題4。2. 線性規(guī)劃的數(shù)學(xué)模型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)品可獲利3元，問應(yīng)如何安排生產(chǎn)計劃使該工廠獲得的利潤最大？有關(guān)資料

5、如下表1-1產(chǎn)品、資源信息產(chǎn)品資源限量設(shè)備/臺128原材料A/kg4016原材料B/kg0412用數(shù)學(xué)語言來描述生產(chǎn)計劃的安排，建立數(shù)學(xué)模型。解：設(shè)x,x分別表示在計劃期內(nèi)產(chǎn)品,的生產(chǎn)量，在滿足資源限量的條件下，它們必須同時滿足下列條件。 對設(shè)備有效臺數(shù)： 對原材料A： 對原材料B： 該工廠的生產(chǎn)目標(biāo)是在不超過所有資源限量的條件下，確定生產(chǎn)量x,x，使該得到的利潤最大。若用Z表示總利潤，則有 綜合上述，該生產(chǎn)計劃問題可用數(shù)學(xué)模型表示為 (1-1)這就是一個線性規(guī)劃模型5。2.2 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型是由一組含有等式或者不等式的代數(shù)方程以及一個具有求極值關(guān)系的目標(biāo)函數(shù)表達(dá)式構(gòu)成

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

7、其中，式(1-2)稱為目標(biāo)函數(shù)，(1-3)式稱為約束條件。2.3 線性規(guī)劃的性質(zhì)定理1 線性規(guī)劃問題的可行解X是基可行解的充要條件是X的非零分量對應(yīng)的系數(shù)矩陣A的列向量線性無關(guān)6。定理2 若一個線性規(guī)劃問題有可行解，則它必有基本可行解7。定理3 若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。證明：設(shè)是可行域的頂點(diǎn)，若不是頂點(diǎn)，且目標(biāo)函數(shù)在處達(dá)到最優(yōu)（標(biāo)準(zhǔn)型是）。因?yàn)椴皇琼旤c(diǎn)，所以D的頂點(diǎn)線性表示為 (1-4)在所有頂點(diǎn)中必然能找到某個頂點(diǎn)，使是所有中最大者，并且將代替式（1-5）中所有的，這就得到，由此得到，根據(jù)假設(shè)最大值，所以只能有，即目標(biāo)函數(shù)在頂點(diǎn)處也達(dá)到最大值。

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

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

10、發(fā)展單純形法（simplex methods），求解線性規(guī)劃的通用方法。單純形法是美國數(shù)學(xué)家G.B.Dantzig于1947年首先提出的。簡單的說就是一種數(shù)學(xué)迭代方法，求解基本過程是從一個基本可行解跳到另一個基本可行解的逐步替代，從而使目標(biāo)函數(shù)不斷得到改善。它的理論根據(jù)是：線性規(guī)劃問題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到9。 單純形法的基本思路單純形法的基本思路是：根據(jù)線性規(guī)劃問題的標(biāo)準(zhǔn)型，從可行域中某個基本可行解（一個頂點(diǎn)）開始，轉(zhuǎn)換到另一個基本可行解（頂點(diǎn)），并且當(dāng)目標(biāo)函數(shù)達(dá)到最大值時，問題就得到了解決，其基本思路的框架圖如下圖2-1。給出一個初始基

11、本可行解是否最優(yōu) 否 是從當(dāng)前基可行解出發(fā)，尋求一個能使目標(biāo)函數(shù)值活的改善的新的基本可行解寫出最優(yōu)解 圖2-1 單純形法的基本思路例2-1 用單純形法討論例1-1的求解。解：已知例1.1的標(biāo)準(zhǔn)型為： (2-1) (2-2) 約束條件(2-2)的系數(shù)矩陣 顯然，的系數(shù)列向量 ， (2-3)是線性獨(dú)立的，因而這些向量構(gòu)成一個基 (2-4)對應(yīng)于的基變量為,，從約束條件(2-2)中可以看到 (2-5)當(dāng)令非基變量，這時得到一個基本可行解 (2-6)將式(2-3)代入目標(biāo)函數(shù)(2-1)得到 (2-7)這個基本可行解表示：工廠沒有安排生產(chǎn),產(chǎn)品；資源都沒有被利用，所以工廠的利潤。分析目標(biāo)函數(shù)的表達(dá)式(2

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

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

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

15、論。 若中存在一個單位基，則將其作為初始可行基 (2-15) 若中不存在一個單位基，則人為地構(gòu)造一個單位初始基。（2） 檢驗(yàn)最優(yōu)解。得到初始基本可行解后，要檢驗(yàn)該解是否為最優(yōu)解。如果是最優(yōu)解，則停止運(yùn)算；否則轉(zhuǎn)入（3）基變換。下面給出最優(yōu)性判別定理。一般情況下，經(jīng)過迭代后可以得到以非基變量表示基變量的表達(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)解，又不能判別無界時，由目標(biāo)函數(shù)(2-10)的約束條件可看到，

16、當(dāng)某些，增加則目標(biāo)函數(shù)值還可能增加，這時就要將其中某個非基變量換到基變量中去（稱為換入變量），同時，某個基變量要換成非基變量（稱為換出變量），隨之會得到一個新的基本可行解。從一個基本可行解到另一個基本可行解的變換，就是進(jìn)行一次基變換。從幾何意義上就是從可行域的一個頂點(diǎn)轉(zhuǎn)向另一個頂點(diǎn)。（4） 迭代。在確定了換入變量和換出變量后，要把和的位置進(jìn)行對換，就是說要把對應(yīng)的系數(shù)列向量變成單位列向量。這可以通過對約束方程組的增廣矩陣進(jìn)行初等行變換來實(shí)現(xiàn)，變換結(jié)果得一新的基本可行解。然后轉(zhuǎn)入（2）。2.2 單純形法的進(jìn)一步討論對于一般的線性規(guī)劃問題，在用單純形法求解之前，總是先化為標(biāo)準(zhǔn)型。如果在系數(shù)矩陣中有

17、一個單位陣，則可以作為初始可行基。如果約束條件的系數(shù)矩陣中不存在單位矩陣，則可以通過添加人工變量的方法，在標(biāo)準(zhǔn)型的約束方程的系數(shù)矩陣中人為地構(gòu)造一個單位陣，從而獲得初始可行基，再作進(jìn)一步迭代。在單純形迭代過程中，要求人工變量逐步從基變量被替換出，變?yōu)榉腔兞浚@有兩種方法：大M法和兩階段法10。人工變量法的基本思想：對于線性規(guī)劃問題，有時候很難找出初始基本可行解，這時可以考慮加入人工變量的方法來解決問題?；驹韺τ跇?biāo)準(zhǔn)型的線性規(guī)劃問題： (2-22)給每個約束方程硬性加入一個人工變量之后得到： (2-23)這樣，就可以以為基變量，得到問題的初始基本可行解。在求解的過程中，通過迭代不斷地將這些

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

19、優(yōu)表格中去掉人工變量，將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，接下去用單純形法計算，直到得到最優(yōu)解為止。3單純形法對偶規(guī)劃是線性規(guī)劃問題從另一個角度進(jìn)行研究，是線性規(guī)劃理論的進(jìn)一步深化，也是線性規(guī)劃理論的進(jìn)一步深化，也是線性規(guī)劃理論整體的一個不可分割的組成部分。3.1 對偶問題的提出每個線性規(guī)劃都有另一個線性規(guī)劃（對偶問題）與它密切相關(guān)，對偶理論揭示了原問題與對偶問題的內(nèi)在聯(lián)系11。3.2 對偶問題的數(shù)學(xué)模型及對偶關(guān)系原問題P的標(biāo)準(zhǔn)形式： (2-24)對偶問題D的標(biāo)準(zhǔn)形式： (2-25)當(dāng)我們討論對偶問題時，它必定是與原問題成對出現(xiàn)的；同時，原問題與對偶問題之間沒有嚴(yán)格的界限，它們互為對偶：一

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

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

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

23、不僅可以同時得到原問題與對偶問題的最優(yōu)解，而且還可以得到變量與約束之間的一種對應(yīng)關(guān)系。互補(bǔ)松弛定理即揭示了這一點(diǎn)。3.4 對偶單純形法的思路對偶單純形法是用對偶理論求解原問題的一種方法，而不是求解對偶問題解的單純形法。與對偶單純形法相對應(yīng)，已有的單純形法稱原始單純形法14。對偶單純形法適應(yīng)求解：（1）使用條件：檢驗(yàn)數(shù)全部0； 解答列至少一個元素小于零。 （2）實(shí)施對偶單純形法的基本原則在保持對偶可行的前提下進(jìn)行基變換每一次迭代過程中取出基變量中的一個負(fù)分量作為換出變量去替換某個非基變量(作為換入變量)，使原始問題的非可行解向可行解靠近。（3） 計算步驟 建立初始單純形表，計算檢驗(yàn)數(shù)行。 基變換

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

25、00-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)解是目標(biāo)函數(shù)最優(yōu)值為。第三章 靈敏度分析靈敏度分析是研究與分析一個系統(tǒng)(或模型)的狀態(tài)或輸出變化對系統(tǒng)參數(shù)或周圍條件變化的敏感程度的方法。在最優(yōu)化方法中經(jīng)常利用靈敏度分析來研究原始數(shù)據(jù)不準(zhǔn)確或發(fā)生變化時

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

27、價為0；影子價為0，資源并不一定有剩余。2價值向量的靈敏度分析價值向量(即目標(biāo)函數(shù)系數(shù))的靈敏度分析分為原最終單純形表中與非基變量和基變量對應(yīng)兩種情況來討論17。（1） 若是非基變量的系數(shù)，則其對應(yīng)的最終單純形表中的檢驗(yàn)數(shù)為 (3-6)或 (3-7)當(dāng)變化，要保證最終單純形表的最優(yōu)解不變，必有 (3-8)保證最終單純形表最優(yōu)解不變，可得的允許變化值 (3-9)（2） 若是基變量的系數(shù)，應(yīng)有,當(dāng)變化時，就引起的變化，這時 (3-10)若要求原最優(yōu)解不變，必須滿足。于是得到 當(dāng) (3-11) (3-12)所以，可變化的范圍是 (3-13)3靈敏度的應(yīng)用（1）投入產(chǎn)出法中靈敏度分析可以用來研究采取某

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

29、甲和乙的數(shù)量分別為：、百箱，則相應(yīng)的甲和乙的原料數(shù)、工人數(shù)、利潤分別為：、；、；、。根據(jù)題設(shè)條件可以得出線性規(guī)劃模型為：目標(biāo)函數(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所以最后應(yīng)該生產(chǎn)的甲和乙分別為：6.4286、4.2857百箱，保留兩位小數(shù)，應(yīng)為6.42百箱和4.28百箱，相應(yīng)

30、的最大利潤為：102.72萬元。下面進(jìn)一步討論：(1) 若投資0.8萬元可增加原料1千克，問應(yīng)否作這項(xiàng)投資。當(dāng)增加1千克原料時的線性規(guī)劃模型如下。目標(biāo)函數(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這說明應(yīng)該生產(chǎn)的甲和乙分別為：6.7143、4.1429百箱，保留兩位小數(shù)，應(yīng)為6.71

31、百箱和4.14百箱。相應(yīng)的利潤增加為：104.36-102.72=1.64>0.8。說明此時應(yīng)該做這項(xiàng)投資。(2) 若每100箱甲飲料獲利可增加1萬元，問應(yīng)否改變生產(chǎn)計劃。此時相應(yīng)的線性規(guī)劃模型的目標(biāo)函數(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)運(yùn)行結(jié)果為：x = 8.0000 2.4000fval = -109.6000即相應(yīng)的利潤為：109.6000>102.8571，說明應(yīng)該改變生產(chǎn)計劃。結(jié) 論本文主要介紹了線性規(guī)劃的應(yīng)用及靈敏度分析，包括解線性規(guī)劃問題的各種方法：圖解法，單純形法，大M法，兩階段法以及對偶單純形法等，以及簡單介紹了有關(guān)靈敏度分析的各種問題。通過對本論文的學(xué)習(xí)研究，除了能夠?qū)懗鼍€性規(guī)劃問題的各種模型并對它進(jìn)行分析求解，還能夠?qū)懗鋈我庖粋€線性規(guī)劃問題的對偶理論，并能應(yīng)用對偶單純形法解決相應(yīng)的線性規(guī)劃問題，同時能對線性規(guī)劃的求解結(jié)果進(jìn)行多種情況的