【正文】 B1b=Z 所以當(dāng)原問(wèn)題為最優(yōu)解時(shí)，對(duì)偶問(wèn)題為可行解且具有相 同的目標(biāo)函數(shù)值。 19 maxZ=+5x2 . 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0 minw=24y1+40y2 . 3y1+4y2≥ 2y1+5y2≥5 y1,y2≥0 y1 y2 x1 x2 maxZ=+5x2 . 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0 minw=24y1+40y2 . 3y1+4y2y3= 2y1+5Y2y4=5 y1,y2,y3,y4≥0 y1 y2 x1 x2 20 cj 5 0 0 θ CB XB b x1 x2 x3 x4 0 x3 24 3 2 1 0 12 0 x4 40 4 5 0 1 8 cjzj 5 0 0 解原問(wèn)題： 21 cj 5 0 0 θ CB XB b x1 x2 x3 x4 0 x3 24 3 2 1 0 12 0 x4 40 4 5 0 1 8 cjzj 5 0 0 0 x3 8 7/5 0 1 2/5 5 x2 8 4/5 1 0 1/5 cjzj 1/2 0 0 1 22 cj 5 0 0 θ CB XB b x1 x2 x3 x4 0 x3 24 3 2 1 0 12 0 x4 40 4 5 0 1 8 cjzj 5 0 0 0 x3 8 7/5 0 1 2/5 40/7 5 x2 8 4/5 1 0 1/5 10 cjzj 1/2 0 0 1 23 cj 5 0 0 θ CB XB b x1 x2 x3 x4 0 x3 24 3 2 1 0 12 0 x4 40 4 5 0 1 8 cjzj 5 0 0 0 x3 8 7/5 0 1 2/5 40/7 5 x2 8 4/5 1 0 1/5 10 cjzj 1/2 0 0 1 x1 40/7 1 0 5/7 2/7 5 x2 24/7 0 1 4/7 3/7 cjzj 0 0 5/14 6/7 Z= 40/7＋ 5 24/7=300/7 24 解對(duì)偶問(wèn)題： w=24 5/14＋ 40 6/7=300/7 cj 24 40 0 0 θ CB YB b y1 y2 y3 y4 24 y1 5/14 1 0 5/7 4/7 40 y2 6/7 0 1 2/7 3/7 cjzj 0 0 40/7 24/7 25 cj 5 0 0 θ CB XB b x1 x2 x3 x4 x1 40/7 1 0 5/7 2/7 5 x2 24/7 0 1 4/7 3/7 cjzj 0 0 5/14 6/7 cj 24 40 0 0 θ CB YB b y1 y2 y3 y4 24 y1 5/14 1 0 5/7 4/7 40 y2 6/7 0 1 2/7 3/7 cjzj 0 0 40/7 24/7 (x3,x4)=(0,0) (y3,y4)=(0,0) y1 y2 y4 y3 x1 x2 x4 x3 26 （ 1）對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶 max z=6x1+9x2 . x1+2x2≤2 2x1 3x2≤3 x1+2x2≤1 x1, x2≥0 minw=2y1+3y2y3 . y1+2y2+y3≥6 2y13y2+2y3≥9 y1, y2, y3≥0 對(duì)偶問(wèn)題的對(duì)偶就是原始問(wèn)題。兩個(gè)問(wèn)題中的任一個(gè)都可以作為原始問(wèn)題。另一個(gè)就是它的對(duì)偶問(wèn)題。 根據(jù)定義寫(xiě)出對(duì)偶問(wèn)題 根據(jù)定義寫(xiě)出對(duì)偶問(wèn)題 max u=6w1+9w2 . w1+2w2≤2 2w1 3w2≤3 w1+2w2≤1 w1, w2≥0 27 maxZ=x1+4x2+2x3 . 5x1x2+2x3≤8 x1+3x23x3≤5 x1,x2,x3≥0 minw=8y1+5y2 . 5y1+y2≥1 y1+3y2≥4 2y13y2 ≥2 y1,y2≥0 28 對(duì)偶問(wèn)題的基本性質(zhì) 原始問(wèn)題 max z=CX . AX≤b X ≥0 對(duì)偶問(wèn)題 min w=Y’b . A’Y≥C’ Y ≥0 （ 2）弱對(duì)偶性 若 X為原問(wèn)題的可行解， Y為對(duì)偶問(wèn)題的可行解，則恒有 CX≤Y’b 29 推論： ? 原問(wèn)題任一可行解的目標(biāo)函數(shù)是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界，反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)是其原問(wèn)題目標(biāo)函數(shù)的上界。 （ 3）無(wú)界性 如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)無(wú)界，則原問(wèn)題無(wú)可行解。（對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題無(wú)界解或無(wú)可行解。 推論： ? 若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解時(shí)，原問(wèn)題目標(biāo)函數(shù)無(wú)界 ? 若對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解時(shí)，對(duì)偶問(wèn)題目標(biāo)函數(shù)無(wú)界。 30 maxZ=x1+x2 . x1+x2+x3 ≤2 2x1+x2+x3 ≤ 1 x1,x2,x3,≥0 minw=2y1+y2 . y12y2 ≥ 1 y1+y2 ≥1 y1y2 ≥0 y1,y2≥0 試用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解 例。已知線性規(guī)劃問(wèn)題 證：首先該問(wèn)題存在可行解。 可知對(duì)偶問(wèn)題無(wú)可行解，因原問(wèn)題有可行解，故無(wú)最優(yōu)解。 31 （ 4）最優(yōu)性 ? 若 X為原問(wèn)題的可行解， Y為對(duì)偶問(wèn)題的可行解，且 CX＝Y(jié)’b則 X， Y分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。 （ 5）強(qiáng)對(duì)偶性 ? 若原問(wèn)題和對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。 32 （ 6）互補(bǔ)松弛定理 ?在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶 變量值為 0，則該約束條件取嚴(yán)格等式，既松弛變量或剩余變 量為 0；反之如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值不為 0，則 該約束條件取嚴(yán)格不等式，既松弛變量或剩余變量不為 0. 若 yi’ ＞ 0,則 ∑aijxj=bi，即 xsi=0 若 yi’ ＝ 0,則 ∑aijxj＜ bi，即 xsi＞ 0 即 xsiy i=0 同理 若 xj’ ＞ 0,則 ∑aijyi=cj，即 ysj=0 若 xj’ ＝ 0,則 ∑aijyi＜ cj，即 ysj＞ 0 即 ysjx j=0 33 maxZ=+5x2 . 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0 y1 y2 minw=24y1+40y2 . 3y1+4y2y3= 2y1+5x2y4=5 y1,y2,y3,y4≥0 x1 x2 X3=0, 3x1+2x2=24,y1=14/5 X4=0,4x1+5x2=40,y2=6/7 y3=0, 3y1+4y2=5,x1=40/7 y4=0, 2y1+5y2=5,x2=24/7 34 利用互補(bǔ)松弛關(guān)系求解線性規(guī)劃 min z=6x1+8x2+3x3 . x1+ x2 ≥1 x1+2x2+x3 ≥1 x1, x2, x3 ≥0 max w=y1y2 . y1+ y2 ≤6 y1+2y2 ≤8 y2 ≤3 y1,y2≥0 原始問(wèn)題 對(duì)偶問(wèn)題 0 1 2 3 4 5 6 7 8 6 5 4 3 2 1 w1 w2 y=1 y=1 y=3 y=6 最優(yōu)解為 (y1, y2)=(6, 0) max y=6 先用圖解法求解對(duì)偶問(wèn)題。 35 min z=6x1+8x2+3x3 . x1+ x2 ≥1 x1+2x2+x3 ≥1 x1, x2, x3 ≥0 max w=y1y2 . y1+ y2 ≤6 y1+2y2 ≤8 y2 ≤3 y1, y2≥0 max w=y1y2 . y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1, y2, y3, y4, y5≥0 (y1, y2) =(6,0) (y1,y2,y3,y4,y5) =(6, 0, 0, 2, 3) min z=6x1+8x2+3x3 . x1+ x2 x4 =1 x1+2x2+x3 x5 =1 x1, x2, x3 ,x4, x5≥0 (x1, x2, x3 | x4, x5) (y1, y2 | y3, y4, y5) x2=x3=x4=0 x1=1, x5=2 引進(jìn)剩余變量 求對(duì)偶 引進(jìn)松弛變量 圖解法求解 代入約束 求出松弛變量 互補(bǔ)松弛關(guān)系 代入約束 求解 (x1, x2, x3, x4, x5) =(1, 0, 0, 0, 2) 36 第 5節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 —— 資源的影子價(jià)格 (Shadow Price) ?影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺 ?影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺 ?如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于 0 yi’=△ w/△ bi=最大利潤(rùn)的增量 /第 i種資源的增量 =第 i種資源的邊際利潤(rùn) w=b1y1+b2y2+… +biyi+… +bmym w+△ w=b1y1+b2y2+… +(bi+△ bi)yi+… +bmym △ w=△ biyi 37 0 1 2 3 4 5 6 7 8 6 5 4 3 2 1 y1 y2 Z*= X=(7/2,3/2) Z*= X=(15/4,5/4) Z=9 X=(3,3) maxZ=2x1+x2 . 2x2≤15 6x1+2x2≤24 x1+x2≤5 x1,x2≥0 25 6 思考 : 如果第一種資源增加 1，也就是把 15變?yōu)?16,目標(biāo)函數(shù)值將怎么變化 ? 為什么 ? 38 ? 資源的影子價(jià)格是一種機(jī)會(huì)成本 ? 根據(jù)互補(bǔ)松弛定理 若 yi’ ＞ 0,則 ∑aijxj=bi， 若 yi’ ＝ 0,則 ∑aijxj＜ bi， ?某種資源 bi未得到充分利用時(shí)，該種資源的影子價(jià)格 為 0； ?當(dāng)資源的影子價(jià)格不為 0，表示該種資源在生產(chǎn)中已 消耗完畢。 ?σ j=cjzj=cjCBB1Pj cj表示第 i種產(chǎn)品的產(chǎn)值， ∑aijyi表示生產(chǎn)該種產(chǎn)品所消 耗各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。 39 Maxz=4x1+10x2 . 3x1+6x2≤5 x1+3x2≤2 2x1+5x2≤4 x1,x2≥0 已知原問(wèn)題為： y1 y2 y3 則對(duì)偶問(wèn)題為： Minw=5y1+2y2+4y3 . 3y1+ y2+2y3≥4 6y1+3y2+5y3≥10 y1,y2,y3≥0 Maxz=4x1+10x2 . 3x1+6x2+x3=5 x1+3x2 +x4=2 2x1+5x2 +x5=4 xj≥0(j=1,2,…,5) Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4