運籌學對偶模型.PPT

1、1趙明霞趙明霞山西大學經濟與管理學院山西大學經濟與管理學院管理運籌學管理運籌學 模型與方法模型與方法2第第3 3章對偶模型章對偶模型3 3.1.1線性規(guī)劃的對偶關系線性規(guī)劃的對偶關系3 3.2.2線性規(guī)劃的對偶性質線性規(guī)劃的對偶性質3.33.3對偶單純形法對偶單純形法33.13.1線性規(guī)劃的對偶關系線性規(guī)劃的對偶關系對偶問題對偶問題例例1-1. 某工廠要安排甲、乙兩種產品分別在車間某工廠要安排甲、乙兩種產品分別在車間A、B生產，生產，然后都在然后都在C車間裝配。生產數(shù)據(jù)如下表：車間裝配。生產數(shù)據(jù)如下表：問題：工廠應分別生產多少單位甲、乙產品才能使工廠獲利問題：工廠應分別生產多少單位甲、乙產品才

2、能使工廠獲利最多？最多？4解：解：設設安排甲、乙兩種產品產量分別為安排甲、乙兩種產品產量分別為x xj j 件件 max z=3x max z=3x1 1+ 2x+ 2x2 2 s.t. x s.t. x1 1 6 6 2x 2x2 28 8 2x2x1 1+3x+3x2 21818 x xj j0 0 （j=1,2j=1,2）22,)26(*zXT，5例例3-3-1 1. . 將例將例1-11-1中三種資源用于對外加工，如何給資源定價？中三種資源用于對外加工，如何給資源定價？解：解：設設三種資源分別可獲利潤為三種資源分別可獲利潤為yj j (100 (100元元/ /工時工時) ) m mi

3、nin w w = = 6y 6y1 1 + +8y8y2 2 + +18y18y3 3 s.t. s.t. y y1 1 + +2y2y3 3 33 2 2y y2 2+ +3y3y3 3 2 2 y yj j0 0 （j=1,2j=1,2,3,3）22,)3/203/5(*wYT，6對偶關系對偶關系規(guī)范對偶關系（對稱對偶）規(guī)范對偶關系（對稱對偶）標準形標準形LPLP對偶關系（非對稱對偶）對偶關系（非對稱對偶）一般對偶關系（混合對偶）一般對偶關系（混合對偶）7規(guī)范對偶關系（對稱對偶）規(guī)范對偶關系（對稱對偶）其中：其中： C= C=（c c1 1，c c2 2, , ,c ,cn n) )T

4、T b= b=（b b1 1，b b2 2, , ,b ,bm m) )T T X= X=（x x1 1，x x2 2, , ,x ,xn n) )T T Y= Y=（y y1 1，y y2 2, , ,y ,ym m) )T T z= 2 xz= 2 x1 1 + x + x2 2 5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0st .st .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz=

5、15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .X 0st.AX bmax z = CTXY 0st.ATY Cmin w = bTYP57表表3-2，38例例3-23-2標準形標準形LPLP對偶關系（非對稱對偶）對偶關系（非對稱對偶）X X 0 0st.st.AX AX = = b bmax z =max z = C CT TX XY Y 自由自由st.st.A AT TY CY Cmin w =min w = b bT TY Y w w= = 5y5y1 1 + + 6y6y2 2

6、2y2y1 1 +3y +3y2 2 5 5y y1 1 + 2 + 2y y2 2 1 13y3y1 1 + + y y2 2 2 2st .st .x x2 2 + + 3x3x3 3= =5 53x3x1 1 + 2 + 2x x2 2 + + x x3 36 6= =z= 5z= 5x x1 1 + + x x2 2 + + 2x2x3 3m maxaxx x1 1 , , x x2 2 , , x x3 30 0st .st .2x1 +P58表表3-49一般對偶關系（混合對偶）一般對偶關系（混合對偶）例例3-312341234123123124min2343252231. .322

7、0,0,0wxxxxxxxxxxxstxxxxxxx x1 1 0, x 0, x2 2 0, x 0, x3 3無約束無約束 st.st.a a1111x x1 1+a+a1212x x2 2+a+a1313x x3 3 b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2323x x3 3 = b = b2 2a a3131x x1 1+a+a3232x x2 2+a+a3333x x3 3 b b3 3max z = cmax z = c1 1x x1 1 + c + c2 2x x2 2 +c +c3 3x x3 3 min w = bmin w = b1 1y

8、 y1 1 + b + b2 2y y2 2 + b + b3 3y y3 3a a1111y y1 1 + + a a2121y y2 2 + a+ a3131y y3 3 c c1 1a a1212y y1 1 + + a a2222y y2 2 + a + a3232y y3 3 c c2 2a a1313y y1 1 + + a a2323y y2 2 + a+ a3333y y3 3 = c = c3 3st.st.y y1 10, y0, y2 2無約束無約束，y y3 3 00對偶規(guī)則對偶規(guī)則 變量、約束與系數(shù)變量、約束與系數(shù)&原問題原問題有有m個約束條件，個約束條件，對偶問題對

9、偶問題有有m個變量個變量&原問題原問題的規(guī)范約束（的規(guī)范約束（max,或或min，）對應）對應對偶問題對偶問題的變量的變量0；&原原問題問題的非規(guī)范的非規(guī)范約束（約束（max,或或min，）對應）對應對偶問題對偶問題的的變量變量0；&原問題原問題的等式約束的等式約束（max,=或或min，=）對應對應對偶問題對偶問題的的變量無限制。變量無限制。&原問題原問題有有n個變量，個變量，對偶問題對偶問題有有n個約束條件個約束條件&原問題原問題的價值系數(shù)對應的價值系數(shù)對應對偶問題對偶問題的右端項的右端項&原問題原問題的右端項對應的右端項對應對偶問題對偶問題的價值系數(shù)的價值系數(shù)&原問題原問題的系數(shù)矩陣轉置

10、后為的系數(shù)矩陣轉置后為對偶問題對偶問題系數(shù)矩陣系數(shù)矩陣P59表表3-511123 3.2 .2線性規(guī)劃的對偶性質線性規(guī)劃的對偶性質11.對稱性對稱性：對偶問題的對偶問題是原問題。：對偶問題的對偶問題是原問題。12.弱對偶性弱對偶性：原問題的任一可行解的目標函數(shù)值，不優(yōu)于其：原問題的任一可行解的目標函數(shù)值，不優(yōu)于其對偶問題任一可行解的目標函數(shù)值對偶問題任一可行解的目標函數(shù)值13.最優(yōu)性最優(yōu)性： ,則則 分別為原問題與對偶問題的最優(yōu)分別為原問題與對偶問題的最優(yōu)解。解。bTTC XY,X YbTTzC XYw最優(yōu)解最優(yōu)解PD1314.強對偶性強對偶性：若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，：若一

11、個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且二者最優(yōu)目標值相等。且二者最優(yōu)目標值相等。 無界性無界性：若一個問題有無界解，則另一問題無可行解。：若一個問題有無界解，則另一問題無可行解。對偶定理對偶定理：要么同時有解，且最優(yōu)值相等；要么同時無解。：要么同時有解，且最優(yōu)值相等；要么同時無解。 不可能一個有解，一個無解。不可能一個有解，一個無解。無界解無可行解1415.互補性互補性：原問題與對偶問題的變量或基本解之間具有互補性。：原問題與對偶問題的變量或基本解之間具有互補性。 互補變量互補變量 互補基本解互補基本解：目標值相等：目標值相等,(1,2, ),(1,2, )Sjm jSin iXYxyjnY

12、Xyxim或或決策變量非決策變量基變量非基變量P1與與D1互相對偶互相對偶PS與與DS廣義對偶廣義對偶1516.兼容性兼容性：原問題：原問題PS單純形表的檢驗行，對應對偶問題單純形表的檢驗行，對應對偶問題DS的一的一個基本解；最優(yōu)單純形表的檢驗行，對應對偶問題的最優(yōu)解。個基本解；最優(yōu)單純形表的檢驗行，對應對偶問題的最優(yōu)解。檢驗行基本解互補基本解均可行必然均為最優(yōu)解。互補基本解均可行必然均為最優(yōu)解。16171817.基本松緊性基本松緊性：互補變量滿足：互補變量滿足 對于非退化的基本解對于非退化的基本解u若若X可行，則有可行，則有u若若Y可行，則有可行，則有18.最優(yōu)松緊性最優(yōu)松緊性：這些性質同樣

13、適用于非對稱形問題這些性質同樣適用于非對稱形問題0, (1,2, )0, (1,2,)jmjn iix yjnxyim00,(1,2, )00, (1,2,)jmjn iixyjnxyim00,(1,2, )00, (1,2,)mjjin iyxjnyxim*100,20=0(1,2, )300,400, (1,2,)jm jm jjn iiin ixyyxjnxyyxim（）（ ），（ ）（ ）19對偶變量的經濟屬性對偶變量的經濟屬性11nmjjiijizc xb ywiizyb*1=,TimYyyyp 是第是第i種資源的種資源的邊際價值邊際價值p 是第是第i種資源的種資源的影子價值影子價值

14、（shadow value） 單位產值（收入），單位產值（收入）， 影子價格影子價格； 單位利潤，單位利潤， 影子利潤影子利潤。p 的值相當于在資源得到最優(yōu)利用的生產條件下，的值相當于在資源得到最優(yōu)利用的生產條件下，bi每增加一個單位時目標函數(shù)每增加一個單位時目標函數(shù)z z的貢獻（增量）的貢獻（增量）。*iyiyjc*iyjc*iy*iy22,)26(*zXT，22,)3/203/5(*wYT，20對資源對資源i現(xiàn)用總量的經濟分析現(xiàn)用總量的經濟分析 代表影子價格代表影子價格 ，可增加資源，可增加資源i的用量，可買進資源，對總目標貢獻的用量，可買進資源，對總目標貢獻 ； ，可買進資源，對總目標貢

15、獻，可買進資源，對總目標貢獻 ； ，應減少資源，應減少資源i的用量，可賣出資源，對總目標貢獻的用量，可賣出資源，對總目標貢獻 。 代表影子利潤代表影子利潤資源資源i單位成本單位成本 ，則資源，則資源i對總價值的單位貢獻即對總價值的單位貢獻即 ，即，即 為資源為資源i的影子價格。的影子價格。對資源對資源i分配方案分配方案的經濟分析的經濟分析*iiyp*0iiyp*=iiyp*=0iiyp*iiyp*iy*iyiq*-0iip y *iiyq*iiyq21對偶問題的經濟意義對偶問題的經濟意義(3-12b)：資源：資源aji對總價值的貢獻，應當不少于將其用于項目對總價值的貢獻，應當不少于將其用于項目

16、j時時的貢獻的貢獻cj; ;(3-12c)：資源：資源i對總價值的貢獻必須非負，否則不用或出售。對總價值的貢獻必須非負，否則不用或出售。(3-12a)：資源隱性價值：資源隱性價值w，確定轉讓的成交價格最低限度，確定轉讓的成交價格最低限度yi。111): min(3 12 )(1,2, )(3 12 ). .0(1,2,)(3 12 )miiimjiijiiDwb yaa ycjnbstyimc（最優(yōu)松緊性的經濟意義最優(yōu)松緊性的經濟意義每經營一個單位項目每經營一個單位項目xj所消耗的各種資源的影子價值總和，必所消耗的各種資源的影子價值總和，必定等于該項目創(chuàng)造的單位價值定等于該項目創(chuàng)造的單位價值c

17、j。*11008 1jm jmmjiijijiimjjixya yca yyc（）*14*13413600522322*333xyyyyyy23*42*23535400223233*023xyyyyyy當資源當資源i的供量未被耗盡時，該資源的邊際價值必為的供量未被耗盡時，該資源的邊際價值必為0。*8 400n iixy（ ）*8 200m jjyx（ ）*8 300in iyx（ ）24最優(yōu)性檢驗的經濟意義最優(yōu)性檢驗的經濟意義 是決策變量，說明該資源的影是決策變量，說明該資源的影子利潤為負，需要改善。子利潤為負，需要改善。 是剩余變量是剩余變量 說明該資源的影子利潤小于項目說明該資源的影子利潤

18、小于項目j的單位利潤的單位利潤cj，需要改善。，需要改善。0,n iiiyy0,jmjmjyy11mjiimjjimjiijia yyca yc25互補基本解均可行必然均為最優(yōu)解。互補基本解均可行必然均為最優(yōu)解。對偶單純形法基本思路對偶單純形法基本思路1 1、標準化，、標準化，允許允許bi0;0;2 2、建立典式，、建立典式，若若 ，轉至，轉至3 3；3 3、最優(yōu)性檢驗、最優(yōu)性檢驗 ，否則轉至，否則轉至4 4；4 4、解的判斷、解的判斷 原問題無可行解，對偶問題無下界；原問題無可行解，對偶問題無下界；否則，否則， 轉至轉至5 5 ；5 5、換基；、換基；先確定出基變量先確定出基變量 后確定入基變量后確定入基變量 主元為負數(shù)主元為負數(shù) 3 3.3 .3對偶單純形法對偶單純形法00b 0,0,ssjbamin0iilb bbmax/0/jljljklka aa2627例例3-428前提條件前提條件進化進化換基換基主元主元原原SM先入先入后出后出 正正數(shù)數(shù)對偶對偶SM先出先出后入后入 負負數(shù)數(shù)0000bb0b 0min0iilb bbmax/0/jljljklka aamin0jjk min0ilikiklkbbaaa原本、對偶單純形法對比原本、對偶單純形法對比29交替單純形法交替單純形法無須顧及二者的