運籌學第二章

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

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

3、 200 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ī)則P56.原問題（或對偶問題）對偶問題（或原問題）目標函數maxz目標函數minn個n個變量約束條件 00無約束約束條件變量m個m個 00無約束約束條件右端項目標函數變量的系數目標函數變量的系數約束條件右端項OR18例題2：寫出下列原問題的對偶問題0, 0, 03254321652. .432max43214321432143214321x

4、xxxxxxxxxxxxxxxxxxxtsz為自由變量，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：寫出以下模型的對偶問題為自由變量xxxxxxxxxxxxxxxxxxxxxtsz54321431432

5、1543254321, 0,2551025222332643. .87523maxOR111例4的解法 為自由變量為自由變量xxxxxxxxxxxxxxxxxxxxxxx54322114314321543254321, 0, 02551025222332643. t . s87523zmax0, 0,847235232332. .255102526min75364211321321762154327654321yyyyyyyyyyyyyyyyyyyyyyyyyyyyyts無約束，OR1122.1.3對偶問題的基本性質p56w 1.對稱性：對偶問題的對偶問題是原問題。w 2.弱對偶性：若 是最大

6、化原問題的可行解， 是對偶問題的可行解，則存在 。w 3.無界性：若原問題為無界解，則對偶問題無可行解。（注：該性質的逆不存在。當原問題無可行解時，其對偶問題可能為無界解，也可能無可行解。）w 4.最優(yōu)解定理：若兩互為對偶的問題均有可行解，且可行解對應的目標函數值相等，則該可行解分別為他們的最優(yōu)解。XYbYXCOR113性質3的應用P59w 已知LP問題：試用對偶理論證明上述LP問題無最優(yōu)解。0,122. .max32132132121xxxxxxxxxxxtszOR114w 5.對偶定理：若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標函數值相等。w 6 .互補松弛性：在LP的最優(yōu)解中，若對應

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

8、xz=CX,AX+Xs=b; X, Xs0,其對偶問題是minw=Yb,YA-Ys=C, Y, Ys 0,則原問題單純形表的檢驗數行對應其對偶問題的一個基解CBB-1 （符號相反），（或者表示為）：若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1。其對應關系如下：OR117非基變量基變量XBXNXS0XSbBNIjCBCNj0CBCN初始單純形表XNXBXSI=B-1BB-1NB-1CBXBB-1bCBCN00CN-CBB-1N_-CBB-1互為對偶問題在單純形表間關系：1、原問題的基解對應于對偶問題的檢驗數。2、原問題的松弛變量對應對偶問題的決策變量。3、原問題的基變量對應對偶問題的非

9、基變量。最終單純形表OR118w 某廠生產兩種產品，需要三種資源，已知各產品的利潤、各資源的限量和各產品的資源消耗系數如下表：問題：如何安排生產計劃，使得獲利最多？回顧例題1： 現在A、B兩產品銷路不暢，可以將所有資源出租或外賣，現在要談判，我們的（資源的）價格底線是多少？產品A產品B資源限制勞動力設備原材料 9 4 3 4 5 10 360 200 300單位利潤 70 120OR119 Cj70 120 0 0 0CBXBbX1 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

10、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 -12070120X3X1X2842024 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)解的經濟解釋影子價格P60Z*= CBB-1b =Y* b= b1y1*+ b2y2* + bm ym* (*) Z= Z(b) b為資源為資源求偏導：求偏導： Z* b=CBB-1=

11、 Y*=(y1* ,y2*, ym* ) 對偶解對偶解yi* 的經濟意義的經濟意義：其它條件不變的情：其它條件不變的情況下，第況下，第i i種資源改變一個單位所引起的目標種資源改變一個單位所引起的目標函數最優(yōu)值的變化。函數最優(yōu)值的變化。OR121影子價格的應用情況情況：某資源對偶解：某資源對偶解00，該資源有利可圖，該資源有利可圖，可增加此種資源量；某資源對偶解為可增加此種資源量；某資源對偶解為0 0，則不增加此種資源量。則不增加此種資源量。情況情況：直接用影子價格與市場價格相比較，：直接用影子價格與市場價格相比較，進行決策，決定是否買入該資源。進行決策，決定是否買入該資源。即：即：影子價格所

12、含有的信息：影子價格所含有的信息：1 1、資源緊缺、資源緊缺狀況；狀況；2 2、確定資源轉讓基價；、確定資源轉讓基價；3 3、取得緊、取得緊缺資源的代價。缺資源的代價。OR122對偶單純形法w 設有問題設有問題maxZ=CX ，w AX b ，w X 0 w 又設又設B是其一個基，當非基變量都為是其一個基，當非基變量都為0時，時，可以得到可以得到XB=B-1b。若在。若在B-1b中至少有一中至少有一個負分量，設第個負分量，設第i個為負分量，并且在單個為負分量，并且在單純形表的檢驗數行中的檢驗數都為非正，純形表的檢驗數行中的檢驗數都為非正，這種情況就可以用對偶單純形法來進行求這種情況就可以用對偶

13、單純形法來進行求解。解。OR123對偶單純形法的計算步驟P61-62w （1 1）根據）根據LPLP問題，列出初始單純形表。檢查問題，列出初始單純形表。檢查b b列的數字，列的數字，若都為非負，檢驗數都為非正，則已得到最優(yōu)解，停止若都為非負，檢驗數都為非正，則已得到最優(yōu)解，停止計算。若檢查計算。若檢查b b列的數字時，至少還有一個負分量，檢列的數字時，至少還有一個負分量，檢驗數保持非正，則進行以下計算。驗數保持非正，則進行以下計算。w （2 2）確定換出變量：將）確定換出變量：將B B-1-1b b中最小的負分量所對應的變中最小的負分量所對應的變量確定為換出變量。量確定為換出變量。w （3 3

14、）確定換入變量：檢查換出變量所在行（第）確定換入變量：檢查換出變量所在行（第L L行）的行）的各系數各系數a aLjLj。若所有的。若所有的a aLj Lj 00，則無可行解，則無可行解 ，停止計算。，停止計算。若存在若存在a aLj Lj 00，則計，則計算算 ，將其最小值所對應的變量作為換入變量。將其最小值所對應的變量作為換入變量。w （4 4）進行迭代計算。）進行迭代計算。w 重復重復1 14 4步，直至得到最優(yōu)解為止。步，直至得到最優(yōu)解為止。0minaazcljljjjjOR124對偶單純形法舉例w 利用對偶單純形法求解以下線性規(guī)劃問題：利用對偶單純形法求解以下線性規(guī)劃問題：0,124

15、2332. .3max321212132121xxxxxxxxxxxxtszOR125cjCBXBbx1x2x3x4x5-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/21000010-10cj-zj0-5/2-1/200-3/2此時所有的此時所有的B-1b均均0 ，且所有的且所有的cj-zj均均0，此此時

16、已得到最時已得到最優(yōu)解為：優(yōu)解為：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2)5 , 4 , 3 , 2 , 1(, 01242332. .003max5214213215421jtszxxxxxxxxxxxxxxjOR126總結：對偶單純形法與單純形法的比較單純形法單純形法對偶單純形法對偶單純形法保持保持B-1b0所有的所有的cj-zj0最優(yōu)解時最優(yōu)解時要求要求所有的所有的cj-zj0B-1b0OR127對偶單純形法的應用時機w 要求最大化時，在單純形表中：如果檢驗要求最大化時，在單純形表中：如果檢驗數均非正，而數均非正，而 列中有負值，此時用對列中有負值，此時用對偶單純形法求

17、解。若所有偶單純形法求解。若所有 ，中有正值，則用單純形法求解；若中有正值，則用單純形法求解；若 列列中有負值，且中有負值，且 中有正值，則必須引中有正值，則必須引入人工變量，建立新的單純形表，重新計入人工變量，建立新的單純形表，重新計算。算。B-1bB-1b0cj-zjB-1bcj-zjOR128對偶單純形法的優(yōu)點P64w （1）初始解可以是非可行解，當檢驗數都為負）初始解可以是非可行解，當檢驗數都為負數時，就可以進行基的變換，這時不需要加入數時，就可以進行基的變換，這時不需要加入人工變量，因此可以直接計算。人工變量，因此可以直接計算。w （2）當變量多于約束條件，對這樣的）當變量多于約束條

18、件，對這樣的LP問題，問題，用對偶單純形法計算可以減少計算工作量。因用對偶單純形法計算可以減少計算工作量。因此，對變量較少，而約束條件很多的此，對變量較少，而約束條件很多的LP問題，問題，可以先將它變換成對偶問題，然后用對偶單純可以先將它變換成對偶問題，然后用對偶單純形法求解。形法求解。w （3）在靈敏度分析中，有時需要用對偶單純形）在靈敏度分析中，有時需要用對偶單純形法，這樣可使問題的處理簡化。法，這樣可使問題的處理簡化。OR1292.2靈敏度分析（考研時?？嫉闹R點）靈敏度分析通常有兩類問題：靈敏度分析通常有兩類問題：是當C,A,b中某一部分數據發(fā)生給定的變化時，討論最優(yōu)解與最優(yōu)值怎么變化

19、；是研究C,A,b中數據在多大范圍內波動時，使原有最優(yōu)基仍為最優(yōu)基，同時討論此時最優(yōu)解如何變動？靈敏度分析的兩把尺子： j =Cj-CBB-1pj 0； XB= B-1b 0OR1302.2.1右端項右端項bi變化的靈敏度分析變化的靈敏度分析bi變化到什么程度可以保持最優(yōu)基不變？變化到什么程度可以保持最優(yōu)基不變？用尺度用尺度xB= B-1b 0。問題：為什么不用尺度為什么不用尺度j =Cj-CBB-1pj 0？OR131例題：求以下模型中第二個約束條件右端項b2的變化范圍。maxZ=70X1+120X29X1+4X23604X1+5X2 200 3X1+10X2 300 X10 X20OR13

20、2 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.2OR133w

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

22、3x4x5i010001100-3.120.4-0.121.16-0.20.1684-3.12 b220+0.4 b224-0,12 b2x3x1x2070120zjj4280+13.6 b270120013.65.2000-13.6-5.2OR135w 上述解是最優(yōu)解，必須是可行解：上述解是最優(yōu)解，必須是可行解：w 即：w 解得：解得：50 b2 26.9。w 可知右端項系數可知右端項系數b2的變化范圍是的變化范圍是: （20050） （20026.9)012. 0244 . 02012. 38430020036016. 012. 002 . 04 . 0016. 112. 3122221b

23、bbbBb012. 02404 . 020012. 384222bbbOR136w 在此范圍內在此范圍內j 0， B-1b 0，最優(yōu)解仍有效，最優(yōu)解仍有效，即最優(yōu)解的基變量不變，最優(yōu)解為：即最優(yōu)解的基變量不變，最優(yōu)解為：w最優(yōu)值為：最優(yōu)值為：Z*=4280+13.6 b2 ) 0 , 0 ,12. 384,12. 024,4 . 020(222*bbbXTOR1372.2.2目標函數中價值系數目標函數中價值系數cj的靈敏度分析的靈敏度分析w 分分c cj j是非基變量的系數還是基變量的系數兩種情況來討是非基變量的系數還是基變量的系數兩種情況來討論。論。w 若若c cj j是非基變量是非基變量x

24、 xj j的系數，此時，當的系數，此時，當c cj j變化變化 c cj j后，后，要保證最終表中這個檢驗數仍小于或等于零即可。要保證最終表中這個檢驗數仍小于或等于零即可。若若c cj j是基變量是基變量x xj j的系數，則引起的變化較大。見例題。的系數，則引起的變化較大。見例題。OR138w 例題：在模型例例題：在模型例1中，求基變量中，求基變量x2的系數變化范圍。的系數變化范圍。w 解：本例的最優(yōu)單純形表如下：解：本例的最優(yōu)單純形表如下：070120cjCBXBbx3x1x2842024x1x2x3x4x5i70120000010001100-3.120.4-0.121.16-0.20.16j4280000-13.6 -5.2OR139w 基變量系數基變量系數c2由由120變?yōu)樽優(yōu)?20 c2后，可以得到迭后，可以得到迭代后的單純形表。代后的單純形表。cjCBXBbx3x1x2842024x1x2x3x4x5i