【正文】 y1+3y2≤4 y1,y2≥0 Maxz=3y1+2y2 . y1+2y2+y3＝ 2 2y1 y2+y4＝ 3 y1+3y2+y5＝ 4 yi≥0 cj 2 3 4 0 0 3 x2 2/5 1 0 1/5 2/5 1/5 2 x1 11/5 0 1 7/5 1/5 2/5 cjzj 0 0 3/5 8/5 1/5 y3 y4 y5 y1 y2 62 對偶單純形法的特點： ? 當(dāng)約束條件為 “ ≥” 時，不需要引入人工變量，從而使計算更為簡便。 47 步驟： 一般設(shè)松弛變量為初時基可行解 若所有的基變量值均 ≥0，則此解為線性規(guī)劃問題的最優(yōu)解，若存在基變量的值 ≤0，則問題還沒有達(dá)到最優(yōu)解，需要進(jìn)行改進(jìn)。 46 第 6節(jié) 對偶單純形法 對于對偶單純形法剛好和單純形法的思路相反，就是在始終保持對偶問題可行的條件下，不斷改進(jìn)原問題可行性的過程。 39 Maxz=4x1+10x2 . 3x1+6x2≤5 x1+3x2≤2 2x1+5x2≤4 x1,x2≥0 已知原問題為： y1 y2 y3 則對偶問題為： 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 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 40 cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 5 3 6 1 0 0 0 x4 2 1 3 0 1 0 0 x5 4 2 5 0 0 1 cjzj 4 10 0 0 0 初始單純形表為： 此時對偶問題的解為 Y＝（ 0， 0， 0，－ 4，－ 10）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 41 cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 5 3 6 1 0 0 5/6 0 x4 2 1 3 0 1 0 2/3 0 x5 4 2 5 0 0 1 4/5 cjzj 4 10 0 0 0 初始單純形表為： 此時對偶問題的解為 Y＝（ 0， 0， 0，－ 4，－ 10）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 42 對原問題進(jìn)行迭代得： cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 1 1 0 1 2 0 10 x2 2/3 1/3 1 0 1/3 0 0 x5 2/3 1/3 0 0 5/3 1 cjzj 2/3 0 0 10/3 0 此時對偶問題的解為 Y＝（ 0， 10/3， 0， 2/3， 0）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 43 對原問題進(jìn)行迭代得： cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 1 1 0 1 2 0 1 10 x2 2/3 1/3 1 0 1/3 0 2 0 x5 2/3 1/3 0 0 5/3 1 2 cjzj 2/3 0 0 10/3 0 此時對偶問題的解為 Y ＝（ 0， 10/3， 0， 2/3， 0 ）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 44 對原問題進(jìn)行迭代得： cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 4 x1 1 1 0 1 2 0 10 x2 1/3 0 1 1/3 1 0 0 x5 1/3 0 0 1/3 1 1 cjzj 0 0 2/3 2 0 此時對偶問題的解為 Y＝（ 2/3， 2， 0， 0， 0）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 是對偶問題的可行解 45 單純形法求解的過程，從對偶的觀點來看，是在始終保持原始可行解的條件下，不斷改進(jì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)剩余變量 求對偶 引進(jìn)松弛變量 圖解法求解 代入約束 求出松弛變量 互補(bǔ)松弛關(guān)系 代入約束 求解 (x1, x2, x3, x4, x5) =(1, 0, 0, 0, 2) 36 第 5節(jié) 對偶問題的經(jīng)濟(jì)解釋 —— 資源的影子價格 (Shadow Price) ?影子價格越大，說明這種資源越是相對緊缺 ?影子價格越小，說明這種資源相對不緊缺 ?如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于 0 yi’=△ w/△ bi=最大利潤的增量 /第 i種資源的增量 =第 i種資源的邊際利潤 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 ? 資源的影子價格是一種機(jī)會成本 ? 根據(jù)互補(bǔ)松弛定理 若 yi’ ＞ 0,則 ∑aijxj=bi， 若 yi’ ＝ 0,則 ∑aijxj＜ bi， ?某種資源 bi未得到充分利用時，該種資源的影子價格 為 0； ?當(dāng)資源的影子價格不為 0，表示該種資源在生產(chǎn)中已 消耗完畢。y i=0 同理 若 xj’ ＞ 0,則 ∑aijyi=cj，即 ysj=0 若 xj’ ＝ 0,則 ∑aijyi＜ cj，即 ysj＞ 0 即 ysj （ 5）強(qiáng)對偶性 ? 若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。 可知對偶問題無可行解，因原問題有可行解，故無最優(yōu)解。 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 試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解 例。（對偶問題無可行解時，其原問題無界解或無可行解。 根據(jù)定義寫出對偶問題 根據(jù)定義寫出對偶問題 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 對偶問題的基本性質(zhì) 原始問題 max z=CX . AX≤b X ≥0 對偶問題 min w=Y’b . A’Y≥C’ Y ≥0 （ 2）弱對偶性 若 X為原問題的可行解， Y為對偶問題的可行解，則恒有 CX≤Y’b 29 推論： ? 原問題任一可行解的目標(biāo)函數(shù)是其對偶問題目標(biāo)函數(shù)值的下界，反之對偶問題任一可行解的目標(biāo)函數(shù)是其原問題目標(biāo)函數(shù)的上界。兩個問題中的任一個都可以作為原始問題。 18 當(dāng) B為最優(yōu)基時， XB為最優(yōu)解時，則有： CNCBB1N≤0 CBB1≤0 ∵ CBCBI=0 代入得： CN－ CBB1N+CBCBI≤0 C－ CBB1(B+N)≤0 整理得： C－ CBB1 A≤0 CBB1≤0 令 CBB1為單純形乘子， Y‘＝ CBB1 則： C－ Y’ A≤0 Y’≤0 Y’ A≥C’ Y’ ≥0 W＝ Y’b=CBB1b=Z 所以當(dāng)原問題為最優(yōu)解時，對偶問題為可行解且具有相 同的目標(biāo)函數(shù)值。 ?原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。x4’x4”=x4,x4’ ≥0,x4” ≥0 minz=2x1’+3x25x3+(x4’x4”) ’+x23x3+(x4’x4”)≥5 2x1’ 2x3+(x4’x4”)≥4 x2+x3 +(x4’x4”) ≥6 x2x3(x4’x4”) ≥6 x1’,x2,x3 ,x4’,x4” ≥0 變?yōu)橐话阈问? y1 y2’ y3’ y3” maxw=5y14y2’+6(y3’y3”) +2y2’ ≤2 y1 +(y3’y3”) ≤3 3y12y2’ +(y3’y3”) ≤ 5 y1+y2’+(y3’y3”) ≤ 1 y1y2’(y3’y3”) ≤1 y1,y2’ ,y3’,y3”≥0 寫出對偶問題 9 ma