第二章、對偶問題與靈敏度分析

1、OR11第二章 對偶問題與靈敏度分析w 重點與難點：1、對偶問題的定義，對偶定理，對偶問題最優(yōu)解的經(jīng)濟含義，由最優(yōu)單純形表求對偶問題最優(yōu)解；2、對偶單純形法的特點，對偶單純形法求解；3、靈敏度分析：價值系數(shù)cj發(fā)生變化，右端常數(shù)bi發(fā)生變化，增加一個變量，增加一個約束，A中對應(yīng)非基變量的一列元素發(fā)生變化。OR12第二章 對偶問題與靈敏度分析w要求： 了解LP對偶問題的實際背景 了解對偶問題的建立規(guī)則與基本性質(zhì) 掌握對偶最優(yōu)解的計算及其經(jīng)濟解釋 掌握LP的靈敏度分析 OR132.1 對偶問題w2.1.1 對偶問題的提出 回顧例題1： 現(xiàn)在A、B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判

2、，我們的（資源的）價格底線是多少？產(chǎn)品A產(chǎn)品B資源限制勞動力設(shè)備原材料 9 4 3 4 5 10 360 200 300單位利潤 70 120OR14對偶模型w 設(shè)每個工時收費Y1元，每設(shè)備臺時費用Y2元，每單位原材料收費Y3元。 出租收入不低于生產(chǎn)收入： 9y1+4y2+3y3 70 4y1+5y2+10y3 120目標(biāo)：=360y1+200y2+300y3出租收入越多越好？還是至少不低于某數(shù)？OR15原問題與對偶問題之比較原問題： 對偶問題：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200

3、 4y1+5y2+10y3 120 3X1+10X2 300 y1 0, y2 0, y3 0X10 X20OR162.1.2對偶規(guī)則原問題一般模型： 對偶問題一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0OR17對偶規(guī)則P57.原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)maxz目標(biāo)函數(shù)minn個n個變量約束條件 00無約束約束條件變量m個m個 00無約束約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項OR18例題2：寫出下列原問題的對偶問題0, 0, 03254321652. .432max43214321432143214321xxxxx

4、xxxxxxxxxxxxxxxtsz為自由變量，OR19例題3：寫出以下模型的對偶問題w例題3 max =7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+ 2x3 -x4 4 -4y1+ 2y2 -6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0;x5無限制 y1 0y2 0y3 無約束 OR110例題4：寫出以下模型的對偶問題為自由變量xxxxxxxxxxxxxxxxxxxxxtsz543214314321543

5、254321, 0,2551025222332643. .87523maxOR111例4的解法2551025222332643. .87523max22114314321543254321xxxxxxxxxxxxxxxxxxxxtsz0, 0,847235232332. .255102526min75364211321321762154327654321yyyyyyyyyyyyyyyyyyyyyyyyyyyyyts無約束，OR1122.1.3對偶問題的基本性質(zhì)w 1.對稱性：對偶問題的對偶問題是原問題。w 2.弱對偶性：若 是最大化原問題的可行解， 是對偶問題的可行解，則存 。w 3.無界性：

6、若原問題為無界解，則對偶問題無可行解。（注：該性質(zhì)的逆不存在。當(dāng)原問題無可行解時，其對偶問題可能為無界解，也可能無可行解。）w 4.最優(yōu)解定理：若兩互為對偶的問題均有可行解，且可行解對應(yīng)的目標(biāo)函數(shù)值相等，則該可行解分別為他們的最優(yōu)解。XYbYXCOR113性質(zhì)3的應(yīng)用P60w 已知LP問題：試用對偶理論證明上述LP問題無最優(yōu)解。0,122. .max32132132121xxxxxxxxxxxtszOR114w 5.對偶定理：若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1。w 6 .互補松弛性：在LP的最優(yōu)解中，若對應(yīng)某一約束條

7、件的對偶變量值不為零，則該約束條件取嚴(yán)格等式；反之，若約束條件取嚴(yán)格等式，則其對應(yīng)的對偶變量一定為零。（另一解釋：在互為對偶的兩個問題中，若原問題的某個變量取正數(shù)，則對偶問題相應(yīng)的約束條件必取“”式；若原問題的某個約束條件取不等式，則對偶問題相應(yīng)的變量為零。）OR115性質(zhì)6的應(yīng)用P60w 已知線性規(guī)劃問題：w 已知其對偶問題的最優(yōu)解為：w 試用對偶理論找出原問題的最優(yōu)解。5 , 4 , 3 , 2 , 1, 0332432. .32532min543215432154321jtsxxxxxxxxxxxxxxxxj5, 5/3, 5/4*2*1zyyOR116w 7.設(shè)原問題是maxz=CX,

8、AX+Xs=b; X, Xs0,其對偶問題是min=Yb,YA-Ys=C, Y, Ys 0,則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解CBB-1 （符號相反），其對應(yīng)關(guān)系如下：OR117非基變量基變量XBXNXS0XSbBNIjCBCNj0CBCN初始單純形表XNXBXSI=B-1BB-1NB-1CBXBB-1bCBCN00CN-CBB-1N_-CBB-1互為對偶問題在單純形表間關(guān)系：1、原問題的基解對應(yīng)于對偶問題的檢驗數(shù)。2、原問題的松弛變量對應(yīng)對偶問題的決策變量。3、原問題的基變量對應(yīng)對偶問題的非基變量。OR118w 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和

9、各產(chǎn)品的資源消耗系數(shù)如下表：問題：如何安排生產(chǎn)計劃，使得獲利最多？回顧例題1： 現(xiàn)在A、B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的（資源的）價格底線是多少？產(chǎn)品A產(chǎn)品B資源限制勞動力設(shè)備原材料 9 4 3 4 5 10 360 200 300單位利潤 70 120OR119 CjC1 C2 CnCBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1

10、-0.5 0.3 1 0 0 0.130.7620100j3600 34 0 0 0 -12701200X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2y1y2y3OR1202.1.4對偶最優(yōu)解的經(jīng)濟解釋影子價格Z*= CBB-1b =Y* b= b1y1*+ b2y2* + bm ym* (*) Z= Z(b) b為資源為資源求偏導(dǎo)：求偏導(dǎo)： Z* b=CBB-1= Y*=(y1* ,y2*, ym* ) 對偶解對偶解yi* 的經(jīng)濟意義的經(jīng)濟意義：其它條件不變的情：其它條件不

11、變的情況下，第況下，第i i種資源改變一個單位所引起的目標(biāo)種資源改變一個單位所引起的目標(biāo)函數(shù)最優(yōu)解的變化。函數(shù)最優(yōu)解的變化。OR121另一種直觀的解釋W(xué)=yb=(y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymbi ： 第第 i 種資源的數(shù)量種資源的數(shù)量yi ：對偶解：對偶解bi增加增加 bi , ,其它資源數(shù)量不變時其它資源數(shù)量不變時, ,目標(biāo)函數(shù)目標(biāo)函數(shù)的增量的增量 Z=bi yiyi ：反映：反映bi 的邊際效益的邊際效益( (邊際成本邊際成本) )OR122影子價格的應(yīng)用情況情況 某資源對偶解某資源對偶解00，該資源有利可圖，該資源有利可圖，可增加此種資源量；某

12、資源對偶解為可增加此種資源量；某資源對偶解為0 0，則不增加此種資源量。則不增加此種資源量。情況情況 直接用影子價格與市場價格相比較，直接用影子價格與市場價格相比較，進行決策，決定是否買入該資源。進行決策，決定是否買入該資源。即：即：影子價格所含有的信息：影子價格所含有的信息：1 1、資源緊缺、資源緊缺狀況；狀況；2 2、確定資源轉(zhuǎn)讓基價；、確定資源轉(zhuǎn)讓基價；3 3、取得緊、取得緊缺資源的代價。缺資源的代價。OR123對偶單純形法w 設(shè)有問題maxZ=CX ，w AX b ，w X 0 w 又設(shè)B是其一個基，當(dāng)非基變量都為0時，可以得到XB=B-1b。若在B-1b中至少有一個負(fù)分量，設(shè)第i個為

13、負(fù)分量，并且在單純形表的檢驗數(shù)行中的檢驗數(shù)都為非正，這種情況就可以用對偶單純形法來進行求解。OR124對偶單純形法的計算步驟P62w （1）根據(jù)LP問題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗數(shù)都為非正，則已得到最優(yōu)解，停止計算。若檢查b列的數(shù)字時，至少還有一個負(fù)分量，檢驗數(shù)保持非正，則進行以下計算。w （2）確定換出變量：將B-1b中最小的負(fù)分量所對應(yīng)的變量確定為換出變量。w （3）確定換入變量：檢查換出變量所在行（第L行）的各系數(shù)aLj。若所有的aLj 0，則無可行解 ，停止計算。若存在aLj 0，則計算 ，將其最小值所對應(yīng)的變量作為換入變量。w （4）進行迭代計算。w 重復(fù)1

14、4步，直至得到最優(yōu)解為止。0minaazcljljjjjOR125對偶單純形法舉例w 利用對偶單純形法求解以下線性規(guī)劃問題：0,1242332. .3max321212132121xxxxxxxxxxxxtszOR126cjCBXBbx1x2x3x4x5-1-3000-2-3-1-1-2-2100010解法001-3-4-1x3x4x5000-1-3000cj-zjj1/33/2x3x1x50101/32/3-4/3100-2/3-1/3-1/3001cj-zj-1/34/31/30-7/30-1/30j1/20-10 x4x1x53/21/2010-1/2-3/2-3/2-1/2-1/210

15、00010-10cj-zj0-5/2-1/200-3/2此時所有的B-1b均0 ，且所有的cj-zj均0，此時已得到最優(yōu)解為：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2)5 , 4 , 3 , 2 , 1(, 01242332. .003max5214213215421jtszxxxxxxxxxxxxxxjOR127總結(jié)：對偶單純形法與單純形法的比較單純形法對偶單純形法保持B-1b0所有的cj-zj0最優(yōu)解時要求所有的cj-zj0B-1b0OR128對偶單純形法的應(yīng)用時機w 要求最大化時，在單純形表中：如果檢驗數(shù)均非正，而 列中有負(fù)值，此時用對偶單純形法求解。若所有 ，中有正值，

16、則用單純形法求解；若 列中有負(fù)值，且 中有正值，則必須引入人工變量，建立新的單純形表，重新計算。B-1bB-1b0cj-zjB-1bcj-zjOR129對偶單純形法的優(yōu)點P64w （1）初始解可以是非可行解，當(dāng)檢驗數(shù)都為負(fù)數(shù)時，就可以進行基的變換，這時不需要加入人工變量，因此可以直接計算。w （2）當(dāng)變量多于約束條件，對這樣的LP問題，用對偶單純形法計算可以減少計算工作量。因此，對變量較少，而約束條件很多的LP問題，可以先將它變換成對偶問題，然后用對偶單純形法求解。w （3）在靈敏度分析中，有時需要用對偶單純形法，這樣可使問題的處理簡化。OR1302.2靈敏度分析（考研時?？嫉闹R點）靈敏度分

17、析通常有兩類問題：是當(dāng)C,A,b中某一部分?jǐn)?shù)據(jù)發(fā)生給定的變化時，討論最優(yōu)解與最優(yōu)值怎么變化；是研究C,A,b中數(shù)據(jù)在多大范圍內(nèi)波動時，使原有最優(yōu)基仍為最優(yōu)基，同時討論此時最優(yōu)解如何變動？靈敏度分析的兩把尺子： j =Cj-CBB-1pj 0； XB= B-1b 0OR1312.2.1右端項bi變化的靈敏度分析bi變化到什么程度可以保持最優(yōu)基不變？用尺度xB= B-1b 0。問題：為什么不用尺度j =Cj-CBB-1pj 0？OR132例題：求以下模型中第二個約束條件右端項b2的變化范圍。maxZ=70X1+120X29X1+4X23604X1+5X2 200 3X1+10X2 300 X10

18、X20OR133 Cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5i 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100j3600 34 0 0 0 -12701200X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2

19、OR134w 解：從最優(yōu)單純形表得出：XB=(20,24,84)Tw 最優(yōu)基為：w 注意：應(yīng)為初始數(shù)據(jù)。為什么？w 還可以從單純形表中找出B-1.1030540491B16. 012. 002 . 04 . 0016. 112. 311BOR135w 設(shè)b2由200變?yōu)?00 b2，則b由w w 由此得到迭代后的單純形表： bbbbBb2222112. 0244 . 02012. 38430020036016. 012. 002 . 04 . 0016. 112. 31242084變?yōu)閏j70120000CBXBbx1x2x3x4x5i010001100-3.120.4-0.121.16-0.

20、20.1684-3.12 b220+0.4 b224-0,12 b2x3x1x2070120zjj4280+13.6 b270120013.65.2000-13.6-5.2OR136w 上述解是最優(yōu)解，必須是可行解：w 即：w 解得：50 b2 26.9。w 可知右端項系數(shù)b2的變化范圍是: （20050） （20026.9)012. 0244 . 02012. 38430020036016. 012. 002 . 04 . 0016. 112. 3122221bbbbBb012. 02404 . 020012. 384222bbbOR137w 在此范圍內(nèi)j 0， B-1b 0，最優(yōu)解仍有效，

21、即最優(yōu)解的基變量不變，最優(yōu)解為：w最優(yōu)值為：Z*=4280+13.6 b2 ) 0 , 0 ,12. 384,12. 024,4 . 020(222*bbbXTOR1382.2.2目標(biāo)函數(shù)中價值系數(shù)cj的靈敏度分析w 分cj是非基變量的系數(shù)還是基變量的系數(shù)兩種情況來討論。w 若cj是非基變量xj的系數(shù)，此時，當(dāng)cj變化 cj后，要保證最終表中這個檢驗數(shù)仍小于或等于零即可。若cj是基變量xj的系數(shù)，則引起的變化較大。見例題。OR139w 例題：在模型例1中，求基變量x2的系數(shù)變化范圍。w 解：本例的最優(yōu)單純形表如下：070120cjCBXBbx3x1x2842024x1x2x3x4x5i70120000010001100-3.120.4-0.121.16-0.20.16j4280000-13.6 -5.2OR140w 基變量系數(shù)c2由120變?yōu)?20 c2后，可以得到迭代后的單純形表。cjCBXBbx3x1x2842024x1x2x3x4x5i70120 c2000010001100-3.120.4-0.121.16-0.20.16j428024 c2000-13.6 +0.12 c2-5.2-0.16 c207012