運(yùn)籌學(xué)-第二章線性規(guī)劃對(duì)偶理論與靈敏度分析_胡運(yùn)權(quán)

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í)的獲利情況如下表所示。問該公司應(yīng)制造各售出一件時(shí)的獲利情況如下表所示。問該公司應(yīng)制造、兩種家電備多少兩種家電備多少件使獲取的利潤為最大。件使獲取的利潤為最大。設(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)量利潤利潤 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 一、標(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 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àn)（三、最優(yōu)解檢驗(yàn)（唯一解、無限多解、無界

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)代入原問題代入原問題( (因?yàn)橐驗(yàn)闉楦郊幼兞繛楦郊幼兞? )四、分析四、分析5 53 32 215/215/224245 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í)，才能使美佳公司愿意出讓自己的資源？6 6y

6、 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 + 5y+ 5y3 3總價(jià)值總價(jià)值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 .問題：?jiǎ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 .問題問題的解的解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= =結(jié)結(jié)論論估價(jià)估價(jià)影子價(jià)格影子價(jià)格（即增加單位資源所（即增加單位資源所得到的貢獻(xiàn)）得到的貢獻(xiàn)）Z= =CTX=YT b Z/ b=(YTb) =YT對(duì)偶規(guī)則對(duì)偶規(guī)則 變量、約束與系數(shù)變量、約束與系數(shù)&原問題有原問題有m m個(gè)約束條件，對(duì)偶問題有個(gè)約束條件，對(duì)偶問題有m m個(gè)變量個(gè)變量&原問題有原問題有n n個(gè)變量，對(duì)偶問題有個(gè)變量，對(duì)偶問題有n n個(gè)

13、約束條件個(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ù)系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問題系數(shù)矩陣原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問題系數(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ān)系解的關(guān)系一、線性規(guī)劃的對(duì)偶問題一、線性規(guī)劃的對(duì)偶問題1、對(duì)偶問題定義、對(duì)偶問題定義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ī)劃的對(duì)偶問題一、線性規(guī)劃的對(duì)偶問題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對(duì)偶規(guī)則對(duì)偶規(guī)則 變量與約束對(duì)應(yīng)關(guān)系變量與約束對(duì)應(yīng)關(guān)系原問題（對(duì)偶問題）原問題（對(duì)偶問題）對(duì)偶問題（原問題）對(duì)偶問題（原問題） max z=CTX AX ( ) b

23、X ( ) 0 或無約束或無約束 min w=YTb 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è)約束條件個(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 無約束無約束0,01038576534max212121212

24、1xxxxxxxxxxZ3 ,2 ,1,03324751086min321321321iyyyyyyyyyywi0,15744325min321321321321xxxxxxxxxxxxZ0,035275434max2121212121yyyyyyyyyyZ0,0,無約束1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ無約束,0,095485862127141018max321213132131321yyyyyyyyyyyyyyyw對(duì)偶問題性質(zhì)證明的幾個(gè)重要內(nèi)容對(duì)偶問題性質(zhì)證明的幾個(gè)重要內(nèi)容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對(duì)偶問題性質(zhì)證明的幾個(gè)重要內(nèi)容對(duì)偶問題性質(zhì)證明的幾個(gè)重要內(nèi)容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 即此時(shí)原問題與對(duì)偶問題的解的值是相等的。即此時(shí)原問題與對(duì)偶問題的解的值是相等的。則可以得到：則可以得到：對(duì)偶問題的基本性質(zhì)（對(duì)稱形）對(duì)偶

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

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

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

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

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

34、本時(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)品更為有利，就不在生產(chǎn)計(jì)劃中安排。這就是單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。安排。這就是單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。 6 6、一般說對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而、一般說對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)

35、格確定一源的最有效利用。如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。又如在社會(huì)上可對(duì)一些最緊缺的資源，借助影子價(jià)格規(guī)定使用這種資源又如在社會(huì)上可對(duì)一些最緊缺的資源，借助影子價(jià)格規(guī)定使用這種資源一單位時(shí)必須上繳的利潤額，以控制一些經(jīng)濟(jì)效益低的企業(yè)自覺地節(jié)約一單位時(shí)必須上繳的利潤額，以控制一些經(jīng)濟(jì)效益低的企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟(jì)效益。使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟(jì)效益。對(duì)偶單純形法對(duì)偶單純形法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對(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ì)為對(duì)偶問題的最優(yōu)解，因此人們提出對(duì)偶單純形法。疊代過程本質(zhì)偶單純形法。疊代過程本質(zhì)：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)或事物對(duì)周圍環(huán)境變化顯靈敏度分析是指系統(tǒng)或事物對(duì)周圍環(huán)境變化顯示出來的敏感程度示出來的敏感程度 在在LP問題中，問題中，aij、cj、bi都有可能發(fā)生變化，都有可能發(fā)生變化，分析這些變化對(duì)最優(yōu)解或目標(biāo)值的影響程度就是靈分析這些變化對(duì)最優(yōu)解或目標(biāo)值的影響程度就是靈敏度分析。敏度分析。二、靈敏度分析 c cj j通常表示一些估計(jì)或預(yù)測(cè)的數(shù)據(jù)，隨市場(chǎng)變化；通常表示一些估計(jì)或預(yù)測(cè)的數(shù)據(jù)，隨市場(chǎng)變化； a aijij通常隨工藝技術(shù)條件的改變而改變；通常隨工藝技術(shù)條件的改變而改變； 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í)的系數(shù)增量最優(yōu)解時(shí)的系數(shù)增量P Pj j* * 與初始的系數(shù)增量與初始的系數(shù)增量P Pj j也成也成B B-1 -1 倍變化倍變化最優(yōu)性條件可表達(dá)為：最優(yōu)性條件可表達(dá)為：-1B1X B b 00TTNNBCCB N二、靈敏度分析通常需要分析的項(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)

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

46、起的最終單純形表上有關(guān)數(shù)字的變化。 2 2、檢查原問題是否仍為可行解。、檢查原問題是否仍為可行解。 3 3、檢查對(duì)偶問題是否仍為可行解。、檢查對(duì)偶問題是否仍為可行解。 4 4、按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。、按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算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 一、標(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 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àn)（三、最優(yōu)解檢驗(yàn)（唯一解、無限多解、無界解和無解唯一解、無限多解、無界解和無解）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ī)劃目標(biāo)函數(shù)中變量系數(shù)線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù)c cj j的變化僅僅影響到檢驗(yàn)數(shù)的變化僅僅影響到檢驗(yàn)數(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元元/ /件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化；件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化；(2)(2)若家電若家電I I的利潤不變，則家電的利潤不變，則家電IIII的利潤在什么范圍內(nèi)變化的利潤在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(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的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代計(jì)算，得表如下：計(jì)算，得表如下：cj1.52000CB基bx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2 即美佳公司

52、隨家電即美佳公司隨家電I、II的利潤變化應(yīng)調(diào)整為生產(chǎn)的利潤變化應(yīng)調(diào)整為生產(chǎn)2件件I，生產(chǎn)生產(chǎn)3件件II。二、靈敏度分析 (2)設(shè)家電設(shè)家電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īng)有：為使上表中的解仍為最優(yōu)解，應(yīng)有：02321,04141mm解得：解得：131m即家電即家電II的利潤的利潤c2的變化范圍應(yīng)

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

54、出最優(yōu)解。 下面舉例說明：下面舉例說明： 例：在上述美佳公司例子中，例：在上述美佳公司例子中，(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)試工序能力在每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變。什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變。二、靈敏度分析 解解 (1)(1)因有因有 ，則：，則：080b22100802/34/102/14/102/154/51

55、1bBb將其反映到最終單純形表中得表如下。由于該表中將其反映到最終單純形表中得表如下。由于該表中原問題為非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算，原問題為非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算，其結(jié)果如下量表所示：其結(jié)果如下量表所示：二、靈敏度分析cj21000CB基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-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由此

56、美佳公司的最優(yōu)計(jì)劃改變?yōu)橹簧a(chǎn)由此美佳公司的最優(yōu)計(jì)劃改變?yōu)橹簧a(chǎn)5件家電件家電I。二、靈敏度分析 (2)(2)設(shè)調(diào)式工序每天可用能力為設(shè)調(diào)式工序每天可用能力為(5+m)h(5+m)h，因有，因有mmmmbBb2321215002/34/102/14/102/154/511將其反映到最終單純形表中，其將其反映到最終單純形表中，其b 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之間。之間。二、靈敏度分析3、增加一個(gè)變量、增加一個(gè)變

57、量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ì)算得到的 和和 直直接寫入最終單純形表中；若接寫入最終單純形表中；若 ，則按單純形法繼續(xù)迭代，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。計(jì)算找出最優(yōu)。 例：在美佳公司例子中，設(shè)該公司又計(jì)劃推出新型號(hào)的家例：在美佳公司例子中，設(shè)該公司又計(jì)劃推出新型號(hào)的家電電IIIIII，生產(chǎn)一件所需設(shè)備，生產(chǎn)一件所需設(shè)備A A、B B及調(diào)試工序的時(shí)間分別為及調(diào)試工序

58、的時(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ì)劃有何變化。miiijjjjjyaczc1jjPBP10jjPj0j二、靈敏度分析 解解 設(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(3

59、6二、靈敏度分析因因 ，故用單純形法繼續(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/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)生產(chǎn)計(jì)劃應(yīng)該為每天生產(chǎn)由上表可知，美佳公司新的最優(yōu)生產(chǎn)計(jì)劃應(yīng)該為每天生產(chǎn)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的的 變化將使相應(yīng)的變化將使相應(yīng)的B B和和B B-1-1發(fā)生變化，因此有可能出現(xiàn)發(fā)生變化，因此有可能出現(xiàn)原問題和對(duì)偶問題均為非可行解的情況。