2對(duì)偶理論運(yùn)籌學(xué)西南交通大學(xué)經(jīng)濟(jì)管理學(xué)院

1、運(yùn)籌學(xué)Operations Research對(duì)偶理論西南交通大學(xué)管理學(xué)院西南交通大學(xué)管理學(xué)院§1單純形法的矩陣描述max z = CX + 0 × X Smax z = CX AX £ bX ³ 0引入松弛變量AX + IX S= b³ 0)TX ³ 0 , Xn + mSmax z = CB X B + CN X N + 0 × X SBX+ NX+ IX S = bBN³ 0SX B= B -1b - B -1NX- B -1 X SNZ = CB B -1b + (C N- C B B -1N ) X N-

2、CB B -1 X S西南交通大學(xué)管理學(xué)院B#I與初等變換一致B-1I#西南交通大學(xué)管理學(xué)院基變量非基變量右側(cè)常數(shù)XBXNXSCBXBIB-1 NB-1B-1 bg0CN - CBB-1N-CBB-1-CBB-1b初始非基變量初始基變量右側(cè)常數(shù)XBXNXS0XSBNIbgCBCN00BiB1=B1-1=IB2AjbIB2-1AjB2-1B2-1bBi-1Bi-1bBiAj-1I西南交通大學(xué)管理學(xué)院§2線性的對(duì)偶理論一、對(duì)偶問(wèn)題的提出周長(zhǎng)一定，面積最大的四邊形面積一定，周長(zhǎng)最小的四邊形 正方形 車(chē)輛數(shù)一定，如何安排使貨運(yùn)量最多貨運(yùn)量一定，如何安排使所用車(chē)輛最少一對(duì)對(duì)應(yīng)問(wèn)題表示了一個(gè)問(wèn)題

3、的兩個(gè)側(cè)面，是對(duì)一個(gè)研究對(duì)象從兩個(gè)角度提出極值問(wèn)題，兩類(lèi)極值問(wèn)題具有相同的目標(biāo)函數(shù)值。對(duì)偶問(wèn)題西南交通大學(xué)管理學(xué)院例1某工廠在計(jì)劃期內(nèi)要安排生產(chǎn),兩種，已知所需的設(shè)備臺(tái)時(shí)及A，B兩種原材料的消獲利能力如下表所示。問(wèn)如何安排生產(chǎn)使該生產(chǎn)耗，及工廠獲利最多？西南交通大學(xué)管理學(xué)院III限量設(shè)備128 臺(tái)時(shí)原材料A4016 Kg原材料B0412 Kg單件利潤(rùn)2 元3 元解根據(jù)上一章的知識(shí)，設(shè)x1，x2分別表示在計(jì)劃期內(nèi)，的產(chǎn)量，得線性模型max z=2x1+3x2 x1+2x284x1164x212x1, x20例2對(duì)例1，假設(shè)該工廠的決策者決定不生產(chǎn)，而將其所有出租或外售。這時(shí)工廠的決策者如何給出每

4、種的定價(jià)？解同理，設(shè)y1 ,y2 ,y3分別表示出租設(shè)備臺(tái)時(shí)的原材料A，B的附加額。和出讓思路：出售生產(chǎn)一件I的的收入應(yīng)不低于生產(chǎn)I的利潤(rùn)，有一件y1+ 4y2 2西南交通大學(xué)管理學(xué)院 原問(wèn)題max z=2x1+3x2 x1+2x28依次類(lèi)推，得線性模型min w=8y1+16y2+12y3y1+4y2 24x1614x 122y1+4y3162y1, y2, y30x , x201(1)(2)(3)(4)系數(shù)互為轉(zhuǎn)置約束條件的常數(shù)項(xiàng)變?yōu)槟繕?biāo)函數(shù)系數(shù)一個(gè)為max問(wèn)題，一個(gè)為min問(wèn)題約束條件一個(gè)為，一個(gè)為西南交通大學(xué)管理學(xué)院這樣并存的兩個(gè)線性問(wèn)題互為對(duì)偶，一個(gè)為原問(wèn)題，另一個(gè)為對(duì)偶問(wèn)題定義 1

5、.設(shè)有線性問(wèn)題（）max z=CX AXb X0式中X=(x1, , xn)T，C=(c1, , cn)，b=(b1, , bm)T，a11 a21am1a12 a22am2a1n a2namnA=設(shè)另一個(gè)線性問(wèn)題（）為min w=YbYACY0式中Y=(y1, , ym)，則稱(chēng)問(wèn)題（）是問(wèn)題（）的對(duì)偶問(wèn)題，式（）稱(chēng)為原問(wèn)題。兩者合在一起稱(chēng)為一對(duì)對(duì)稱(chēng)的對(duì)偶線性問(wèn)題。西南交通大學(xué)管理學(xué)院原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系z(mì) =+ c 2+ "+ "x 2 + " + c n x nmaxc 1 x 1x 1 +x 1 +x n£ b 1x n£ b 2a 1

6、1a 21a 12a 22xa 1 na 2 n2x 2" " " "x 1 +x 2 + " +x n£ bma m 1a ma mn2x³ 0=+jy 1 b11 , 2 , " , njw =+ "+miny 2 b 2ym bm³ c1³ c 2y 1+y 1+ "+ "+a 11a 12a 21a 22y 2y 2a m 1a m 2y my m" " " "y 1+y i³+ "+³

7、c na 1 na 2 n0y 2a mny mi = 1, 2 , " , m西南交通大學(xué)管理學(xué)院原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系西南交通大學(xué)管理學(xué)院0x1x2xny1 y2yma11a12a1na21a22a2nam1am2amnb1 b2bmc1c2cnmin max現(xiàn)考慮標(biāo)準(zhǔn)形式的線性（ ）max z=CX AX b- AX - bX0對(duì)偶變量UVmax z=CX AX = bX0等價(jià)寫(xiě)成對(duì)偶問(wèn)題為min w = Ub -Vbmin w = Yb YA ³ CY為自由變量令Y = U - VUA -VA ³ CU ³ 0,V ³ 0西南交通大學(xué)管

8、理學(xué)院構(gòu)造對(duì)偶的規(guī)則1、若目標(biāo)函數(shù)為min，把原問(wèn)題中的約束條件統(tǒng)一為“”或“=”；若目標(biāo)函數(shù)為max，把原問(wèn)題中的約束條件統(tǒng)一為“” 或“=”。2、原問(wèn)題的一個(gè)約束對(duì)應(yīng)于一個(gè)對(duì)偶變量 yi ，如果第i個(gè)約yi ³ 0；如果第i個(gè)約束是等式，則 yi束是不等式，則限制。3、原問(wèn)題每個(gè)變量 x j 對(duì)應(yīng)于一個(gè)對(duì)偶問(wèn)題的約束，如果 x j ³ 0 ，則對(duì)偶約束為不等式；如果 x約束為等式。4、如果原問(wèn)題目標(biāo)函數(shù)為min ，則對(duì)偶問(wèn)題為max；如果原問(wèn)題目標(biāo)函數(shù)為max ，則對(duì)偶問(wèn)題為min。，則對(duì)偶j西南交通大學(xué)管理學(xué)院例3 寫(xiě)出下述線性min z=問(wèn)題的對(duì)偶問(wèn)題5 +x+x

9、5 ³4£6=23 ³04無(wú)x符號(hào)限制0³)令mz i=n解- 24+ x-+³-x³542446=3 ³0無(wú)x 約束4西南交通大學(xué)管理學(xué)院設(shè)對(duì)應(yīng)于約束條件(1)、(2)、(3)的對(duì)偶變量分別 為 y1 、y2 、y3=-+ 6 y 3max-y-y yw5 y 14 y 2£- 5約束西南交通大學(xué)管理學(xué)院二、對(duì)偶定理max z=CXmin w=YbYA CY0(LP)AXbX0(LD)定理1(弱對(duì)偶定理) 若X和Y分別是（LP)和(LD)的任一可行解，則有CX Yb推論1 若X為原問(wèn)題LP的任一可行解，則CX為其

10、對(duì)偶問(wèn)題LD的一個(gè)下界；若Y為L(zhǎng)D的任一可行解，則Yb為L(zhǎng)P的一個(gè)上界。推論2 若LP有可行解，LD無(wú)可行解，則LP無(wú)上界；同理，若LD有可行解，LP無(wú)可行解，則LD無(wú)下界。推論3 若LP有可行解，但其目標(biāo)函數(shù)值無(wú)上界，則LD無(wú)可行解；同理，若LD有可行解，但其目標(biāo)函數(shù)值無(wú)下界，則LP無(wú)可行解。推論4 若X*與Y*分別是LP與LD的可行解，且CX* =Y*b，則X*與Y*分別是LP和LD的最優(yōu)解。推論5 LP與LD同時(shí)有最優(yōu)解的充要條件是：LP與LD同時(shí)有可行解。西南交通大學(xué)管理學(xué)院例4：考慮下列線性問(wèn)題，假定（1）和（2）都有可行解，證明若其中一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解；若其中一個(gè)，；

11、在都有最優(yōu)解的條件下，若 X 和 U 分別則另一個(gè)也CX ³ CU為（1）和（2）的可行解，則（1） min z1 = CX AX ³ b證明：（1）和（2）線性max z2 = CU AU £ b的對(duì)偶問(wèn)題分別為（2）=maxz '1YA = CbYmin z1 = CX AX ³ bmax z2 = CU（3）（1）³Y0=minz '2bV（2）（4）VA= CV³ 0管理學(xué)院AU £ b西南交通大學(xué)問(wèn)題1 （1）和（2）都有可行解，假設(shè)（1）有最優(yōu)解，證明（2）也有最優(yōu)解由于（1）有最優(yōu)解，則（3）有

12、可行解，（3）與（4）約束同，則（4）也有可行解。由于（2）和（4）互為對(duì)偶且都有可行解，根據(jù)推論1知，（2）和（4）都有最優(yōu)解。問(wèn)題得證。問(wèn)題2 （1）和（2）都有可行解，假設(shè)（1）（2）也，證明由于（1）有可行解但，據(jù)推論4則其對(duì)偶問(wèn)題（3）無(wú)可行解。（3）和（4）約束相同，則（4）也無(wú)可行解。（2）和（4）互為對(duì)偶，（2）有可行解，（4）無(wú)可行解，據(jù)推論5知（2）。問(wèn)題得證。西南交通大學(xué)管理學(xué)院U分別為（1）X 和問(wèn)題3 （1）和（2）都有最優(yōu)解，則若CX ³ CU和（2）的可行解，證明由問(wèn)題1的證明過(guò)程可知，（1）（2）都有可行解，且（3）和（4）也都有可行解，設(shè)Y 為（3）

13、和（4）的可行解，則由定理1可得 CX ³ Yb 和 Yb ³ CU ，因此CX ³ CU問(wèn)題得證西南交通大學(xué)管理學(xué)院例5用弱對(duì)偶定理，證明下述線性min z=x1x2+x3問(wèn)題無(wú)下界x1x3 4x1x2 +2x33x1, x2 , x3 0證：其對(duì)偶問(wèn)題為max w=4y1+3y2y1+y21y2 1y1+2y21y1, y20原問(wèn)題有可行解，如X=(4,0,0)T。但對(duì)偶問(wèn)題第一個(gè)約束加上第三個(gè)約束，得3y22。第二個(gè)約束兩邊同乘以（-1），得y2 1，故對(duì)偶問(wèn)題無(wú)可行解。由推論5，原問(wèn)題無(wú)下界。西南交通大學(xué)管理學(xué)院定理2 （最優(yōu)性定理）若原和對(duì)偶都有可行解，

14、則它們都有有限最優(yōu)解，而且其最優(yōu)目標(biāo)函數(shù)值相等，即max CX=min Yb定理3（對(duì)偶定理）若（LP）和（LD）中有一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)值相等。原問(wèn)題關(guān)系對(duì)偶問(wèn)題有有限最優(yōu)解有可行解，目標(biāo)函數(shù)無(wú)可行解有有限最優(yōu)解有可行解，目標(biāo)函數(shù)無(wú)可行解西南交通大學(xué)管理學(xué)院定理 4 （互補(bǔ)松弛定理） 若X*與Y*分別是（LP）與（LD） 的可行解，則X*和Y*為最優(yōu)解的充要條件是Ys*X*=0Y*Xs*=0等價(jià)于等價(jià)于*x *=0ysjj*=0yi xsij=1,2,ni=1,2,m如果最優(yōu)解使某個(gè)約束取等號(hào)，則稱(chēng)這個(gè)約束是緊的，否則稱(chēng)為松的。原問(wèn)題對(duì)偶問(wèn)題y*x* > 0=

15、0某個(gè)變量對(duì)應(yīng)變量約束為等式sjjy*> 0x*= 0約束為嚴(yán)格不等式sjjx*> 0y*= 0約束為嚴(yán)格不等式對(duì)應(yīng)變量某個(gè)變量siiy* > 0x*= 0約束為等式isi西南交通大學(xué)管理學(xué)院例6對(duì)例1，已知其最優(yōu)解為(4,2)T ，試根據(jù)對(duì)偶理論，直接求出其對(duì)偶問(wèn)題例2的最優(yōu)解。解：首先將（LP）及（LD）化為max z=2x1+3x2x1+2x2+xs1=84x1+ xs2=164x2+ xs3=12(LP)x1, x20xs1, xs2 , xs3 0min w=8y1+16y2+12y3y1+4y2 ys1=22y1+4y3 ys2=3(LD)y1, y2, y30

16、ys1, ys2 0西南交通大學(xué)管理學(xué)院再將(4,2)T代入（LP）的約束，得xs1=0, xs2=0 , xs3=4由定理4（互補(bǔ)松弛定理）知*=0yi xsiy3=0i=1,2,3得*=0由ysj xjj=1,2ys1= ys2=0得代入（LD）的約束，得y1+4y2 =22y1=3解得 y1*=3/2, y2*=1/8Y*=(3/2,1/8,0,0,0)西南交通大學(xué)從而有管理學(xué)院定理6LP的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)解原問(wèn)題達(dá)到最優(yōu)時(shí)，單純形表中檢驗(yàn)數(shù)的負(fù)值，就等于其對(duì)偶問(wèn)題的最優(yōu)解西南交通大學(xué)管理學(xué)院原問(wèn)題CBCN0XBXNXS初始表BNI最終表IB-1 NB-1檢驗(yàn)數(shù)0CN - CBB

17、-1N-CBB-1對(duì)應(yīng)的對(duì)偶變量-ys1-ys2-y舉例：ma3x1 + 2x2min w = 90 y1 + 200 y2 + 210 y32£ 90£ 2003 y1 + 4 y22 y1 + 6 y2³ 7+ 7 y3 ³ 54x + 6x127x2 £ 210x1 ³ 0 , x2 ³ 0y1 , y2 , y3 ³ 0min w = 90 y1+ 200 y 2 + 210 y 33 y1 + 4 y2 - y4 + y6 = 72 y1 + 6 y2y i³ 0+ 7 y3 - y5 + y7

18、= 5i = 1," ,7西南交通大學(xué)管理學(xué)院y3y4y5y1y22x3x4x5x1x2管理學(xué)院西南交通大學(xué)cj9020021000MMbCBXBy1y2y3y4y5y6y79000y1 y210-14/5 -3/5-2/53/5-2/50121/101/5 -3/10 -1/53/1011/51/10gj00421424M-14 M- 24-218cj75000bCBXBx1x2x3x4x5750x1 x2 x5103/5-1/5001-2/53/1000014/5-21/101142442gj00-11/5-1/100三、對(duì)偶問(wèn)題的意義B-1b = y*b + y*b +&quo

19、t;+ y* b= w* = Cz*B1122mm¶z=y *i¶biyi*變量位的意義是在其它條件不變的情況下，單的變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。在完全市場(chǎng)條件下，價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用當(dāng)?shù)氖袌?chǎng)價(jià)低于價(jià)格時(shí)，企業(yè)應(yīng)買(mǎi)進(jìn)該用于擴(kuò)大生產(chǎn)當(dāng)?shù)氖袌?chǎng)價(jià)高于價(jià)格時(shí)，企業(yè)應(yīng)把已有賣(mài)掉西南交通大學(xué)管理學(xué)院例7對(duì)例1，原問(wèn)題最優(yōu)點(diǎn)B(4,2),最優(yōu)值Z*=14/8)89(1)設(shè)備臺(tái)時(shí)數(shù)由8增到9，則可行域界線從移到了，最優(yōu)點(diǎn)變?yōu)镋,*y目標(biāo)值由14增加到31/2，增加了3/2，等于對(duì)偶問(wèn)題的1(2)原材料A若增加1千克，可行域邊界由移到，最優(yōu)點(diǎn)變?yōu)镕，最優(yōu)值y*增加1/8，等于對(duì)偶問(wèn)題

20、的2(3)原材料B若增加1千克，可行域由移到了，最優(yōu)點(diǎn)不變，最優(yōu)值不變，y*所以對(duì)偶問(wèn)題的等于03西南交通大學(xué)管理學(xué)院§對(duì)偶單純形法一、對(duì)偶單純形法的基本思想LP的最優(yōu)解必須滿(mǎn)足三個(gè)條件(1)基本解B -1b ³ 0C - CBB-1A £ 0 ÞYA³ C(2)可行性(對(duì)偶問(wèn)題可行)(3)最優(yōu)性LD可行性LP最優(yōu)性西南交通大學(xué)管理學(xué)院逐步減少>0的檢驗(yàn)數(shù)個(gè)數(shù)保持LP解可行g(shù)£ 0( 最優(yōu) )另一基解LP的基解j使LD解的不可行性逐步消除LD解可行 對(duì)偶單純形法 保持LD解可行LP的基解逐步消除LD解的不可行性LD解可行( 最優(yōu)

21、 )另一基解單純形法：(1) (2)(1) (2) (3)對(duì)偶單純形法：(1)(3)(1) (2) (3)西南交通大學(xué)管理學(xué)院對(duì)偶可行解可行性基可行解最優(yōu)性單純形法二、對(duì)偶單純形法的解題步驟（1）假定已給一對(duì)偶可行基（即它對(duì)應(yīng)的對(duì)偶問(wèn)題的解可行）單位陣B ，相應(yīng)的基解為XB=B-1b。若它的各個(gè)分量均非負(fù)，則這個(gè)解就是最優(yōu)解，停止迭代。（2）如果XB有分量xBi<0，且xi所在行的所有系數(shù)aij0，則（LP） 無(wú)可行解，停止迭代；否則轉(zhuǎn)（3）。（3）確定換出變量，若minbi| bi <0 =bli則對(duì)應(yīng)的xl為換出變量；計(jì)算的值，若ìï gQ = min

22、52;ïa< 0=g kjíýljïî aljalkïþj則選擇xk為換入變量，alk為主元。（4）以alk為主元，進(jìn)行系數(shù)變換，得一新的正則解，轉(zhuǎn)（2）。西南交通大學(xué)管理學(xué)院例1用對(duì)偶單純形法解線性min z=3x1+2x2+x3+4x4問(wèn)題2x1+4x2+5x3 +x4 03x1x2 +7x3 2 x4 25x1+2x2+x3+6x4 10x1, x2, x3, x4 0解引入剩余變量x5, x6, x7, 化所給max z= 3x1 2x2 x3 4x4為2x14x25x3x4+x53x1 + x2 7x3 +2

23、 x4+ x6=0= 25x12x2 x36x4x1, , x7 0+ x7= 10西南交通大學(xué)管理學(xué)院其初始單純形表為當(dāng)前解為正則解，但不可行（存在負(fù)分量）根據(jù)min0, 2, 10= 10,以x7為換出變量,由ì -3 , -2 , - 1 , -4 ü3Q = min=í -6 ý5-2- 1-5îþ以為x1為換入變量，以a31= 換，得新單純形表西南交通大學(xué)5為主元進(jìn)行系數(shù)變管理學(xué)院cj3 2 1 4000biCBXBx1x2x3x4x5x6x7000x5 x6 x72 4 5 110031 720105 2 1 600102

24、10rj32 1 40000由此得正則解X=(2,0,0,0,4,4,0)T,及相應(yīng)目標(biāo)函數(shù)值。因?yàn)閎i0,所以X為最優(yōu)解, 相應(yīng)目標(biāo)函數(shù)值6。西南交通大學(xué)管理學(xué)院cj3214000biCBXBx1x2x3x4x5x6x7003x5 x6 x10 16/5 23/57/510 2/5011/532/5 28/501 3/512/51/56/500 1/5442rj0 4/5 2/5 2/500 3/5-6§3靈敏度分析對(duì)于標(biāo)準(zhǔn)形式的線性來(lái)說(shuō)max z = CX AX = bX ³ 0一旦其系數(shù)矩陣A，約束條件右側(cè)向量b和價(jià)值系數(shù)向量C給定之后，這個(gè)線性系數(shù)是可能發(fā)生變化的。

25、問(wèn)題也就確定了但是，這些研究線性模型某些系數(shù)或限制量的變化對(duì)最優(yōu)解的影響極其程度的分析就稱(chēng)之為靈敏度分析。西南交通大學(xué)管理學(xué)院對(duì)解的影響主要有：1、最優(yōu)解保持不變，即基變量和它們的取值沒(méi)有變化2、基變量保持不變，但它們的值改變了3、基解完全變了因此，我們最終要回答下面兩個(gè)問(wèn)題：1、這些系數(shù)在什么范圍內(nèi)變化時(shí)，原先求出的線性規(guī) 劃問(wèn)題的最優(yōu)解不變。2、如果系數(shù)的變化超出了上述范圍，如何用最簡(jiǎn)便的 方法求出新的最優(yōu)解。西南交通大學(xué)管理學(xué)院一價(jià)值系數(shù)變化B是原問(wèn)題的最優(yōu)基，xr ® c' = c + DcrrrXB = B-1bg = C - CBB-1A與c無(wú)關(guān)與c有關(guān)價(jià)值系數(shù)變

26、化不影響基的可行性，只影響基的最優(yōu)性。1、xr 為非基變量cr 的變化只影響其本身的檢驗(yàn)數(shù)gr,只要gr =< 0,最優(yōu)解B-1 A不變.既對(duì)該c ,只需滿(mǎn)足 g ' = C ' - C£ 0,否則可將rrrBrxr作為引入變量, 進(jìn)行單純形迭代求解.西南交通大學(xué)管理學(xué)院2、xr為基變量= Cr - CB B-1Ar雖然cr的變化不影響基B的可行性，但由 g r,而cB=(c1 , cr , cm)，故這種變化對(duì)所有變量的檢驗(yàn)數(shù)都將產(chǎn)B-1 Ar生影響。只有 g '= Cr - C '£ 0（r=m+1, , n）時(shí)，最優(yōu)解Br才不變。

27、否則，取最大檢驗(yàn)數(shù)作單純形迭代求解。西南交通大學(xué)管理學(xué)院例1 考慮線性問(wèn)題max z=x1+2x2 x3x1+2x2+x38x1+x22x3 4x1, x2, x30當(dāng)x1在目標(biāo)函數(shù)中系數(shù)由1變?yōu)?時(shí)，進(jìn)行靈敏度分析。解：該線性問(wèn)題的原始單純形表如下所示（表1）西南交通大學(xué)管理學(xué)院cj12100biCBXBx1x2x3x4x500x4 x5121101120184rj12100經(jīng)一步迭代得最終單純形表如下所示（表2）當(dāng)x1的價(jià)值系數(shù)由1變?yōu)?時(shí)，注意到在最終表中為非基變量，故只須計(jì)算其新檢驗(yàn)數(shù)，由于é 1 / 2ùg = C - C BA2（21B1-1ú = 1

28、 > 00）êë- 3 / 2û最優(yōu)解發(fā)生變化，故需在最終表的基礎(chǔ)上進(jìn)一步求解。一步迭代得下表（表3），得以重新尋優(yōu)西南交通大學(xué)管理學(xué)院cj12100biCBXBx1x2x3x4x520x2 X51/211/21/203/205/21/2140rj00210西南交通大學(xué)管理學(xué)院cj22100biCBXBx1x2x3x4x520x2 X51/211/21/203/205/21/2140rj10210cj22100biCBXBx1x2x3x4x520x1 X51211003111812rj02320二、右側(cè)常數(shù)變化不影響最優(yōu)性，只影響可行性XB = B-1bg

29、= C - CBB-1Agr =Cr -CBB-1Ar和X=B-1b知b的變化對(duì)檢驗(yàn)數(shù)沒(méi)由有影響，故不 影響B(tài)的最優(yōu)性，但有可能對(duì)B的可行性產(chǎn)生影響。只要X=B-1b ³0，最優(yōu)基就仍可B行。否則用對(duì)偶單純形法迭代求解。西南交通大學(xué)管理學(xué)院例2對(duì)例1中的線性問(wèn)題，當(dāng)?shù)谝粋€(gè)約束方程的右側(cè)常數(shù)由8變?yōu)?0時(shí)，進(jìn)行靈敏度分析。max z=x1+2x2 x3x1+2x2+x310x1+x22x3 4x1, x2, x30-1 é 1 / 20ùé10ùé 5 ù解X B = Bb = ê- 1 / 21ú

30、4; 4 ú = ê- 1úëûëûëû顯然，最優(yōu)解的可行性遭到破壞，以最終表為基礎(chǔ)進(jìn)一步求解。 得到表4西南交通大學(xué)管理學(xué)院西南交通大學(xué)管理學(xué)院cj12100biCBXBx1x2x3x4x520x2 X51/211/21/203/2 0 5/21/2151rj00210cj12100biCBXBx1x2x3x4x521x2 x1011/31/31/3105/31/32/314/32/3rj00210三、約束條件系數(shù)矩陣A的變化非基變量的系數(shù)列向量Aj變化XB = B-1bg = C - CBB-1A對(duì)于

31、不在基B中的元素akr發(fā)生變化時(shí)，注意到A的第r列Ar,amr)，而 g = C - CBB-1A ，顯然只也變?yōu)锳r=(a1r,akr對(duì)xr對(duì) 應(yīng)的檢驗(yàn)數(shù)gr產(chǎn)生影響（不影響可行性，只影響最優(yōu)性）。若滿(mǎn)足=c -C B-1A' £0g 'rrBr則B仍為最優(yōu)基。否則按一般單純形法在原有的基礎(chǔ)上重新尋優(yōu)。對(duì)于基B中元素發(fā)生變化，情況比較復(fù)雜，這里就不再討論。西南交通大學(xué)管理學(xué)院x3例3對(duì)例1中的線性問(wèn)題，當(dāng)?shù)诙€(gè)約束中的系數(shù)由-2變?yōu)?1時(shí)，作相應(yīng)的靈敏度分析。解 注意到0 é 1 / 20ùé 1 ù = -2 < 0g

32、 1（2）êúêú3ë- 1 / 21ûë- 1û故最優(yōu)解不變。西南交通大學(xué)管理學(xué)院四、增加或刪去一個(gè)變量1、增加一個(gè)變量在原問(wèn)題的最優(yōu)單純形表中增加一列，對(duì)應(yīng)變量xn+1及B-1An+1，gB-1 A= c- C,不難看出， 原最優(yōu)基仍是新問(wèn)題的一檢驗(yàn)數(shù)n+1n+1n+1B個(gè)可行基， xn+1為非基變量。（1）g n+1£ 0> 0,滿(mǎn)足最優(yōu)性條件，原B是新問(wèn)題的最優(yōu)基（2）gB -1 A£ 0 新問(wèn)題，否則繼續(xù)迭代。n+1n+12、刪去一個(gè)變量若為非基變量，刪去不影響最優(yōu)基可行解和最優(yōu)

33、目標(biāo)函數(shù)值。若為基變量，可將其基（實(shí)施對(duì)偶單純形法迭代，或以M為價(jià)值系數(shù)將其迭代出基），一旦出基即可刪除。西南交通大學(xué)管理學(xué)院例4對(duì)例1中的線性問(wèn)題，增加一變量，價(jià)值系數(shù)為2，約束系數(shù)矩陣列向量為(1,2)T，作相應(yīng)的靈敏度分析。解：注意到æ0öæ 1 ö1 / 2= 2 - (20)çg÷ç÷ = 1 > 0ç - 1 / 21 ÷ç 2÷6èøèøæ0öæ 1 öæ 1 / 2

34、 ö1 / 2A6 = BA6 = ç-1÷ç÷ = ç÷1è - 1 / 21 øè 2øè 3 / 2ø將x6 引入，作單純形迭代，得表5。西南交通大學(xué)管理學(xué)院西南交通大學(xué)管理學(xué)院cj121002biCBXBx1x2x3x4x5x620x2 X51/211/21/201/23/205/21/213/240rj002101cj121002biCBXBx1x2x3x4x5x622x2 X6114/32/ 31/30105/31/32/3140rj101/32/32/

35、30cj121002biCBXBx1x2x3x4x5x612x1 X6114/32/ 31/30011/31/31/3144rj0 15/34/31/30五、增加或刪去一個(gè)約束條件1、增加一個(gè)約束條件x2=7 x+ 5 xmaxz123x +2x =903 x 1 +4 x 1 +2 x 2£ 9012£j =6 x 22001, "7x2=210C³x0, 5jDEB4x1+6x2=200z = 7 x 1+ 5 x 2max3 x 1 +4 x 1 +2 x 2£ 90£o6 x 2200x1Ax³ 0j = 1, &q

36、uot; ,5jR' Í R增加一個(gè)約束后，可行域的變化為西南交通大學(xué)管理學(xué)院7 x 2 £ 210分三種情況：R'R'= f新問(wèn)題無(wú)可行解= R新問(wèn)題最優(yōu)解不變R' Ì R首先將原問(wèn)題最優(yōu)解代入束，如滿(mǎn)足束，則最優(yōu)解不變，否則在表中添加一個(gè)新變量為第n+1列，新約束為m+1行，但基變量所在列不是向量，用行初等變換將其化。2、刪除一個(gè)約束條件若這個(gè)約束條件對(duì)來(lái)說(shuō)是不起作用約束，即松弛變量，剩余變量不為零，則去掉這個(gè)約束條件對(duì)最優(yōu)解無(wú)影響。反之，則使最優(yōu)解發(fā)生變化，將松弛變量或剩余變量或人 工變量轉(zhuǎn)為基變量即可。西南交通大學(xué)管理學(xué)院?jiǎn)?/p>

37、題，增加一個(gè)約束，x 2+x 3£ 3例5 對(duì)例1中的線性作靈敏度分析。解：顯然原最優(yōu)解不滿(mǎn)足束，采用上述加行加列的方法對(duì)新問(wèn)題的最初單純形表（對(duì)偶單純形法）迭代，依次得表，得以重新尋優(yōu)。西南交通大學(xué)管理學(xué)院cj121000biCBXBx1x2x3x4x5x6200x2 X5 X61/211/21/2003/205/21/210011001403rj002101西南交通大學(xué)管理學(xué)院cj121000biCBXBx1x2x3x4x5x6200x2 X5 X41/211/21/2003/205/21/2101/2 01/21/201401rj002100cj121000biCBXBx1x2

38、x3x4x5x6201x2 X5 X1011001004113101102332rj002100= -5mazx例-2£0£1290³0, T 5,c =12,-=0A1()A6(1)b 變?yōu)?5(5)的系數(shù)變?yōu)?T,c10=(=x ，系數(shù)為35)(2)b 變?yōu)?5(6)增加一個(gè)變量61(3) c3變?yōu)?(4) c2變?yōu)?6(7)增加一個(gè)約束250(8)第二個(gè)約束1變0 為100解,T=2010)z*=100æ 10ö-1= ç -4÷1øBè西南交通大學(xué)管理學(xué)院cj-551300b(CBXBx1x2x3x4x550x2 x5-11310160-2-412010gj00-2-50解(1)最優(yōu)性不變，影響可行性= æçö÷1B