運(yùn)籌學(xué)2對(duì)偶理論與靈敏度分析

1、1第二章第二章 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論窗含西嶺千秋雪，門泊東吳萬里船窗含西嶺千秋雪，門泊東吳萬里船本章主要內(nèi)容本章主要內(nèi)容： 線性規(guī)劃的對(duì)偶問題概念、理論及經(jīng)濟(jì)意義線性規(guī)劃的對(duì)偶問題概念、理論及經(jīng)濟(jì)意義 線性規(guī)劃的對(duì)偶單純形法線性規(guī)劃的對(duì)偶單純形法 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析2第一節(jié)第一節(jié) 對(duì)偶問題的提出對(duì)偶問題的提出 材料材料產(chǎn)品產(chǎn)品甲甲乙乙丙丙丁丁單件單件收益收益A32112000B41324000C22343000限額限額600400300200假設(shè)工廠考慮不進(jìn)行生產(chǎn)而把假設(shè)工廠考慮不進(jìn)行生產(chǎn)而把全部資源都轉(zhuǎn)讓，問如何定價(jià)全部資源都轉(zhuǎn)讓，問如何定價(jià)這些資源，既

2、能使其獲利不低這些資源，既能使其獲利不低于安排生產(chǎn)所獲得的收益，又于安排生產(chǎn)所獲得的收益，又能使資源租讓具有競爭力。能使資源租讓具有競爭力。一、引例一、引例Max Z = 2000 x1+4000 x2+3000 x3 s.t. 3x1+4x2+2x3600 2x1+ x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1, x2, x30 Min W =600y1+400y2+300y3+200y4 s.t. 3y1+2y2+ y3+ y42000 4y1+ y2+3y3+2y44000 2y1+2y2+3y3+4y43000 y1, y2, y3, y40 x1x

3、2x3y1 y2 y3 y43二、對(duì)偶問題二、對(duì)偶問題（1 1）對(duì)稱）對(duì)稱LPLP問題的定義問題的定義MaxZCXAXbS TX. .0 MinWYbYACS TY. .0 （2 2）對(duì)稱）對(duì)稱LPLP問題的對(duì)偶問題問題的對(duì)偶問題( )L()DMinWYbYACS TY. .0 第一類對(duì)稱形式第一類對(duì)稱形式第二類對(duì)稱形式第二類對(duì)稱形式MaxZCXAXbS TX. .0 原問題原問題對(duì)偶問題對(duì)偶問題4( )L()DMinWYbYACS TY. .0 MaxZCXAXbS TX. .0 原問題中目標(biāo)函數(shù)的價(jià)值向量原問題中目標(biāo)函數(shù)的價(jià)值向量C C，在對(duì)偶問題中是約束條，在對(duì)偶問題中是約束條件的右端常

4、數(shù)項(xiàng)；件的右端常數(shù)項(xiàng)；原問題中約束條件的右端常數(shù)項(xiàng)原問題中約束條件的右端常數(shù)項(xiàng)b b，在對(duì)偶問題中是目標(biāo)，在對(duì)偶問題中是目標(biāo)函數(shù)的價(jià)值系數(shù)；函數(shù)的價(jià)值系數(shù)；原問題中約束條件的系數(shù)矩陣在對(duì)偶問題中進(jìn)行了轉(zhuǎn)置。原問題中約束條件的系數(shù)矩陣在對(duì)偶問題中進(jìn)行了轉(zhuǎn)置。5Max Z = 2000 x1+4000 x2+3000 x3 s.t. 3x1+4x2+2x3600 2x1+ x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1, x2, x30 Min W =600y1+400y2+300y3+200y4 s.t. 3y1+2y2+ y3+ y42000 4y1+ y2+

5、3y3+2y44000 2y1+2y2+3y3+4y43000 y1, y2, y3, y40 原問題中的原問題中的約束條件個(gè)數(shù)約束條件個(gè)數(shù)對(duì)應(yīng)于對(duì)偶問題中的對(duì)應(yīng)于對(duì)偶問題中的決策變量個(gè)數(shù)決策變量個(gè)數(shù)原問題中的原問題中的決策變量個(gè)數(shù)決策變量個(gè)數(shù)對(duì)應(yīng)于對(duì)偶問題中的對(duì)應(yīng)于對(duì)偶問題中的約束條件個(gè)數(shù)約束條件個(gè)數(shù)原問題原問題求極大化求極大化，對(duì)偶問題，對(duì)偶問題求極小化求極小化對(duì)于對(duì)稱的對(duì)于對(duì)稱的LP問題，如果原問題是求極大化問題，如果原問題是求極大化 其對(duì)偶問題的決策變量其對(duì)偶問題的決策變量的方向與原問題約束條的方向與原問題約束條件不等號(hào)的方向相反件不等號(hào)的方向相反 其對(duì)偶問題的約束條件其對(duì)偶問題的約束

6、條件不等號(hào)的方向與原問題不等號(hào)的方向與原問題決策變量的方向相同決策變量的方向相同6例例1 1 寫出下列寫出下列LPLP問題的對(duì)偶問題問題的對(duì)偶問題對(duì)偶對(duì)偶 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0 s.t. y1+4y2 2 2y1 +4y3 3 y1 ,y2,y3 0 I II設(shè)設(shè) 備備 1 2 8臺(tái)時(shí)臺(tái)時(shí) 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤設(shè)工廠每生產(chǎn)一件產(chǎn)品設(shè)工廠每生產(chǎn)一件產(chǎn)品I 可獲利可獲利2 2元，元，每生產(chǎn)一件產(chǎn)品每生產(chǎn)一件產(chǎn)品II 可獲利可獲利3 3元，問應(yīng)元，問應(yīng)如何安排生產(chǎn)使該

7、廠獲利最多？如何安排生產(chǎn)使該廠獲利最多？2 3y1y2y3Min W =8y1+16y2+12y37（3 3）對(duì)偶問題的對(duì)偶是原問題）對(duì)偶問題的對(duì)偶是原問題推導(dǎo)過程推導(dǎo)過程變形對(duì)偶變變形形對(duì)偶對(duì)偶對(duì)偶對(duì)偶變變形形( )LMax Z=CXs.t. AXb X0()DMin W=Ybs.t. YAC Y0Max W = -Ybs.t. -YA -C Y0Min Z = (-C)Xs.t. (-A)X (-b) X0()DDMax W = Y(-b)s.t. Y(-A) (-C) Y0加工加工81212312312312334334748:1,0MinWxxxxxxxxSTxxxxxx 123123

8、1231231237834334: 40,0MaxZyyyyyyyyySTyyyyyy 例例2 2 寫出下列寫出下列LPLP問題的對(duì)偶問題問題的對(duì)偶問題對(duì)于對(duì)稱的對(duì)于對(duì)稱的LP問題，如果原問題是求極小化問題，如果原問題是求極小化 其對(duì)偶問題的決策變量其對(duì)偶問題的決策變量的方向與原問題約束條的方向與原問題約束條件不等號(hào)的方向相同件不等號(hào)的方向相同 其對(duì)偶問題的約束條件其對(duì)偶問題的約束條件不等號(hào)的方向與原問題不等號(hào)的方向與原問題決策變量的方向相反決策變量的方向相反對(duì)偶對(duì)偶9三、非對(duì)稱三、非對(duì)稱LPLP問題的對(duì)偶問題問題的對(duì)偶問題例例3 3 寫出下列寫出下列LPLP問題的對(duì)偶問題問題的對(duì)偶問題解：用

9、解：用x2= -x2, x3=x3-x3代入上述代入上述LP問題，并將其問題，并將其化為第一類對(duì)稱形式化為第一類對(duì)稱形式Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3無約束無約束 Max Z = x1-2x2 +x3-x3 x1 -x2 -x3+x3 2 x1+x2+x3 -x3 1s.t. -x1 -x2 -x3+x3 -1 -2x1+x2 -x3+x3 -2 x1, x2, x3, x3 0 x1 -x2+x3 1x1 -x2+x3 1x1 -x2+x3 1-x1 +x2-x3 - 1-2x1

10、-x2-x3 -210上述第一類對(duì)稱形式上述第一類對(duì)稱形式LP問題的對(duì)偶問題為：問題的對(duì)偶問題為：則上述問則上述問題變?yōu)椋侯}變?yōu)椋篗in W =2y1+y2 -y3-2y4 y1+y2 -y3-2y4 1 -y1+y2 -y3 +y4 -2 s.t. -y1+y2 -y3 -y4 1 y1 -y2+y3 +y4 -1 y1, y2, y3, y4 0 Min W =2u1+u2+2u3 u1+u2+2u3 1 s.t. u1 -u2+ u3 2 -u1+u2+ u3 =1 u10, u30 ,u2無約束無約束 令令 u1= y1 u2=y2-y3 u3=-y4Max Z = x1-2x2 +x

11、3-x3 x1 -x2 -x3+x3 2 x1+x2+x3 -x3 1s.t. -x1 -x2 -x3+x3 -1 -2x1+x2 -x3+x3 -2 x1, x2, x3, x3 0 -y1+y2 -y3 -y4 1y1-y2+y3 -y4 211(D)Min W =2u1+u2+2u3 u1+u2+2u3 1 s.t. u1 -u2+ u3 2 -u1+u2+ u3 =1 u10, u30 ,u2無約束無約束 (L)Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3無約束無約束 對(duì)偶關(guān)系：對(duì)偶關(guān)系

12、：一個(gè)問題第一個(gè)問題第i個(gè)變量的約束情況決定另一問題個(gè)變量的約束情況決定另一問題第第i個(gè)約束不等式的方向，反之亦然。個(gè)約束不等式的方向，反之亦然。正常的對(duì)正常的，不正常的對(duì)不正常的正常的對(duì)正常的，不正常的對(duì)不正常的 原問題約束條件是等式對(duì)應(yīng)于對(duì)偶問題決策變原問題約束條件是等式對(duì)應(yīng)于對(duì)偶問題決策變量無約束，反之亦然量無約束，反之亦然12例例3 3 直接寫出直接寫出LPLP問題的對(duì)偶問題問題的對(duì)偶問題1231231231231232 2 1:2 20,0,MaxZxxxxxxxxxSTxxxxxx 無無約束束12322MinWuuu123uuu1232uuu123uuu12 10u ，1:ST 2

13、u無無約束束，30u 13 12312312312312322212:10,0MinWuuuuuuuuuSTuuuuuu 無無約束束1232MaxZxxx:ST 123xxx123xxx1232xxx21210 x 20 x 3x 無無約束束 14原問題原問題對(duì)偶問題對(duì)偶問題目標(biāo)函數(shù)目標(biāo)函數(shù)Max zMin w變量變量n個(gè)約束條件約束條件n個(gè)=00無約束無約束約束條件約束條件m個(gè)=變量變量m個(gè)00無約束無約束約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)的價(jià)值系數(shù)目標(biāo)函數(shù)的價(jià)值系數(shù)目標(biāo)函數(shù)的價(jià)值系數(shù)目標(biāo)函數(shù)的價(jià)值系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)15第二節(jié)第二節(jié) LPLP問題的對(duì)偶理論問題的對(duì)偶理論若若X

14、(0),Y(0)分別為分別為(L),(D)的可行解，則有的可行解，則有CX(0)Y(0)b 定理定理1(1(弱對(duì)偶定理弱對(duì)偶定理): ): 極大化原問題目標(biāo)函數(shù)值總是不極大化原問題目標(biāo)函數(shù)值總是不大于其對(duì)偶問題的目標(biāo)函數(shù)值。大于其對(duì)偶問題的目標(biāo)函數(shù)值。證明：證明：max z=CX;AXb;X0(L) min w=Yb;YAC;Y0(D)由于由于X(0)是是(L)的可行解，有的可行解，有AX(0)b, X(0)0.由于由于Y(0)是是(D)的可行解，有的可行解，有Y(0)0. Y(0)左乘不等式組左乘不等式組AX(0)b的兩邊得：的兩邊得：Y(0)AX(0) Y(0)b (1)16 min w=

15、Yb;YAC;Y0(D)又又Y(0)AC用用X(0)(X(0)0)右乘上式，得右乘上式，得Y(0)AX(0) CX(0) (2)由（由（1），（），（2）得：得：CX(0)Y(0)AX(0)Y(0)b所以所以 CX(0)Y(0)b17推論推論1(P57)1(P57) 若若LPLP問題有無界解，則其對(duì)偶問題無可行解問題有無界解，則其對(duì)偶問題無可行解( (弱對(duì)偶性弱對(duì)偶性) )； 若若LPLP問題無可行解，則對(duì)偶問題或有無界解或無可行解。問題無可行解，則對(duì)偶問題或有無界解或無可行解。x2x111-1-1y2y111-1-1( (書書P57)P57)原問題原問題對(duì)偶問題對(duì)偶問題18推論推論2 2極大

16、化問題（極大化問題（L）的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函）的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值都是其對(duì)偶問題數(shù)值都是其對(duì)偶問題（D）目標(biāo)函數(shù)值的下界。目標(biāo)函數(shù)值的下界。極小化問題（極小化問題（D）的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)）的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值都是其對(duì)偶問題函數(shù)值都是其對(duì)偶問題（L）目標(biāo)函數(shù)值的上界。目標(biāo)函數(shù)值的上界。推論推論3 3YbCX(0)CX Y(0)bmax z=CX; AXb; X0(L) min w=Yb; YAC; Y0(D)19例例4 4 考慮下面一對(duì)考慮下面一對(duì)LPLP問題問題其對(duì)偶問題為：其對(duì)偶問題為：由于由于X(0) =(1,1,1,1)T,Y(0)=(1,

17、1)T分別為分別為(L),(D)的可行解，的可行解，Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0 Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20Z(0)=10W(0)=40W10推論推論2Z40推論推論3故故Z40,W10.20P59（書（書 例例4 4）12123123123max221,0zxxxxxxxxxxx 利用推論利用推論1 1 min W = 2y1+y2 - y1- 2y2 1

18、 s.t. y1+ y2 1 y1- y2 0 y1, y20X=(0, 0, 0)s.t.若若LP問題無可行解，則對(duì)偶問題或有無界解或無可行解。問題無可行解，則對(duì)偶問題或有無界解或無可行解。21定理定理2 2（最優(yōu)性準(zhǔn)則）（最優(yōu)性準(zhǔn)則） 當(dāng)當(dāng)LPLP問題目標(biāo)函數(shù)值與其對(duì)偶問問題目標(biāo)函數(shù)值與其對(duì)偶問題目標(biāo)函數(shù)值相等時(shí)，各自的可行解即為最優(yōu)解。題目標(biāo)函數(shù)值相等時(shí)，各自的可行解即為最優(yōu)解。(P57)(P57)若若X(0),Y(0)分別為分別為(L)，(D)的可行解的可行解, ,且且CX(0)Y(0)b,則則X(0),Y(0)分別為分別為(L)，(D)的最優(yōu)解。的最優(yōu)解。證明：證明：由定理由定理1

19、1可知，對(duì)于可知，對(duì)于(L)的任意可行解的任意可行解X，有，有CX Y(0)b 由于由于CX(0) =Y(0)b，CX CX(0) ，故故X(0)為為 (L) 的最優(yōu)解；的最優(yōu)解；同理，同理，由定理由定理1 1可知，可知，對(duì)于對(duì)于(D)的任意可行解的任意可行解Y，有，有YbCX(0)，由于由于CX(0) =Y(0)b，YbY(0)b，Y(0)為為(D)的最優(yōu)的最優(yōu)解。解。22例例5 5( )L()DMax Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0 Min W = 20y1+20y2 y

20、1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20由于由于X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是是(L)，(D)的的可行解且可行解且 CX(0)=bTY(0)=28，所以，所以X(0),Y(0)分別為分別為(L)，(D)的最優(yōu)解。的最優(yōu)解。23線性規(guī)劃的矩陣表示線性規(guī)劃的矩陣表示Max Z=CXs.t. AX b X0令令A(yù)=(B,N), X= XB ,C=(CB,CN) XN由由AX+IXs=b (B,N,I) XB =b BXB+NXN+IXs=b BXB=b-NXN-IXs XN Xs XB=B-1b-B-1NX

21、N -B-1Xs (1)將將(1)式代入目標(biāo)函數(shù)得式代入目標(biāo)函數(shù)得Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN -B-1Xs)+CNXN XN = CBB-1b+(CN-CBB-1N)XN -CB B-1Xs (2) Max Z=CX+0Xss.t. AX+IXs=b X, Xs0用非基變量表示基變量用非基變量表示基變量用非基變量表示目標(biāo)函數(shù)用非基變量表示目標(biāo)函數(shù)24=(0, CN-CBB-1N, -CB B-1) =(C-CBB-1A, -CB B-1)(C-CBB-1A, -CB B-1)= (C-CBB-1(B,N), -CB B-1)=(C

22、B-CBB-1B, CN-CBB-1N, -CB B-1)=(0, CN-CBB-1N, -CB B-1)若若CN-CBB-1N0, -CB B-10,則則Z為最優(yōu)解為最優(yōu)解令令XN=0, Xs=0，可以得到基可以得到基B的基可行解和目標(biāo)函數(shù)值的基可行解和目標(biāo)函數(shù)值XB=B-1b-B-1NXN -B-1XsZ= CBB-1b+(CN-CBB-1N)XN -CB B-1XsX=(XB, XN, Xs)=(B-1b,0,0)Z= CBB-1b25CCBXBbXBXNXS-ZCBXBB-1bCBCN0ICN-CBB-1NB-1NB-10-CBB-1-CBB-1b26初始單純形表初始單純形表cj CB

23、 XB b x1 x2 x3 x4 x5 j cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/40 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 2 3 0 0 004-3經(jīng)過一次迭代經(jīng)過一次迭代初始基初始基 第一輪第一輪迭代后迭代后的基的基P3 P4 P51 0 00 1 00 0 1B=P3 P4 P21 0 20 1 00 0 4B=1 0

24、 -1/20 1 00 0 1/4B-1=27初始單純形表初始單純形表cj CB XB b x1 x2 x3 x4 x5 j cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/40 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 2 3 0 0 004-3經(jīng)過一次迭代經(jīng)過一次迭代1 0 -1/20 1 00 0 1/4B-1=B-1 b=1 0 -1

25、/20 1 00 0 1/48 16122 16 3=Z= CBB-1b=928初始單純形表初始單純形表cj CB XB b x1 x2 x3 x4 x5 j cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/40 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 2 3 0 0 004-3經(jīng)過一次迭代經(jīng)過一次迭代1 0 -1/20 1 00 0 1/

26、4B-1=B-1A=-CBB-1=(0, 0, -3/4)A29定理定理3 3（強(qiáng)對(duì)偶定理）（強(qiáng)對(duì)偶定理） 若若(L)，(D)均有可行解，則均有可行解，則(L)，(D)均有最優(yōu)解，均有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。且目標(biāo)函數(shù)最優(yōu)值相等。證明：證明： 設(shè)設(shè)X(0),Y(0)分別為分別為(L)，(D)的可行解的可行解, ,由弱對(duì)偶定理由弱對(duì)偶定理( (推論推論3)3)，對(duì)于，對(duì)于(L)的任意可行解的任意可行解X，有，有CX Y(0)b，所以，所以CX在可行域內(nèi)有上界，故在可行域內(nèi)有上界，故(L)有最優(yōu)解。有最優(yōu)解。 同理，對(duì)于同理，對(duì)于(D)的任意可行解的任意可行解Y，由弱對(duì)偶定理由弱對(duì)偶定理（推

27、（推論論2 2），有有Y bCX(0)，所以，所以Yb在可行域內(nèi)有下界，故在可行域內(nèi)有下界，故(D)有最優(yōu)解。有最優(yōu)解。設(shè)設(shè)(L)的最優(yōu)解為的最優(yōu)解為X(0)，且，且X(0)所對(duì)應(yīng)的最優(yōu)基為所對(duì)應(yīng)的最優(yōu)基為B，X(0)可以表示為可以表示為X(0) = = XB(0) = = B-1b XN(0) 0max z=CX; AXb; X0(L) min w=Yb; YAC; Y0(D)30則則( (A, ,S)= ( (C, ,0) CBB-1(A, I)=( (C CBB-1A, CBB-1)0由于由于CCBB-1A0，所以所以CBB-1A C (1)(1)又又CBB-10，故故CBB-10. (

28、2). (2)令令Y(0)=CBB-1，由由(1)、(2)(2)知知Y(0)是是(D)的可行解的可行解. .因?yàn)橐驗(yàn)镃X(0)=(CB, CN) XB(0) =CBXB(0)+CNXN(0) = CBB-1b XN(0)Y(0)A CY(0)0 而而Y(0)b = CBB-1b 則則CX(0)=Y(0)b ，由最優(yōu)性準(zhǔn)則知，由最優(yōu)性準(zhǔn)則知， X(0),Y(0)分別為分別為(L)，(D)的最優(yōu)解的最優(yōu)解, , 且目標(biāo)函數(shù)最優(yōu)值相等。且目標(biāo)函數(shù)最優(yōu)值相等。31推論：推論： 在用單純形法求解在用單純形法求解LPLP問題問題(L)的最優(yōu)單純形表中，的最優(yōu)單純形表中，松弛變量的檢驗(yàn)數(shù)的相反數(shù)就是其對(duì)偶問

29、題松弛變量的檢驗(yàn)數(shù)的相反數(shù)就是其對(duì)偶問題(D)的最優(yōu)解。的最優(yōu)解。例例5 5 求下列問題對(duì)偶問題的最優(yōu)解求下列問題對(duì)偶問題的最優(yōu)解Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0 解：化為標(biāo)準(zhǔn)型解：化為標(biāo)準(zhǔn)型Max Z =2x1+3x2+0 x3+0 x4+0 x5 s.t. x1+ 2x2+x3 = 8 4x1 +x4 =16 4x2 +x5=12 x1 ,x2 , x3, x4, x50 CCBXBbXBXNXS-ZCBXBB-1bCBCN0ICN-CBB-1NB-1NB-10-CBB-1-CBB-1b32cj 2 3 0 0 0 CB

30、 XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x244 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0此時(shí)達(dá)到最優(yōu)解此時(shí)達(dá)到最優(yōu)解X*=(4, 2)T, Max Z=14。對(duì)偶問題的最優(yōu)解為對(duì)偶問題的最優(yōu)解為Y*=(3/2, 1/8, 0)T運(yùn)用單純形法計(jì)算得原問題的最終表如下：運(yùn)用單純形法計(jì)算得原問題的最終表如下：33 推論：對(duì)偶問題的最優(yōu)解對(duì)應(yīng)于原問題的最優(yōu)推論：對(duì)偶問題的最優(yōu)解對(duì)應(yīng)于原問題的最優(yōu)單純型表中松弛變量檢驗(yàn)數(shù)的相反數(shù)或剩余變單純型表中松弛變量檢驗(yàn)數(shù)的相反數(shù)或剩余變量的檢驗(yàn)數(shù)。量的檢驗(yàn)

31、數(shù)。34Min z=2x1+3x2 x1+x2 350 x1 1252x1+x2 600 x1, x2 0Max w=350y1+125y2+600y3 s.t. y1+ y2+2y32 y1 + y3 3 y1 ,y2 0 ;y3 0cj 2 3 0 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 3 x2 2 x1 0 x4100250125 0 1 -2 0 -1 2 0 1 0 1 0 1 -1 0 0 0 1 1 1 -1 -1 原問題的最優(yōu)單純型表如下所示：原問題的最優(yōu)單純型表如下所示： 0 0 4 0 1 -4+M MY*=(4, 0, -1)Tw*=8

32、00例例35定理定理4 4（互補(bǔ)松弛定理）（互補(bǔ)松弛定理）在最優(yōu)情況下，原問題的第在最優(yōu)情況下，原問題的第i個(gè)決策變個(gè)決策變量與其對(duì)偶問題第量與其對(duì)偶問題第i個(gè)約束中的松弛變量的乘積恒為零個(gè)約束中的松弛變量的乘積恒為零。 , (1,1)k lkmln 設(shè)設(shè)X(0),Y(0)分別為分別為(L),(D)的的可行解，則可行解，則X(0),Y(0)分別為分別為(L),(D)的最優(yōu)解的充要條件為的最優(yōu)解的充要條件為 , ,有有(y1(0), , yk(0) , , ym(0) )xn+1xn+kxn+m= 0(ym+1, , ym+l , , ym+n)x1(0)xl(0)xn(0)= 036 m(1)

33、(1)若若xl(0) 0，則則ail yi(0) = Cl i=1 m(2)(2)若若ail yi(0) Cl ，則則xl(0) = 0 i=1 n(3)(3)若若yk(0) 0，則則akj xj(0) = bk j=1 n(4)(4)若若akj xj(0) 0y*40y*5=0y*6=040*123422320(1)xxxx *123423220(2)xxxx *342320 xx *343220 xx 所以所以x1*=x2*=0. 解：由互補(bǔ)松弛性知解：由互補(bǔ)松弛性知解得解得x3*= x4*=4. 所以所以(L)的最優(yōu)解為的最優(yōu)解為X*=(0,0,4,4)T由于由于代入代入(L)得得(y1

34、*, y2*) x5 =0 x6y30, y40， x1*(y3,y4,y5,y6) x2* =0 x3* x4*由于由于y1* 0, y2* 0, , 所以，所以，x5=0, x6=0代入代入(1)、(2)得得41若若X*,Y* 分別為分別為(L),(D)的最優(yōu)解，那么的最優(yōu)解，那么CX*=Y*b。由由 Z*= Y*b =y1*b1+y2*b2+ym*bm 可知可知 Z*/ b= Y* yi*= = Z*/ bi yi*表示資源量表示資源量bi 變化變化1 1個(gè)單位對(duì)目標(biāo)函數(shù)最優(yōu)值個(gè)單位對(duì)目標(biāo)函數(shù)最優(yōu)值Z 產(chǎn)生的影產(chǎn)生的影響，稱之為響，稱之為第第i 種資源的影子價(jià)格種資源的影子價(jià)格。 第三節(jié)

35、第三節(jié) 對(duì)偶問題的經(jīng)濟(jì)解釋對(duì)偶問題的經(jīng)濟(jì)解釋-影子價(jià)格影子價(jià)格一、影子價(jià)格一、影子價(jià)格 (Shadow Price)1.1.定義定義 影子價(jià)格是最優(yōu)配置下資源的理想價(jià)格。影子價(jià)格是最優(yōu)配置下資源的理想價(jià)格。2.2.含義含義 對(duì)偶問題的最優(yōu)解實(shí)際上就是右端常數(shù)項(xiàng)的單位變化所引對(duì)偶問題的最優(yōu)解實(shí)際上就是右端常數(shù)項(xiàng)的單位變化所引起的目標(biāo)值的變化。起的目標(biāo)值的變化。42 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 4422 x1 0 x5 3 x2 x1 x2 x3 x4 x5 CB XB b 2 3 0 0 0 cj-14 0 0 -3/2 -1/8 0例例7 7

36、 下面是一張下面是一張LPLP問題的最優(yōu)單純形表，其中問題的最優(yōu)單純形表，其中x3, x4, x5為為松弛變量松弛變量則對(duì)偶問題的最優(yōu)解為則對(duì)偶問題的最優(yōu)解為Y*=(1.5, 0.125, 0)T43例例8 8X* =(4, 2)T，Z* =14Q(4, 2)Z=14x1x24x1=164x2=12x1+2x2=844083Q(4.25, 1.875)Z=14.125Q(4, 2.5)Z=15.5Q(4, 2)Z=14 Max Z =2x1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0 8X1* =(4, 2.5)T，Z1*=15.5X2* =(4.25,

37、1.875)T，Z2* =14.125X3* =(4, 2)T，Z3* =1444資源的影子價(jià)格是針對(duì)具體生產(chǎn)或具體企業(yè)而言的：資源的影子價(jià)格是針對(duì)具體生產(chǎn)或具體企業(yè)而言的：1.1.同一種資源在不同的生產(chǎn)條件下或不同的范圍內(nèi)可同一種資源在不同的生產(chǎn)條件下或不同的范圍內(nèi)可能有不同的影子價(jià)格；能有不同的影子價(jià)格；A A2.2.產(chǎn)品的市場價(jià)格發(fā)生變化，資源的影子價(jià)格也會(huì)發(fā)產(chǎn)品的市場價(jià)格發(fā)生變化，資源的影子價(jià)格也會(huì)發(fā)生變化；生變化；C C3.3.資源的數(shù)量結(jié)構(gòu)不同，資源的影子價(jià)格也不同。資源的數(shù)量結(jié)構(gòu)不同，資源的影子價(jià)格也不同。b b I II設(shè)設(shè) 備備 1 2 8臺(tái)時(shí)臺(tái)時(shí) 原材料原材料A 4 0 1

38、6公斤公斤原材料原材料B 0 4 12公斤公斤2 3a21=3 (1.5, 1/6, 0)c2=4 (2, 0, 0)b1=10 (0, 0.5, 0.75)45（2 2）告訴管理者增加何種資源對(duì)企業(yè)更有利）告訴管理者增加何種資源對(duì)企業(yè)更有利(擇優(yōu)分配擇優(yōu)分配) )；cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x244 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0（1 1）告訴管理者花多大代價(jià)買進(jìn)資源或賣出資源）告訴管理者花多大代價(jià)買進(jìn)資源或賣出資源是合適的；是合適

39、的；二、影子價(jià)格的作用二、影子價(jià)格的作用 （3 3）要提高資源的影子價(jià)格，可以對(duì)生產(chǎn)工藝進(jìn)行革要提高資源的影子價(jià)格，可以對(duì)生產(chǎn)工藝進(jìn)行革新，以降低這種資源的單耗，從而增加企業(yè)的利潤新，以降低這種資源的單耗，從而增加企業(yè)的利潤。市市 影影46第四節(jié)第四節(jié) 對(duì)偶單純形法對(duì)偶單純形法 正則解：正則解：設(shè)設(shè)X(0)是線性規(guī)劃問題是線性規(guī)劃問題(Max)的一個(gè)基本解，的一個(gè)基本解，如果它的檢驗(yàn)數(shù)如果它的檢驗(yàn)數(shù)j0(jJ)，則稱，則稱X(0)是該線性規(guī)劃問題是該線性規(guī)劃問題的一個(gè)正則解。相應(yīng)的基稱為正則基。的一個(gè)正則解。相應(yīng)的基稱為正則基。cj CB XBb x1x2x3x4x5x6j 0 x40 x50

40、 x6-48-2-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 10 -1 -2 -3 0 0 0-1 -2 -3 0 0 0正則解若是可行解，則它是最優(yōu)解。正則解若是可行解，則它是最優(yōu)解。47第四節(jié)第四節(jié) 對(duì)偶單純形法對(duì)偶單純形法 從一基可行解從一基可行解( (BbBb-1-10)0)出發(fā)，在滿足可行解的基礎(chǔ)出發(fā)，在滿足可行解的基礎(chǔ)上，通過逐次基可行解的轉(zhuǎn)換，直至上，通過逐次基可行解的轉(zhuǎn)換，直至j j0(0(j jJ)J)成成立立（對(duì)（對(duì)maxmax問題）問題），即達(dá)到可行的正則解，從而判斷，即達(dá)到可行的正則解，從而判斷是否得到最優(yōu)解或無最優(yōu)解。是否得到最優(yōu)解或無最

41、優(yōu)解。 從一正則解從一正則解( (j j0(0(j jJ J)出發(fā)出發(fā)（對(duì)（對(duì)maxmax問題）問題），在，在滿足正則解的基礎(chǔ)上，通過逐次轉(zhuǎn)換，直至滿足正則解的基礎(chǔ)上，通過逐次轉(zhuǎn)換，直至BbBb-1-100成成立，即達(dá)到滿足正則解條件的可行解，從而判斷是否立，即達(dá)到滿足正則解條件的可行解，從而判斷是否得到最優(yōu)解或無最優(yōu)解。得到最優(yōu)解或無最優(yōu)解。單純形法的基本思想單純形法的基本思想：對(duì)偶單純形法的基本思想：對(duì)偶單純形法的基本思想：48例例9 9 用對(duì)偶單純形法求解下列用對(duì)偶單純形法求解下列LPLP問題問題解：原問題變形為解：原問題變形為Min Z = x1+2x2+3x3 s.t. x1 -x2

42、+ x34 x1+x2+2x38 x2 - x32 x1, x2, x30 Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3-4 x1+x2+2x38 -x2+ x3-2 x1, x2, x30 Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3+x4 =-4 x1+x2+2x3 +x5 = 8 -x2+ x3 +x6=-2 x1, x2, x3, x4, x5, x60 一、對(duì)偶單純形法的舉例一、對(duì)偶單純形法的舉例第一類對(duì)稱形式第一類對(duì)稱形式49cj CB XBb x1x2x3x4x5x6j 0 x40 x50 x6-48-2-1 1 -1 1

43、0 0 1 1 2 0 1 0 0 -1 1 0 0 10 -1 -2 -3 0 0 0cj-1 -2-3000 CB XBb x1x2x3x4x5x6-1 x141-11-1000 x540 211100 x6-20-11001j 4 0 -3 -2 -1 0 0-1 -2 -3 0 0 0Min-4，-2=Min -1-1-3-1,Min-2=Min -3-150*6 2 0X T T（ ， ， ）cj-1 -2-3000 CB XBb x1x2x3x4x5x6-1 x16100-10-10 x500 03112-2 x2201-100-1j 10 0 0 -5 -1 0 -3Z* = x

44、1* +2x2*+3x3*=10所以所以51二、對(duì)偶單純形法的步驟二、對(duì)偶單純形法的步驟(1)(1)化化LP問題的約束條件為問題的約束條件為“”形式形式, ,引入松弛變量引入松弛變量, ,建立初始表建立初始表; ;(2)(2)若所有常數(shù)項(xiàng)若所有常數(shù)項(xiàng)bi0，則最優(yōu)解已經(jīng)達(dá)到，否則，則最優(yōu)解已經(jīng)達(dá)到，否則bl=Minbi|bi0， 選取選取bl所對(duì)應(yīng)的變量為出基變量；所對(duì)應(yīng)的變量為出基變量；(3)(3)計(jì)算計(jì)算k=Minj /alj |alj 0，即，即cj - -j 時(shí)，原最優(yōu)解改變。時(shí)，原最優(yōu)解改變。五、價(jià)值系數(shù)五、價(jià)值系數(shù) C 的變化分析的變化分析公式推導(dǎo)公式推導(dǎo) 則則xj 的檢驗(yàn)數(shù)由的檢

45、驗(yàn)數(shù)由j= cj -CBB-1Pj 變?yōu)樽優(yōu)?()jBjjcC B Pc 69例例6 6 Max Z = -2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1, x2, x3, x4, x5 0五、價(jià)值系數(shù)五、價(jià)值系數(shù) C 的變化分析的變化分析例題例題 最優(yōu)單純形表為最優(yōu)單純形表為cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5j00-9/5-8/5-1/5為使原最優(yōu)解不變，求為使原最優(yōu)解不變，求 c3 的變化范圍。的變化范圍

46、。70解：最優(yōu)單純形表為解：最優(yōu)單純形表為從表中看到從表中看到3=-9/5+c3 , ,可見可見, ,當(dāng)當(dāng)c3 9/5 ，即，即 c3 -49/5-11/5時(shí)，原最優(yōu)解不變。時(shí)，原最優(yōu)解不變。cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5j00-9/5-8/5-1/5cj-2-3-4+c300CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5712.2. 基變量價(jià)值系數(shù)的改變基變量價(jià)值系數(shù)的改變五

47、、價(jià)值系數(shù)五、價(jià)值系數(shù) C 的變化分析的變化分析公式推導(dǎo)公式推導(dǎo) 11(,)kkmjBBBBjcccccB P 1100(,)( , )kmkjBBBBjcccccB P 1kjBjBkjcC B Pc a kjBkjc a 0 00|kjjkjBkjkjkjMaxacMinaaa kBkjjc a 即即1jjBjcCB P 若基變量若基變量 的價(jià)值系數(shù)的價(jià)值系數(shù) 變?yōu)樽優(yōu)?則則,kkkBBBccc kBckBx11(,)TjjkjmjB Paaa 非基變量非基變量xj的檢驗(yàn)數(shù)由的檢驗(yàn)數(shù)由j= cj -CBB-1Pj 變?yōu)樽優(yōu)?2例例7 7 下表為最優(yōu)單純形表下表為最優(yōu)單純形表, ,計(jì)算計(jì)算

48、c2 變化的范圍，使得變化的范圍，使得原最優(yōu)解不變。原最優(yōu)解不變。c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/80五、價(jià)值系數(shù)五、價(jià)值系數(shù) C 的變化分析的變化分析例題例題 73當(dāng)當(dāng)-3c21，即即 0c24 時(shí)，原最優(yōu)解不變。時(shí)，原最優(yōu)解不變。c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/80cj23+c2000CBXBbx1x2x3x4x52 x1 41001/400 x5

49、400-21/213+c2 x2 2011/2-1/80j00-3/2 -c2/2-1/8+c2/803=0-20+0(-2)+ (3+c2)1/2=-3/2 -c2/2 04=0-21/4+01/2+(3+c2)(-1/8)=-1/8+c2/8 0741.1.增減變量增減變量(2)(2)刪除變量刪除變量(1)(1)增加變量增加變量若所增加變量的檢驗(yàn)數(shù)若所增加變量的檢驗(yàn)數(shù)00，則原最優(yōu)解不變；，則原最優(yōu)解不變；否則，用單純形法迭代求最優(yōu)解。否則，用單純形法迭代求最優(yōu)解。六、技術(shù)矩陣六、技術(shù)矩陣 A 的變化分析的變化分析75P66 P66 例例9 91231231323123:max235228

50、4616. .4312,0OBJZxxxxxxxxs txxx x x c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/80 I II設(shè)設(shè) 備備 1 2 8臺(tái)時(shí)臺(tái)時(shí) 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤 263 利潤利潤( (元元) 2 3) 2 35 55x3B-176P66 P66 例例9 9c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/805

51、x3/./.1301 4021 521 21621 21 8030 25B P 1.520.253= c3-CBB-1P3 =5-(2, 0, 3)(1.5, 2, 0.25)T=1.2501.25說明增加產(chǎn)品說明增加產(chǎn)品的生產(chǎn)，可以提高企業(yè)的的收益。的生產(chǎn)，可以提高企業(yè)的的收益。利用單純形法進(jìn)行迭代利用單純形法進(jìn)行迭代77P66 P66 例例9 9c j23000CBXBbx1x2x3x4x52 x1 1101.5-0.125-0.755x3200-10.250.53 x2 1.5010.75-0.1875-0.125j00-0.25-0.4375-0.6255x30100 最優(yōu)生產(chǎn)計(jì)劃：最優(yōu)生產(chǎn)計(jì)劃：生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品I 1I 1件件 產(chǎn)品產(chǎn)品II 1.5II 1.5件件 產(chǎn)品產(chǎn)品III 2III 2件件總利潤為：總利潤為：16.516.5元。元。78jjPP2.2.Pj 的變化的變化10jjBjcC B P 10jjBjcC BP則最優(yōu)解不變則最優(yōu)解不變則原最優(yōu)解改變則原