1、管理運(yùn)籌學(xué)8/28/20221對偶問題與靈敏度分析第三講8/28/20222對偶問題18/28/20223一般性的資源交易問題，見P70。一、問題的提出8/28/20224定義: 滿足下列條件的LP問題稱為具有對稱形式。二、對稱形式下對偶問題的一般形式目標(biāo)函數(shù)取最大時，約束條件為小于等于0，變量均為非負(fù)；目標(biāo)函數(shù)取最小時，約束條件為大于等于0，變量均為非負(fù)。8/28/20225一般地，將求最大目標(biāo)的LP問題稱為原問題；將求最小目標(biāo)的LP問題稱為對偶問題。對稱形式下LP問題的一般形式為:二、對稱形式下對偶問題的一般形式原問題:對偶問題:8/28/20226二、對稱形式下對偶問題的一般形式原問題:

2、對偶問題:8/28/20227非對稱形式的轉(zhuǎn)換見P72三、非對稱形式下對偶問題的一般形式8/28/20228三、非對稱形式下對偶問題的一般形式例 8/28/20229設(shè)經(jīng)過若干次迭代之后，基變量為XB，XB在初始單純型中對應(yīng)的矩陣為B。 四、LP問題的矩陣表達(dá)8/28/2022108/28/202211cj322000CB基bx1x2x3x4x5x60 x4(b)1111000 x515(a)120100 x6202(c)1001cj-zj3220000 x45/400(d)(l)-1/4-1/43x125/410(e)03/4(i)2x25/201(f)0(h)1/2cj-zj0(k)(g)

3、0-5/4(j)8/28/2022121.對稱性-對偶問題的對偶問題是原問題四、對偶問題的基本性質(zhì) 8/28/2022132. 弱對偶性四、對偶問題的基本性質(zhì) 若 為原問題的可行解， 為對偶問題的可行解，則恒有 原問題：對偶問題：8/28/2022143. 最優(yōu)性四、對偶問題的基本性質(zhì) 若 為原問題的可行解， 為對偶問題的可行解，如 ，此時兩個可行解同時達(dá)到最優(yōu)。 設(shè) 為原問題的最優(yōu)解，顯然也是可行解，則：又：8/28/2022154. 強(qiáng)對偶性-(對偶定理)四、對偶問題的基本性質(zhì) 若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。8/28/2022165. 無界性四、對偶問題的基

4、本性質(zhì) 若原問題(對偶問題)為無界解，則其對偶問題(原問題)為無可行解。故原問題必將小于某個值，與原問題無界矛盾。 若其對偶問題有可行解，則:8/28/202217例 已知LP問題:該問題的對偶問題的最優(yōu)解為:求原LP問題的最優(yōu)解？6. 互補(bǔ)性8/28/2022188/28/2022196. 互補(bǔ)性四、對偶問題的基本性質(zhì) 剩余變量對偶問題的變量原問題的變量松弛變量8/28/202220原問題與對偶問題的系數(shù)矩陣分別為:標(biāo)準(zhǔn)化之后，原問題變量X，與對偶問題變量Y，其維度均為m+n, X中的決策變量對應(yīng)Y中的松弛變量；Y中的決策變量對應(yīng)X中的松弛變量。變量X與變量Y成對出現(xiàn)。X中的決策變量與Y中的

5、松弛變量，稱為一對原變量及其補(bǔ)變量(反之亦然)，統(tǒng)稱互補(bǔ)變量。特別地，兩個對偶問題的基解相互對應(yīng)，成對出現(xiàn)，且對應(yīng)的目標(biāo)值相等。8/28/202221(0,0,6,8,18)是0(0,/,0,/,/)/(0,4,6,0,6)是8(0,6,6,-4,0)否12(6,0,0,8,6)是18(/,0,/,0,/)/(9,0,-3,8,0)否27(6,4,0,0,-6)否26(6,2,0,4,0)是22(3,4,3,0,0)是17(3,1,0,0,0)是26(5/3,0,2/3,0,0)是22(/,0,0,/,0)/(3,0,0,0,-2)否18(0,-1/4,3/2,0,0)否17(0,1,0,-3

6、,0)否8(0,/,0,0,/)否/(0,0,2/3,-5/3,0)否12(0,0,3/2,0,5/2)是27(0,0,0,-3,-2)否08/28/202222影子價(jià)格的理論本屬于經(jīng)濟(jì)學(xué)范疇，此處是用影子價(jià)格來解釋 對偶問題的解的經(jīng)濟(jì)學(xué)意義。影子價(jià)格是廠家對所用有的資源的稀缺程度的一種度量，是相對于具體廠家而言的。Z*=CBB-1b=Y*b =b1y*1+.+ bmy*m此y*i即資源的影子價(jià)格。設(shè)備出租的影子價(jià)格即最低出租價(jià)格，資源出售的影子價(jià)格，即在原價(jià)基礎(chǔ)上的最低上浮價(jià)格。當(dāng)影子價(jià)格y*i 為零時，說明資源i增加一個單位時，獲利并不增加，即該種資源對該廠的生產(chǎn)所需而言是有多的(或稀缺程

7、度為零)，出售時可原價(jià)出售；當(dāng)然，如果別人肯出更高的價(jià)格，那當(dāng)然更好！五、影子價(jià)格8/28/202223基本思路:根據(jù)性質(zhì)：對偶問題為可行解，原問題和對偶問題均為最優(yōu)解。六、對偶單純型法8/28/2022248/28/2022251. 確定出基變量選取minbi對應(yīng)的變量為出基變量2. 確定入基變量8/28/202226例 用對偶單純型求解Cj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101Cj-Zj-15-24-5008/28/202227Cj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101C

8、j-Zj-15-24-500-24y21/3011/6-1/600y5-1/3-50-2/3-1/31Cj-Zj-150-1-40-24y21/3-5/410-1/41/4-5y31/215/2011/2-3/2Cj-Zj-15/200-7/2-3/28/28/202228靈敏度分析28/28/2022291. Cj的變化CB03/220001/8-9/4問題1: 當(dāng)產(chǎn)品I，產(chǎn)品II的利潤分別變化至1.5, 2時，最優(yōu)生產(chǎn)計(jì)劃有何變化？cj3/220008/28/202230cj3/22000CB基bx1x2x3x4x50 x46004/51-63/2x1210-1/50-12x23011/5

9、00cj-zj00-1/100-3/28/28/202231問題2: 當(dāng)產(chǎn)品I的利潤不變，產(chǎn)品II的利潤在什么范圍變動，不影響最優(yōu)生產(chǎn)計(jì)劃？CB021+cj21+000/4-1/4-3/2-1/28/28/2022322. bi的變化問題1: 當(dāng)設(shè)備B的能力由24增加到32時(其他資源不變)，最優(yōu)生產(chǎn)計(jì)劃有何變化？b35/211/2-1/2-1/2-1/48/28/202233cj21000CB基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2cj-zj000-1/4-1/20 x315051002x1511001

10、0 x420-401-6cj-zj000-1/4-1/28/28/2022342. bi的變化問題2: 當(dāng)設(shè)備A, B的能力不變，調(diào)試能力在什么范圍變化，最優(yōu)生產(chǎn)計(jì)劃不變？cj21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-1/4-1/28/28/2022358/28/2022363. xj的變化增加一個變量，相當(dāng)于增加一種產(chǎn)品。問題1: 公司決定增加一種新產(chǎn)品，所需耗費(fèi)資源分別為3, 4, 2，單位盈利為3，問最優(yōu)生產(chǎn)計(jì)劃有何變化？-70218/28/202237cj210003CB

11、基bx1x2x3x4x5x60 x33/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj000-1/4-1/218/28/2022384. aij的變化問題1: 當(dāng)產(chǎn)品II所需資源變化為8, 4, 1，該產(chǎn)品的單位利潤為3，求最優(yōu)生產(chǎn)計(jì)劃？可將變化后的產(chǎn)品II看成一種新產(chǎn)品，故：cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/211/22x17/21001/4-1/21/21x23/2010-1/43/21/2cj-zj000-1/4-1/23/28/28/202239cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/211/22x17/21001/4-1/21/21x23/2010-1/43/23/2cj-z