第二章、對(duì)偶問題與靈敏度分析

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

2、，我們的（資源的）價(jià)格底線是多少？產(chǎn)品A產(chǎn)品B資源限制勞動(dòng)力設(shè)備原材料 9 4 3 4 5 10 360 200 300單位利潤(rùn) 70 120OR14對(duì)偶模型w 設(shè)每個(gè)工時(shí)收費(fèi)Y1元，每設(shè)備臺(tái)時(shí)費(fèi)用Y2元，每單位原材料收費(fèi)Y3元。 出租收入不低于生產(chǎn)收入： 9y1+4y2+3y3 70 4y1+5y2+10y3 120目標(biāo)：=360y1+200y2+300y3出租收入越多越好？還是至少不低于某數(shù)？OR15原問題與對(duì)偶問題之比較原問題： 對(duì)偶問題：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對(duì)偶規(guī)則原問題一般模型： 對(duì)偶問題一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0OR17對(duì)偶規(guī)則P57.原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)maxz目標(biāo)函數(shù)minn個(gè)n個(gè)變量約束條件 00無(wú)約束約束條件變量m個(gè)m個(gè) 00無(wú)約束約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)OR18例題2：寫出下列原問題的對(duì)偶問題0, 0, 03254321652. .432max43214321432143214321xxxxx

4、xxxxxxxxxxxxxxxtsz為自由變量，OR19例題3：寫出以下模型的對(duì)偶問題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無(wú)限制 y1 0y2 0y3 無(wú)約束 OR110例題4：寫出以下模型的對(duì)偶問題為自由變量xxxxxxxxxxxxxxxxxxxxxtsz543214314321543

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

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

7、件的對(duì)偶變量值不為零，則該約束條件取嚴(yán)格等式；反之，若約束條件取嚴(yán)格等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。（另一解釋：在互為對(duì)偶的兩個(gè)問題中，若原問題的某個(gè)變量取正數(shù)，則對(duì)偶問題相應(yīng)的約束條件必取“”式；若原問題的某個(gè)約束條件取不等式，則對(duì)偶問題相應(yīng)的變量為零。）OR115性質(zhì)6的應(yīng)用P60w 已知線性規(guī)劃問題：w 已知其對(duì)偶問題的最優(yōu)解為：w 試用對(duì)偶理論找出原問題的最優(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,其對(duì)偶問題是min=Yb,YA-Ys=C, Y, Ys 0,則原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解CBB-1 （符號(hào)相反），其對(duì)應(yīng)關(guān)系如下：OR117非基變量基變量XBXNXS0XSbBNIjCBCNj0CBCN初始單純形表XNXBXSI=B-1BB-1NB-1CBXBB-1bCBCN00CN-CBB-1N_-CBB-1互為對(duì)偶問題在單純形表間關(guān)系：1、原問題的基解對(duì)應(yīng)于對(duì)偶問題的檢驗(yàn)數(shù)。2、原問題的松弛變量對(duì)應(yīng)對(duì)偶問題的決策變量。3、原問題的基變量對(duì)應(yīng)對(duì)偶問題的非基變量。OR118w 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和

9、各產(chǎn)品的資源消耗系數(shù)如下表：?jiǎn)栴}：如何安排生產(chǎn)計(jì)劃，使得獲利最多？回顧例題1： 現(xiàn)在A、B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的（資源的）價(jià)格底線是多少？產(chǎn)品A產(chǎn)品B資源限制勞動(dòng)力設(shè)備原材料 9 4 3 4 5 10 360 200 300單位利潤(rùn) 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對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋影子價(jià)格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* ) 對(duì)偶解對(duì)偶解yi* 的經(jīng)濟(jì)意義的經(jīng)濟(jì)意義：其它條件不變的情：其它條件不

11、變的情況下，第況下，第i i種資源改變一個(gè)單位所引起的目標(biāo)種資源改變一個(gè)單位所引起的目標(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 ：對(duì)偶解：對(duì)偶解bi增加增加 bi , ,其它資源數(shù)量不變時(shí)其它資源數(shù)量不變時(shí), ,目標(biāo)函數(shù)目標(biāo)函數(shù)的增量的增量 Z=bi yiyi ：反映：反映bi 的邊際效益的邊際效益( (邊際成本邊際成本) )OR122影子價(jià)格的應(yīng)用情況情況 某資源對(duì)偶解某資源對(duì)偶解00，該資源有利可圖，該資源有利可圖，可增加此種資源量；某

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

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

14、4步，直至得到最優(yōu)解為止。0minaazcljljjjjOR125對(duì)偶單純形法舉例w 利用對(duì)偶單純形法求解以下線性規(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此時(shí)所有的B-1b均0 ，且所有的cj-zj均0，此時(shí)已得到最優(yōu)解為：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2)5 , 4 , 3 , 2 , 1(, 01242332. .003max5214213215421jtszxxxxxxxxxxxxxxjOR127總結(jié)：對(duì)偶單純形法與單純形法的比較單純形法對(duì)偶單純形法保持B-1b0所有的cj-zj0最優(yōu)解時(shí)要求所有的cj-zj0B-1b0OR128對(duì)偶單純形法的應(yīng)用時(shí)機(jī)w 要求最大化時(shí)，在單純形表中：如果檢驗(yàn)數(shù)均非正，而 列中有負(fù)值，此時(shí)用對(duì)偶單純形法求解。若所有 ，中有正值，

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

17、析通常有兩類問題：是當(dāng)C,A,b中某一部分?jǐn)?shù)據(jù)發(fā)生給定的變化時(shí)，討論最優(yōu)解與最優(yōu)值怎么變化；是研究C,A,b中數(shù)據(jù)在多大范圍內(nèi)波動(dòng)時(shí)，使原有最優(yōu)基仍為最優(yōu)基，同時(shí)討論此時(shí)最優(yōu)解如何變動(dòng)？靈敏度分析的兩把尺子： j =Cj-CBB-1pj 0； XB= B-1b 0OR1312.2.1右端項(xiàng)bi變化的靈敏度分析bi變化到什么程度可以保持最優(yōu)基不變？用尺度xB= B-1b 0。問題：為什么不用尺度j =Cj-CBB-1pj 0？OR132例題：求以下模型中第二個(gè)約束條件右端項(xiàng)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 可知右端項(xiàng)系數(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ù)中價(jià)值系數(shù)cj的靈敏度分析w 分cj是非基變量的系數(shù)還是基變量的系數(shù)兩種情況來(lái)討論。w 若cj是非基變量xj的系數(shù)，此時(shí)，當(dāng)cj變化 cj后，要保證最終表中這個(gè)檢驗(yàn)數(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