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

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

2、法，但未引起注意。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)用到經(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ī)

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

4、規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。 建立線性規(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。2. 線性規(guī)劃的數(shù)學(xué)模型2.1 線性規(guī)劃問(wèn)題例1-1某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)兩種產(chǎn)品,，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)數(shù)及A,B兩種原材料的消耗量，見(jiàn)表1-1。該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利3元，問(wèn)應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲得的利潤(rùn)最大？有關(guān)資料

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

6、的符合抽象數(shù)學(xué)模型。下面介紹建立實(shí)際問(wèn)題線性規(guī)劃模型的基本步驟。（1） 確定決策變量。這是很關(guān)鍵的一步，決策變量選取得當(dāng)，不僅會(huì)使線性規(guī)劃的數(shù)學(xué)模型建得容易，而且求解比較方便。 （2） 找出所有限制條件，并用決策變量的線性等式或不等式來(lái)表示，從而得到約束條件。一般可用表格形式列出所有的限制數(shù)據(jù)，然后根據(jù)所列出的數(shù)據(jù)寫(xiě)出相應(yīng)的約束條件，以避免遺漏或重復(fù)所規(guī)定的限制要求。 （3） 把實(shí)際問(wèn)題所要達(dá)到的目的用決策變量的線性函數(shù)來(lái)表示，得到目標(biāo)函數(shù)，并確定是求最大值還是最小值。 （4） 根據(jù)實(shí)際問(wèn)題添加非負(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ī)劃問(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)。證明：設(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)中必然能找到某個(gè)頂點(diǎn)，使是所有中最大者，并且將代替式（1-5）中所有的，這就得到，由此得到，根據(jù)假設(shè)最大值，所以只能有，即目標(biāo)函數(shù)在頂點(diǎn)處也達(dá)到最大值。

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

9、解，所有可行解組成的集合稱為可行域。圖解法的求解步驟如下：第一步，根據(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ú)界解（無(wú)解）圍成無(wú)界區(qū)域，且無(wú)有限最優(yōu)值缺少一必要條件的方程2. 單純形法2.1 單純形法的

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

11、本可行解是否最優(yōu) 否 是從當(dāng)前基可行解出發(fā)，尋求一個(gè)能使目標(biāo)函數(shù)值活的改善的新的基本可行解寫(xiě)出最優(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)成一個(gè)基 (2-4)對(duì)應(yīng)于的基變量為,，從約束條件(2-2)中可以看到 (2-5)當(dāng)令非基變量，這時(shí)得到一個(gè)基本可行解 (2-6)將式(2-3)代入目標(biāo)函數(shù)(2-1)得到 (2-7)這個(gè)基本可行解表示：工廠沒(méi)有安排生產(chǎn),產(chǎn)品；資源都沒(méi)有被利用，所以工廠的利潤(rùn)。分析目標(biāo)函數(shù)的表達(dá)式(2

12、-7)可以看到：非基變量,的系數(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è)非基變量為換入變量，將它換入到基變量中區(qū)，同時(shí)還有確定基變量中有一個(gè)要換出來(lái)成為非基變量，可按以下方法來(lái)確定換出變量。現(xiàn)分析式(2-5)，當(dāng)將定為換入變量后，必須從,中換出一個(gè)，并保證其余的都是非負(fù)，即,0。當(dāng)，由式(2-5)得到 (2-8)從式(2-8)中可以看出，只有選擇 (2-9)時(shí)

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

14、出變量，繼續(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)題的思路。 單純形法的一般描述和求解步驟一般的線性規(guī)劃問(wèn)題的求解有以下幾個(gè)步驟。（1） 確定初始基本可行解。為了確定初始基本可行解，首先要找出初始可行解。設(shè)一線性規(guī)劃問(wèn)題為 (2-14)可分為兩種情況討

15、論。 若中存在一個(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í)，由目標(biāo)函數(shù)(2-10)的約束條件可看到，

16、當(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é)果得一新的基本可行解。然后轉(zhuǎn)入（2）。2.2 單純形法的進(jìn)一步討論對(duì)于一般的線性規(guī)劃問(wèn)題，在用單純形法求解之前，總是先化為標(biāo)準(zhǔn)型。如果在系數(shù)矩陣中有

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

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

19、優(yōu)表格中去掉人工變量，將目標(biāo)函數(shù)系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，接下去用單純形法計(jì)算，直到得到最優(yōu)解為止。3單純形法對(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。3.2 對(duì)偶問(wèn)題的數(shù)學(xué)模型及對(duì)偶關(guān)系原問(wèn)題P的標(biāo)準(zhǔn)形式： (2-24)對(duì)偶問(wèn)題D的標(biāo)準(zhǔn)形式： (2-25)當(dāng)我們討論對(duì)偶問(wèn)題時(shí)，它必定是與原問(wèn)題成對(duì)出現(xiàn)的；同時(shí)，原問(wèn)題與對(duì)偶問(wèn)題之間沒(méi)有嚴(yán)格的界限，它們互為對(duì)偶：一

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

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

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

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

24、。先確定換出變量解答列中的負(fù)元素(一般選最小的負(fù)元素)對(duì)應(yīng)的基變量出基；即 (2-28)相應(yīng)的行為主元行。然后確定換入變量原則是：在保持對(duì)偶可行的前提下，減少原始問(wèn)題的不可行性。如果 (2-29)(最小比值原則)，則選為換入變量，相應(yīng)的列為主元列，主元行和主元列交叉處的元素為主元素。 將主元素進(jìn)行換基迭代(旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解15。例2-3 用對(duì)偶單純形法解下列線性規(guī)劃問(wèn)題 (2-30)解：先將這個(gè)問(wèn)題化成標(biāo)準(zhǔn)型 (2-31)再建立這個(gè)問(wèn)題的初始單純形表，并進(jìn)行迭代計(jì)算，見(jià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)值為。第三章 靈敏度分析靈敏度分析是研究與分析一個(gè)系統(tǒng)(或模型)的狀態(tài)或輸出變化對(duì)系統(tǒng)參數(shù)或周圍條件變化的敏感程度的方法。在最優(yōu)化方法中經(jīng)常利用靈敏度分析來(lái)研究原始數(shù)據(jù)不準(zhǔn)確或發(fā)生變化時(shí)

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

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

28、一項(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ā)生變化或變化多少。第四章 應(yīng)用實(shí)例某廠生產(chǎn)甲乙兩種口味的飲料，每百箱甲飲料需用原料6千克，工人10名，可獲利10萬(wàn)元；每百箱乙飲料需用原料5千克，工人20名，可獲利9萬(wàn)元。今工廠共有原料60千克，工人150名，又由于其他條件所限甲飲料產(chǎn)量不超過(guò)800箱。問(wèn)如何安排生產(chǎn)計(jì)劃，即兩種飲料各生產(chǎn)多少使獲利最大.進(jìn)一步討論：1)若投資0.8萬(wàn)元可增加原料1千克，問(wèn)應(yīng)否作這項(xiàng)投資。2)若每100箱甲飲料獲利可增加1萬(wàn)元，問(wèn)應(yīng)否改變生產(chǎn)計(jì)劃。解：分別設(shè)在利潤(rùn)最大的時(shí)候生產(chǎn)

29、甲和乙的數(shù)量分別為：、百箱，則相應(yīng)的甲和乙的原料數(shù)、工人數(shù)、利潤(rùn)分別為：、；、；、。根據(jù)題設(shè)條件可以得出線性規(guī)劃模型為：目標(biāo)函數(shù)為： (4-1)約束條件為： s.t. (4-2)編寫(xiě)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)計(jì)算結(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、的最大利潤(rùn)為：102.72萬(wàn)元。下面進(jìn)一步討論：(1) 若投資0.8萬(wàn)元可增加原料1千克，問(wèn)應(yīng)否作這項(xiàng)投資。當(dāng)增加1千克原料時(shí)的線性規(guī)劃模型如下。目標(biāo)函數(shù)： ； (4-3)約束條件： s.t. (4-4)編寫(xiě)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)計(jì)算結(jié)果為：x = 6.7143 4.1429fval = -104.4286這說(shuō)明應(yīng)該生產(chǎn)的甲和乙分別為：6.7143、4.1429百箱，保留兩位小數(shù)，應(yīng)為6.71

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