二章節(jié)單純形法ppt課件

1、第二章第二章 單純形法單純形法 p 單純形法的普通原理 p 表格單純形法 p 借助人工變量求初始的根本可行解p 單純形表與線性規(guī)劃問題的討論p 改良單純形法 思索到如下線性規(guī)劃問題 其中一個mn矩陣，且秩為m，總可以被調整為一個m維非負列向量，為n維行向量，為n維列向量。 根據(jù)線性規(guī)劃根本定理： 假設可行域= n / =，0非空有界， 那么上的最優(yōu)目的函數(shù)值=一定可以在的一個頂點上到達。 這個重要的定理啟發(fā)了Dantzig的單純形法， 即將尋優(yōu)的目的集中在D的各個頂點上。maxZ=CXAX=bX0p單純形法的普通原理單純形法的普通原理 Dantzig的單純形法把尋優(yōu)的目的集中在一切根本可行解即

2、可行域頂點中。其根本思緒是從一個初始的根本可行解出發(fā)，尋覓一條到達最優(yōu)根本可行解的最正確途徑。 單純形法的普通步驟如下： 1尋覓一個初始的根本可行解。 2檢查現(xiàn)行的根本可行解能否最優(yōu)，假設為最優(yōu)， 那么停頓迭代，已找到最優(yōu)解，否那么轉一步。 3移至目的函數(shù)值有所改善的另一個根本可行解， 然后轉會到步驟2。 n 確定初始的根本可行解確定初始的根本可行解 確定初始的根本可行解等價于確定初始的可行基，一旦初始的可行基確定了，那么對應的初始根本可行解也就獨一確定 為了討論方便，無妨假設在規(guī)范型線性規(guī)劃中，系數(shù)矩陣中前m個系數(shù)列向量恰好構成一個可行基，即 =，其中 =1，2，m為基變量x1，x2，xm的

3、系數(shù)列向量 構成的可行基， =(m+1，Pm+2， Pn)為非基變量xm+1，xm+2， xn的 系數(shù)列向量構成的矩陣。 所以約束方程所以約束方程 就可以表示為就可以表示為BBNNXAX=(BN)=BX+NX=bX 用可行基的逆陣-1左乘等式兩端，再經(jīng)過移項可推得：假設令一切非基變量, 那么基變量由此可得初始的根本可行解1B bX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =0問題：要判別m個系數(shù)列向量能否恰好構成一個基并不是一件容易的事。基由系數(shù)矩陣中m個線性無關的系數(shù)列向量構成。但是要判別m個系數(shù)列向量能否線性無關并非易事。即使系數(shù)矩陣中找到了一個基B，也不能保證

4、該基恰好是可行基。由于不能保證基變量B=-1b0。為了求得根本可行解 ，必需求基的逆陣-1。但是求逆陣-1也是一件費事的事。結論：在線性規(guī)劃規(guī)范化過程中設法得到一個m階單位矩陣I作為初始可行基，1B bX=0-1-1-1BNBNNBAX=bBX +NX =bX =B b-B NXX =0,X =B b 假設在化規(guī)范方式前，約束方程中有假設在化規(guī)范方式前，約束方程中有“不等式，不等式， 那么在化規(guī)范形時除了在方程式左端減去剩余變量使不等式變那么在化規(guī)范形時除了在方程式左端減去剩余變量使不等式變 成等式以外，還必需在左端再加上一個非負新變量，稱為成等式以外，還必需在左端再加上一個非負新變量，稱為

5、人工變量人工變量 假設在化規(guī)范方式前，約束方程中有等式方程，那么可以直接在假設在化規(guī)范方式前，約束方程中有等式方程，那么可以直接在 等式左端添加人工變量。等式左端添加人工變量。為了設法得到一個為了設法得到一個m m階單位矩陣階單位矩陣I I作為初始可行基，可在性規(guī)作為初始可行基，可在性規(guī)劃規(guī)范化過程中作如下處置：劃規(guī)范化過程中作如下處置： 假設在化規(guī)范方式前，m個約束方程都是“的方式，那么在化規(guī)范形時只需在一個約束不等式左端都加上一個松弛變量xn+i (i=12m)。n判別現(xiàn)行的根本可行解能否最優(yōu)判別現(xiàn)行的根本可行解能否最優(yōu) 假設已求得一個根本可行解將這一根本可行解代入目的函數(shù)，可求得相應的目

6、的函數(shù)值將這一根本可行解代入目的函數(shù)，可求得相應的目的函數(shù)值其中分別表示基變量和非基變量所對應的價值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )要斷定能否曾經(jīng)到達最大值，只需將代入目的函數(shù)，使目的函數(shù)用非基變量表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中 稱為非基變量N的檢驗向量，它的各個分量稱為檢驗數(shù)。假設N的每一個檢驗數(shù)均小于等于0，即N0，那么如今的根本可行解就是最優(yōu)解。-1-1BNX=B b-B NX-1BZ=C

7、B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X定理定理1 1：最優(yōu)解判別定理：最優(yōu)解判別定理 對于線性規(guī)劃問題對于線性規(guī)劃問題假設某個根本可行解所對應的檢驗向量，假設某個根本可行解所對應的檢驗向量，那么這個根本可行解就是最優(yōu)解。那么這個根本可行解就是最優(yōu)解。定理定理2 2：無窮多最優(yōu)解判別定理：無窮多最優(yōu)解判別定理 假設是一個根本可行解，所對應的檢驗向量假設是一個根本可行解，所對應的檢驗向量，其中存在一個檢驗數(shù)，其中存在

8、一個檢驗數(shù)m+k=0m+k=0，那么線性規(guī)劃問題有無窮多最優(yōu)解。那么線性規(guī)劃問題有無窮多最優(yōu)解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N01B bX=0-1NNB=C -C B N0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xn 根本可行解的改良根本可行解的改良 假設現(xiàn)行的根本可行解不是最優(yōu)解，即在檢驗向量 中存在正的檢驗數(shù)，那么需在原根本可行解的根底上尋覓一個新的根本可行解，并使目的函數(shù)值有所改善。詳細做法是：先從檢驗數(shù)為正的非基變量中確定一個換入變量，使它從非基變量變成基變量將它的值從零增至正值，再從原來的基變量中確定一個換出變量，使

9、它從基變量變成非基變量將它的值從正值減至零。由此可得一個新的根本可行解，由 可知，這樣的變換一定能使目的函數(shù)值有所添加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x 換入變量和換出變量確實定：換入變量和換出變量確實定：l換入變量確實定換入變量確實定 最大添加原那么最大添加原那么 假設檢驗向量假設檢驗向量 ， 假設其中有兩個以上的檢驗數(shù)為正，那么為了使目的函數(shù)值添加得假設其中有兩個以上的檢驗數(shù)為正，那么為了使目的函數(shù)值添加得快些，通常要用快些，通常要用“最大添加原那么，即選取最大正檢驗數(shù)所對應的非最大添加原那么，即選取最大正檢驗數(shù)所對應的非基變量為

10、換入變量，即假設基變量為換入變量，即假設 那么選取對應的那么選取對應的 為換入變量，為換入變量， 由于且為最大，由于且為最大， 因此當由零增至正值，因此當由零增至正值，可使目的函數(shù)值可使目的函數(shù)值 最大限制的添加。最大限制的添加。-1NNBm+1m+2n=C -C B N=(,)jjm+kmax / 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xl 換出變量確實定換出變量確實定 最小比值原那么最小比值原那么l 假設確定為換入變量，方程假設確定為換入變量，方程l l 其中為中與對應的系數(shù)列向量。其中為中與對應的系數(shù)列向量。l 如今需在

11、如今需在 中確定一個基變量為換出變量。中確定一個基變量為換出變量。l 當由零漸漸添加到某個值時，當由零漸漸添加到某個值時， 的非負性能夠被突破。的非負性能夠被突破。l 為堅持解的可行性，可以按最小比值原那么確定換出變量：為堅持解的可行性，可以按最小比值原那么確定換出變量：l 假設假設B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)min/(B P) 0,1im =(B P)(B P)ll m+kx-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Pxm+kPm+kxm+kx那么選取對應的基變量那么選取對應的基變量 為換出變

12、量。為換出變量。 xlBX 定理定理3 3：無最優(yōu)解判別定理：無最優(yōu)解判別定理 假設假設 是一個根本可行解，有一個檢驗數(shù)是一個根本可行解，有一個檢驗數(shù) ，但是，那么該線性規(guī)劃問題無最優(yōu)解。但是，那么該線性規(guī)劃問題無最優(yōu)解。1B bX=0-1m+kB P0m+k0證：令證：令 ，那么得新的可行解，那么得新的可行解將上式代入將上式代入由于由于 , , 故當故當+時，時，Z+Z+。-1-1-1-1Bm+km+km+kX =B b-B PxB b-B Pm+1-1-1Bm+1m+knBm+knxZ=C B b+(, )C B b+x m+kx,(0) m+k0n 用初等變換求改良了的根本可行解用初等變

13、換求改良了的根本可行解 假設是線性規(guī)劃 的可行基，那么令非基變量，那么基變量。可得根本可行解 。 1B bX=0BNXA X =b(B N )bXmaxZ=CX,AX=b,X0B-1-1NX(I,BN )=BbX用逆陣左乘約束方程組的兩端，等價于對方程組施以一系列用逆陣左乘約束方程組的兩端，等價于對方程組施以一系列的初等的初等“行變換。變換的結果是將系數(shù)矩陣中的可行基變換成行變換。變換的結果是將系數(shù)矩陣中的可行基變換成單位矩陣單位矩陣I I，把非基變量系數(shù)列向量構成的矩陣變換成，把，把非基變量系數(shù)列向量構成的矩陣變換成，把資源向量資源向量b b變換成。變換成。1B1BX =B b1B N1B

14、bNX =0且改良了的根本可行解只是在的基變量的根底上用一個換入變量替代其中一個換出變量，其它的基變量依然堅持不變。這些基變量的系數(shù)列向量是單位矩陣I中的單位向量。為了求得改良的根本可行解 ，只需對增廣矩陣 施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對應的單位向量即可。由于行初等變換后的方程組與原約束方程組 或同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N )=bXX123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x012210A=341018b7 C = ( 5

15、, 2 , 3 ,1 , 1 )例例1 1解：解：( () )確定初始的根本可行解。確定初始的根本可行解。 ，基變量，基變量 ，非基變量，非基變量 。4510B=(P P )=0145x ,x123x ,x ,x14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 1NB8X=0X=Bb=7X = (0 ,0 ,0 , 8 , 7 )T1B8Z=C B b=(-1,1)17 (2) 檢驗檢驗 能否最優(yōu)。能否最優(yōu)。檢驗向量檢驗向量 由于由于1=3，3=4 均大于零，均大于零，所以不是最優(yōu)解。所以不是最優(yōu)解。X =(0,0,0

16、,8, 7)T-1NNB123122=C-C B N=(5,2,3)-(-1,1)341=(5,2,3)-(2,2,-1)=(3, 0, 4) 14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x X =(0,0,0,8, 7)T3 3根本可行解的改良根本可行解的改良 選取換入變量選取換入變量由于由于max3max3，4=44=4，取，取x3x3為換入變量。為換入變量。 選取換出變量選取換出變量 且且 ， 選取選取x4x4為換出變量為換出變量. .8 78min,2 12X = (0,0,0,8, 7 )T11382Bb=

17、,BP07114BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x N123=(,)(3, 0, 4)4-1-13335x82=B b-B P x =-xx71 4 4求改良了的根本可行解求改良了的根本可行解 對約束方程組的增廣矩陣施以初等行變換，使換入變量對約束方程組的增廣矩陣施以初等行變換，使換入變量x3x3所對應的所對應的系數(shù)列向量系數(shù)列向量 變換成換出變量變換成換出變量x4x4所對應的單位向量所對應的單位向量 , , 留意堅持基變量留意堅持基變量x5x5的系數(shù)列向量的系數(shù)列向量 為單位向量不變。為單位向量不變。32P

18、 =1 41P0 50P =1 111 104122 108 2234 10 1734 10 17111 10422 5-1301 322 X14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 第一行除以第一行除以第二行減去第一行第二行減去第一行可得改良的根本可行解。 ， 基 變 量 ， 非 基 變 量。根本可行解目的函數(shù)值易見目的函數(shù)值比原來的Z=-1添加了， 再轉向步驟(2)3510B=(P P )=0113BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)

19、015-133x22 1NB4X =0X =B b=3X = (0,0,4, 0, 3)T1B4Z=C Bb=(3,1)153C = ( 5 ,2 ,3 ,1,1)C = (5 ,2 ,3 ,1,1)111 10412210822 5341017-130132235x x124x ,x ,x2檢驗檢驗 能否最優(yōu)。能否最優(yōu)。檢驗向量檢驗向量由于，由于，所以仍不是最優(yōu)解。所以仍不是最優(yōu)解。X = (0,0,4, 0, 3)T-1NNB12411122=C-C B N=(5,2,-1)-(3,1)5-1322=(5,2,-1)-(4,6,1)=(1, -4, -2) X =(0,0,4, 0,3)T

20、13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 110 3 3根本可行解的改良根本可行解的改良 選取換入變量選取換入變量由于，取為換入變量。由于，取為換入變量。 選取換出變量選取換出變量且且 ，選取為換出變量選取為換出變量. .433min,1/2 5/25/2X = (0,0,4, 0, 3)T111142Bb=, BP0352110 1x5x13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 3-1-11115x41/2

21、=B b-B P x =-xx35/2 4 4求改良了的根本可行解求改良了的根本可行解 對約束方程組的增廣矩陣施以初等行變換，使換入變量所對應對約束方程組的增廣矩陣施以初等行變換，使換入變量所對應的系數(shù)列向量變換成換出變量所對應的單位向量的系數(shù)列向量變換成換出變量所對應的單位向量 , , 112P =5250P1 X1x5x111111041104 2222665-12-11030135555223172-101 5555 66-12105555 13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 第二行乘以第

22、二行乘以/第一行減以第二行的第一行減以第二行的/倍倍可得改良的根本可行解。 ，基變量，非基變量根本可行解目的函數(shù)值 比Z=15添加了，再轉向步驟(2)3110B=(P P )=012B3BN4N1523-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x55551NB175X =0X =B b=65617X=(,0,0,0)55T1B17815Z=C Bb=(3,5)655C = (5 ,2 ,3,1,1)C = (5 ,2 ,3,1,1)31x ,x245x ,x ,x3172-111011104555522 566-1-123

23、013102255552檢驗 能否最優(yōu)。檢驗向量由于一切檢驗數(shù)均小于零，所以是最優(yōu)解，-1NNB24523-1555=C-CBN =(2,-1,1)-(3,5)6-125553647-26-9-2=(2,-1,1)-(,)=(,)555555 617X =(,0,0,0)55T*617X =X =(,0,0,0)55T*81Z =52B3BN4N1523-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x5555p表格單純形法表格單純形法經(jīng)過例我們發(fā)現(xiàn)，在單純形法的求解過程中，有以下重要目的：每一個根本可行解的檢驗向量根據(jù)檢驗向量

24、可以確定所求得的根本可行解能否為最優(yōu)解。假設不是最優(yōu)又可以經(jīng)過檢驗向量確定適宜的換入變量。每一個根本可行解所對應的目的函數(shù)值經(jīng)過目的函數(shù)值可以察看單純形法的每次迭代能否能使目的函數(shù)值有效地添加，直至求得最優(yōu)目的函數(shù)為止。 在單純形法求解過程中，每一個根本可行解都以某個經(jīng)過初等行變換的約束方程組中的單位矩陣為可行基。當=時，-1=，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b 可將這些重要結論的計算設計成如下一個簡單的表格，即單純形表來完成：C CBCN CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1C2.Cm m X1X2 .Xm b1b2

25、.bm I I N 12.m Z CBb 0 CN- - CBN 例例2 2、試利用單純形表求例、試利用單純形表求例1 1中的最優(yōu)解解：中的最優(yōu)解解：得初始的單純形表：得初始的單純形表：C = (5 ,2 ,3 ,1,1)122108(Ab)=341017123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x0NNB=C-C NBZ=C b初始根本可行解，初始根本可行解，Z= -1Z= -1，X =(0,0,0,8, 7)T 1 2 2 1 08x4-1 3 0 4 0 0-1Z 3 4 1 0 17x51 x1 x2 x3 x4

26、 x5bXBCB 5 2 3 -1 1C換入變量，換出變量，為主元進展旋轉變換換入變量，換出變量，為主元進展旋轉變換3x4x根本可行解，根本可行解，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2 1 1 1/2 04x33 1 -4 0 -2 015Z5/2 3 0 -1/2 13x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 1 2 2 1 08x4-1 3 0 4 0 0-1Z 3 4 1 0 17x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C8/27/1最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值 617X,0,0,055T換入變量，換出變

27、量，換入變量，換出變量，/ /為主元進展旋轉變換為主元進展旋轉變換1x5xNNB=C-C N081Z54/1/21/2 1 1 1/2 04x33 1 -4 0 -2 015Z3/5/25/2 3 0 -1/2 13x51x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 0 2/5 1 3/5 -1/517/5x33 0 -26/5 0 -9/5 -2/581/5Z 1 6/5 0 -1/5 2/56/5x15 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C例例3 3、用單純形方法求解線性規(guī)劃問題、用單純形方法求解線性規(guī)劃問題解：此題的目的函數(shù)是求極小化的線性函數(shù)

28、，解：此題的目的函數(shù)是求極小化的線性函數(shù)，可以令可以令那么那么這兩個線性規(guī)劃問題具有一樣的可行域和最優(yōu)解，這兩個線性規(guī)劃問題具有一樣的可行域和最優(yōu)解，只是目的函數(shù)相差一個符號而已。只是目的函數(shù)相差一個符號而已。 121324125jminZ=-x -2xxx4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ 0 1 0 1 03x22 0 0 1 2 -12x30-0 1 0 1 03x224/11 0 1 0 04x303/10 1 0 1 03x40_1 0 1 0 04x30 0 0 0 0 -18Z 1 0 0

29、 -2 12x11 1 0 0 -2 06Z2/11 0 0 -2 12x50 1 2 0 0 00Z8/21 2 0 0 18x50 x1 x2 x3 x4 x5bXBCB 1 2 0 0 0C最優(yōu)解最優(yōu)值最優(yōu)解最優(yōu)值X2,3,2,0,0TmaxZ =8 or minZ=-82/23/1- 由于非基變量x4的檢驗數(shù)4=0，由無窮多最優(yōu)解判別定理，本例的線性規(guī)劃問題存在無窮多最優(yōu)解?，F(xiàn)實上假設以x4為換入變量，以x3為換出變量，再進展一次迭代，可得一下單純形表：最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值最優(yōu)解的普通表示式最優(yōu)解的普通表示式maxZ=8 or minZ=-8X4,2,0,1,0TX(2,3,2,

30、0,0)(1) 4,2,0,1,0,01.TTC 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x4x2x1124 0 0 1/2 1 -1/2 0 1 -1/2 0 1/2 1 0 1 0 0Z8 0 0 0 0 -1對于極小化的線性規(guī)劃問題的處置：對于極小化的線性規(guī)劃問題的處置：先化為規(guī)范型，即將極小化問題變換為極大化問題，然后利用單先化為規(guī)范型，即將極小化問題變換為極大化問題，然后利用單純形方法求解純形方法求解直接利用單純形方法求解，但是檢驗能否最優(yōu)的準那么有所不同直接利用單純形方法求解，但是檢驗能否最優(yōu)的準那么有所不同，即：即： 假設某個根本可行解的一切非基變量對應的

31、檢驗數(shù)假設某個根本可行解的一切非基變量對應的檢驗數(shù) 而不是而不是，那么根本可行解為最優(yōu)解那么根本可行解為最優(yōu)解否那么采用最大減少原那么而非最大添加原那么來確定換入否那么采用最大減少原那么而非最大添加原那么來確定換入變量，變量，即：即： 假設假設那么選取對應的非基變量那么選取對應的非基變量xm+kxm+k為換入變量為換入變量確定了換入變量以后，換出變量仍采用最小比值原那么來確定。確定了換入變量以后，換出變量仍采用最小比值原那么來確定。 NNB= C-CN0jjm+kmin / 0因因但但所以原問題所以原問題無最優(yōu)解無最優(yōu)解1-1P=01-2n 退化解 當線性規(guī)劃問題的根本可行解中有一個或多個基變

32、量取零值時，稱此根本可行解為退化解。 產(chǎn)生的緣由：在單純形法計算中用最小比值原那么確定換出變量時，有時存在兩個或兩個以上一樣的最小比值，那么在下次迭代中就會出現(xiàn)一個甚至多個基變量等于零。遇到的問題：當某個基變量為零，且下次迭代以該基變量作為換出變量時，目的函數(shù)并不能因此得到任何改動由旋轉變換性質可知，任何一個換入變量只能仍取零值，其它基變量的取值堅持不變。經(jīng)過基變換以后的前后兩個退化的根本可行解的坐標方式完全一樣。從幾何角度來解釋，這兩個退化的根本可行解對應線性規(guī)劃可行域的同一個頂點，處理的方法：最小比值原那么計算時存在兩個及其以上一樣的最小比值時，選取下標最大的基變量為換出變量，按此方法進展

33、迭代一定能防止循環(huán)景象的產(chǎn)生攝動法原理。例例8 8、求解下述線性規(guī)劃問題：、求解下述線性規(guī)劃問題：解：引入松弛變量解：引入松弛變量化規(guī)范型化規(guī)范型123412341234 3jmaxZ=3x -80 x +2x -24xx -32x -4x36x 0 x -24x - x 6x 0 x 1 x0,j1,2,3,41234123451234 637jmaxZ=3x -80 x +2x -24xx -32x -4x36x x 0 x -24x - x 6x x 0 x x 1 x0,j1,2,3,4,5,6,7567x ,x ,x000-242-8030Z-5-60-420-805Z1000100

34、1x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代第一次迭代中運用了攝動中運用了攝動法原理，選擇法原理，選擇下標為下標為6的基的基變量變量x6離基。離基?？傻米顑?yōu)解可得最優(yōu)解 ，目的函數(shù)值，目的函數(shù)值maxZ=，X1,0,1,0,3Tn 無窮多最優(yōu)解無窮多最優(yōu)解 無窮多最優(yōu)

35、解判別原理：假設線性規(guī)劃問題某個根本可行解一切的非基變量檢驗數(shù)都小于等于零，但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例：最優(yōu)表：非基變量檢驗數(shù)，所以有無窮多最優(yōu)解。最優(yōu)解集為可行域兩個頂點的凸組合：C1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -14= 0X(2,3,2,0,0)(1) 4,2,0,1,0,01.TTn改良單純形法的特點改良單純形法的特點n 利用單純形表求解線性規(guī)劃時，每一次迭利用單純形表求解線性規(guī)劃時，每一次迭代都把整個單純

36、形表計算一遍，現(xiàn)實上我們關懷代都把整個單純形表計算一遍，現(xiàn)實上我們關懷的只是以下一些數(shù)據(jù)：的只是以下一些數(shù)據(jù)：n根本可行解根本可行解 ，其相應的目的函數(shù)值，其相應的目的函數(shù)值 ，n非基變量檢驗數(shù)非基變量檢驗數(shù) ，及其換入，及其換入變量變量 ，n 設設n主元列元素主元列元素 ，及其換出變量，及其換出變量 ，n設設n 利用它們可得到一組新的基變量以及新的可行利用它們可得到一組新的基變量以及新的可行基基1 1。1-1-1iki-11kik(B b)(B b)min/(B P ) 0, i (B P )(B P )llp改良單純形法改良單純形法-1BX =B b-1BZ=C B b-1NNB=C -C

37、 B Nkxxl-1kB P為基變量下標為基變量下標jjkmax / 0, j =為非基變量下標為非基變量下標對任一根本可行解，只需知道，上述關鍵數(shù)據(jù)都可以從線性規(guī)劃問題的初始數(shù)據(jù)直接計算出來。因此如何計算根本可行解對應的可行基的逆陣成為改良單純形法的關鍵改良單純形法推導出從可行基變換到1時，到的變換公式。當初始可行基為單位矩陣時，變換公式將更具有優(yōu)越性，由于這樣可以防止矩陣求逆的費事以下推導從到的變換公式：-1B-1B-1B-11B-1B-11B-1BX =B b-1BZ=C B b-1NNB=C -C B N-1kB P-1-1-1-1-1-1-11211mB B(B P ,B P ,B

38、P ,B P,B P ,B P )lllm m1.0.0.1-1-1-1-1-1-1-11121k1mB B(B P ,B P ,B P ,B P ,B P ,B P )ll-1121k1m(, , , ,B P , , )lleeeee1211mB(P,P ,P ,P,P ,P )lll假設當前基，假設當前基， 基變換中用非基變量取代基變量基變換中用非基變量取代基變量可得新基可得新基前后二個基相比僅相差一列，且前后二個基相比僅相差一列，且比較以上二式，可得比較以上二式，可得 xl1121k1mB(P,P ,P ,P ,P ,P )llkx其中表示第個元素為其中表示第個元素為1 1，其它元素均

39、為零的單位列向量，其它元素均為零的單位列向量，為主元列元素。為主元列元素。 iei-1kB P假設 ，那么1k2k-1KkmkaaB P =aal1klk2klkkm klka1-0aa-a111k1aa0-1a-E(BB )ll-1-111211mB B(, , , ,B P , , )lkleeeee第列換出變量對應列第列換出變量對應列 第行第行l(wèi)l所以由所以由-1-1-1-1-1k111kE(B B )BB BE Bllxl主元素主元素n改良單純形法的步驟改良單純形法的步驟n1 1根據(jù)給出的線性規(guī)劃問題的規(guī)范型，根據(jù)給出的線性規(guī)劃問題的規(guī)范型，確定初始基變量和初始可行基。求初始可行基確定

40、初始基變量和初始可行基。求初始可行基B B的逆陣的逆陣-1-1，得初始根本可行解，得初始根本可行解n。 n2 2計算單純形乘子計算單純形乘子 ，得目的函數(shù)，得目的函數(shù)當前值當前值n 3 3 計 算 非 基 變 量 檢 驗 數(shù)計 算 非 基 變 量 檢 驗 數(shù)，n假設假設N0N0，那么當前解已是最優(yōu)解，停頓，那么當前解已是最優(yōu)解，停頓計算；否那么轉下一步。計算；否那么轉下一步。n4 4 根據(jù)，確定非基變根據(jù)，確定非基變量為換入變量，計算量為換入變量，計算, ,假設假設00，那么問題沒有有限最優(yōu)解，停頓計算，那么問題沒有有限最優(yōu)解，停頓計算，n否那么轉下一步。否那么轉下一步。-1B=C B-1NN

41、BN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB P5 5 根據(jù)根據(jù) ，確定基變量，確定基變量 為換出變量。為換出變量。 6 6 用替代用替代 得新基得新基1 1，由變換公式，由變換公式計算新基的逆陣計算新基的逆陣1-11-1，求出新的根本可行解，求出新的根本可行解 其中為變換矩陣，構造方法是：其中為變換矩陣，構造方法是： 從一個單位矩陣出發(fā)，把換出變量從一個單位矩陣出發(fā)，把換出變量 在基在基B B中的對應列的單位中的對應列的單位 向量，交換成換入變量向量，交換成換入變量 對應的系數(shù)列向量對應的系數(shù)列向量 ，并做

42、如下變形，并做如下變形， 主元素主元素 應在主對角線上取倒數(shù)，其它元素除以主元素應在主對角線上取倒數(shù)，其它元素除以主元素 并取相反數(shù)。并取相反數(shù)。反復反復2 26 6直至求得最優(yōu)解。直至求得最優(yōu)解。 -1-1-1iki-1-1kik(B b)(B b)min/(B P ) 0 =(B P )(B P )llxlPlkP-1-11k BE Blk Elkal-1kB Pxlkxkal B=I-1BNX =B b,X0-1B=C BZ=bNN=C -Nkx換入換入-1kB P無界解無界解換出換出xl1 B-1-11k BE Bl最優(yōu)解最優(yōu)解jjkmax / 0 =-1-1-1iki-1-1kik(

43、B b)(B b)min/(B P ) 0 =(B P )(B P )ll初始基初始基maxZ=CXAX=bX0新基新基 例9、試用改良單純形法求解解：察看法確定，為基變量 為非基變量 121231241234maxZ=3x +2x x +x +x =402x +x +x =60 x ,x ,x ,x01 1 10A=2101C = (3 ,2 ,0 ,0 )4 0b =6 003410B =(P P )=0134x ,x-1-10B0010104040B, X =B b=, X(0,0,40,60)01016060T12x ,x 2計算單純行乘子 目的函數(shù)當前值 3非基變量檢驗數(shù)-1-10B034010 =C B(c ,c )B(0,0)(0,0)010040Z = b = (0,0)060NN0120121211 =C - N=(c ,c )- (P P )=(3,2)-(0,0)= (3, 2)21 (4(4 選擇換入變量選擇換入變量 故故 為換入