[其它]第2章對偶理論

1、第第2章章 對對 偶偶 理理 論論(duality theory)對偶問題的提出對偶問題的提出線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論對偶問題的經(jīng)濟解釋對偶問題的經(jīng)濟解釋-影子價格影子價格 對對 偶偶 單單 純純 形形 法法 靈靈 敏敏 度度 分分 析析 例例1、某工廠用、某工廠用a、b、c、d四種原料生產(chǎn)甲乙兩四種原料生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)甲乙所需各種原料的數(shù)量、在一個計種產(chǎn)品，生產(chǎn)甲乙所需各種原料的數(shù)量、在一個計劃期內(nèi)各種原料的現(xiàn)有數(shù)量及單件產(chǎn)品的利潤見下劃期內(nèi)各種原料的現(xiàn)有數(shù)量及單件產(chǎn)品的利潤見下表，問應(yīng)如何安排生產(chǎn)才能獲得最大利潤表，問應(yīng)如何安排生產(chǎn)才能獲得最大利潤?線性規(guī)劃模型線性規(guī)劃模

2、型12121211212464628422083224240maxzxxxxxxs.t.xxxx ,x 分析問題：現(xiàn)從另一角度討論該問題分析問題：現(xiàn)從另一角度討論該問題假如某人要租賃該廠的四種原料生產(chǎn)這兩種產(chǎn)品，此時需考慮：假如某人要租賃該廠的四種原料生產(chǎn)這兩種產(chǎn)品，此時需考慮：這四種原料的加價應(yīng)如何確定才便于廠方和租賃者達(dá)成協(xié)議。這四種原料的加價應(yīng)如何確定才便于廠方和租賃者達(dá)成協(xié)議。對于工廠對于工廠：希望定價盡可能地高，但太高了人家不會租賃，所以：希望定價盡可能地高，但太高了人家不會租賃，所以只能期望，盡管我不生產(chǎn)，但收益不能低于自己生產(chǎn)所得，否則，只能期望，盡管我不生產(chǎn)，但收益不能低于自己

3、生產(chǎn)所得，否則，不如自己生產(chǎn)而不租賃出去。不如自己生產(chǎn)而不租賃出去。對于租賃者對于租賃者，當(dāng)然希望定價盡可能地低，至少不應(yīng)超過原來，當(dāng)然希望定價盡可能地低，至少不應(yīng)超過原來實際生產(chǎn)所得的利潤實際生產(chǎn)所得的利潤為了便于達(dá)成協(xié)議，就必須在保證原工廠利益不降為了便于達(dá)成協(xié)議，就必須在保證原工廠利益不降低的情況下，總的價格盡可能地低。低的情況下，總的價格盡可能地低。1234y ,y ,y ,y為為此此，設(shè)設(shè)為為四四種種原原料料的的單單位位加加價價，則則有有123412344482442046yyyyyyyy即出售生產(chǎn)兩種產(chǎn)品的原料的價格不應(yīng)低于自己生產(chǎn)即出售生產(chǎn)兩種產(chǎn)品的原料的價格不應(yīng)低于自己生產(chǎn)所得

4、的利潤，同時為了不虧本，各種原料加價不能為所得的利潤，同時為了不虧本，各種原料加價不能為負(fù)，即：負(fù)，即：12340y ,y ,y ,y 123428203224wyyyy為為了了實實現(xiàn)現(xiàn)交交易易，應(yīng)應(yīng)讓讓盡盡可可能能地地低低可得線性規(guī)劃模型：可得線性規(guī)劃模型：12341234123412342820322444824420460minwyyyyyyyys.t.yyyyy ,y ,y ,y 線性規(guī)劃問題的對偶問題線性規(guī)劃問題的對偶問題12121211212464628422083224240maxzxxxxxxs.t.xxxx ,x 線性規(guī)劃問題的原問題線性規(guī)劃問題的原問題兩個數(shù)學(xué)模型間的關(guān)系：

5、兩個數(shù)學(xué)模型間的關(guān)系：(1)(1)原問題為求最大值，而對偶問題是求最小值；原問題為求最大值，而對偶問題是求最小值；(2)(2)原問題的約束條件為原問題的約束條件為“”，而對偶問題的約束，而對偶問題的約束條件為條件為“”；(3)(3)原問題的目標(biāo)函數(shù)系數(shù)為對偶問題的約束條件右端原問題的目標(biāo)函數(shù)系數(shù)為對偶問題的約束條件右端的常數(shù)項，而原問題的約束右端常數(shù)項為對偶問題的的常數(shù)項，而原問題的約束右端常數(shù)項為對偶問題的目標(biāo)函數(shù)系數(shù)；目標(biāo)函數(shù)系數(shù)；(4)(4)原問題的約束條件中原問題的約束條件中xi 的系數(shù)為對偶問題第的系數(shù)為對偶問題第i個約束個約束條件的系數(shù)條件的系數(shù)例例2 合理配料問題合理配料問題 某

6、飼養(yǎng)場用某飼養(yǎng)場用n種飼料種飼料b1,b2, bn配置成含有配置成含有m種營養(yǎng)成分種營養(yǎng)成分a1,a2, am的混合飼料，其余資料如表所示。問應(yīng)如何配料，的混合飼料，其余資料如表所示。問應(yīng)如何配料，才能既滿足需要，又使混合飼料的總成本最低？才能既滿足需要，又使混合飼料的總成本最低？ 假設(shè)工廠想把這假設(shè)工廠想把這m 種營養(yǎng)成分分別制成一種營養(yǎng)丸種營養(yǎng)成分分別制成一種營養(yǎng)丸銷售，問如何定價，以保證總收入為最多？銷售，問如何定價，以保證總收入為最多？nbb 1mnmnaaaa 11111maa1mbb,設(shè) 為種飼料所用的數(shù)量jjxb1minnjjjzc x 1(1,2,.,). .0(1,2,.,

7、)nijjijja xb ims txjn 1ncc解：解： 顯然顯然為了保證銷路為了保證銷路，價格不能太高，設(shè)含一個單，價格不能太高，設(shè)含一個單位的第位的第i種營養(yǎng)種營養(yǎng)成分的營養(yǎng)丸定價為成分的營養(yǎng)丸定價為yi(i=1,2,m).因為因為原來的飼料中，第原來的飼料中，第j種飼料每單位的價格為種飼料每單位的價格為cj(j=1,n),而它所含第而它所含第i種營養(yǎng)成分的量為種營養(yǎng)成分的量為aij,即現(xiàn)在要用即現(xiàn)在要用aij個單位個單位的第的第i種營養(yǎng)丸才能代替它，因此，種營養(yǎng)丸才能代替它，因此，為了使飼養(yǎng)場愿意為了使飼養(yǎng)場愿意用營養(yǎng)丸來代替原來的飼料，用營養(yǎng)丸來代替原來的飼料，必須使?fàn)I養(yǎng)丸的價格滿

8、足必須使?fàn)I養(yǎng)丸的價格滿足 11 2mijijia ycj, ,.,n 由于每一份飼料中必須含有由于每一份飼料中必須含有bi個單位的第個單位的第i種營養(yǎng)成分，種營養(yǎng)成分，因此這樣一份代替飼料的總收入為因此這樣一份代替飼料的總收入為1miiiwb y 對于工廠來說對于工廠來說，問題是如何確定每種營養(yǎng)丸的售價，問題是如何確定每種營養(yǎng)丸的售價yi(i=1,m)使在滿足上述約束條件下工廠的總收入達(dá)使在滿足上述約束條件下工廠的總收入達(dá)到最大，則問題可歸結(jié)為到最大，則問題可歸結(jié)為 111 201miiimijijiimaxwb ya ycj, ,.,ns.t.yi,.,m 對偶問題對偶問題 110 njjj

9、nijjijjmin zc xa xbi =,.,mxj =,.,n 11原問題原問題兩個數(shù)學(xué)模型間的關(guān)系：兩個數(shù)學(xué)模型間的關(guān)系：(1)(1)原問題為求最小值，而對偶問題是求最大值；原問題為求最小值，而對偶問題是求最大值；(2)(2)原問題的約束條件為原問題的約束條件為“”而對偶問題的約束條件而對偶問題的約束條件為為 “” ；(3)(3)原問題的目標(biāo)函數(shù)系數(shù)為對偶問題的約束條件右端原問題的目標(biāo)函數(shù)系數(shù)為對偶問題的約束條件右端的常數(shù)項，而原問題的約束右端常數(shù)項為對偶問題的的常數(shù)項，而原問題的約束右端常數(shù)項為對偶問題的目標(biāo)函數(shù)系數(shù)；目標(biāo)函數(shù)系數(shù)；(4)(4)原問題的約束條件原問題的約束條件xi 的

10、系數(shù)為對偶問題第的系數(shù)為對偶問題第i個約束條個約束條件的系數(shù)件的系數(shù)對稱型對偶問題對稱型對偶問題變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時均取大時均取“”號，當(dāng)目標(biāo)函數(shù)求極小時均取號，當(dāng)目標(biāo)函數(shù)求極小時均取“”號。號。0maxzcxaxbs.t.x 0minwybyacs.t.y pd矩陣形式矩陣形式,.c x bnamnyn 其其中中為為 維維的的為為維維的的為為 維維的的 例例1、寫出線性規(guī)劃問題的對偶問題、寫出線性規(guī)劃問題的對偶問題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxz解

11、：首先將原式變形解：首先將原式變形12312312312312323423523734650m ax zxxxxxxxxxxxxx , x, x 12312312312312323523234376405 5m in wyyyyyyyyyyyyy , y, y 例例2、原問題、原問題12312312312312323423523734650maxzxxxxxxxxxs.t.xxxx ,x ,x 123123123123123123123123234235223523733734654650maxzxxxxxxxxxxxxs.t.xxxxxxxxxx ,x ,x 解：原問題化為解：原問題化為11

12、2233112233112233112233112233223355223323344355776640minwyyyyyyyyyyyyyyyyyys.t.yyyyyyy ,y ,y ,y ,y ,y 111222333yyy ,yyy ,yyy令令1231231231231232352323435764minwyyyyyyyyys.t.yyyy ,y ,y 則則有有無無約約束束12312312312312323423523734650maxzxxxxxxxxxs.t.xxxx ,x ,x 123412341241234123423543253274234600maxzxxxxxxxxxxxs

13、.t.xxxxx,x ,x,x 無無約約束束例例3、求下列問題的對偶問題、求下列問題的對偶問題原問題可化為：原問題可化為：123441234412441234412344123442354322532774234623460maxzxxxxxxxxxxxxxxs.t.xxxxxxxxxxx ,x ,xxx ， ，123441234412441234412344123442354322532774234623460maxzxxxxxxxxxxxxxxs.t.xxxxxxxxxxx ,x ,xxx ， ，12331233123313312331233123354664322223333445271

14、2710minwyyyyyyyyyyyyyyys.t.yyyyyyyyy ,y ,y ,y 對偶問題為：對偶問題為：12312312313123123546432223334527100minwyyyyyyyyys.t.yyyyyy,yy ， 無無約約束束1333yy ,yyy 1令令則則有有123412341241234123423543253274234600maxzxxxxxxxxxxxs.t.xxxxx,x ,x,x 無無約約束束綜上所述，其變換形式歸納如下：綜上所述，其變換形式歸納如下：例例4、線性規(guī)劃問題如下：、線性規(guī)劃問題如下：123412341342341234min23535

15、2244. .60,0,zxxxxxxxxxxxs txxxxx xx 無無約約束束1231213123123123max546223. .325410,0,wyyyyyyys tyyyyyyyyy 無無約約束束對偶問題是對偶問題是 無無約約束束、，4321432143243214321321321321321321 ,0024732543 0432 4323min2 0,564 37 32532 422min.1xxxxxxxxxxxxxxxxxxxz. xxxxxxxxxxxxxxxz 無無約約束束答答案案：32132132132131321321321321321321y0,y0,y44

16、y4y4y 37y3y3y 23yy 2y32y y 253max.2 0.yy0,y46y7y5y24yy 3y2y 3y2y 532max.1yyywyyyw1 1、對稱性定理：對偶問題的對偶是原問題。、對稱性定理：對偶問題的對偶是原問題。對偶的定義對偶的定義對偶的定義對偶的定義min. .0wybyacs ty min. .0zcxaxbs tx max. .0wybyacs ty max. .0zcxaxbs tx 2 2、弱對偶原理（弱對偶性）：設(shè)、弱對偶原理（弱對偶性）：設(shè) 和和 分別是問題分別是問題（p）和（）和（d）的可行解，則必有）的可行解，則必有_x_y njmiiijjb

17、yxcbyxc11_ ,即即 推論推論. .若若 和和 分別是問題（分別是問題（p p）和（）和（d d）的可行解，）的可行解，則則 是（是（d d）的目標(biāo)函數(shù)最小值的一個下界；）的目標(biāo)函數(shù)最小值的一個下界； 是是（p p）的目標(biāo)函數(shù)最大值的一個上界。）的目標(biāo)函數(shù)最大值的一個上界。_xcby_x_yxaxb y設(shè)設(shè) 是是對對偶偶問問題題的的可可行行解解因因是原問題的可行解，所以滿足約束條件，即是原問題的可行解，所以滿足約束條件，即yyaxyb 將將 左左乘乘上上式式，得得到到原問題的對偶問題是原問題的對偶問題是 min w=yb; ya c;y 0yac y因因為為 是是對對偶偶問問題題的的可

18、可行行解解，x將將 右右乘乘上上式式y(tǒng)axcx 得得到到cxyaxyb于于是是得得到到;0zcx axb x證證 設(shè)設(shè)原原問問題題是是 推論推論.在一對對偶問題在一對對偶問題（p）和（）和（d）中，若其中）中，若其中一個問題可行但目標(biāo)函數(shù)一個問題可行但目標(biāo)函數(shù)無界，則另一個問題不可無界，則另一個問題不可行。行。 0,024 2max21212121xxxxxxxxz無界無界如：如：（原）（原） 0,012 24min21212121yyyyyyyyw無可無可行解行解（對）（對）例例1、試估計它們目標(biāo)函數(shù)的界，并驗證弱對偶性原理。試估計它們目標(biāo)函數(shù)的界，并驗證弱對偶性原理。（p）12341234

19、12341234max23422320. . 23220,0zxxxxxxxxs txxxxx x x x 121212121212min20202122. . 233324,0wyyyyyys tyyyyy y :(1,1,1,1),(1,1),xy由由觀觀察察知知10,40,zwcxyb故故有有( )().pd分分別別是是和和的的可可行行解解.(1)弱弱對對偶偶定定理理成成立立由由推推論論知知10,w的的最最小小值值不不能能小小于于40.z的的最最大大值值不不能能超超過過解解3,( )(),pd推推論論 在在一一對對對對偶偶問問題題和和中中 若若一一個個可可行行 而而另另一一個個,.不不可

20、可行行 則則該該可可行行的的問問題題無無界界例例2、已知、已知試用對偶理論證明原問題無界。試用對偶理論證明原問題無界。12123123123:max22. .21,0pzxxxxxs txxxx x x 1212121212:min2212. .0,0dwyyyyyys tyyy y (0,0,0),xpd 解解：是是 的的一一個個可可行行解解 而而 的的第第一一個個約約束束條條件件12(,0).,(3)y y 不不能能成成立立 因因為為因因此此 對對偶偶問問題題不不可可行行 由由推推論論知知, ,.原原問問題題無無界界例例3 3、已知、已知顯然，這兩個問題都無可行解。顯然，這兩個問題都無可行

21、解。12121212:max1. .1,0pzxxxxs txxx x 12121212:min1. .1,0dwyyyys tyyy y 3 3、最優(yōu)性判別定理：、最優(yōu)性判別定理：例如例如, ,在例在例1 1中中, ,可找到可找到x*=(0,0,4,4),y*=（1.2,0.2）, ,則則z=28,w=28. .故故x* ,y*分別是分別是 p和和d 的最優(yōu)解。的最優(yōu)解。*,xypdcxy bx 若若和和分分別別是是 和和 的的可可行行解解 且且則則*.ypd和和分分別別是是問問題題 和和 的的最最優(yōu)優(yōu)解解*,:cxy by 證證 若若由由性性質(zhì)質(zhì)知知 對對偶偶問問題題的的所所有有可可行行解

22、解 都都*,.,ybcxyby by存存在在所所以以可可見見是是使使目目標(biāo)標(biāo)函函數(shù)數(shù)取取最最小小,.值值的的可可行行解解 因因而而是是最最優(yōu)優(yōu)解解:,x同同理理可可證證明明 對對于于原原問問題題的的所所有有可可行行解解存存在在*,.cxy bcxx所所以以是是原原問問題題的的最最優(yōu)優(yōu)解解4 4、對偶定理（強對偶性）：、對偶定理（強對偶性）： 若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等。標(biāo)函數(shù)的最優(yōu)值相等。綜上所述，一對對偶問題的關(guān)系，只能有下面三種情況綜上所述，一對對偶問題的關(guān)系，只能有下面三種情況之一出現(xiàn)：之一出現(xiàn)：.都有最優(yōu)解

23、，分別設(shè)為都有最優(yōu)解，分別設(shè)為x* 和和 y*，則必有，則必有cx* =y*b；. 一個問題無界，則另一個問題無可行解；一個問題無界，則另一個問題無可行解；.兩個都無可行解。兩個都無可行解。*,xb證證 設(shè)設(shè)是是原原問問題題的的最最優(yōu)優(yōu)解解 它它對對應(yīng)應(yīng)的的基基矩矩陣陣 必必存存在在1*10,bbcc b ay acyc b即即得得到到其其中中*1,bywy bc b b 此此時時是是對對偶偶問問題題的的可可行行解解 它它使使*1,bxzcxc b b 因因是是原原問問題題的的最最優(yōu)優(yōu)解解 使使目目標(biāo)標(biāo)函函數(shù)數(shù)值值*,.cxy 可可見見是是對對偶偶問問題題的的最最優(yōu)優(yōu)解解5 5、互補松弛定理：

24、、互補松弛定理： 設(shè)設(shè)x*和和y*分別是問題分別是問題p 和和 d 的可行解，則它們分別的可行解，則它們分別是最優(yōu)解的充要條件是是最優(yōu)解的充要條件是剩剩余余變變量量或或或或ssssyxxyxcayxyaxby.00)(00)( 同時成立同時成立max. .,0sspzcxaxxbs tx x min. .,0ssdwybyaycs ty y ss例例4、已知、已知試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對偶問題為解：對偶問題為1234523451234512534min34259532. .23,0,0zxxxxxxxxxs txxxxx

25、x x xx x 1221212121212max23342. .55329,0wyyyyyyys tyyyyy y *:1311.yw用用圖圖解解法法求求出出（， ），*121,3,yy將將代代入入對對偶偶約約束束條條件件(1),(2),(5),為為緊緊約約束束(3),(4).為為松松約約束束令令原原問問題題的的最最優(yōu)優(yōu)解解*12345(,),xx x x x x 則則根根據(jù)據(jù)340.xx互互補補松松弛弛條條件件必必有有此方程組有無窮多組解此方程組有無窮多組解*120,0,yy又又由由于于則則原原問問題題的的約約束束條條件件必必為為等等式式 即即251253223xxxxx 化化簡簡為為15

26、25123xxxx *51210,1,2(1,2,0,0,0)xxxx令令得得到到即即為為原原問問題題的的11.z 一一個個最最優(yōu)優(yōu)解解, ,*51222552,0,0 0 03333xxxx再再令令得得到到即即， ， ， ， 也也是是,11.z 原原問問題題的的一一個個最最優(yōu)優(yōu)解解例例5、已知原問題的最優(yōu)、已知原問題的最優(yōu)解為解為x* =（0,0,4），），z=12 試求對偶問題的最優(yōu)解。試求對偶問題的最優(yōu)解。解：解： 無約束無約束321321321321321, 0, 03654 3 132 42minyyyyyyyyyyyyyyyw（1）（2）（3）123123123123123max4

27、32352361. .40,0,zxxxxxxxxxs txxxxxx 無無約約束束將將x* =（0 , 0 ,4）代入原問題中，有下式：）代入原問題中，有下式：所以，根據(jù)互補松弛條件，必有所以，根據(jù)互補松弛條件，必有y*1= y*2=0，代入對偶，代入對偶問題問題 （3 3）式，）式， y3 =3。因此，對偶問題的最優(yōu)解為。因此，對偶問題的最優(yōu)解為 y*=（0 ,0 ,3），），w=12。123123123235202. . 3624144xxxs txxxxxx 6 6、對偶問題的解、對偶問題的解引入引入xs ，構(gòu)建初始基變量，然后用單純形法求解。當(dāng)所，構(gòu)建初始基變量，然后用單純形法求解。

28、當(dāng)所有非基變量的檢驗數(shù)滿足有非基變量的檢驗數(shù)滿足j0 ，則求得最優(yōu)解。此時，則求得最優(yōu)解。此時， xs對應(yīng)的對應(yīng)的s 為為- y* ，故求對偶問題的最優(yōu)解，故求對偶問題的最優(yōu)解y* ，只要將，只要將最優(yōu)單純形表上最優(yōu)單純形表上xs 對應(yīng)的檢驗數(shù)反號即可。對應(yīng)的檢驗數(shù)反號即可。ccbcn0cbxbbxbxnxscbxbb-1bib-1nb-1-zcb b-1b0cncb b-1ncb b-1max. .0pzcxaxbs tx max. .,0sspzcxaxxbs tx x (1)例例1、1212121212max10185217023100. .5150,0pzxxxxxxs txxx x

29、12123124125125max10185217023100. .5150,.,0pzxxxxxxxxs txxxx xx 123123123123min1701001505210. . 23518,0wyyyyyys tyyyy yy i初初始始表表最終表最終表 由上表可知：由上表可知： x*=（50/7 , 200/7），），z=4100/7對偶問題的最優(yōu)解：對偶問題的最優(yōu)解： y*=（0 ,32/7 , 6/7），），w=4100/7也就是外加工時的收費標(biāo)準(zhǔn)。也就是外加工時的收費標(biāo)準(zhǔn)。此時，矩陣此時，矩陣a中沒有現(xiàn)成的單位矩陣中沒有現(xiàn)成的單位矩陣i作為可行基，必作為可行基，必須通過加入

30、人工變量來湊一個單位矩陣，再用大須通過加入人工變量來湊一個單位矩陣，再用大m法法或兩階段法求解?；騼呻A段法求解。(2):設(shè)設(shè)原原問問題題是是max. .0zcxaxbs tx *,:y如如何何求求經(jīng)經(jīng)分分析析得得出出如如下下結(jié)結(jié)論論max. .0pzcxaxbs tx max. .,0iipzcxaxixbs tx x 0b 最最優(yōu)優(yōu)基基變變量量對對應(yīng)應(yīng)的的檢檢驗驗數(shù)數(shù)向向量量1iibcc b 初初始始基基變變量量對對應(yīng)應(yīng)的的檢檢驗驗數(shù)數(shù)向向量量1nnbcc b n 非非基基變變量量對對應(yīng)應(yīng)的的檢檢驗驗數(shù)數(shù)向向量量*,iiyc所所以以例例2、12312312313123max3211423.

31、.21,0pzxxxxxxxxxs txxx x x 123123412356137127max3211423. .21,.,0zxxxxxxxxxxxxs txxxx xx 12312312123123min11342321. .210,0,dwyyyyyyyys tyyyyyy 無無約約束束原原問問題題化化為為標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型: :i 所以，所以， x*=（4 ,1 ,9），），z = 2 y*1= (0 4 )=1/3 y*2=(m 6 )= m(1/3m)=1/3 y*3 =(m 7 )= m(2/3 m)=2/3 y*=（1/3 ,1/3 , 2/3） w = 2 初始基變量的檢驗數(shù)初始

32、基變量的檢驗數(shù)4 =1/3，6 =1/3m, 7 =2/3mmax. .0pzcxaxbs tx min. .0dwybyacs ty :,pdp定定義義 在在一一對對 和和 中中 若若 的的某某個個約約束束條條件件的的右右端端項項常常數(shù)數(shù)*,ibz增增加加一一個個單單位位時時 所所引引起起的的目目標(biāo)標(biāo)函函數(shù)數(shù)最最優(yōu)優(yōu)值值的的改改變變量量*,.iyi稱稱為為第第 個個約約束束條條件件的的影影子子價價格格 又又稱稱為為邊邊際際價價格格ccbcn0cbxbbxbxnxscbxbb-1bib-1nb-1zcb b-1b0cncb b-1ncb b-1bp設(shè)設(shè) 是是問問題題 的的最最優(yōu)優(yōu)基基, ,由由

33、前前式式可可知知, ,*1*bzc b by b *1122.iimmy by by by b1(,)iibbb 當(dāng)當(dāng) 變變?yōu)闉闀r時 其其余余右右端端項項不不變變 假假設(shè)設(shè)最最優(yōu)優(yōu)基基 不不變變 目標(biāo)函數(shù)最優(yōu)值變?yōu)椋耗繕?biāo)函數(shù)最優(yōu)值變?yōu)椋阂部梢詫懗桑阂部梢詫懗桑?其經(jīng)濟意義是：在其它條件不變的情況下，單位資源其經(jīng)濟意義是：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即對偶變量變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即對偶變量yi 就是第就是第 i 個約束條件的影子價格。個約束條件的影子價格。*1122.(1).iimmzy by by by b *izzzy *.iiyzb即

34、即 表表示示對對 的的變變化化率率*(1,2,.,)iizy imb 也可以理解為目標(biāo)函數(shù)最優(yōu)值對資源的一階偏導(dǎo)數(shù)也可以理解為目標(biāo)函數(shù)最優(yōu)值對資源的一階偏導(dǎo)數(shù)（但問題中所有其它數(shù)據(jù)都保持不變）。（但問題中所有其它數(shù)據(jù)都保持不變）。 例例1、某工廠用、某工廠用a、b、c三種三種原料生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)原料生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)甲乙所需各種原料的數(shù)量、在甲乙所需各種原料的數(shù)量、在一個計劃期內(nèi)各種原料的現(xiàn)有一個計劃期內(nèi)各種原料的現(xiàn)有數(shù)量及單件產(chǎn)品的利潤見下表，數(shù)量及單件產(chǎn)品的利潤見下表，問應(yīng)如何安排生產(chǎn)才能獲得最問應(yīng)如何安排生產(chǎn)才能獲得最大利潤大利潤? 0,150510032170251810ma

35、x2121212121xxxxxxxxpxxz其對偶問題其對偶問題 12312312317010015052102351801 2 3iminwyyyyyys.t.yyyyi, , 原問題的最優(yōu)解為原問題的最優(yōu)解為 x*=（50/7 , 200/7），），z*=4100/7對偶問題的最優(yōu)解：對偶問題的最優(yōu)解： y*=（0 ,32/7 , 6/7），），w*=4100/7即原問題中第即原問題中第1種資源種資源(鋼材鋼材)的影子價格的影子價格y1*=0,第第2種資源種資源(煤炭煤炭)的的影子價格為影子價格為y2*=32/7,第第3種資源種資源(設(shè)備臺時設(shè)備臺時)的影子價格為的影子價格為y3*=6/

36、7即在現(xiàn)有資源的基礎(chǔ)上，若再增加即在現(xiàn)有資源的基礎(chǔ)上，若再增加1噸煤，可使總利潤增加噸煤，可使總利潤增加32/7萬元，若再增加一個臺時，可使總利潤增加萬元，若再增加一個臺時，可使總利潤增加6/7萬元，萬元，但若增加但若增加1噸鋼材，將不會使總利潤增加。噸鋼材，將不會使總利潤增加。之所以出現(xiàn)上述幾種不同情況，由互補松弛條件可知，之所以出現(xiàn)上述幾種不同情況，由互補松弛條件可知，233260077*y,y由由于于對對偶偶問問題題的的最最優(yōu)優(yōu)解解1212231002 35150*xx,xx 則則原原問問題題的的第第兩兩個個約約束束條條件件將將變變?yōu)闉榈鹊仁绞?，即即這說明按最優(yōu)生產(chǎn)計劃進(jìn)行生產(chǎn)，現(xiàn)有資源

37、中的煤炭和設(shè)備臺時這說明按最優(yōu)生產(chǎn)計劃進(jìn)行生產(chǎn)，現(xiàn)有資源中的煤炭和設(shè)備臺時已經(jīng)全部用完而沒有剩余，因此，若再增加這兩種資源，肯定會已經(jīng)全部用完而沒有剩余，因此，若再增加這兩種資源，肯定會給工廠帶來新的收益。給工廠帶來新的收益。1250200177*x,x而而這這時時將將使使原原問問題題的的第第 個個約約束束條條件件變變成成嚴(yán)嚴(yán)格格不不等等式式1252170*xx即即10*y 根根據(jù)據(jù)互互補補松松弛弛條條件件，必必有有。這這說說明明按按最最優(yōu)優(yōu)計計劃劃安安排排生生產(chǎn)產(chǎn)，第第一一 3540 7*x/ 種種資資源源 鋼鋼材材 還還有有剩剩余余 其其剩剩余余量量即即最最優(yōu)優(yōu)解解中中松松弛弛變變量量的的

38、值值若再增加這種資源，只能造成積壓，而不會使工廠增加收益。若再增加這種資源，只能造成積壓，而不會使工廠增加收益。 bi 代表第代表第i種資源的擁有量；種資源的擁有量；yi*代代表在資源最優(yōu)利用條件下對第表在資源最優(yōu)利用條件下對第i種資種資源的單位估價。這種估價不是資源源的單位估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價。中作出的貢獻(xiàn)而作的估價。 設(shè)設(shè) xj 表示第表示第 j 種產(chǎn)品每天的產(chǎn)量種產(chǎn)品每天的產(chǎn)量設(shè)設(shè) yj 表示第表示第 j 種原料的收費單價種原料的收費單價 由對偶定理知當(dāng)由對偶定理知當(dāng)p問題求得問題求得最優(yōu)解最優(yōu)解x*時，

39、時，d問題也得到最問題也得到最優(yōu)解優(yōu)解y*，且有，且有*11nmjjiijizc xb yw影子價格影子價格若若 ，則，則*0iy*1nijjija xb*1nijjija xb若若 ，則，則*0iy當(dāng)某個右端常數(shù)當(dāng)某個右端常數(shù)bi bi+1時時*1miiizb y由由 得得*iizyb說明說明 的值相當(dāng)于在資源得到最優(yōu)的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，利用的生產(chǎn)條件下， 每增加一個每增加一個單位時目標(biāo)函數(shù)單位時目標(biāo)函數(shù)z的增量的增量*iyib*11iimmzb yb yb y*11(1)iimmzb ybyb y*11iimmib yb yb yy*izy邊際價格邊際價格說明若某資源

40、說明若某資源 未被充分利用，未被充分利用，則該種資源的影子價格為則該種資源的影子價格為0 0；ib若某資源的影子價格不為若某資源的影子價格不為0 0，則說，則說明已有資源已消耗完畢。明已有資源已消耗完畢。1x2x3x4x5xjc bc基bjjczi340340001x2x5x42110001021111100100210y1* = 2y2* = 1y3* = 0y*t= cbb-1cbb-1 y1* = 2y2* = 1y3* = 0若原料若原料a a增加增加1 1單位，該廠按最優(yōu)計劃安排生產(chǎn)可多獲利單位，該廠按最優(yōu)計劃安排生產(chǎn)可多獲利200200元；元；若原料若原料b b增加增加1 1單位，

41、可多獲利單位，可多獲利100100元元; ;原料原料c c本已剩余，再增加不會帶來收益。本已剩余，再增加不會帶來收益。1 1、指示企業(yè)內(nèi)部挖潛的方向、指示企業(yè)內(nèi)部挖潛的方向影子價格能說明增加哪種資源對增加經(jīng)濟效益最有利影子價格能說明增加哪種資源對增加經(jīng)濟效益最有利 y1* = 2y2* = 1y3* = 02 2、在企業(yè)經(jīng)營決策中的作用、在企業(yè)經(jīng)營決策中的作用當(dāng)某種資源的影子價當(dāng)某種資源的影子價格高于市場價格時：格高于市場價格時：當(dāng)某種資源的影子價當(dāng)某種資源的影子價格低于市場價格時：格低于市場價格時： 企業(yè)經(jīng)營決策者可通過把本企業(yè)資源的影子價格與當(dāng)時企業(yè)經(jīng)營決策者可通過把本企業(yè)資源的影子價格與

42、當(dāng)時的市場價格進(jìn)行比較，決定資源的買賣，以獲取較大利潤。的市場價格進(jìn)行比較，決定資源的買賣，以獲取較大利潤。買進(jìn)買進(jìn)賣出賣出特別是影子價特別是影子價格為零時格為零時 y1* = 2y2* = 1y3* = 03 3、在新產(chǎn)品開發(fā)決策中的應(yīng)用、在新產(chǎn)品開發(fā)決策中的應(yīng)用 利用影子價格，通過分析新產(chǎn)品使用資源的經(jīng)濟效果，利用影子價格，通過分析新產(chǎn)品使用資源的經(jīng)濟效果，以決定新產(chǎn)品是否應(yīng)該投產(chǎn)。以決定新產(chǎn)品是否應(yīng)該投產(chǎn)。 假設(shè)該企業(yè)計劃生產(chǎn)一類新產(chǎn)品，單件消耗三種原料的數(shù)假設(shè)該企業(yè)計劃生產(chǎn)一類新產(chǎn)品，單件消耗三種原料的數(shù)量為（量為（2,3,22,3,2），則新產(chǎn)品的單位利潤必須大于），則新產(chǎn)品的單位利

43、潤必須大于 2 22 + 12 + 13 + 03 + 02 = 72 = 7（百元）（百元）才能增加公司的收益，否則生產(chǎn)是不合算的。才能增加公司的收益，否則生產(chǎn)是不合算的。 y1* = 2y2* = 1y3* = 04 4、分析現(xiàn)有產(chǎn)品價格變動對資源緊缺情況的影響、分析現(xiàn)有產(chǎn)品價格變動對資源緊缺情況的影響 若甲產(chǎn)品提價，單位利潤增至若甲產(chǎn)品提價，單位利潤增至4 4，則影子價格改變，由，則影子價格改變，由y*t= cbb-1210(4,4,0)110111(4,0,0)說明如果甲產(chǎn)品提價的話，資源說明如果甲產(chǎn)品提價的話，資源a將變得更緊俏將變得更緊俏. . y1* = 2y2* = 1y3*

44、= 05 5、分析工藝改變后對資源節(jié)約的收益、分析工藝改變后對資源節(jié)約的收益 若企業(yè)革新技術(shù)，改進(jìn)工藝過程后使資源若企業(yè)革新技術(shù)，改進(jìn)工藝過程后使資源a能節(jié)約能節(jié)約2%2%，則，則帶來的經(jīng)濟收益每天將是帶來的經(jīng)濟收益每天將是 2 26 62% = 0.242% = 0.24（百元）（百元）y1* = 2y2* = 1y3* = 0注意注意: :1 1、以上分析都是在最優(yōu)基不變的條件下進(jìn)行的、以上分析都是在最優(yōu)基不變的條件下進(jìn)行的2 2、應(yīng)對、應(yīng)對影子價格有更為廣義的理解影子價格有更為廣義的理解 若增加產(chǎn)量若增加產(chǎn)量約束約束 x1+ x2 40：產(chǎn)量不超過市場需求量產(chǎn)量不超過市場需求量若若y4*

45、較大，則說明擴大銷路能比增加資源帶來更大的經(jīng)濟效益較大，則說明擴大銷路能比增加資源帶來更大的經(jīng)濟效益 y*t= cbb-16單純形表中各個檢驗數(shù)的經(jīng)濟意義單純形表中各個檢驗數(shù)的經(jīng)濟意義當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時，表明生產(chǎn)該項產(chǎn)當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排，否則這些資源來生產(chǎn)別品有利，可在計劃中安排，否則這些資源來生產(chǎn)別的產(chǎn)品更為有利，就不在計劃中安排。這就是單純的產(chǎn)品更為有利，就不在計劃中安排。這就是單純形表中各個檢驗數(shù)的經(jīng)濟意義。形表中各個檢驗數(shù)的經(jīng)濟意義。mjjbjjijiicc bpca y 1101 2 3 4 5 6 7 8 1 2 3 4 5 6 x

46、2 x1(4 2)*(4,2,0,0,0,4)x *310,028y121212122212284164120 xxxxxs.t.xx ,x 1223maxzxx12(1)(1) :2,.xx 當(dāng)當(dāng)直直線線變變?yōu)闉?2=13+2=13時時最最優(yōu)優(yōu)解解不不變變01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 2)2(4)(4) :4,.x 當(dāng)當(dāng)直直線線變變?yōu)闉?13=13時時最最優(yōu)優(yōu)解解不不變變 對偶單純形法是求解線性規(guī)劃的另一個基本方法。對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的，它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的

47、，因此稱為對偶單純形法。不要簡單理解為是求解對偶因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。問題的單純形法。 由對偶理論可以知道，對于一個線性規(guī)劃問題，我由對偶理論可以知道，對于一個線性規(guī)劃問題，我們能夠通過求解它的對偶問題來找到它的最優(yōu)解。們能夠通過求解它的對偶問題來找到它的最優(yōu)解。 0maxzcxaxbp s.t.x minwybyacd s.t.y 無無符符號號限限制制考慮一般的標(biāo)準(zhǔn)形線性規(guī)劃問題及其對偶問題考慮一般的標(biāo)準(zhǔn)形線性規(guī)劃問題及其對偶問題 12mbpbp ,p ,.,p 設(shè)設(shè) 為為原原問問題題的的一一個個基基，不不妨妨設(shè)設(shè)，則則 1010bnxbbxx 10

48、2bxbb p為為原原問問題題的的一一個個基基本本解解，且且當(dāng)當(dāng) 0xb時時，則則為為一一個個基基可可行行解解， 為為可可行行基基，若若檢檢驗驗數(shù)數(shù)滿滿足足 10 3bcc ba 0xpb則則為為原原問問題題的的一一個個最最優(yōu)優(yōu)解解， 為為最最優(yōu)優(yōu)基基。原始單純形法的基本思路是：從滿足初始可行性條件原始單純形法的基本思路是：從滿足初始可行性條件 0x的的一一個個基基可可行行解解出出發(fā)發(fā)，經(jīng)經(jīng)過過換換基基運運算算迭迭代代到到另另一一個個基基可可行行解解，直直到到最最后后得得到到滿滿足足原原始始最最優(yōu)優(yōu)性性條條件件的的基基可可行行解解，這這個個解解就就是是原原問問題題的的最最優(yōu)優(yōu)解解。用用對對偶偶

49、的的觀觀點點解解釋釋一一下下這這個個問問題題 1byc b 令令，代代入入式式 3 3 ，得得， 10 2bxbb 10 3bcc ba 4yac y即即 是是對對偶偶問問題題的的一一個個可可行行解解，條條件件(4)(4)稱稱為為對對偶偶可可行行性性條條件件，即即原原始始最最優(yōu)優(yōu)性性條條件件(3)(3)與與對對偶偶可可行行性性條條件件(4)(4)是是等等價價的的。因因此此，如如果果bbyc -1-1一一個個原原始始可可行行基基 也也是是原原問問題題(p)(p)的的最最優(yōu)優(yōu)基基，則則b b 為為對對偶偶問問題題 1bwybc bb d d 的的一一個個可可行行解解，且且對對應(yīng)應(yīng)的的目目標(biāo)標(biāo)函函數(shù)

50、數(shù)值值等等于于 1*byc b 原原問問題題 p p 的的目目標(biāo)標(biāo)函函數(shù)數(shù)值值，可可知知也也是是對對偶偶問問題題 d d 的的最最優(yōu)優(yōu)解解定定義義( )px若若原原問問題題的的一一個個基基本本解解對對應(yīng)應(yīng)的的檢檢驗驗數(shù)數(shù)向向量量滿滿足足下下列列,條條件件 即即1(,)(0,)0bnnbcc b n .xp則則稱稱 為為 的的一一個個正正則則解解,對對偶偶單單純純形形法法所所使使用用的的表表格格與與原原單單純純形形法法一一樣樣 可可將將,典典式式中中的的數(shù)數(shù)據(jù)據(jù)放放在在原原單單純純形形表表上上 即即得得對對偶偶單單純純形形表表 所所不不10(1,., ),0jjmnb b 同同的的是是這這里里保

51、保證證而而不不保保證證,對對偶偶單單純純形形法法的的迭迭代代方方式式與與原原單單純純形形法法基基本本一一致致 所所不不同同:,的的是是 先先選選出出基基變變量量 再再選選進(jìn)進(jìn)基基變變量量 決決定定主主元元并并作作換換基基運運算算得得到到一一個個新新的的正正則則解解，從從而而完完成成一一次次迭迭代代，算算法法的的.后后半半部部分分與與原原單單純純形形法法完完全全一一致致(1)先先選選出出基基變變量量: :若若min|0,1riibb bim.rrbx 則則取取與與 相相對對應(yīng)應(yīng)的的基基變變量量 為為出出基基變變量量(2):,0,krxb 再再選選進(jìn)進(jìn)基基變變量量 假假定定為為進(jìn)進(jìn)基基變變量量 因

52、因為為而而換換基基,rkar 運運算算的的第第一一步步是是用用主主元元去去除除第第 行行中中的的各各元元素素 為為了了使使,rrkbar變變換換后后的的 為為正正數(shù)數(shù) 所所以以主主元元必必須須從從第第 行行的的負(fù)負(fù)元元素素中中0rka 選選取取, ,即即,k設(shè)設(shè)主主元元處處在在第第 列列 于于是是換換基基運運算算后后 各各檢檢驗驗數(shù)數(shù)變變?yōu)闉?1,2,., )rjjjkrkajna ,因因為為要要求求迭迭代代后后得得到到的的解解仍仍為為正正則則解解 于于是是0(1,2,., )rjjjkrkajna 0,0,0(1,2,., )0rkkjrjajna又又因因為為于于是是當(dāng)當(dāng)時時，,0,rja

53、上上述述不不等等式式顯顯然然成成立立 否否則則，當(dāng)當(dāng)時時 要要使使不不等等式式成成立立必必須須jkrkrjaa 因因此此可可令令min0,1jkrjrjrkajnaa kkx則則取取與與相相對對應(yīng)應(yīng)的的非非基基變變量量為為進(jìn)進(jìn)基基變變量量. .,rkrkxxa 出出基基變變量量 與與進(jìn)進(jìn)基基變變量量確確定定以以后后 以以為為主主元元進(jìn)進(jìn)行行換換基基,.運運算算 即即可可得得新新的的正正則則解解,0,0,0,rrkkba對對于于新新的的正正則則解解 因因為為故故(1)(0)(0)krrkwwbwa 單純形法：單純形法：在整個迭代過程中，始終保持在整個迭代過程中，始終保持原問題的可行原問題的可行性

54、性，即常數(shù)列，即常數(shù)列b00，而檢驗數(shù)，而檢驗數(shù)c-cbb-1a（即（即c-ya）由）由有正分量逐步變?yōu)槿坑姓至恐鸩阶優(yōu)槿?(0(即滿足即滿足ya c,y為對偶問為對偶問題的可行解題的可行解) )即同時得到原問題和對偶問題的最優(yōu)解。即同時得到原問題和對偶問題的最優(yōu)解。對偶單純形法對偶單純形法：在整個迭代過程中，始終保持：在整個迭代過程中，始終保持對偶問題對偶問題的可行性的可行性，即全部檢驗數(shù)，即全部檢驗數(shù)00，而常數(shù)列由有負(fù)分量逐，而常數(shù)列由有負(fù)分量逐步變?yōu)槿坎阶優(yōu)槿?(0(即變?yōu)闈M足原問題的可行性即變?yōu)闈M足原問題的可行性) )，即同時，即同時得到原問題和對偶問題的最優(yōu)解。得到原問題

55、和對偶問題的最優(yōu)解。單純形法與對偶單純形法的迭代過程之比較單純形法與對偶單純形法的迭代過程之比較對偶單純形法所對偶單純形法所使用的表格使用的表格與原單純形法一樣，所不同與原單純形法一樣，所不同的是對偶單純性表保證的是對偶單純性表保證j j 0,0,而不保證右端常數(shù)非負(fù)。而不保證右端常數(shù)非負(fù)。對偶單純形法的對偶單純形法的迭代方式迭代方式與原單純形法基本一致，所不與原單純形法基本一致，所不同的是：先選出基變量，再選進(jìn)基變量，決定主元并作同的是：先選出基變量，再選進(jìn)基變量，決定主元并作換基運算得到一個新的對偶可行解。換基運算得到一個新的對偶可行解。對偶單純形法具體步驟：對偶單純形法具體步驟：(1)(

56、1)據(jù)線性規(guī)劃問題，列初始單純形表，設(shè)檢驗數(shù)全據(jù)線性規(guī)劃問題，列初始單純形表，設(shè)檢驗數(shù)全都小于或等于都小于或等于0,0,檢查檢查b b列數(shù)字，若全為非負(fù)數(shù)，則已列數(shù)字，若全為非負(fù)數(shù)，則已得到最優(yōu)解，停止計算，否則，轉(zhuǎn)下一步得到最優(yōu)解，停止計算，否則，轉(zhuǎn)下一步(2)(2)確定換出變量，若確定換出變量，若min(b-1b)i|(b-1b)i0=(b-1b)l則則xl出基出基(3)(3)確定換入變量，檢查確定換入變量，檢查xl 所在行的各系數(shù)所在行的各系數(shù)alj(j=1,n)若若所有所有alj00則無可行解，計算結(jié)束，若存在則無可行解，計算結(jié)束，若存在alj0,0=3/40 125c,當(dāng)當(dāng) 變變?yōu)闉?/p>

57、 求求新新的的最最優(yōu)優(yōu)解解. . 131,x ,x問問： 為為保保持持現(xiàn)現(xiàn)有有最最優(yōu)優(yōu)解解不不變變 分分別別求求非非基基變變量量的的13c ,c;系系數(shù)數(shù)的的變變化化范范圍圍111354x,c, 3 3故故 進(jìn)進(jìn)基基 以以代代替替變變?yōu)闉?其其余余不不變變, ,再再迭迭代代求求解解. .4 4 1jjbbjcccb p 1jbjc b p 12000jjjrrjnjaa.,., c , ,.,aa jrrjc a 要使最優(yōu)解不變，則必須滿足要使最優(yōu)解不變，則必須滿足0jjrrjc a 00jjrjrrjjjrjrjmaxacminaaa 2.jjxc基基變變量量 的的價價值值系系數(shù)數(shù) 的的變變

58、化化,rrbxc對對于于最最優(yōu)優(yōu)基基 而而言言 設(shè)設(shè)基基變變量量 的的價價值值系系數(shù)數(shù) 改改變變?yōu)闉?rrrrbccccc 因因則則變變化化后后的的檢檢驗驗數(shù)數(shù)為為rc則則的的允允許許變變化化范范圍圍為為rjrax 為為基基變變量量 所所在在行行的的系系數(shù)數(shù)解：解： 211 4113 41 411 413 43 4/max,cmin,/ 2113c 413 41 411 412121/max,cmin, 4114c 242 :x ,x,例例為為保保持持現(xiàn)現(xiàn)有有最最優(yōu)優(yōu)解解不不變變, ,求求基基變變量量的的變變化化范范圍圍 0 6 2bc, ,并并問問當(dāng)當(dāng)由由 0,4,50,4,5 變變?yōu)闉闀r時

59、 求求最最優(yōu)優(yōu)解解. . 420 6 223bc, , c, c 當(dāng)當(dāng)由由 0,4,50,4,5 變變?yōu)闉闀r時超超出出了了允允許許的的范范圍圍bbcc 此此時時在在原原最最優(yōu)優(yōu)單單純純形形表表中中用用代代替替繼繼續(xù)續(xù)迭迭代代求求解解. .二、二、 右端常數(shù)的靈敏度分析右端常數(shù)的靈敏度分析 1bxbbb 111100rrrmmrbab bbbbba 00iiirriririrbbmaxabminaaa ,rrrrbbbb 若若某某一一個個右右端端常常數(shù)數(shù) 變變?yōu)闉閯t則使使最最終終單單純純形形表表中中原原問問題題的的解解相相應(yīng)應(yīng)地地變變?yōu)闉?0,bbx 若若要要使使最最優(yōu)優(yōu)基基 不不變變 則則必必

60、須須使使即即0,(1,2,.,),irirrbb aimb因因此此的的允允許許范范圍圍為為1irab 其其中中為為的的第第r r列列. .解解(1)11001maxb 1100b 21002001001 413 4max,bmin/ 24002003b 3100100200111maxbmin, 3100100b 111180025040111200350385050014bxbbb 12331:b ,b ,b例例 （）為為保保持持現(xiàn)現(xiàn)有有最最優(yōu)優(yōu)解解不不變變, ,求求的的允允許許變變化化 32150.b,.范范圍圍若若 減減少少求求最最優(yōu)優(yōu)解解 32150b 超超出出了了允允許許范范圍圍將將