第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析

1、2021-10-291運(yùn)籌學(xué)運(yùn)籌學(xué)趙明霞趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院山西大學(xué)經(jīng)濟(jì)與管理學(xué)院2021-10-292第二章第二章 線性規(guī)劃的對(duì)偶理論與靈敏度分析線性規(guī)劃的對(duì)偶理論與靈敏度分析線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題影子價(jià)格影子價(jià)格對(duì)偶單純形法對(duì)偶單純形法靈敏度分析靈敏度分析2021-10-293例例1 美佳公司計(jì)劃制造美佳公司計(jì)劃制造、兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備備A A、B B的臺(tái)時(shí)、調(diào)試時(shí)間及的臺(tái)時(shí)、調(diào)試時(shí)間及A A、B B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時(shí)的獲利

2、情況如下表所示。問該公司應(yīng)制造各售出一件時(shí)的獲利情況如下表所示。問該公司應(yīng)制造、兩種家電備多少兩種家電備多少件使獲取的利潤(rùn)為最大。件使獲取的利潤(rùn)為最大。設(shè)：設(shè)： x x1 1 A A產(chǎn)品的生產(chǎn)量產(chǎn)品的生產(chǎn)量 x x2 2 B B產(chǎn)品的生產(chǎn)量產(chǎn)品的生產(chǎn)量利潤(rùn)利潤(rùn) 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 .第一節(jié)第一節(jié) 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題2021-10-2945 5x x2 2

3、 + + x x3 3 = = 15 156 6x x1 1 + 2x + 2x2 2 + x+ x4 4 = = 24 24x x1 1 + x + x2 2 + + x x5 5 = = 5 5x x1 1，x x2 2 ，x x3 3 ，x x4 4 ，x x5 5 0 0約束約束條件條件st .st .利潤(rùn)利潤(rùn) max z= 2 xmax z= 2 x1 1 + x + x2 2 + 0 x+ 0 x3 3 + 0 x + 0 x4 4 + 0 x + 0 x5 5 標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化最終單純形表最終單純形表C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2

4、 x3 x4 x50 0 0 0 x x3 3 x x4 4 x x5 5151524245 5 0 5 1 0 0 0 5 1 0 0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 2 1 0 0 0 2 1 0 0 0最優(yōu)解最優(yōu)解X X* *=(7/2,3/2,=(7/2,3/2,15/215/2, ,0 0, ,0 0) )Z Z* *= 17/2= 17/2C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 2 2 x x3 3 x x1 1 x x2 215/215/27/27/23/23/2

5、0 0 1 5/4 -15/2 0 0 1 5/4 -15/2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/2 0 0 00 0 0 -1/4 -1/2 -1/4 -1/2 2021-10-2955 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 0約束約束條件條件把解把解X=(7/2,3/2)X=(7/2,3/2)代入原問題代入原問題( (因?yàn)橐驗(yàn)闉楦郊幼兞繛楦郊幼兞? )分析分析5 53 32 215/215/22

6、4245 5P O 一個(gè)問題？一個(gè)問題？ 市場(chǎng)上設(shè)備市場(chǎng)上設(shè)備A A、設(shè)備設(shè)備B B和調(diào)試工序每小時(shí)值多少錢？和調(diào)試工序每小時(shí)值多少錢？在什么價(jià)位時(shí)，才能使美佳公司愿意出讓自己的資源？在什么價(jià)位時(shí)，才能使美佳公司愿意出讓自己的資源？2021-10-2966 6y y2 2 + y + y3 3分分析析設(shè)：設(shè)： y y1 1 設(shè)備設(shè)備A A值的值的價(jià)值價(jià)值 y y2 2 設(shè)備設(shè)備B B值的值的價(jià)值價(jià)值 y y3 3 調(diào)試工序調(diào)試工序值的值的價(jià)值價(jià)值2 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5

7、y+ 5y3 3總價(jià)值總價(jià)值minminy y1 1 , y , y2 2 , y , y3 30 0st .st .2021-10-2976 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3maxmaxst .st .6 6y y2 2 + y + y3

8、3 y y4 4= =2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y y5 51 1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 5 0 0C C-15 -24 -5 -15 -24 -5 0 0 -M -M0 0 -M -MC CB BY YB Bb y1 y2 y3 y4 y5 y6 y7 - -M M-M-My y6 6y y7 72 21 1 0 6 1 -1 0 1 0 0 6 1 -1 0 1 0 5 2 5 2 1 1 0 -1 0 1 0 -1 0 1 M-15 8M-24 2M-5 -M -M 0 0M-

9、15 8M-24 2M-5 -M -M 0 0問題求解問題求解2021-10-298C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y y2 2y y3 31/41/41/21/2-5/4 1 0 -1/4 1/4-5/4 1 0 -1/4 1/415/2 0 1 15/2 0 1 1/2 -3/2 1/2 -3/2 -15/2 0 0 -7/2 -3/2 -15/2 0 0 -7/2 -3/2 Y=(0, , , 0, 0)Y=(0, , , 0, 0)z z=-17/2=-17/2z z = 17/2

10、= 17/22021-10-299Y=(0, , , 0, 0 )Y=(0, , , 0, 0 )問題分析問題分析問題問題的解的解6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .問題：?jiǎn)栴}：？原問題：原問題：利潤(rùn)利潤(rùn) z= 2 xz= 2 x1 1 + x + x2 2 約束約束條件條件5 5x x2 2 15 156 6x x1 1 + 2x + 2x

11、2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0st .st .問題問題的解的解X X* *=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)Z Z* *= 17/2= 17/2Z Z* *= 17/2= 17/25 5* *3/2 = 15/23/2 = 15/215156 6* *7/2+27/2+2* *3/2 = 243/2 = 242424= =7/2+3/2 = 57/2+3/2 = 55 5= =結(jié)結(jié)論論估價(jià)估價(jià)影子價(jià)格影子價(jià)格（即增加單位資源所（即增加單位資源所得到的貢獻(xiàn)）得到的貢獻(xiàn)）Z= =CX=Yb Z

12、/ b=(Yb) =Y2021-10-2910C C 2 1 2 1 0 0 00 0 0C CB BX XB Bbx1 x2 x3 x4 x50 02 21 1x x3 3x x1 1x x2 215/215/27/27/23/23/20 0 1 5/4 -15/20 0 1 5/4 -15/21 01 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/20 0 0 -1/4 -1/20 0 0 -1/4 -1/2- -0 0 0 1/4 1/20 0 0 1/4 1/2利潤(rùn)利潤(rùn) z= 2 xz= 2 x1 1 + x + x2 2 約束約

13、束條件條件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= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-

14、24-24-5-5y y2 2y y3 31/41/41/21/2 -5/4 1 0 -1/4 1/4 -5/4 1 0 -1/4 1/4 15/2 0 1 15/2 0 1 1/2 -3/2 1/2 -3/2 -15/2 0 0 -7/2 -3/2-15/2 0 0 -7/2 -3/2- - 15/2 0 0 7/2 3/2 15/2 0 0 7/2 3/2 Y=(0, , , 0, 0 )Y=(0, , , 0, 0 )X X* *=(7/2,3/2, 15/2,0,0)=(7/2,3/2, 15/2,0,0)問題變量問題變量問題剩余松弛變量問題剩余松弛變量解的關(guān)系解的關(guān)系2021-10-

15、2911一、對(duì)偶問題一、對(duì)偶問題X X 0 0st.st.AX AX b bmax z =max z = CXCX其中：其中： C= C=（c c1 1，c c2 2, , ,c ,cn n) ) 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 TY Y 0 0st.st.A AT TY CY CT Tmin w =min w = Y YT Tb b利潤(rùn)利潤(rùn) z= 2 xz= 2 x1 1 + x + x2 2 約束約束

16、條件條件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= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .2021-10-2912x x1 1 0, x 0, x2 2 0, x 0, x3 3無約束無約束 st.st.a a1

17、111x 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 x x1 1 , , x x2 2 , , x x3 3 ，x x3 3 00st.st.a a1111x x1 1 - a- a1212x x2 2 + a+ a1313x x3 3- a

18、a1313x x3 3 b b1 1a a2121x x1 1 - a- a2222x x2 2 + a+ a2323x x3 3- a a2323x x3 3 b b2 2-a-a2121x x1 1 + a+ a2222x x2 2 _ a_ a2323x x3 3+ a a2323x x3 3 -b-b2 2-a-a3131x x1 1 + a+ a3232x x2 2 - a- a3333x x3 3+ a a3333x x3 3 -b-b3 3max z = cmax z = c1 1x x1 1 - c - c2 2x x2 2 + c + c3 3x x3 3 - c - c3

19、3x x3 3 y y1 1 , y, y2 2 , y, y2 2 ，y y3 3 00st.st.a a1111y y1 1 + + a a2121y y2 2 a a2121y y2 2 - - a a3131y y3 3 c c1 1-a-a1212y y1 1 - - a a2222y y2 2 + a+ a2222y y2 2 - - a a3232y y3 3 -c-c2 2a a1313y y1 1 + + a a2323y y2 2 a a2323y y2 2- a a3333y y3 3 c c3 3-a-a1313y y1 1 - - a a2323y y2 2 + a+

20、 a2323y y2 2+ a a3333y y3 3 -c-c3 3min w = bmin w = b1 1y y1 1 + b + b2 2y y2 2 - b- b2 2y y2 2 - b - b3 3y y3 3 min w = bmin w = b1 1y 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

21、+ + a a2323y y2 2 + + a a3333y y3 3 = c= c3 3st.st.y y1 10, y0, y2 2無約束無約束，y y3 3 0 02021-10-2913二、對(duì)偶規(guī)則二、對(duì)偶規(guī)則 &原問題有原問題有m m個(gè)約束條件，對(duì)偶問題有個(gè)約束條件，對(duì)偶問題有m m個(gè)變量個(gè)變量&原問題有原問題有n n個(gè)變量，對(duì)偶問題有個(gè)變量，對(duì)偶問題有n n個(gè)約束條件個(gè)約束條件&原問題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問題的右端項(xiàng)原問題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問題的右端項(xiàng)&原問題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問題的價(jià)值系數(shù)原問題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問題的價(jià)值系數(shù)&原問題的系數(shù)矩陣轉(zhuǎn)

22、置后為對(duì)偶問題系數(shù)矩陣原問題的系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問題系數(shù)矩陣變量、約束與系數(shù)變量、約束與系數(shù)2021-10-2914變量與約束對(duì)應(yīng)關(guān)系變量與約束對(duì)應(yīng)關(guān)系原問題（對(duì)偶問題）原問題（對(duì)偶問題）對(duì)偶問題（原問題）對(duì)偶問題（原問題） max z=CX AX ( ) b X ( ) 0 或無約束或無約束 min w=Yb ATY ( ) C Y ( ) 0 或無約束或無約束 有有n個(gè)決策變量個(gè)決策變量 xj (j0、2n) xj 0 0變量變量 xj 0 0 xj 無約束無約束 有有n個(gè)約束條件個(gè)約束條件 對(duì)應(yīng)的約束為對(duì)應(yīng)的約束為 約束約束 對(duì)應(yīng)的約束為對(duì)應(yīng)的約束為 對(duì)應(yīng)的約束為對(duì)應(yīng)的約束為 有有m個(gè)

23、約束條件個(gè)約束條件 對(duì)應(yīng)的約束為對(duì)應(yīng)的約束為 約束約束 對(duì)應(yīng)的約束為對(duì)應(yīng)的約束為 對(duì)應(yīng)的約束為對(duì)應(yīng)的約束為 有有m個(gè)決策變量個(gè)決策變量 yj (j0、2m) yj 0 0變量變量 yj 0 0 yj 無約束無約束2021-10-2915三、對(duì)偶問題的基本性質(zhì)（對(duì)稱形）三、對(duì)偶問題的基本性質(zhì)（對(duì)稱形）1對(duì)稱性：對(duì)偶問題的對(duì)偶問題是原問題對(duì)稱性：對(duì)偶問題的對(duì)偶問題是原問題1弱對(duì)偶性：極大化原問題的任一可行解的目弱對(duì)偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對(duì)偶問題任意可行解的標(biāo)函數(shù)值，不大于其對(duì)偶問題任意可行解的目標(biāo)函數(shù)值目標(biāo)函數(shù)值1對(duì)偶定理：若一個(gè)問題有最優(yōu)解，則另一問對(duì)偶定理：若一個(gè)

24、問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問題最優(yōu)基為題最優(yōu)基為B B，則其對(duì)偶問題最優(yōu)解則其對(duì)偶問題最優(yōu)解Y Y* *=C=CB BB B-1-11無界性：原問題無界，對(duì)偶問題無可行解無界性：原問題無界，對(duì)偶問題無可行解需要說明的是：需要說明的是：這些性質(zhì)同樣適用于非對(duì)稱形問題這些性質(zhì)同樣適用于非對(duì)稱形問題2021-10-2916X X 0 0st.st.AX AX b bmax z = CXmax z = CXX, Xs 0X, Xs 0st.st.AX + IXs AX + IXs = = b bmax z = CX + 0Xsmax

25、 z = CX + 0XsC C C C 0 0C CB BX XB Bb X Xs0 0X Xs sb b A IA IC C C CB B C CN N 0 0C CB BX XB Bb XB XN Xs0 0X Xs sb b B N IB N IC C C CB B C CN N 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B-1-1B B B B-1-1N N B B-1-1I IC CB B-C-CB BB B-1-1B B C CN N-C-CB BB B-1-1N 0-CN 0-CB BB B-1-1I I C C C C

26、B B C CN N 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B-1-1B B B B-1-1N N B B-1-1I I 0 0 C CN N-C-CB BB B-1-1N -CN -CB BB B-1-12021-10-2917C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x5151524245 5 0 5 1 0 0 0 5 1 0 0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 C C 2 1 2 1 0 0 0 0 0 0C CB BX X

27、B Bb x1 x2 x3 x4 x515/215/27/27/23/23/2 0 0 1 5/4 -15/2 0 0 1 5/4 -15/2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/2 B與與B-1B B-1-1= =1 5/4 -15/21 5/4 -15/20 1/4 -1/20 1/4 -1/20 -1/4 3/20 -1/4 3/2B=B=1 0 51 0 50 6 20 6 20 1 10 1 12021-10-2918第二節(jié)第二節(jié) 影子價(jià)格影子價(jià)格*1*1*miiinjjjybxczbi是線性規(guī)劃原問題約束

28、條件的右端項(xiàng)，它代表第是線性規(guī)劃原問題約束條件的右端項(xiàng)，它代表第i i種資源的擁種資源的擁有量；有量；對(duì)偶變量對(duì)偶變量yiyi* *的意義代表在資源最優(yōu)利用條件下對(duì)單位第的意義代表在資源最優(yōu)利用條件下對(duì)單位第i i種資種資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)，為區(qū)別起見，稱為產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)，為區(qū)別起見，稱為影子價(jià)格影子價(jià)格(shadow price)(shadow price)。2021-10-29191 1、資源的市場(chǎng)價(jià)格是其價(jià)值的客觀體現(xiàn)，相對(duì)比較穩(wěn)定，、資源的市場(chǎng)價(jià)格是其價(jià)值的客觀體

29、現(xiàn)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況。因企業(yè)生產(chǎn)任而它的影子價(jià)格則有賴于資源的利用情況。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改隨之改變變。2 2、影子價(jià)格是一種、影子價(jià)格是一種邊際價(jià)格邊際價(jià)格，若對(duì)式中目標(biāo)函數(shù)，若對(duì)式中目標(biāo)函數(shù)z z求求bibi的偏的偏導(dǎo)數(shù)可得導(dǎo)數(shù)可得 。這說明。這說明yiyi* *的值相當(dāng)于在資源得到的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，最優(yōu)利用的生產(chǎn)條件下，bibi每增加一個(gè)單位時(shí)目標(biāo)函數(shù)每增加一個(gè)單位時(shí)目標(biāo)函數(shù)z z的增量。的增量。*/iiybz2021-10-2920injijb

30、xa1 3 3、資源的影子價(jià)格實(shí)際上又是一種、資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本機(jī)會(huì)成本。在完全市場(chǎng)經(jīng)濟(jì)條件下，。在完全市場(chǎng)經(jīng)濟(jì)條件下，當(dāng)?shù)诋?dāng)?shù)? 2種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，可以買進(jìn)這種資源；相反，當(dāng)市種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，可以買進(jìn)這種資源；相反，當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，就會(huì)賣出這種資源。隨著資源的買進(jìn)賣出，其影場(chǎng)價(jià)格高于影子價(jià)格時(shí)，就會(huì)賣出這種資源。隨著資源的買進(jìn)賣出，其影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平，才子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平，才處于平衡狀態(tài)。處于平衡狀態(tài)。 4 4、在上一節(jié)對(duì)偶問題的互補(bǔ)松弛性質(zhì)中有

31、、在上一節(jié)對(duì)偶問題的互補(bǔ)松弛性質(zhì)中有 時(shí)，時(shí)，yi=0yi=0；當(dāng)；當(dāng)yi0yi0時(shí)，有時(shí)，有 ，這表明生產(chǎn)過程中如果某種資源，這表明生產(chǎn)過程中如果某種資源bibi未得到充分利未得到充分利用時(shí)，該種資源的影子價(jià)格為用時(shí)，該種資源的影子價(jià)格為零零；又當(dāng)資源的影子價(jià)格；又當(dāng)資源的影子價(jià)格不為零時(shí)不為零時(shí)，表明該，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。種資源在生產(chǎn)中已耗費(fèi)完畢。 5 5、當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該產(chǎn)品有利，可在計(jì)劃中安、當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該產(chǎn)品有利，可在計(jì)劃中安排，否則用這些資源來生產(chǎn)別的產(chǎn)品更為有利，就不在生產(chǎn)計(jì)劃中安排。排，否則用這些資源來生產(chǎn)別的產(chǎn)品更為有利

32、，就不在生產(chǎn)計(jì)劃中安排。這就是單純形表中這就是單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。意義。injjijbxa 1miiijjjyac12021-10-29216 6、一般說、一般說對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估，這種估價(jià)直接涉及資源的最有效利用。價(jià)直接涉及資源的最有效利用。 如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定一些內(nèi)部如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的結(jié)

33、算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的好壞。好壞。 又如在社會(huì)上可對(duì)一些最緊缺的資源，借助影子價(jià)格規(guī)定使又如在社會(huì)上可對(duì)一些最緊缺的資源，借助影子價(jià)格規(guī)定使用這種資源一單位時(shí)必須上繳的利潤(rùn)額，以控制一些經(jīng)濟(jì)效用這種資源一單位時(shí)必須上繳的利潤(rùn)額，以控制一些經(jīng)濟(jì)效益低的企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大益低的企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟(jì)效益。的經(jīng)濟(jì)效益。2021-10-2922第三節(jié)第三節(jié) 對(duì)偶單純形法對(duì)偶單純形法C C C CB B C CN N 0 0C CB BX XB Bb XB B XB B XsC CB BX XB BB B-1-1b b

34、 B B-1-1B B B B-1-1N N B B-1-1I I 0 0 C CN N-C-CB BB B-1-1N -CN -CB BB B-1-1對(duì)于單純形法疊代過程本質(zhì)對(duì)于單純形法疊代過程本質(zhì)：確保：確保1 1）z z變大；變大； 2 2）B B-1-1b b 00由對(duì)偶理論知道，當(dāng)原問題為最優(yōu)解時(shí)，由對(duì)偶理論知道，當(dāng)原問題為最優(yōu)解時(shí)，- -00且且為對(duì)偶問題的最優(yōu)解，為對(duì)偶問題的最優(yōu)解，因此人們提出對(duì)偶單純形法。疊代過程本質(zhì)因此人們提出對(duì)偶單純形法。疊代過程本質(zhì)：1 1） 0 0； 2 2）逐步使）逐步使B B-1-1b b 000|minijaaijj0|min0ijaxaiji與

35、與2021-10-29236 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3st .st .maxmax6 6y y2 2 + y + y3 3 y y4 4= = 2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y y5 51

36、1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 5= = 0 0問題求解問題求解z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3 + 0y+ 0y4 4 + 0y+ 0y5 5 st .st .maxmax-6y-6y2 2 - y - y3 3 + y+ y4 4= =-2-2 -5y -5y1 1 - 2y - 2y2 2 - y - y3 3 + y+ y5 5-1-1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 50 02021-10-29241.1.確

37、定出基變量確定出基變量。在常數(shù)列中找一個(gè)最小的。在常數(shù)列中找一個(gè)最小的負(fù)常量負(fù)常量，把這個(gè)常量所在行作為出基，把這個(gè)常量所在行作為出基變量變量0,miniirbbb 0 0 -6-6 -1 1 0 -1 1 0 -5 -2 -1 -5 -2 -1 0 10 1-2-2-1-1y1 y2 y3 y4 y5bY YB BC CB B-15 -24 -5 -15 -24 -5 0 00 0C Cy4 y50 0-15 -24 -5-15 -24 -5 0 00 0rsssrjrjjjazcaazc0min2. 確定入基變量確定入基變量。在系數(shù)列中找。在系數(shù)列中找負(fù)數(shù)負(fù)數(shù)，把這個(gè)常量所在行作為入基變量

38、。，把這個(gè)常量所在行作為入基變量。2021-10-2925 0 1 1/6 1/6 0 0 1 1/6 1/6 0 -5 0 -2/3 1/3-5 0 -2/3 1/3 1 11/31/3-1/3-1/3 y1 y2 y3 y4 y5bY YB BC CB B-15 -24 -5 -15 -24 -5 0 00 0C C -5/4 1 0 -1/4 1/4 -5/4 1 0 -1/4 1/4 15/2 0 15/2 0 1 1/21 1/2 -3/2 -3/21/41/41/21/2-15 0 -1-15 0 -1 -4 -4 0 0y2 y5-24 0-24 -5y2 y3-15-15/2

39、0 0 -7/2/2 0 0 -7/2 3/2 3/22021-10-2926第四節(jié)第四節(jié) 靈敏度分析靈敏度分析 ),.,2 , 1(0),.,2 , 1(max1njxmibxaxcZjijijnjjj 靈敏度分析是指系統(tǒng)或事物對(duì)周圍環(huán)境變化顯示出來的敏感靈敏度分析是指系統(tǒng)或事物對(duì)周圍環(huán)境變化顯示出來的敏感程度。程度。 在在LPLP問題中，問題中，a aijij、c cj j、b bi i都有可能發(fā)生變化，分析這些變化都有可能發(fā)生變化，分析這些變化對(duì)最優(yōu)解或目標(biāo)值的影響程度就是對(duì)最優(yōu)解或目標(biāo)值的影響程度就是靈敏度分析靈敏度分析。2021-10-2927c cj j通常表示一些估計(jì)或預(yù)測(cè)的數(shù)據(jù)

40、，隨市場(chǎng)而變化；通常表示一些估計(jì)或預(yù)測(cè)的數(shù)據(jù)，隨市場(chǎng)而變化；a aijij通常隨工藝技術(shù)條件的改變而改變；通常隨工藝技術(shù)條件的改變而改變；b bi i則反映了企業(yè)資源狀況。則反映了企業(yè)資源狀況。 CBB-1b C - CBB-1 AB-1 b B-1 A原始數(shù)據(jù)原始數(shù)據(jù)A A，b b，C CA=(A=(P1 P2 Pn ) ) Z Z0= = CBB-1b X XB= = B-1b A = = C - CBB-1 A N = = CN - CBB-1 N j = = Cj- CBB-1 Pj 2021-10-2928b b* *= = B-1 b b 最優(yōu)解的增量最優(yōu)解的增量b b* *與初始

41、與初始b b的增量的增量b b 成成B-1 倍變化倍變化Pj* * = =B-1 Pj最優(yōu)解時(shí)的系數(shù)增量最優(yōu)解時(shí)的系數(shù)增量Pj* * 與初始的系與初始的系數(shù)增量數(shù)增量Pj也成也成B-1 倍變化倍變化最優(yōu)性條件可表達(dá)為：最優(yōu)性條件可表達(dá)為：01NBCCBNN0 bB X-1B2021-10-2929通常需要分析的項(xiàng)目：通常需要分析的項(xiàng)目：(1)(1) 參數(shù)參數(shù)a a，b b，C C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前方案無影響？在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前方案無影響？(2)(2) 參數(shù)參數(shù)b b，b b，c c中的一個(gè)中的一個(gè)( (幾個(gè)幾個(gè)) )變動(dòng)，對(duì)當(dāng)前方案影響程度？變動(dòng)，對(duì)當(dāng)前方案影響程度？(3)(3)

42、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？2021-10-2930靈敏度分析的步驟：靈敏度分析的步驟： 1 1、將參數(shù)的改變通過計(jì)算反映到最終單純形表上來。、將參數(shù)的改變通過計(jì)算反映到最終單純形表上來。 具體計(jì)算方法是，按下列公式計(jì)算出由參數(shù)具體計(jì)算方法是，按下列公式計(jì)算出由參數(shù)a aijij，b bi i，c cj j的的變化而引起的最終單純形表上有關(guān)數(shù)字的變化。變化而引起的最終單純形表上有關(guān)數(shù)字的變化。 2 2、檢查原問題是否仍為可行解。、檢查原問題是否仍為可行解。 3 3、檢查對(duì)偶問題是否仍為可行解。、檢查對(duì)偶問題是否仍為可行解。 4 4、按下表

43、所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。、按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。原問題原問題對(duì)偶問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解問題的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解非可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解用單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算引進(jìn)人工變量，編制新的單純形表重新計(jì)算0ib0j2021-10-2931一、分析一、分析cj的變化的變化 線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù)線性規(guī)

44、劃目標(biāo)函數(shù)中變量系數(shù)c cj j的變化僅僅影響到檢驗(yàn)數(shù)的變化僅僅影響到檢驗(yàn)數(shù)(cj-zj)(cj-zj)的變化。的變化。所以將所以將cjcj的變化直接反映到的變化直接反映到最終單純形表最終單純形表中，只可能出現(xiàn)上頁(yè)中，只可能出現(xiàn)上頁(yè)表中前兩種情況。表中前兩種情況。jjmiijijjzcacc12021-10-2932 例例1-11-1：在美佳公司例子中，：在美佳公司例子中，(1)(1)若家電若家電I I的利潤(rùn)降至的利潤(rùn)降至1.51.5元元/ /件，而家電件，而家電IIII的利潤(rùn)增至的利潤(rùn)增至2 2元元/ /件件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化；時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化；(2)(2)若家

45、電若家電I I的利潤(rùn)不變，則家電的利潤(rùn)不變，則家電IIII的利潤(rùn)在什么范圍內(nèi)變化時(shí)，的利潤(rùn)在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？2021-10-2933 解解 (1)：將家電：將家電I、II的利潤(rùn)變化直接反映到最終單純的利潤(rùn)變化直接反映到最終單純形表中得到表如下：形表中得到表如下：cj1.52000CB基基bx1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/4 因變量因變量x4的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代計(jì)算，的檢驗(yàn)數(shù)大于零，故需繼

46、續(xù)用單純形法迭代計(jì)算，得表如下：得表如下：cj1.52000CB基基bx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2 即美佳公司隨家電即美佳公司隨家電I、II的利潤(rùn)變化應(yīng)調(diào)整為生產(chǎn)的利潤(rùn)變化應(yīng)調(diào)整為生產(chǎn)2件件I，生產(chǎn)生產(chǎn)3件件II。2021-10-2934 (2)：設(shè)家電：設(shè)家電II的利潤(rùn)為的利潤(rùn)為(1+m)元，反映到最終單純形元，反映到最終單純形表中，得表如下：表中，得表如下：cj21+m000CB基基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21+mx23/2

47、010-1/43/2cj-zj000-1/4+1/4m-1/2-3/2m 為使上表中的解為使上表中的解仍為最優(yōu)解仍為最優(yōu)解，應(yīng)有：，應(yīng)有：02321,04141mm解得：解得：131m即家電即家電II的利潤(rùn)的利潤(rùn)c2的變化范圍應(yīng)滿足：的變化范圍應(yīng)滿足：2322 c2021-10-2935二、分析二、分析bi的變化的變化 右端項(xiàng)右端項(xiàng)bibi的變化在實(shí)際問題中反映為可用資源數(shù)量的變化。的變化在實(shí)際問題中反映為可用資源數(shù)量的變化。bibi變化反映到最終單純形表變化反映到最終單純形表上將引起上將引起b b列數(shù)字的變化列數(shù)字的變化，在表中，在表中可能出現(xiàn)第一或第三的兩種情況?？赡艹霈F(xiàn)第一或第三的兩種情

48、況。 出現(xiàn)第一種情況時(shí)，問題的最優(yōu)基不變，變化后的出現(xiàn)第一種情況時(shí)，問題的最優(yōu)基不變，變化后的b b列值為最列值為最優(yōu)解。優(yōu)解。 出現(xiàn)第三種情況時(shí)，用對(duì)偶單純形法迭代繼續(xù)找出最優(yōu)解。出現(xiàn)第三種情況時(shí)，用對(duì)偶單純形法迭代繼續(xù)找出最優(yōu)解。2021-10-2936例例1-21-2：在上述美佳公司例子中，：在上述美佳公司例子中，(1)(1)若設(shè)備若設(shè)備A A和調(diào)試工序的每天能力不變，而設(shè)備和調(diào)試工序的每天能力不變，而設(shè)備B B每天的能力每天的能力增加到增加到32h32h，分析公司最優(yōu)計(jì)劃的變化；，分析公司最優(yōu)計(jì)劃的變化；(2)(2)若設(shè)備若設(shè)備A A和設(shè)備和設(shè)備B B每天可用能力不變，則調(diào)試工序能力在

49、什每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變。么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變。2021-10-2937 解解 (1)(1)：因有：因有 ，則：，則：080b22100802/34/102/14/102/154/511bBb將其反映到最終單純形表中得表如下。由于該表中原問題為將其反映到最終單純形表中得表如下。由于該表中原問題為非可行解非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算，其結(jié)果如下量表所，故用對(duì)偶單純形法繼續(xù)計(jì)算，其結(jié)果如下量表所示：示：2021-10-2938cj21000CB基基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-

50、1/21x2-1/2010-1/43/2cj-zj000-1/4-1/2對(duì)偶單純形法處理后結(jié)果：對(duì)偶單純形法處理后結(jié)果：cj21000CB基基bx1x2x3x4x50 x315051002x15110010 x420-401-6cj-zj0-100-2由此美佳公司的最優(yōu)計(jì)劃改變?yōu)橹簧a(chǎn)由此美佳公司的最優(yōu)計(jì)劃改變?yōu)橹簧a(chǎn)5件家電件家電I。2021-10-2939 (2)(2)：設(shè)調(diào)式工序每天可用能力為設(shè)調(diào)式工序每天可用能力為(5+m)h(5+m)h，因有，因有mmmmbBb2321215002/34/102/14/102/154/511將其反映到最終單純形表中，其將其反映到最終單純形表中，其b

51、b列數(shù)字為：列數(shù)字為：mmmb23232127215215當(dāng)當(dāng)b=0b=0時(shí)問題的最優(yōu)基不變，解得時(shí)問題的最優(yōu)基不變，解得-1=m=1-1=m=1。由此調(diào)試工序。由此調(diào)試工序的能力應(yīng)在的能力應(yīng)在4h-6h4h-6h之間。之間。2021-10-2940三、增加一個(gè)變量三、增加一個(gè)變量xj的分析的分析 增加一個(gè)變量在實(shí)際問題中反映為增加一種新的產(chǎn)品。其分增加一個(gè)變量在實(shí)際問題中反映為增加一種新的產(chǎn)品。其分析步驟為：析步驟為： 1 1、計(jì)算、計(jì)算 2 2、計(jì)算、計(jì)算 3 3、若、若 ，原最優(yōu)解不變，只需將計(jì)算得到的，原最優(yōu)解不變，只需將計(jì)算得到的 和和 直接直接寫入最終單純形表中；若寫入最終單純形表

52、中；若 ，則按單純形法繼續(xù)迭代計(jì)算，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。找出最優(yōu)。 例例1-31-3：在美佳公司例子中，設(shè)該公司又計(jì)劃推出新型號(hào)的：在美佳公司例子中，設(shè)該公司又計(jì)劃推出新型號(hào)的家電家電IIIIII，生產(chǎn)一件所需設(shè)備，生產(chǎn)一件所需設(shè)備A A、B B及調(diào)試工序的時(shí)間分別為及調(diào)試工序的時(shí)間分別為3h3h、4h4h、2h2h，該產(chǎn)品的預(yù)期盈利為，該產(chǎn)品的預(yù)期盈利為3 3元元/ /件，試分析該種產(chǎn)品是否值件，試分析該種產(chǎn)品是否值得投產(chǎn)；若投產(chǎn)，該公司的最優(yōu)生產(chǎn)計(jì)劃有何變化。得投產(chǎn)；若投產(chǎn)，該公司的最優(yōu)生產(chǎn)計(jì)劃有何變化。miiijjjjjyaczc1jjPBP10jjPj0j2021-10-

53、2941 解解 設(shè)該公司生產(chǎn)設(shè)該公司生產(chǎn)x6x6件家電件家電IIIIII，有，有c6=3c6=3，P6=(3,4,2)P6=(3,4,2)T T2072432/34/102/14/102/154/516P將其反映到最終單純形表中得表如下將其反映到最終單純形表中得表如下: :1243)21,41,0(362021-10-2942因因 ，故用單純形法繼續(xù)迭代計(jì)算結(jié)果為：，故用單純形法繼續(xù)迭代計(jì)算結(jié)果為：cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/2106c

54、j210003CB基bx1x2x3x4x5x60 x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40由上表可知，美佳公司新的最優(yōu)生產(chǎn)計(jì)劃應(yīng)該為每天生產(chǎn)由上表可知，美佳公司新的最優(yōu)生產(chǎn)計(jì)劃應(yīng)該為每天生產(chǎn)7/27/2件家電件家電I I，51/451/4件家電件家電IIIIII。2021-10-2943四、分析參數(shù)四、分析參數(shù)aij的變化的變化 a aijij的變化使線性規(guī)劃的約束系數(shù)矩陣的變化使線性規(guī)劃的約束系數(shù)矩陣A A發(fā)生變化。發(fā)生變化。 若變量若變量x xj j在最終單純形表中為基變量，則在最

55、終單純形表中為基變量，則a aijij的變化分析步驟的變化分析步驟可參照本節(jié)之三；可參照本節(jié)之三； 若變量若變量x xj j在最終單純形表中為基變量，則在最終單純形表中為基變量，則a aijij的變化將使相應(yīng)的變化將使相應(yīng)的的B B和和B B-1-1發(fā)生變化，因此有可能出現(xiàn)原問題和對(duì)偶問題均為非發(fā)生變化，因此有可能出現(xiàn)原問題和對(duì)偶問題均為非可行解的情況。出現(xiàn)這種情況時(shí)，需引進(jìn)人工變量先將原問題可行解的情況。出現(xiàn)這種情況時(shí)，需引進(jìn)人工變量先將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解。的解轉(zhuǎn)化為可行解，再用單純形法求解。 例例1-41-4：在美佳公司的例子中，若家電：在美佳公司的例子中，若家電II

56、II每件需設(shè)備每件需設(shè)備A A、B B和和調(diào)試工時(shí)變?yōu)檎{(diào)試工時(shí)變?yōu)?h8h、4h4h、1h1h，該產(chǎn)品的利潤(rùn)變?yōu)椋摦a(chǎn)品的利潤(rùn)變?yōu)? 3元元/ /件，試重新件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃。確定該公司最優(yōu)生產(chǎn)計(jì)劃。2021-10-2944 解解 先將生產(chǎn)工時(shí)變化后的新家電先將生產(chǎn)工時(shí)變化后的新家電IIII看作是一種新產(chǎn)品，看作是一種新產(chǎn)品，生產(chǎn)量生產(chǎn)量x x2 2，仿上一節(jié)的步驟直接計(jì)算，仿上一節(jié)的步驟直接計(jì)算 和和 并反映到最終并反映到最終單純形表中。其中：?jiǎn)渭冃伪碇小Ｆ渲校?/12/12/111482/34/102/14/102/154/512P將其反映到最終單純形表中得表如下。將其反映到

57、最終單純形表中得表如下。22P2/3148)2/1 ,4/1 ,0(322021-10-2945 因因x2x2已變換為已變換為x2x2，故用單純形算法將，故用單純形算法將x2x2替換出基變量替換出基變量中的中的x2x2，并在下一個(gè)表中不再保留，并在下一個(gè)表中不再保留x2x2，得表如下：，得表如下：cj213000CB基基bx1x2x2x3x4x50 x315/20011/215/4-15/22x17/2101/201/4-1/21x23/2011/20-1/43/2cj-zj003/20-1/4-1/2cj23000CB基基bx1x2x3x4x50 x3-90014-242x121001/2-23x23010-1/23cj-zj00