對偶與靈敏度分析

1、§2 對偶與靈敏度分析§2.1LP的對偶問題無論從理論和實踐角度，對偶理論是LP中的一個最重要和有趣的概念，支持對偶理論的基本思想是：每一個LP問題都存在一個與其對偶的問題，在求解一個問題解的時候，也同時給出了另一問題的解。一、問題的提出例2.1：設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲乙，生產(chǎn)過程需要4種設(shè)備ABCD進行加工，每件產(chǎn)品加工所需機時數(shù)，每件產(chǎn)品的利潤值及每種設(shè)備的可利用機時如下表：設(shè)備產(chǎn)品ABCD利潤甲21402乙22043總機時12816121.問：充分利用設(shè)備時，應(yīng)怎樣安排甲乙產(chǎn)品的生產(chǎn)數(shù)量，利潤才能最大？2.問：如有另外一家公司想租用該廠設(shè)備加工生產(chǎn)，那么，這家公司應(yīng)至

2、少對每臺設(shè)備的機時價格為多少時，才能使該廠愿意出租設(shè)備？解：1.設(shè)甲乙產(chǎn)品各生產(chǎn)件LP1：2.設(shè)每臺設(shè)備的機時最低價分別為：，LP2：二、原問題和對偶問題之間的關(guān)系：1.對稱形式下的原問題與對偶問題對稱形式下原問題的一般式：矩陣形式：若用代表第i種資源的估價，則其對偶問題的一般式為：2.非對稱形式下原問題與對偶問題：方法一：將非對稱形式轉(zhuǎn)化為對稱形式，求出對偶問題，然后再還原。例2.2寫出下列LP問題的對偶問題：為寫出基對偶問題，先將其轉(zhuǎn)化為對稱形式，再進行變化：因目標(biāo)函數(shù)為，故約束條件全部轉(zhuǎn)化為“”，所有變量均應(yīng)為“”。將（1）式變?yōu)椋骸Ｔ賹ⅲ?）式兩端同乘以“-1”，并令：得：所以，例2

3、.2可以變?yōu)椋毫顚?yīng)上述四個約束條件的對偶變量為，則其對偶問題為：令，將第4與第5個不等式合并，將第三個不等式兩端同乘以“-1”得：由以上的推導(dǎo)可以發(fā)現(xiàn)有以下規(guī)律：方法二：根據(jù)原問題與對偶問題之間的關(guān)系，可將其歸納如下表：原問題（或?qū)ε紗栴}）對偶問題（原問題）目標(biāo)函數(shù)目標(biāo)函數(shù)變量 約束條件約束條件變量A約束系數(shù)矩陣b約束條件右端項向量C目標(biāo)函數(shù)中的價格系數(shù)向量約束系數(shù)矩陣的轉(zhuǎn)置C目標(biāo)函數(shù)中的價格系數(shù)向量b約束條件右端項向量§2.2 對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述設(shè)線性規(guī)劃問題的矩陣表達式為：，加上松弛變量后為：式中：。單純形法計算時，總選取為初始基I，對應(yīng)基變量為。設(shè)迭

4、代若干步后，基變量為，在初始單純形表中的系數(shù)矩陣為B。將B在初始單純形表中單獨列出，而A中去掉B的若干列后組成矩陣N，同時將C也分為兩塊，是目標(biāo)函數(shù)中基變量的系數(shù)行向量；是目標(biāo)函數(shù)中非基變量的系數(shù)行向量。這樣LP的初始單純形表可列成如下形式：項目非基變量基變量0bBNI0于是原LP問題可以改寫為：將約束條件移項并左乘后得到的表達式：代入目標(biāo)函數(shù)得：所以，經(jīng)過迭代之后，得出新的單純形表為：項目基變量非基變量I0當(dāng)為最優(yōu)基時，在上述單純形表中有：， 而的檢驗數(shù)可以寫為：因此有：，稱為單純形乘子，若令則有：可以發(fā)現(xiàn)這時檢驗數(shù)行，若取其相反數(shù)恰好是其對偶問題的一個可行解。將這個解代入對偶問題的目標(biāo)函數(shù)

5、值，有：即：當(dāng)原問題為最優(yōu)解時，這時對偶問題為可行解，且兩者具有相同的目標(biāo)函數(shù)值。（其實，這時對偶問題的解也為最優(yōu)解。）二、本節(jié)討論先假定原問題和對偶問題為對稱形式的LP，即原問題為：其對偶問題為：然后說明對偶問題的基本性質(zhì)在非對稱形式也適用。1.對稱性：對偶問題的對偶是原問題。證明：原問題與其對偶問題分別為：與2.弱對偶性：若是原問題可行解，是對偶問題的可行解，則存在。證明：設(shè)原問題為：原問題的對偶問題為：3.無界性：若原問題為無界解，則其對偶問題為無可行解。證明：由弱對偶性可得，本性質(zhì)成立。4.可行解是最優(yōu)解時的性質(zhì)：若是原問題可行解，是對偶問題的可行解，當(dāng)時，與是原問題與對偶問題的最優(yōu)解

6、。證明：5.對偶定理：若原問題有最優(yōu)解，那么其對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。6.互補松弛性：若是原問題可行解，是對偶問題的可行解，那么，當(dāng)且僅當(dāng)為，最優(yōu)解。（在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量值一定為零。）；。將互補松弛性質(zhì)應(yīng)用于其對偶問題時可以這樣敘述：；。由互補松弛定理可知：若原問題最優(yōu)解中的第j個變量為正，則其對偶問題中與之對應(yīng)的第j個約束條件在最優(yōu)情況下必呈嚴格等式（即其松弛變量為0）；而如果對偶問題中第j個約束條件在最優(yōu)情況下呈嚴格不等式，則原問題最優(yōu)解中第j個變量必為0。

7、類似地，若對偶問題最優(yōu)解中第i個對偶變量為正，則其原問題中與之對應(yīng)的第i個約束條件在最優(yōu)情況下必呈嚴格等式（即其剩余變量為0）；而如果原問題中第i個約束條件在最優(yōu)情況下呈嚴格不等式，則對偶問題最優(yōu)解中第i個對偶變量必為0?；パa松弛定量闡明了原問題及其對偶問題最優(yōu)解各分量之間的關(guān)系，當(dāng)已知一對對偶問題之一的最優(yōu)解時，可利用該定量求出另一個問題的最優(yōu)解。7.設(shè)原問題是：對偶問題為：則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解，其對應(yīng)關(guān)系如下表所示：0這里是對應(yīng)原問題中基變量的剩余變量，是對應(yīng)原問題中非基變量的剩余變量。證明：例2.3已知LP已知其對偶問題的最優(yōu)解為：試用對偶理論找出原問題的最

8、優(yōu)解。練習(xí)：1. 已知LP寫出其對偶問題；已知原問題的最優(yōu)解為試根據(jù)對偶理論求出對偶問題最優(yōu)解。2. 已知LP寫出其對偶問題；已知原問題的最優(yōu)解為試根據(jù)對偶理論求出對偶問題最優(yōu)解。§2.3對偶問題的經(jīng)濟解釋影子價格由對偶問題的性質(zhì)可知，當(dāng)LP原問題求得最優(yōu)解時，其對偶問題也得到最優(yōu)解，且代入各自目標(biāo)函數(shù)后有：，在式中是LP原問題約束條件的右端項，它代表第i種資源的擁有量，對偶變量的意義代表在資源最優(yōu)利用條件下，對單位第i種資源的估價。這種估價還是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見稱為影子價格。其特點如下：1.資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它

9、的影子價格則有賴于資源的利用情況，是未知的。由于企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。2.影子價格是一種邊際價格，在上式中對求的偏導(dǎo)數(shù)得：。說明的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，每增加一單位時目標(biāo)函數(shù)的增量。3.資源的影子價格實際上又是一種機會成本。當(dāng)某種資源的市場價格低于影子價格時，企業(yè)可以買進該資源用于擴大生產(chǎn)；而當(dāng)某種資源的市場價格高于影子價格時，則企業(yè)的決策者應(yīng)賣出已有資源，可見影子價格對市場有調(diào)節(jié)作用。4.由對偶問題互補的松弛性有：；，這表明生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價格為0，又當(dāng)資源的影子價格不為0時，表明該種資源在生

10、產(chǎn)中已耗費完畢。5.從影子價格的含義上來考察單純形表的計算。，式中代表第種產(chǎn)品的產(chǎn)值；是生產(chǎn)該種產(chǎn)品所消耗各項資源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時，表明生產(chǎn)該種產(chǎn)品有利，可在計劃中安排生產(chǎn)；否則用這些資料來生產(chǎn)別的產(chǎn)品更有利，就不在生產(chǎn)計劃中安排。這就是單純形表中各個檢驗數(shù)的經(jīng)濟意義。6.一般來說，對LP的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種估價直接涉及到資源的最有效的利用，如在一個大公司內(nèi)部，可借助于資源的影子價格確定一些內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。又如在社會上可借助影子價格規(guī)定使用這種

11、資源一單位時必須上繳的利潤額，以控制一些經(jīng)濟效益低的企業(yè)自學(xué)地節(jié)約緊缺資源，使有限資源發(fā)揮最大的經(jīng)濟效益。§2.4對偶單純形法一、對偶單純形法的理論依據(jù)：根據(jù)對偶問題的基本性質(zhì)7，在單純形表進行迭代求解時，在b列中得到的是原問題的基本可行解，在檢驗數(shù)行得到的是對偶問題的基可行解，根據(jù)最優(yōu)性定理，原問題有最優(yōu)解時，對偶問題也達到最優(yōu)解。根據(jù)其對稱性，也可以這樣考慮，若保持對偶問題的解是基可行解，即，而原問題是在非可行解的基礎(chǔ)上，通過逐步迭代的方式達到基可行解，這樣也可以得到最優(yōu)解。其優(yōu)點是原問題的初始解不一定要是基可行解，可從非基可行解的基礎(chǔ)上開始迭代。二、基本步驟：1.根據(jù)LP問題，

12、列出初始單純形表，檢查b列數(shù)字若都非負，檢驗數(shù)都為非正，則已得到最優(yōu)解，停止計算；否則，轉(zhuǎn)入下一步。2.確定換出變量：因為總存在，令，其對應(yīng)變量為換出變量。3. 確定換入變量：在單純形表中檢查所在行的各系數(shù)，若所有，則無可行解，停止計算；若存在，計算：，按規(guī)則所對應(yīng)的列的非基變量為換入變量。4. 以為主元素，進行迭代運算。5. 得到新單純形表，返回步驟1。例：2.4用對偶形法求解下列LP解： 從以上表中看出，用對偶單純形法求解LP時的優(yōu)點：1.初始解可以是非可行解，當(dāng)檢驗數(shù)都為負數(shù)時，就可以進行基的變換，這時不需要加入人工變量，可以簡化計算。2.當(dāng)約束條件為“”時，不必引進人工變量，可以使計算

13、簡化。3.當(dāng)變量多于約束條件，對這樣的線性規(guī)劃問題，用對偶單純形法計算可以減少計算工作量，因此對變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成對偶問題，然后用對偶單純形法求解。4.但在初始單純形表中其對偶問題應(yīng)是其可行解這一點很多LP很難實現(xiàn)，因此，對偶單純形法一般不單獨使用，而主要用于靈敏度分析及整數(shù)規(guī)劃等有關(guān)章節(jié)。§2.5靈敏度分析靈敏度分析是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。在以前講的LP問題中，總是假定問題中的是已知常數(shù)，但實際上這些參數(shù)往往是一些估計和預(yù)測的數(shù)字。如果市場條件變化，的值就會變化；是隨著工藝技術(shù)條件的改變而改變，而值則是根據(jù)資源投入

14、后能產(chǎn)生多大的經(jīng)濟效果來決定的一種決策選擇。因此，靈敏度分析要解決如下問題：l 當(dāng)這些參數(shù)中的一個或幾個發(fā)生變化時，問題最優(yōu)解有什么變化；l 這些在多大范圍內(nèi)變化時，問題的最優(yōu)解不變。靈敏度分析的步驟可歸納如下：1.將參數(shù)的改變計算反映到最終單純形表上來：2.檢查原問題是否仍為可行解。3.檢查對偶問題是否仍為可行解。4.按下表所列情況得出結(jié)論和決定繼續(xù)計算的步驟。原問題對偶問題結(jié)論或繼續(xù)計算步驟可行解可行解問題最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量，編制新的單純形表重新計算一、分析的變化LP目標(biāo)函數(shù)中價

15、值系數(shù)的變化僅僅影響到檢驗數(shù)的變化，所以將的變化直接反映到最終單純形表中，只可能出現(xiàn)上表中前兩種情況。例2.5，在第一章中例1.7中，假設(shè)產(chǎn)品的市場利潤變化為，在最優(yōu)解保持不變前提下，確定的變化范圍。解：利用前面計算出的最終單純形表進行計算：230002410000400-2132010000當(dāng)變?yōu)楹?，上表變?yōu)槿缦聠渭冃伪恚?3+0002410000400-213+2010000為了使原最優(yōu)解保持不變：則，解之得：說明產(chǎn)品的市場利潤可以在0,4之間變化，而不影響最優(yōu)解。二、分析的變化資源系數(shù)的變化反映到最終單純形表上將引起b列數(shù)字的變化，在上表中可能出現(xiàn)第一或第三兩種情況。出現(xiàn)第一種情況時，問題的最優(yōu)基不變，變化后的b列值為最優(yōu)解。出現(xiàn)第三種情況時，用對偶單純形法迭代繼續(xù)找出最優(yōu)解。當(dāng)發(fā)生變化時，即，并假設(shè)規(guī)劃中的其它系數(shù)都不變，這樣使最終表中原問題的解