對偶理論與靈敏度分析

1、 對偶理論與靈敏度分析對偶問題的提出對偶理論影子價格對偶單純形法靈敏度分析對偶問題的提出定義：一個線性規(guī)劃問題常伴隨著與之配對的、兩者有密切聯(lián)系的另一個線性規(guī)劃問題，我們將其中一個稱為原問題，另一個就稱為對偶問題。應(yīng)用:1. 在某些情況下，解對偶問題比解原問題更加容易2. 對偶變量有重要的經(jīng)濟解釋(影子價格)3. 作為靈敏度分析的工具4. 對偶單純形法(從一個非可行基出發(fā)，得到線性規(guī)劃問題的最優(yōu)解)5. 避免使用人工變量(人工變量帶來很多麻煩，兩階段法則增加一倍的計算量)一、對偶問題的提出例：某家具廠木器車間生產(chǎn)木門與木窗；兩種產(chǎn)品。加工木門收入為56元/扇，加工木窗收入為30元/扇。生產(chǎn)一扇

2、木門需要木工4小時，油漆工2小時；生產(chǎn)一扇木窗需要木工3小時，油漆工1小時；該車間每日可用木工總共時為120小時，油漆工總工時為50小時。問：(1)該車間應(yīng)如何安排生產(chǎn)才能使每日收入最大？ (2)假若有一個個體經(jīng)營者，手中有一批木器家具生產(chǎn)訂單。他想利用該木器車間的木工與油漆工來加工完成他的訂單。他就要考慮付給該車間每個工時的價格。他可以構(gòu)造一個數(shù)學(xué)模型來研究如何定價才能既使木器車間覺得有利可圖而愿意為他加工這批訂單、又使自己所付的工時費用最少。解(1)：設(shè)該車間每日安排生產(chǎn)木門x1扇，木窗x2扇，則數(shù)學(xué)模型為X*=(15,20) Z*=1440元解(2)：設(shè)y1為付給木工每個工時的價格，y2

3、為付給油工每個工時的價格Y*=(2,24) W*=1440元將上述問題1與問題2稱為一對對偶問題，兩者之間存在著緊密的練習(xí)與區(qū)別：它們都使用了木器生產(chǎn)車間相同的數(shù)據(jù)，只是數(shù)據(jù)在模型中所處的位置不同，反映所要表達的含義也不同。二、LP和DP的聯(lián)系與區(qū)別(1)一個極大化，一個極小化(2)LP的價值系數(shù)行向量(DP右端項)(3)LP的系數(shù)矩陣(DP系數(shù)矩陣)(4)LP的右端項(DP的價值系數(shù))(5)LP的約束個數(shù)DP的變量個數(shù)(6)LP的變量個數(shù)DP的約束個數(shù)三、 原問題與對偶問題的關(guān)系1對稱形式下對偶問題的一般形式定義：滿足下列條件的線性規(guī)劃問題稱為具有對稱形式：(1)其變量均為非負約束；(2)其

4、約束條件當目標函數(shù)求極大時取“”號，當目標函數(shù)求極小時取“”號；(3)右端項b可取負值。對稱形式下原問題及對偶問題的矩陣形式對稱性定理：對偶問題的對偶是原問題。證明：在DP中，令W = -W則有其對偶問題為：令Z=-Z，則有所以，對偶問題的對偶是原問題。例：寫出LP的對偶問題2. 非對稱形式的原對偶問題關(guān)系并非所有的LP問題都有對稱形式，故討論一般情況下LP問題如何寫出其對偶問題例 寫出下述線性規(guī)劃的對偶問題解：先化為對稱形式，因為目標函數(shù)求極大，所以約束條件變?yōu)椤啊保瑳Q策變量0令對應(yīng)上述4個約束條件的對偶變量分別為則有令，將上邊3，4兩個約束條件合并，得經(jīng)過以上分析，可以總結(jié)出原規(guī)劃與對偶規(guī)

5、劃相關(guān)數(shù)據(jù)間的聯(lián)系。對偶關(guān)系相互對照表原問題(LP)對偶問題(DP)目標函數(shù)形式max目標函數(shù)形式min變量N個變量變量0變量0無正負限制約束n個約束約束約束約束約束M個約束約束約束約束變量m個變量變量0變量0無正負限制約束方程右端項目標函數(shù)價值系數(shù)目標函數(shù)價值系數(shù)約束方程右端項例 寫出下列線性規(guī)劃的對偶問題 結(jié)果練習(xí) 寫出下列線性規(guī)劃的對偶問題練習(xí)結(jié)果對偶問題的基本性質(zhì)(對偶定理)一、單純形法的矩陣描述對于對稱形式的線性規(guī)劃問題，其標準形式為XS為松弛變量,XS=(xn+1,xn+2,xn+m), I為m×m矩陣列出初始單純形表非基變量基變量CBXBbXBXNXS0XSbBNI-Z

6、0CBCN0設(shè)若干步迭代后，基變量為XB, XB在初始單純形表中的系數(shù)矩陣為B，而A中去掉B的若干列組成矩陣N，則迭代后的單純形表為：基變量非基變量CBXBbXBXNXSCBXBB-1bIB-1NB-1-Z-CB B-1b0CN-CB B-1N-CB B-1從表中看出：(1)對應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1(2)初始單純形表中的基變量XS=b，迭代后為XB=B-1b(3)初始單純形表中約束系數(shù)矩陣A,I=B,N,I，迭代后的表中為B-1A, B-1I= B-1B, B-1N, B-1I I, B-1N, B-1(4)若初始矩陣中變量xj的系數(shù)列向量為Pj，迭代后為Pj

7、，則Pj= B-1Pj(5)當B為最優(yōu)基時，應(yīng)有又因為XB的檢驗數(shù)可寫為將(1)和(3)合并，則有CBB-1稱為單純形因子，令CBB-1Y則有CBB-1Y，檢驗數(shù)行的相反數(shù)，恰好是對偶問題的可行解。將YCBB-1代入對偶問題的目標函數(shù)值，所以當原問題為最優(yōu)解是，對偶問題為可行解，且兩者目標函數(shù)值相同，根據(jù)下節(jié)的對偶問題的基本性質(zhì)，將看到這時對偶問題的解也為最優(yōu)解。二、對偶問題的基本性質(zhì)(對偶定理)對于下面標準形式的原，對偶問題，有以下定理：定理1(弱對偶定理)：如果X(0)是原問題的可行解，Y(0)是對偶問題的可行解，則恒有 C X(0) Y(0) b證明：X(0)是原問題的可行解， 所以A

8、X(0) b (1)Y(0)是對偶問題的可行解，所以Y(0) A C (2)X(0) ， Y(0)0，用X(0)右乘(2)，Y(0)左乘(1)Y(0)A X(0) Y(0)bY(0) A X(0)C X(0)即 C X(0) Y(0) b(1)原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。(2)如原問題有可行解且目標函數(shù)值無界，則其對偶問題無可行解；反之對偶問題有可行解且目標函數(shù)值無界則其原問題無可行解。(3)如原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，則對偶問題

9、的目標函數(shù)值無界。定理2(最優(yōu)準則定理)：如果X(0)是原問題的可行解，Y(0)是對偶問題的可行解，則當C X(0) Y(0) b時， X(0) ， Y(0分別為各自問題的最優(yōu)解。證明：設(shè)X是LP的任一個可行解，則有C X Y(0) bC X(0)所以 X(0) 是最大化問題的最優(yōu)解 Y(0是最小化問題的最優(yōu)解定理3(最優(yōu)解存在定理)：若LP和DP同時存在可行解，則它們必都存在最優(yōu)解。證明同上。定理4(無界解定理)：若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解。證明：反證法設(shè)原問題目標函數(shù)為極大值，無上界對偶問題的可行解為Y(0)則C X Y(0) b根據(jù)定理1，原問題存在最優(yōu)

10、解，與假設(shè)矛盾，假設(shè)不成立定理5(強對偶性定理)：如果原問題和對偶問題中有一個有最優(yōu)解，則另一個問題也必存在最優(yōu)解，且兩個問題的最優(yōu)解的目標函數(shù)值相等。證明：設(shè)LP存在最優(yōu)解，將其化為標準型，則有Xa為松弛變量，Ca為其價值系數(shù)(Ca=0)，設(shè)原問題的最優(yōu)解為X(0)，基為B，則有即 令CBB-1Y(0) 則有 所以Y(0)是對偶問題的一個可行解引入定理2，W(0)=Y(0) bCBB-1b=CBXB 也是對偶問題的最優(yōu)解原問題與對偶問題的解之間只有以下3種可能的關(guān)系(1) 兩個問題都有可行解，從而都有最優(yōu)解(2) 一個為無界，另一個必無可行解(3) 兩個都無可行解定理6(互補松弛性定理)：在

11、線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束取嚴格等式；反之如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。證明：設(shè)原問題和對偶問題的標準型是則 充分性：若YSX=0 YXS=0 則有Z=W 即CX(0)Y(0)b則X(0)，Y(0)必是各自問題的最優(yōu)解必要性：若X(0)，Y(0)是各自問題的最優(yōu)解則有CX(0)Y(0)bY(0)A X(0)即YSX=0 YXS=0互補松弛性定理的應(yīng)用：在已知一個問題的最優(yōu)解時，可求其對偶問題的最優(yōu)解。例 已知下列問題的最優(yōu)解為X*=(1/7,11/7),用互補松弛定理求其對偶問題的最優(yōu)解。解：第一步，寫出對偶問題第二步，將L

12、P，DP都化為標準型第三步：將最優(yōu)解代入標準型中，確定松弛變量取值第四步：利用互補松弛定理 Y3*=0 Y1S=0 Y2S=0第五步：將Y3*=0 Y1S=0 Y2S=0 代入約束條件則有 對偶問題的最優(yōu)解為Y*=(4/7,5/7,0)解題步驟第1步：寫出對偶問題第2步：將LP，DP都化為標準型第3步：將最優(yōu)解代入標準型中，確定松弛變量取值第4步：利用互補松弛定理練習(xí) 若對偶問題的最優(yōu)解為Y*=(4.1)，試用互補松弛定理求原問題的最優(yōu)解。X*=(0,0,4,4)影子價格定義：根據(jù)最優(yōu)性定理Z*=CX*=Y*b=W*，其中bi既是原問題約束條件的右端項(第i種資源的擁有量)，又是對偶問題的價值

13、系數(shù)，那么在最優(yōu)解處W* = Y*b Y*1b1 Y*2b2 Y*mbm此時bi增加一個單位，目標函數(shù)則變化Yi個單位則Y*(對偶解)的經(jīng)濟意義為：資源的單位改變量引起目標函數(shù)值的增加量，也就是在資源最優(yōu)利用條件下對單位第種資源的估價。但這種估價不是資源的市場價格，而是根據(jù)資源對生產(chǎn)所作的貢獻而作的估價。為區(qū)別起見，稱為影子價格(shadow price)。 (1)影子價格的大小客觀的反映了資源的稀缺程度。如果第I種資源供大于求，即達到最優(yōu)解時，資源并沒用完，即Xsi0 為非稀缺資源由互補松弛定理，Yi*=0，即該資源的影子價格0增加該資源的供應(yīng)不會引起目標函數(shù)值的增加。反之，如果Yi*0，即

14、影子價格0，則說明增加該資源的供應(yīng)，會引起目標函數(shù)值的增加（Yi*=增加量）例 木門，木窗Cj563000CBXBbx1x2x3x400x3x412050423110013025-Z0563000056x3x120250111/210-21/22050-Z-56*25020-283056x2x1201501101-1/2-23/2-Z-144000-2-24Z*=20, X*=(15,20) Y*=(2,24)這說明增加這兩種資源都會引起目標值的增加，也就是說，它們都是稀缺資源。木工工時從120增加到121，Z*=1442油工工時從50增加到51，Z*=1464驗證：Cj563000CBXBb

15、x1x2x3x400x3x41215042311001121/425-Z0563000056x3x121250111/210-21/22150-Z-56*25020-283056x2x12129/201101-1/2-23/2-Z-144200-2-24如果某個Yi*=0，則增加該資源對Z無影響應(yīng)用：（1）邊際價格。管理者增加某種資源對經(jīng)濟效益有無影響及影響程度。（2）隱含成本。如果增加第3種產(chǎn)品（木椅子），告知新產(chǎn)品的定價標準。假設(shè)木椅子對兩種資源的消耗分別為木工3h，油工2h，問銷價應(yīng)為多少才能盈利？3×22×2454元 售價54，才盈利。如售價54，不如把資源投入到原

16、來的兩種產(chǎn)品中。（3）告知管理者目前工廠中各種資源的稀缺程度。Y1*=0 則X1S0， 第一種資源有剩余Y2*0 則X2S=0， 第二種資源無剩余對偶單純形法對偶單純形法是利用對偶理論求解原問題的一種方法，而不是求解對偶問題的方法一、 基本思路原始單純形法：從一個基可行解迭代到下一個基可行解，一直到找出最優(yōu)解(在迭代過程中，保持解的可行性不變，變化的只是檢驗數(shù)行)檢驗數(shù)行是對偶問題的解：不可行可行此時，原問題的解： 可行最優(yōu)也就是說，原問題的最優(yōu)性條件與對偶解的可行性條件是一致的。對偶單純形法求解思路：在迭代過程中，始終保持對偶解的可行性，而原問題的解由不可行向可行性轉(zhuǎn)化，一旦原問題的解也滿足

17、了可行性條件，根據(jù)對偶定理，兩個問題同時達到最優(yōu)。 二、計算步驟（通過例題說明）正則解定義：設(shè)X(0)是原問題的一個基本解，對應(yīng)的基是B。若它所對應(yīng)的檢驗數(shù)向量0成立，則稱X(0)是原問題的一個正則解。對應(yīng)的基矩陣B稱為正則基。例1 用對偶單純形法解下列線性規(guī)劃問題解：先化為標準型約束條件兩邊同乘(-1) 列單純形表Cj1524500CBXBbx1x2x3x4x500x4x52105-6-2-1-11001-15-24-500-45-240x2x51/3-1/30-5101/6-2/3-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/

18、41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2) Y*=(7/2,3/2)例2 用對偶單純形法解下列線性規(guī)劃問題解：改寫為標準形式列單純形表如下：Cj4121800CBXBbx1x2x3x4x500x4x535100-2-3-21001-4-12-1800-690-12x4x2-35/2-1001-31100-1/2-40-60-64212-18-12x3 x213/21/3-1/30110-1/31/30-1/2-200-2-6X*=(0,3/2,1) Y*=(2,6)對偶單純形法并不萬能，只有在約束條件全都為0時，才不必引進人工變量，使計算簡化。但在初始單純

19、形表中，使對偶問題是基可行解這點對多數(shù)LP問題是很難實現(xiàn)的。因此，對偶單純形法一般不單獨使用，主要用于靈敏度分析和整數(shù)規(guī)劃中。對偶單純形法計算步驟第1步：給定一個初始正則解，其對應(yīng)的基為B第2步：計算，若 ，則停止計算，當前正則解為最優(yōu)解，否則轉(zhuǎn)下一步。第3步：確定離基變量，令則xr為離基變量，第r行為主行第4步：確定進基變量則xk為進基變量，Pk是主列。此時如果所有，則原問題無可行解。因為，當時，無論xj改為怎樣的正數(shù)，都無法使xBr的值轉(zhuǎn)為正數(shù)，故無可行解。第5步：迭代。用xk替代xr。靈敏度分析靈敏度分析一詞的含義是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。在前面所講的線性規(guī)

20、劃問題中，都假定了各系數(shù)cj,aij,bi等始終保持不變，是已知常數(shù)。而實際當中，這些系數(shù)通常是一些估計或預(yù)測數(shù)字。如果外界條件發(fā)生了變化，這些系數(shù)也會發(fā)生相應(yīng)變化，這樣以來，就會引出一些問題：這些系數(shù)中，如果有一些發(fā)生變化，問題的最優(yōu)解會發(fā)生怎樣的變化？如果發(fā)生變化，又將使用何種簡便方法求出新的最優(yōu)解？一、 靈敏度分析通常有兩類問題：一是當C、A、b中某一部分數(shù)據(jù)發(fā)生變化時，討論最優(yōu)解與最優(yōu)值怎么變？二是研究C、A、b中數(shù)據(jù)在多大范圍內(nèi)波動時，使原有最優(yōu)解仍為最優(yōu)解、同時討論此時最優(yōu)解如何變動？二、參數(shù)變化對最優(yōu)解的影響設(shè)問題相應(yīng)的最優(yōu)單純形表為CjC1C2CnCBXBbx1x2xnCB1C

21、B2CBmXB1XB2XBmB-1bB-1A =B-1(P1,P2,Pn)-Z-CB B-1bC-CB B-1A1當C發(fā)生變化時不變項：(1)可行域不變。(2)原問題的最優(yōu)解還是新問題的基本可行解。要修改：(1) 目標函數(shù)系數(shù)行Cj；(2) 檢驗數(shù)行j；(3) 目標函數(shù)值；然后根據(jù)檢驗數(shù)是否滿足j0 的條件，決定是否迭代。若cj是非基變量的系數(shù)，則只有其對應(yīng)的j發(fā)生改變。若cj是基變量的系數(shù)，則CB將發(fā)生改變，那么所有的j發(fā)生改變。例1 已知線性規(guī)劃的標準形式為其最優(yōu)單純形表如下Cj12100CBXBbx1x2x3x4x520x2x56101310111101-Z-12-30-1-20問：(1

22、)當C1由1變?yōu)?時，求新問題的最優(yōu)解(2)討論C2在什么范圍內(nèi)變化時，原有的最優(yōu)解仍是最優(yōu)解解：由表可知，C1是非基變量的價值系數(shù)，因此C1的改變只影響1可見最優(yōu)性準則已不滿足，繼續(xù)迭代Cj42100CBXBbx1x2x3x4x520x2x56101310111101610/3-Z-1220-1-2024x2x18/310/301102/31/32/31/3-1/31/3-Z-56/300-5/3-8/3-2/3(2)要使原最優(yōu)解仍為最優(yōu)解，只要在新的條件下滿足0成立，因為x2是基變量，所以所有的值都將發(fā)生變化C-CBB-1A即 則c21 c2+c21 c2-1所以當x2的系數(shù)c2-1時，原

23、最優(yōu)解仍能保持為最優(yōu)解。2右端列向量b發(fā)生改變 即b變成b=b+b，此時需修改表中第三列 即基變量的取值由XB=B-1b變?yōu)閄B=B-1(b+ b) 目標函數(shù)值由Z= CB B-1b變?yōu)閆= CB B-1(b +b) 此時若b0，則因為j沒有改變，最優(yōu)解仍是最優(yōu)解，否則，單純形表對應(yīng)的是新問題的一個正則解，此時需用對偶單純形法繼續(xù)迭代。 例2 已知線性規(guī)劃問題及其最優(yōu)單純形表 Cj114000CBXBbx1x2x3x4x5x6104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2若右端列向量，求新問題的最優(yōu)解。解：因為1小

24、于0，因此繼續(xù)迭代Cj114000CBXBbx1x2x3x4x5x6104x1x5x3152100-1/322/30011/301/3010-2/311/3-Z-90-40-10-2j/arj123004x6x5x33/27/23/2-3/23/21/21/23/21/2001-1/21/21/2010100-Z-6-3-30-200新問題的最優(yōu)解為X*=(0,0,3/2,0,7/2,3/2) Z*=63、約束條件的系數(shù)列向量pk發(fā)生改變(1)若相應(yīng)的xk為非基變量，此時最優(yōu)基不變，最優(yōu)解不變，只改變pk為pk ，檢驗數(shù)k變?yōu)閗= Ck- CB B-1 pk若k 0，則原問題的最優(yōu)解也是新問題

25、的最優(yōu)解，否則用單純形法繼續(xù)迭代。(2)若相應(yīng)的xk為基變量，則表中所有系數(shù)都要改變，因此還是用單純形法重新計算比較方便。例3 已知線性規(guī)劃問題及其最優(yōu)單純形表 最優(yōu)單純形表如下：Cj23100CBXBbx1x2x3x4x523x1x2121001124111610/3-Z-800-3-51若p3由原來的，最優(yōu)解將如何改變？解：計算 繼續(xù)迭代Cj23100CBXBbx1x2x3x4x523x1x21210011/157/3041111560/7-Z-8001/6-5121x1x33/760/710-2/7-30/70130/7-30/79/7-30/71560/7-Z-66/70-5/70-3

26、0/712/7X*=(3/7,0,60/7,0,0) Z*=66/74、增加一個新變量xn+1設(shè)增加一個新變量xn+1，其價值系數(shù)Cn+1，在約束條件中對應(yīng)的列向量為Pn+1。令xn+10，顯然原問題的最優(yōu)基是新問題的可行基，原有變量的檢驗數(shù)并沒有改變，所以，將xn+1看成非基變量，在原問題的最優(yōu)單純行表中增加一列Pn+1 B-1Pn+1 n+1= Cn+1+ CBB-1Pn+1如果n+10，則原問題的最優(yōu)解就是新問題的最優(yōu)解，否則繼續(xù)迭代。例4 (仍以例2為例) 已知線性規(guī)劃問題及其最優(yōu)單純形表 Cj114000CBXBbx1x2x3x4x5x6104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2現(xiàn)增加一個新變量x7，且c7=3，p7=(3,1,-3)，求新問題的最優(yōu)解。解：由表知： 繼續(xù)迭代Cj1140003CBXBbx1