運籌學-第二章線性規(guī)劃對偶理論與靈敏度分析_胡運權

1、例一例一 美佳公司計劃制造美佳公司計劃制造、兩種家電產品。已知各制造一件時分別占用的設兩種家電產品。已知各制造一件時分別占用的設備備A A、B B的臺時、調試時間及的臺時、調試時間及A A、B B設備和調試工序每天可用于這兩種家電的能力、設備和調試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如下表所示。問該公司應制造各售出一件時的獲利情況如下表所示。問該公司應制造、兩種家電備多少兩種家電備多少件使獲取的利潤為最大。件使獲取的利潤為最大。設：設： x x1 1 A A產品的生產量產品的生產量 x x2 2 B B產品的生產量產品的生產量利潤利潤 z= 2 xz= 2 x1 1 + x

2、+ 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 .5 5x x2 2 + + 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 .利潤利潤 max z= 2 xmax z= 2 x1 1 +

3、x + x2 2 + 0 x+ 0 x3 3 + 0 x + 0 x4 4 + 0 x + 0 x5 5 一、標準化一、標準化二、寫出初始單純形表（二、寫出初始單純形表（必定存在有單位矩陣必定存在有單位矩陣）C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 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)解檢驗（唯一解、無限多解、無界

4、解和無解唯一解、無限多解、無界解和無解）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 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 -

5、1/4 -1/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 0約束約束條件條件把解把解X=(7/2,3/2)X=(7/2,3/2)代入原問題代入原問題( (因為因為為附加變量為附加變量) )四、分析四、分析5 53 32 215/215/224245 5P O 一個問題？一個問題？ 市場上設備市場上設備A A、設備設備B B和調試工序每小時值多少錢？和調試工序每小時值多少錢？在什么價位時，才能使美佳公司愿意出讓自己的資源？在什么價位時，才能使美佳公司愿意出讓自己的資源？6 6y

6、 y2 2 + y + y3 3分分析析設：設： y y1 1 設備設備A A值的值的價值價值 y y2 2 設備設備B B值的值的價值價值 y y3 3 調試工序調試工序值的值的價值價值2 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3總價值總價值minminy y1 1 , y , y2 2 , y , y3 30 0st .st .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15

7、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 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

8、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-15 8M-24 2M-5 -M -M 0 0問題求解問題求解6 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

9、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 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 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y y2 2

10、y 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, Y=(0, , , , 0, 0) , 0, 0)z z=-17/2=-17/2z z = 17/2= 17/2問題求解問題求解Y=(0, Y=(0, , , , 0, 0 ) , 0, 0 )問題分析問題分析問題問題的解的解6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y

11、3 31 1z= 15yz= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .問題：問題：原問題：原問題：利潤利潤 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 .問題問題的解的解X X* *=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)Z Z* *= 17/2

12、= 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= =結結論論估價估價影子價格影子價格（即增加單位資源所（即增加單位資源所得到的貢獻）得到的貢獻）Z= =CTX=YT b Z/ b=(YTb) =YT對偶規(guī)則對偶規(guī)則 變量、約束與系數(shù)變量、約束與系數(shù)&原問題有原問題有m m個約束條件，對偶問題有個約束條件，對偶問題有m m個變量個變量&原問題有原問題有n n個變量，對偶問題有個變量，對偶問題有n n個

13、約束條件個約束條件&原問題的價值系數(shù)對應對偶問題的右端項原問題的價值系數(shù)對應對偶問題的右端項&原問題的右端項對應對偶問題的價值系數(shù)原問題的右端項對應對偶問題的價值系數(shù)&原問題的技術系數(shù)矩陣轉置后為對偶問題系數(shù)矩陣原問題的技術系數(shù)矩陣轉置后為對偶問題系數(shù)矩陣C 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/

14、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利潤利潤 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 .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 3

15、minminy 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-24-24-5-5y y2 2y y3 31/41/41/21/2 -5/4 1 0 -1/4 -5/4 1 0 -1/4 1/41/4 15/2 0 1 15/2 0 1 1/2 -1/2 -3/2 3/2 -15/2 0 0 -7/2 -15/2 0 0 -7/2 -3/23/2- - 15/2 0 0 7/2 15/2 0 0 7/2 3/2 3/2 Y=(0, Y=(0, , ,

16、 , 0, 0 ) , 0, 0 )X X* *=(7/2,3/2, 15/2,0,0)=(7/2,3/2, 15/2,0,0)問題變量問題變量問題剩余松弛變量問題剩余松弛變量解的關系解的關系一、線性規(guī)劃的對偶問題一、線性規(guī)劃的對偶問題1、對偶問題定義、對偶問題定義X X 0 0st.st.AX AX b bmax z =max z = C CT TX X其中：其中： C= C=（c c1 1，c c2 2, , ,c ,cn n) )T T 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

17、Y= Y=（y y1 1，y y2 2, , ,y ,ym m) )T TY Y 0 0st.st.A AT TY CY Cmin w =min w = Y YT Tb b利潤利潤 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 .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz= 15y1 1 + 24y + 24

18、y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .一、線性規(guī)劃的對偶問題一、線性規(guī)劃的對偶問題x x1 1 0, x 0, x2 2 0, x 0, x3 3無約束無約束 st.st.a a1111x 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 x

19、1 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 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

20、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 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

21、 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+ 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 3

22、y 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 + + a a2323y y2 2 + + a a3333y y3 3 = c= c3 3st.st.y y1 10, y0, y2 2無約束無約束，y y3 3 0 0對偶規(guī)則對偶規(guī)則 變量與約束對應關系變量與約束對應關系原問題（對偶問題）原問題（對偶問題）對偶問題（原問題）對偶問題（原問題） max z=CTX AX ( ) b

23、X ( ) 0 或無約束或無約束 min w=YTb ATY ( ) C Y ( ) 0 或無約束或無約束 有有n個決策變量個決策變量 xj (j0、2n) xj 0 0變量變量 xj 0 0 xj 無約束無約束 有有n個約束條件個約束條件 對應的約束為對應的約束為 約束約束 對應的約束為對應的約束為 對應的約束為對應的約束為 有有m個約束條件個約束條件 對應的約束為對應的約束為 約束約束 對應的約束為對應的約束為 對應的約束為對應的約束為 有有m個決策變量個決策變量 yj (j0、2m) yj 0 0變量變量 yj 0 0 yj 無約束無約束0,01038576534max212121212

24、1xxxxxxxxxxZ3 ,2 ,1,03324751086min321321321iyyyyyyyyyywi0,15744325min321321321321xxxxxxxxxxxxZ0,035275434max2121212121yyyyyyyyyyZ0,0,無約束1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ無約束,0,095485862127141018max321213132131321yyyyyyyyyyyyyyyw對偶問題性質證明的幾個重要內容對偶問題性質證明的幾個重要內容X X 0 0st.st.AX AX b b

25、max z = Cmax z = CT TX XX, Xs 0X, Xs 0st.st.AX + IXs AX + IXs = = b bmax z = Cmax z = CT TX + 0XsX + 0XsC C C CT 0 0C CB BX XB Bb X Xs0 0X Xs sb b A IA IC C C CB BT T C CN NT T 0 0C CB BX XB Bb XB XN Xs0 0X Xs sb b B N IB N IC C C CB BT T C CN NT T 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B

26、-1-1B B B B-1-1N N B B-1-1I IC CB BT T-C-CB BT TB B-1-1B B C CN NT T-C-CB BT TB B-1-1N 0-CN 0-CB BT TB B-1-1I I C C C CB BT T C CN NT T 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 NT T-C-CB BT TB B-1-1N -CN -CB BT TB B-1-1對偶問題性質證明的幾個重要內容對偶問題性質證明的幾個重要內容X

27、X 0 0st.st.AX AX b bmax z = Cmax z = CT TX XY 0Y 0st.st.A AT TY CY Cmin w = Ymin w = YT Tb bC C C CB B C CN N 0 0C CB BX XB Bb XB B XN N 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 BT T-C-CB BT TB B-1-1B B C CN NT T-C-CB BT TB B-1-1N -CN -CB BT TB B-1-1原問題為最優(yōu)解原問題為最優(yōu)解00，即：即：C CB BT

28、T-C-CB BT TB B-1-1B B 00C CN NT T-C-CB BT TB B-1-1N N 00 -C -CB BT TB B-1 -1 00C CT T - C - CB BT TB B-1-1A A00令令Y YT T= = C CB BT TB B-1-1, ,則有：則有： C CB BT TB B-1 -1 0 0A AT TY CY Cw = w = Y YT Tb b = C = CB BT TB B-1-1b = z b = z 即此時原問題與對偶問題的解的值是相等的。即此時原問題與對偶問題的解的值是相等的。則可以得到：則可以得到：對偶問題的基本性質（對稱形）對偶

29、問題的基本性質（對稱形）1對稱性：對偶問題的對偶問題是原問題1弱對偶性：極大化原問題的任一可行解的目標函數(shù)值，不大于其對偶問題任意可行解的目標函數(shù)值1對偶定理：若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標函數(shù)值相等。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-11無界性：原問題無界，對偶問題無可行解需要說明的是：需要說明的是：這些性質同樣適用于非對稱形問題這些性質同樣適用于非對稱形問題影子價格影子價格 從上節(jié)對偶問題的基本性質可以看出，當線性規(guī)劃原問題求得最優(yōu)從上節(jié)對偶問題的基本性質可以看出，當線性規(guī)劃原問題求得最優(yōu)解解xjxj* *(j=1,n)(j=1,n)時，其對偶問題也得到

30、最優(yōu)解時，其對偶問題也得到最優(yōu)解yiyi* *(i=1,.,m)(i=1,.,m)，且代入，且代入各自的目標函數(shù)后有：各自的目標函數(shù)后有：*1*1*miiinjjjybxcz式中式中bibi是線性規(guī)劃原問題約束條件的右端項，它代表第是線性規(guī)劃原問題約束條件的右端項，它代表第i i種資源的擁有種資源的擁有量；對偶變量量；對偶變量yiyi* *的意義代表在資源最優(yōu)利用條件下對單位第的意義代表在資源最優(yōu)利用條件下對單位第i i種資源的種資源的估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產中作出的貢估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產中作出的貢獻而做的估價，為區(qū)別起見，稱為獻而做

31、的估價，為區(qū)別起見，稱為影子價格影子價格(shadow price)(shadow price)。 1 1、資源的市場價格是其價值的客觀體現(xiàn)，相對比較穩(wěn)定，而它的影、資源的市場價格是其價值的客觀體現(xiàn)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況。因企業(yè)生產任務、產品結構等情況發(fā)子價格則有賴于資源的利用情況。因企業(yè)生產任務、產品結構等情況發(fā)生變化，資源的影子價格也隨之改變。生變化，資源的影子價格也隨之改變。 2 2、影子價格是一種邊際價格，若對式中目標函數(shù)、影子價格是一種邊際價格，若對式中目標函數(shù)z z求求bibi的偏導數(shù)可的偏導數(shù)可得得 。這說明這說明yiyi* *的值相當于在資源得到最

32、優(yōu)利用的生產條件下，的值相當于在資源得到最優(yōu)利用的生產條件下，bibi每增加一每增加一個單位時目標函數(shù)個單位時目標函數(shù)z z的增量。的增量。 */iiybz 3 3、資源的影子價格實際上又是一種機會成本。、資源的影子價格實際上又是一種機會成本。在完全市場經(jīng)濟條件下，當?shù)谠谕耆袌鼋?jīng)濟條件下，當?shù)? 2種資源的市場價格低于影子價格時，可以種資源的市場價格低于影子價格時，可以買進這種資源；相反，當市場價格高于影子價格時，就會賣出這種資源。買進這種資源；相反，當市場價格高于影子價格時，就會賣出這種資源。隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格隨著資源的買進賣出，它的影子價格也

33、將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。與市場價格保持同等水平時，才處于平衡狀態(tài)。 4 4、在對偶問題的互補松弛性質中有、在對偶問題的互補松弛性質中有 時，時，yi=0yi=0；當；當yi0yi0時，時，有有 ，這表明生產過程中如果某種資源，這表明生產過程中如果某種資源bibi未得到充分利用未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產中已耗費完畢。該種資源在生產中已耗費完畢。injijbxa1injjijbxa 1影子價格影子價格 5 5、當產品產值大于隱含成

34、本時，表明生產該產品有利，可在計劃、當產品產值大于隱含成本時，表明生產該產品有利，可在計劃中安排，否則用這些資源來生產別的產品更為有利，就不在生產計劃中中安排，否則用這些資源來生產別的產品更為有利，就不在生產計劃中安排。這就是單純形表中各個檢驗數(shù)的經(jīng)濟意義。安排。這就是單純形表中各個檢驗數(shù)的經(jīng)濟意義。 6 6、一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而、一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當估價，這種估價直接涉及資對于對偶問題的求解則是確定對資源的恰當估價，這種估價直接涉及資源的最有效利用。如在一個大公司內部，可借助資源的影子價

35、格確定一源的最有效利用。如在一個大公司內部，可借助資源的影子價格確定一些內部結算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。些內部結算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。又如在社會上可對一些最緊缺的資源，借助影子價格規(guī)定使用這種資源又如在社會上可對一些最緊缺的資源，借助影子價格規(guī)定使用這種資源一單位時必須上繳的利潤額，以控制一些經(jīng)濟效益低的企業(yè)自覺地節(jié)約一單位時必須上繳的利潤額，以控制一些經(jīng)濟效益低的企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟效益。使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟效益。對偶單純形法對偶單純形法C C C CB B C CN N 0 0

36、C CB BX XB Bb XB B XB B 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-1對于單純形法疊代過程本質對于單純形法疊代過程本質：1 1）確保）確保z z變大；變大； 2 2）B B-1-1b b 00由對偶理論知道，當原問題為最優(yōu)解時，由對偶理論知道，當原問題為最優(yōu)解時，- -00且且為對偶問題的最優(yōu)解，因此人們提出對為對偶問題的最優(yōu)解，因此人們提出對偶單純形法。疊代過程本質偶單純形法。疊代過程本質：1 1） 0 0； 2 2

37、）逐步使）逐步使B B-1-1b b 000|minijaaijjmin|0iijbijaa與與區(qū)別：區(qū)別：6 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 3 y y4 4= = 2 25

38、 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-15 8M-24 2M-5 -

39、M -M 0 0問題求解問題求解6 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 3 y y4 4= = 2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y y5

40、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 00 0C CB BY YB Bb y1 y2 y3 y4 y52 21 1 0 6 1 -1 0 0 6 1 -1 0 5 2 5 2 1 1 0 -10 -1問題求解問題求解-2-2-1-1 0 -6 -1 1 0 0 -6 -1 1 0 -5 -2 -5 -2 -1 1 0 10 1y4 y50 0-15 -24 -5-15 -24 -5 0 00 0C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY Y

41、B Bb b y1 y2 y3 y4 y51/31/3-1/3-1/3 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/41/41/21/2 -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/2-15 0 -1-15 0 -1 -4 -4 0 0y2 y5-24 0-24 -5y2 y3-15-15/2 0 0 -7/2/2 0 0 -7/2 3/23/20|minijaaijj二、靈敏度分析 ),.,2 , 1(0),.,2 , 1(

42、max1njxmibxaxcZjijijnjjj 靈敏度分析是指系統(tǒng)或事物對周圍環(huán)境變化顯靈敏度分析是指系統(tǒng)或事物對周圍環(huán)境變化顯示出來的敏感程度示出來的敏感程度 在在LP問題中，問題中，aij、cj、bi都有可能發(fā)生變化，都有可能發(fā)生變化，分析這些變化對最優(yōu)解或目標值的影響程度就是靈分析這些變化對最優(yōu)解或目標值的影響程度就是靈敏度分析。敏度分析。二、靈敏度分析 c cj j通常表示一些估計或預測的數(shù)據(jù)，隨市場變化；通常表示一些估計或預測的數(shù)據(jù)，隨市場變化； a aijij通常隨工藝技術條件的改變而改變；通常隨工藝技術條件的改變而改變； b bi i則反映了企業(yè)資源狀況。則反映了企業(yè)資源狀況。

43、 C CB BT T B B-1-1b Cb CT T - C- CB BT TB B-1 -1 A AB B-1 -1 b Bb B-1 -1 A A原始數(shù)據(jù)原始數(shù)據(jù)A A，b b，C CA=(PA=(P1 1 P P2 2 P Pn n ) )公式公式 Z Z0 0= C= CB BT TB B-1-1b Xb XB B= B= B-1-1b b A A = C= CT T - C- CB BT TB B-1 -1 A A N N = C= CN N T T- C- CB BT TB B-1 -1 N N j j = C= Cj jT T- C- CB BT TB B-1 -1 P Pj

44、j 二、靈敏度分析b b* *= = B B-1 -1 b b 最優(yōu)解的增量最優(yōu)解的增量b b* *與初始與初始b b的增量的增量b b 成成B B-1 -1 倍變化倍變化P Pj j* * = =B B-1 -1 P Pj j最優(yōu)解時的系數(shù)增量最優(yōu)解時的系數(shù)增量P Pj j* * 與初始的系數(shù)增量與初始的系數(shù)增量P Pj j也成也成B B-1 -1 倍變化倍變化最優(yōu)性條件可表達為：最優(yōu)性條件可表達為：-1B1X B b 00TTNNBCCB N二、靈敏度分析通常需要分析的項目：通常需要分析的項目：(1)(1)、參數(shù)、參數(shù)a a，b b，C C在什么范圍內變動，對當前方案在什么范圍內變動，對當

45、前方案無影響？無影響？(2)(2)、參數(shù)、參數(shù)a a，b b，c c中的一個中的一個( (幾個幾個) )變動，對當前方變動，對當前方案影響程度？案影響程度？(3)(3)、如果最優(yōu)方案改變，如何用簡便方法求新方、如果最優(yōu)方案改變，如何用簡便方法求新方案？案？二、靈敏度分析靈敏度分析的步驟可歸納如下：靈敏度分析的步驟可歸納如下： 1 1、將參數(shù)的改變通過計算反映到最終單純形表上來。、將參數(shù)的改變通過計算反映到最終單純形表上來。 具體計算方法是，按下列公式計算出由參數(shù)具體計算方法是，按下列公式計算出由參數(shù)a aijij，b bi i，c cj j的的變化而引起的最終單純形表上有關數(shù)字的變化。變化而引

46、起的最終單純形表上有關數(shù)字的變化。 2 2、檢查原問題是否仍為可行解。、檢查原問題是否仍為可行解。 3 3、檢查對偶問題是否仍為可行解。、檢查對偶問題是否仍為可行解。 4 4、按下表所列情況得出結論或決定繼續(xù)計算的步驟。、按下表所列情況得出結論或決定繼續(xù)計算的步驟。原問題對偶問題結論或繼續(xù)計算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量，編制新的單純形表重新計算5 5x x2 2 + + x x3 3 = = 15 156 6x x1 1 + 2x + 2x2 2 + x+ x4 4

47、= = 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 .利潤利潤 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 一、標準化一、標準化二、寫出初始單純形表（二、寫出初始單純形表（必定存在有單位矩陣必定存在有單位矩陣）C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 0 0 x x3

48、 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 b x x1 1 x x2 2 x x3 3 x x4 4 x x5 50 0 2 2

49、 x x3 3 x x1 1 x x2 215/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 0 0 00 0 0 -1/4 -1/2 -1/4 -1/2 二、靈敏度分析1、分析、分析cj的變化的變化 線性規(guī)劃目標函數(shù)中變量系數(shù)線性規(guī)劃目標函數(shù)中變量系數(shù)c cj j的變化僅僅影響到檢驗數(shù)的變化僅僅影響到檢驗數(shù)(c(cj j-z-zj j) )的變化。所以將的變化。所以將c cj j的變化直接反映到最終單純形表中，的變化直接反

50、映到最終單純形表中，只可能出現(xiàn)上頁表中前兩種情況。只可能出現(xiàn)上頁表中前兩種情況。 下面舉例說明：下面舉例說明： 例：在第一章例例：在第一章例I I的美佳公司例子中，的美佳公司例子中，(1)(1)若家電若家電I I的利潤降至的利潤降至1.51.5元元/ /件，而家電件，而家電IIII的利潤增至的利潤增至2 2元元/ /件時，美佳公司最優(yōu)生產計劃有何變化；件時，美佳公司最優(yōu)生產計劃有何變化；(2)(2)若家電若家電I I的利潤不變，則家電的利潤不變，則家電IIII的利潤在什么范圍內變化的利潤在什么范圍內變化時，該公司的最優(yōu)生產計劃將不發(fā)生變化？時，該公司的最優(yōu)生產計劃將不發(fā)生變化？二、靈敏度分析

51、解解 (1)將家電將家電I、II的利潤變化直接反映到最終單純形的利潤變化直接反映到最終單純形表中得到表如下：表中得到表如下：cj1.52000CB基bx1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/4 因變量因變量x4的檢驗數(shù)大于零，故需繼續(xù)用單純形法迭代的檢驗數(shù)大于零，故需繼續(xù)用單純形法迭代計算，得表如下：計算，得表如下：cj1.52000CB基bx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2 即美佳公司

52、隨家電即美佳公司隨家電I、II的利潤變化應調整為生產的利潤變化應調整為生產2件件I，生產生產3件件II。二、靈敏度分析 (2)設家電設家電II的利潤為的利潤為(1+m)元，反映到最終單純形表元，反映到最終單純形表中，得表如下：中，得表如下：cj21+m000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21+mx23/2010-1/43/2cj-zj000-1/4+1/4m-1/2-3/2m 為使上表中的解仍為最優(yōu)解，應有：為使上表中的解仍為最優(yōu)解，應有：02321,04141mm解得：解得：131m即家電即家電II的利潤的利潤c2的變化范圍應

53、滿足：的變化范圍應滿足：2322 c二、靈敏度分析2、分析、分析bj的變化的變化 右端項右端項b bi i的變化在實際問題中反映為可用資源數(shù)量的變化。的變化在實際問題中反映為可用資源數(shù)量的變化。b bi i變化反映到最終單純形表上將引起變化反映到最終單純形表上將引起b b列數(shù)字的變化，在表列數(shù)字的變化，在表2-92-9中可能出現(xiàn)第一或第三的兩種情況。出現(xiàn)第一種情況時，中可能出現(xiàn)第一或第三的兩種情況。出現(xiàn)第一種情況時，問題的最優(yōu)基不變，變化后的問題的最優(yōu)基不變，變化后的b b列值為最優(yōu)解。出現(xiàn)第三種列值為最優(yōu)解。出現(xiàn)第三種情況時，用對偶單純形法迭代繼續(xù)找出最優(yōu)解。情況時，用對偶單純形法迭代繼續(xù)找

54、出最優(yōu)解。 下面舉例說明：下面舉例說明： 例：在上述美佳公司例子中，例：在上述美佳公司例子中，(1)(1)若設備若設備A A和調試工序的每天能力不變，而設備和調試工序的每天能力不變，而設備B B每天的能每天的能力增加到力增加到32h32h，分析公司最優(yōu)計劃的變化；，分析公司最優(yōu)計劃的變化；(2)(2)若設備若設備A A和設備和設備B B每天可用能力不變，則調試工序能力在每天可用能力不變，則調試工序能力在什么范圍內變化時，問題的最優(yōu)基不變。什么范圍內變化時，問題的最優(yōu)基不變。二、靈敏度分析 解解 (1)(1)因有因有 ，則：，則：080b22100802/34/102/14/102/154/51

55、1bBb將其反映到最終單純形表中得表如下。由于該表中將其反映到最終單純形表中得表如下。由于該表中原問題為非可行解，故用對偶單純形法繼續(xù)計算，原問題為非可行解，故用對偶單純形法繼續(xù)計算，其結果如下量表所示：其結果如下量表所示：二、靈敏度分析cj21000CB基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2cj-zj000-1/4-1/2對偶單純形法處理后結果：對偶單純形法處理后結果：cj21000CB基bx1x2x3x4x50 x315051002x15110010 x420-401-6cj-zj0-100-2由此

56、美佳公司的最優(yōu)計劃改變?yōu)橹簧a由此美佳公司的最優(yōu)計劃改變?yōu)橹簧a5件家電件家電I。二、靈敏度分析 (2)(2)設調式工序每天可用能力為設調式工序每天可用能力為(5+m)h(5+m)h，因有，因有mmmmbBb2321215002/34/102/14/102/154/511將其反映到最終單純形表中，其將其反映到最終單純形表中，其b b列數(shù)字為：列數(shù)字為：mmmb23232127215215當當b=0b=0時問題的最優(yōu)基不變，解得時問題的最優(yōu)基不變，解得-1=m=1-1=m=1。由此調試工序。由此調試工序的能力應在的能力應在4h-6h4h-6h之間。之間。二、靈敏度分析3、增加一個變量、增加一個變

57、量xj的分析的分析 增加一個變量在實際問題中反映為增加一種新的產品。增加一個變量在實際問題中反映為增加一種新的產品。其分析步驟為：其分析步驟為： 1 1、計算、計算 2 2、計算、計算 3 3、若、若 ，原最優(yōu)解不變，只需將計算得到的，原最優(yōu)解不變，只需將計算得到的 和和 直直接寫入最終單純形表中；若接寫入最終單純形表中；若 ，則按單純形法繼續(xù)迭代，則按單純形法繼續(xù)迭代計算找出最優(yōu)。計算找出最優(yōu)。 例：在美佳公司例子中，設該公司又計劃推出新型號的家例：在美佳公司例子中，設該公司又計劃推出新型號的家電電IIIIII，生產一件所需設備，生產一件所需設備A A、B B及調試工序的時間分別為及調試工序

58、的時間分別為3h3h、4h4h、2h2h，該產品的預期盈利為，該產品的預期盈利為3 3元元/ /件，試分析該種產品是否件，試分析該種產品是否值得投產；若投產，該公司的最優(yōu)生產計劃有何變化。值得投產；若投產，該公司的最優(yōu)生產計劃有何變化。miiijjjjjyaczc1jjPBP10jjPj0j二、靈敏度分析 解解 設該公司生產設該公司生產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(3

59、6二、靈敏度分析因因 ，故用單純形法繼續(xù)迭代計算結果為：，故用單純形法繼續(xù)迭代計算結果為：cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/2106cj210003CB基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)生產計劃應該為每天生產由上表可知，美佳公司新的最優(yōu)生產計劃應該為每天生產7/27/2

60、件家電件家電I I，51/451/4件家電件家電IIIIII。二、靈敏度分析4、分析參數(shù)、分析參數(shù)aij的變化的變化aij的變化使線性規(guī)劃的約束系數(shù)矩陣的變化使線性規(guī)劃的約束系數(shù)矩陣A A發(fā)生變化。發(fā)生變化。若變量若變量x xj j在最終單純形表中為非基變量，則在最終單純形表中為非基變量，則a aijij的變化分析步的變化分析步驟可參照本節(jié)之三；若變量驟可參照本節(jié)之三；若變量x xj j在最終單純形表中為基變量，在最終單純形表中為基變量，則則aijaij的的 變化將使相應的變化將使相應的B B和和B B-1-1發(fā)生變化，因此有可能出現(xiàn)發(fā)生變化，因此有可能出現(xiàn)原問題和對偶問題均為非可行解的情況。