運(yùn)籌學(xué)對(duì)偶模型.PPT

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

2、能使工廠獲利最多？最多？4解：解：設(shè)設(shè)安排甲、乙兩種產(chǎn)品產(chǎn)量分別為安排甲、乙兩種產(chǎn)品產(chǎn)量分別為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中三種資源用于對(duì)外加工，如何給資源定價(jià)？中三種資源用于對(duì)外加工，如何給資源定價(jià)？解：解：設(shè)設(shè)三種資源分別可獲利潤(rùn)為三種資源分別可獲利潤(rùn)為yj j (100 (100元元/ /工時(shí)工時(shí)) ) 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對(duì)偶關(guān)系對(duì)偶關(guān)系規(guī)范對(duì)偶關(guān)系（對(duì)稱對(duì)偶）規(guī)范對(duì)偶關(guān)系（對(duì)稱對(duì)偶）標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形LPLP對(duì)偶關(guān)系（非對(duì)稱對(duì)偶）對(duì)偶關(guān)系（非對(duì)稱對(duì)偶）一般對(duì)偶關(guān)系（混合對(duì)偶）一般對(duì)偶關(guān)系（混合對(duì)偶）7規(guī)范對(duì)偶關(guān)系（對(duì)稱對(duì)偶）規(guī)范對(duì)偶關(guān)系（對(duì)稱對(duì)偶）其中：其中： 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標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形LPLP對(duì)偶關(guān)系（非對(duì)稱對(duì)偶）對(duì)偶關(guān)系（非對(duì)稱對(duì)偶）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一般對(duì)偶關(guān)系（混合對(duì)偶）一般對(duì)偶關(guān)系（混合對(duì)偶）例例3-312341234123123124min2343252231. .322

7、0,0,0wxxxxxxxxxxxstxxxxxxx x1 1 0, x 0, x2 2 0, x 0, x3 3無(wú)約束無(wú)約束 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無(wú)約束無(wú)約束，y y3 3 00對(duì)偶規(guī)則對(duì)偶規(guī)則 變量、約束與系數(shù)變量、約束與系數(shù)&原問(wèn)題原問(wèn)題有有m個(gè)約束條件，個(gè)約束條件，對(duì)偶問(wèn)題對(duì)

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

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

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

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

13、適用于非對(duì)稱形問(wèn)題這些性質(zhì)同樣適用于非對(duì)稱形問(wèn)題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對(duì)偶變量的經(jīng)濟(jì)屬性對(duì)偶變量的經(jīng)濟(jì)屬性11nmjjiijizc xb ywiizyb*1=,TimYyyyp 是第是第i種資源的種資源的邊際價(jià)值邊際價(jià)值p 是第是第i種資源的種資源的影子價(jià)值影子價(jià)值

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

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

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

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

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