單純形法大M法求解線性規(guī)劃問題（課堂PPT）

1、.1第二章第二章 單純形法單純形法 p 單純形法的一般原理單純形法的一般原理 p 表格單純形法表格單純形法 p 借助人工變量求初始的基本可行解借助人工變量求初始的基本可行解p 單純形表與線性規(guī)劃問題的討論單純形表與線性規(guī)劃問題的討論p 改進單純形法改進單純形法 .2 考慮到如下線性規(guī)劃問題考慮到如下線性規(guī)劃問題 其中一個其中一個m mn n矩陣，且秩為矩陣，且秩為m m，總可以被調(diào)整為一個，總可以被調(diào)整為一個m m維非負列維非負列向量，為向量，為n n維行向量，為維行向量，為n n維列向量。維列向量。 根據(jù)線性規(guī)劃基本定理：根據(jù)線性規(guī)劃基本定理： 如果可行域如果可行域= = n n / / =

2、 =，00非空有界，非空有界， 則上的最優(yōu)目標函數(shù)值則上的最優(yōu)目標函數(shù)值= =一定可以在的一個頂點上達到。一定可以在的一個頂點上達到。 這個重要的定理啟發(fā)了這個重要的定理啟發(fā)了DantzigDantzig的單純形法，的單純形法， 即將尋優(yōu)的目標集中在即將尋優(yōu)的目標集中在D D的各個頂點上。的各個頂點上。maxZ=CXAX=bX0p單純形法的一般原理單純形法的一般原理 .3 DantzigDantzig的單純形法把尋優(yōu)的目標集中在所有基本可行解的單純形法把尋優(yōu)的目標集中在所有基本可行解（即可行域頂點）中。（即可行域頂點）中。其基本思路是從一個初始的基本可行解出發(fā)，尋找一條達到其基本思路是從一個初

3、始的基本可行解出發(fā)，尋找一條達到最優(yōu)基本可行解的最佳途徑。最優(yōu)基本可行解的最佳途徑。 單純形法的一般步驟如下：單純形法的一般步驟如下： （1 1）尋找一個初始的基本可行解。）尋找一個初始的基本可行解。 （2 2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)， 則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。 （3 3）移至目標函數(shù)值有所改善的另一個基本可行解，）移至目標函數(shù)值有所改善的另一個基本可行解， 然后轉(zhuǎn)會到步驟（然后轉(zhuǎn)會到步驟（2 2）。）。 .4n 確定初始的基本可行解確定初始的基本可行解 確定初始的基本可行解等價于

4、確定初始的可行基，一旦初始確定初始的基本可行解等價于確定初始的可行基，一旦初始的可行基確定了，那么對應(yīng)的初始基本可行解也就唯一確定的可行基確定了，那么對應(yīng)的初始基本可行解也就唯一確定 為了討論方便，不妨假設(shè)在標準型線性規(guī)劃中，系數(shù)矩陣為了討論方便，不妨假設(shè)在標準型線性規(guī)劃中，系數(shù)矩陣中前中前m m個系數(shù)列向量恰好構(gòu)成一個可行基，即個系數(shù)列向量恰好構(gòu)成一個可行基，即 = =（），其中（），其中 = =（1 1，2 2，m m）為基變量）為基變量x x1 1，x x2 2，xxm m的系數(shù)列向量的系數(shù)列向量 構(gòu)成的可行基，構(gòu)成的可行基， =(=(m+1m+1，P Pm+2m+2， P Pn n)

5、)為非基變量為非基變量x xm+1m+1，x xm+2m+2， xxn n的的 系數(shù)列向量構(gòu)成的矩陣。系數(shù)列向量構(gòu)成的矩陣。 .5所以約束方程所以約束方程 就可以表示為就可以表示為BBNNXAX=(BN)=BX+NX=bX 用可行基的逆陣用可行基的逆陣-1-1左乘等式兩端，再通過移項可推得：左乘等式兩端，再通過移項可推得：若令所有非基變量若令所有非基變量, , 則基變量則基變量由此可得初始的基本可行解由此可得初始的基本可行解1B bX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =0.6l 問題：問題： 要判斷要判斷m m個系數(shù)列向量是否恰好構(gòu)成一個基并不是一件容易的事

6、。個系數(shù)列向量是否恰好構(gòu)成一個基并不是一件容易的事?；上禂?shù)矩陣中基由系數(shù)矩陣中m m個線性無關(guān)的系數(shù)列向量構(gòu)成。個線性無關(guān)的系數(shù)列向量構(gòu)成。但是要判斷但是要判斷m m個系數(shù)列向量是否線性無關(guān)并非易事。個系數(shù)列向量是否線性無關(guān)并非易事。 即使系數(shù)矩陣中找到了一個基即使系數(shù)矩陣中找到了一個基B B，也不能保證該基恰好是可行基。，也不能保證該基恰好是可行基。因為不能保證基變量因為不能保證基變量B B= =-1-1b0b0。 為了求得基本可行解為了求得基本可行解 ，必須求基的逆陣，必須求基的逆陣-1-1。但是求逆陣但是求逆陣-1-1也是一件麻煩的事。也是一件麻煩的事。l 結(jié)論：在線性規(guī)劃標準化過程中

7、設(shè)法得到一個結(jié)論：在線性規(guī)劃標準化過程中設(shè)法得到一個m m階單位矩陣階單位矩陣I I作為初始作為初始可行基，可行基，1B bX=0-1-1-1BNBNNBAX=bBX +NX =bX =B b-B NXX =0,X =B b.7 若在化標準形式前，約束方程中有若在化標準形式前，約束方程中有“”不等式，不等式，那么在化標準形時除了在方程式左端減去剩余變量使不等式變那么在化標準形時除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個非負新變量，稱為成等式以外，還必須在左端再加上一個非負新變量，稱為人工變量人工變量 若在化標準形式前，約束方程中有等式方程，那么可以直接在若在化標準

8、形式前，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。等式左端添加人工變量。為了設(shè)法得到一個為了設(shè)法得到一個m m階單位矩陣階單位矩陣I I作為初始可行基，可在性規(guī)作為初始可行基，可在性規(guī)劃標準化過程中作如下處理：劃標準化過程中作如下處理： 若在化標準形式前，若在化標準形式前，m m個約束方程都是個約束方程都是“”的形式，的形式，那么在化標準形時只需在一個約束不等式左端都加上一個松弛變那么在化標準形時只需在一個約束不等式左端都加上一個松弛變量量x xn+in+i (i=12m) (i=12m)。.8n判斷現(xiàn)行的基本可行解是否最優(yōu)判斷現(xiàn)行的基本可行解是否最優(yōu) 假如已求得一個基本可行解

9、假如已求得一個基本可行解將這一基本可行解代入目標函數(shù)，可求得相應(yīng)的目標函數(shù)值將這一基本可行解代入目標函數(shù)，可求得相應(yīng)的目標函數(shù)值其中分別表示基變量和其中分別表示基變量和非基變量所對應(yīng)的價值系數(shù)子向量。非基變量所對應(yīng)的價值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c ).9要判定是否已經(jīng)達到最大值，只需將要判定是否已經(jīng)達到最大值，只需將代入目標函數(shù)，使目標函數(shù)用非代入目標函數(shù)，使目標函數(shù)用非基變量基變量表示，即：表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+

10、XC B b+( )x 其中其中 稱為非基變量稱為非基變量N N的檢驗向量，它的各個分量稱為檢驗數(shù)。若的檢驗向量，它的各個分量稱為檢驗數(shù)。若N N的每一個檢驗數(shù)均小的每一個檢驗數(shù)均小于等于于等于0 0，即，即N N00，那么現(xiàn)在的基本可行解就是最優(yōu)解。，那么現(xiàn)在的基本可行解就是最優(yōu)解。-1-1BNX=B b-B NX-1BZ=C 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.10定理定理1 1：最優(yōu)解判別定理：最優(yōu)解判

11、別定理 對于線性規(guī)劃問題對于線性規(guī)劃問題若某個基本可行解所對應(yīng)的檢驗向量，若某個基本可行解所對應(yīng)的檢驗向量，則這個基本可行解就是最優(yōu)解。則這個基本可行解就是最優(yōu)解。定理定理2 2：無窮多最優(yōu)解判別定理：無窮多最優(yōu)解判別定理 若是一個基本可行解，所對應(yīng)的檢驗向量若是一個基本可行解，所對應(yīng)的檢驗向量，其中存在一個檢驗數(shù)，其中存在一個檢驗數(shù)m+km+k=0=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+(

12、)x.11n 基本可行解的改進基本可行解的改進 如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗向量如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗向量 中存在正的檢驗數(shù)，則需在原基本可行解的基中存在正的檢驗數(shù)，則需在原基本可行解的基礎(chǔ)上尋找一個新的基本可行解，并使目標函數(shù)值有所改善。具體礎(chǔ)上尋找一個新的基本可行解，并使目標函數(shù)值有所改善。具體做法是：做法是： 先從檢驗數(shù)為正的非基變量中確定一個換入變量，使它從非基先從檢驗數(shù)為正的非基變量中確定一個換入變量，使它從非基變量變成基變量（將它的值從零增至正值），變量變成基變量（將它的值從零增至正值）， 再從原來的基變量中確定一個換出變量，使它從基變量變成非再從原來

13、的基變量中確定一個換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。基變量（將它的值從正值減至零）。由此可得一個新的基本可行解，由由此可得一個新的基本可行解，由 可知，這樣的變換一定能使目標函數(shù)值有所增加。可知，這樣的變換一定能使目標函數(shù)值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x.12 換入變量和換出變量的確定換入變量和換出變量的確定：l換入變量的確定換入變量的確定 最大增加原則最大增加原則 假設(shè)檢驗向量假設(shè)檢驗向量 ， 若其中有兩個以上的檢驗數(shù)為正，那么為了使目標函數(shù)值增加得快若其中有兩個以上的檢驗數(shù)為正，那么為了使目標

14、函數(shù)值增加得快些，通常要用些，通常要用“最大增加原則最大增加原則”，即選取最大正檢驗數(shù)所對應(yīng)的非基，即選取最大正檢驗數(shù)所對應(yīng)的非基變量為換入變量，即若變量為換入變量，即若 則選取對應(yīng)的則選取對應(yīng)的 為換入變量，為換入變量， 由于且為最大，由于且為最大， 因此當(dāng)由零增至正值，因此當(dāng)由零增至正值，可使目標函數(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+( )x.13l 換出變量的確定換出變量的確定 最小比值原則最小比值原則

15、 如果確定為換入變量，方程如果確定為換入變量，方程其中為中與對應(yīng)的系數(shù)列向量。其中為中與對應(yīng)的系數(shù)列向量。現(xiàn)在需在現(xiàn)在需在 中確定一個基變量為換出變量。中確定一個基變量為換出變量。 當(dāng)由零慢慢增加到某個值時，當(dāng)由零慢慢增加到某個值時， 的非負性可能被打破。的非負性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：為保持解的可行性，可以按最小比值原則確定換出變量： 若若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

16、NXX=B b-B Pxm+kPm+kxm+kx則選取對應(yīng)的基變量則選取對應(yīng)的基變量 為換出變量。為換出變量。 xlBX.14 定理定理3 3：無最優(yōu)解判別定理：無最優(yōu)解判別定理 若若 是一個基本可行解，有一個檢驗數(shù)是一個基本可行解，有一個檢驗數(shù) ，但是，則該線性規(guī)劃問題無最優(yōu)解。但是，則該線性規(guī)劃問題無最優(yōu)解。1B bX=0-1m+kB P0m+k0證：令證：令 ，則得新的可行解，則得新的可行解將上式代入將上式代入因為因為 , , 故當(dāng)故當(dāng)+時，時，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+(,

17、 )C B b+x m+kx,(0) m+k0.15n 用初等變換求改進了的基本可行解用初等變換求改進了的基本可行解 假設(shè)是線性規(guī)劃假設(shè)是線性規(guī)劃 的可行基，則的可行基，則令非基變量，則基變量。令非基變量，則基變量?？傻没究尚薪饪傻没究尚薪?。 1B bX=0BNXA X =b(B N )bXmaxZ=CX,AX=b,X0B-1-1NX(I,BN )=BbX用逆陣左乘約束方程組的兩端，等價于對方程組施以一系列用逆陣左乘約束方程組的兩端，等價于對方程組施以一系列的初等的初等“行變換行變換”。變換的結(jié)果是將系數(shù)矩陣中的可行基變換成。變換的結(jié)果是將系數(shù)矩陣中的可行基變換成單位矩陣單位矩陣I I，

18、把非基變量系數(shù)列向量構(gòu)成的矩陣變換成，把，把非基變量系數(shù)列向量構(gòu)成的矩陣變換成，把資源向量資源向量b b變換成。變換成。1B1BX =B b1B N1B bNX =0.16且改進了的基本可行解只是在的基變量的基礎(chǔ)上用一個換且改進了的基本可行解只是在的基變量的基礎(chǔ)上用一個換入變量替代其中一個換出變量，其它的基變量仍然保持不變。這些入變量替代其中一個換出變量，其它的基變量仍然保持不變。這些基變量的系數(shù)列向量是單位矩陣基變量的系數(shù)列向量是單位矩陣I I中的單位向量。為了求得改進的基中的單位向量。為了求得改進的基本可行解本可行解 ，只需對增廣矩陣，只需對增廣矩陣 施行初等行變換，將換入變量的系數(shù)列向量

19、變換成換出變量所對施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對應(yīng)的單位向量即可。應(yīng)的單位向量即可。由于行初等變換后的方程組由于行初等變換后的方程組與原約束方程組與原約束方程組 或同解或同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N )=bXX.17123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x012210A=341018b7 C = ( 5 , 2 , 3 ,1 , 1 )例例1 1解：解：( () )確定初始的基本可行解。確定初始的基本可行解。 ，基變量，基變

20、量 ，非基變量，非基變量 。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 .18(2) 檢驗檢驗 是否最優(yōu)。是否最優(yōu)。檢驗向量檢驗向量 因為因為1 1=3=3，3 3=4 =4 均大于零，均大于零，所以不是最優(yōu)解。所以不是最優(yōu)解。X =(0,0,0,8, 7)T-1NNB123122=C-C B N=(5,2,3)-(-1,1)341=(5,2

21、,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)T.19（3）基本可行解的改進基本可行解的改進 選取換入變量選取換入變量因為因為max3max3，4=44=4，取，取x x3 3為換入變量。為換入變量。 選取換出變量選取換出變量 且且 ， 選取選取x x4 4為換出變量為換出變量. .8 78min,2 12X = (0,0,0,8, 7 )T11382Bb=,BP07114BBN25N3xxC =(-1,1)101228X =,X = x,

22、B=,N=,b=xC =(5,2,3)013417x N123=(,)(3, 0, 4)4-1-13335x82=B b-B P x =-xx71 .20（4）求改進了的基本可行解求改進了的基本可行解 對約束方程組的增廣矩陣施以初等行變換，使換入變量對約束方程組的增廣矩陣施以初等行變換，使換入變量x x3 3所對應(yīng)的所對應(yīng)的系數(shù)列向量系數(shù)列向量 變換成換出變量變換成換出變量x x4 4所對應(yīng)的單位向量所對應(yīng)的單位向量 , , 注意保持基變量注意保持基變量x x5 5的系數(shù)列向量的系數(shù)列向量 為單位向量不變。為單位向量不變。32P =1 41P0 50P =1 111 104122 108 22

23、34 10 1734 10 17111 10422 5-1301 322 X14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 第一行除以第一行除以第二行減去第一行第二行減去第一行.21可得改進的基本可行解?？傻酶倪M的基本可行解。 ，基變量，基變量，非基變量。非基變量?；究尚薪饣究尚薪饽繕撕瘮?shù)值目標函數(shù)值易見目標函數(shù)值比原來的易見目標函數(shù)值比原來的Z=-1Z=-1增加了，增加了， 再轉(zhuǎn)向步驟再轉(zhuǎn)向步驟(2)(2)3510B=(P P )=0113BBN25N411x1xC =(3,1)10422X =,X = x,B

24、=,N=,b=xC =(5,2,-1)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 ,x.22（2）檢驗檢驗 是否最優(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,

25、-4, -2) X =(0,0,4, 0,3)T13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 110 .23（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,-

26、1)015-133x22 3-1-11115x41/2=B b-B P x =-xx35/2 .24（4）求改進了的基本可行解求改進了的基本可行解 對約束方程組的增廣矩陣施以初等行變換，使換入變量所對應(yīng)對約束方程組的增廣矩陣施以初等行變換，使換入變量所對應(yīng)的系數(shù)列向量變換成換出變量所對應(yīng)的單位向量的系數(shù)列向量變換成換出變量所對應(yīng)的單位向量 , , 112P =5250P1 X1x5x111111041104 2222665-12-11030135555223172-101 5555 66-12105555 13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b

27、=xC =(5,2,-1)015-133x22 第二行乘以第二行乘以/第一行減以第二行的第一行減以第二行的/倍倍.25可得改進的基本可行解?？傻酶倪M的基本可行解。 ，基變量，基變量，非基變量非基變量基本可行解基本可行解目標函數(shù)值目標函數(shù)值 比比Z=15Z=15增加了，再轉(zhuǎn)向步增加了，再轉(zhuǎn)向步驟驟(2)(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

28、 = (5 ,2 ,3,1,1)C = (5 ,2 ,3,1,1)31x ,x245x ,x ,x3172-111011104555522 566-1-12301310225555.26（2）檢驗檢驗 是否最優(yōu)。是否最優(yōu)。檢驗向量檢驗向量因為所有檢驗數(shù)均小于零，因為所有檢驗數(shù)均小于零，所以是最優(yōu)解，所以是最優(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 =

29、(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x5555.27p表格單純形法表格單純形法通過例我們發(fā)現(xiàn)，在單純形法的求解過程中，有下列重要指標：通過例我們發(fā)現(xiàn)，在單純形法的求解過程中，有下列重要指標：l 每一個基本可行解的檢驗向量每一個基本可行解的檢驗向量根據(jù)檢驗向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不根據(jù)檢驗向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過檢驗向量確定合適的換入變量。是最優(yōu)又可以通過檢驗向量確定合適的換入變量。l 每一個基本可行解所對應(yīng)的目標函數(shù)值每一個基本可行解所對應(yīng)的目標函數(shù)值通過目標函數(shù)值可

30、以觀察單純形法的每次迭代是否能使目標函數(shù)值通過目標函數(shù)值可以觀察單純形法的每次迭代是否能使目標函數(shù)值有效地增加，直至求得最優(yōu)目標函數(shù)為止。有效地增加，直至求得最優(yōu)目標函數(shù)為止。 在單純形法求解過程中，每一個基本可行解都以在單純形法求解過程中，每一個基本可行解都以某個經(jīng)過初等行某個經(jīng)過初等行變換的變換的約束方程組中的單位矩陣約束方程組中的單位矩陣為可行基。為可行基。當(dāng)當(dāng)= =時，時，-1-1= =，易知：，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b.28 可將這些重要結(jié)論的計算設(shè)計成如下一個簡單的表格，可將這些重要結(jié)論的計算設(shè)計成如下一個簡單的表格，即單純形表

31、來完成：即單純形表來完成：C CBCN CB XB b X1X2Xm Xm+1Xm+2Xn C1C2.Cm X1X2.Xm b1b2.bm I I N 12.m Z CBb 0 CN- -CBN .29例例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

32、=(0,0,0,8, 7)T122108x4-130400-1Z341017x51x1x2x3x4x5bXBCB523-11C.30換入變量，換出變量，為主元進行旋轉(zhuǎn)變換換入變量，換出變量，為主元進行旋轉(zhuǎn)變換3x4x基本可行解，基本可行解，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2111/204x331-40-2015Z5/230-1/213x51x1x2x3x4x5bXBCB523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCB523-11C8/27/1.31最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值 617X,0,0,055T換入變量，換出

33、變量，換入變量，換出變量，/ /為主元進行旋轉(zhuǎn)變換為主元進行旋轉(zhuǎn)變換1x5xNNB=C-C N081Z54/1/21/2111/204x331-40-2015Z3/5/25/230-1/213x51x1x2x3x4x5bXBCB523-11C02/513/5-1/517/5x330-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCB523-11C.32例例3 3、用單純形方法求解線性規(guī)劃問題、用單純形方法求解線性規(guī)劃問題解：本題的目標函數(shù)是求極小化的線性函數(shù)，解：本題的目標函數(shù)是求極小化的線性函數(shù)，可以令可以令則則這兩個線性規(guī)劃問題具有相同的

34、可行域和最優(yōu)解，這兩個線性規(guī)劃問題具有相同的可行域和最優(yōu)解，只是目標函數(shù)相差一個符號而已。只是目標函數(shù)相差一個符號而已。 121324125jminZ=-x -2xxx4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ.33010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x300000-18Z100-212x11100-206Z2/1100-212x50120000Z8/2120018x50 x1x2x3x4x5bXBCB12000C最優(yōu)解最優(yōu)值最

35、優(yōu)解最優(yōu)值X2,3,2,0,0TmaxZ =8 or minZ=-82/23/1-.34 因為非基變量因為非基變量x x4 4的檢驗數(shù)的檢驗數(shù)4 4=0=0，由無窮多最優(yōu)解判別定理，本例，由無窮多最優(yōu)解判別定理，本例的線性規(guī)劃問題存在無窮多最優(yōu)解。事實上若以的線性規(guī)劃問題存在無窮多最優(yōu)解。事實上若以x x4 4為換入變量，以為換入變量，以x x3 3為為換出變量，再進行一次迭代，可得一下單純形表：換出變量，再進行一次迭代，可得一下單純形表：最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值最優(yōu)解的一般表示式最優(yōu)解的一般表示式maxZ=8 or minZ=-8X4,2,0,1,0TX(2,3,2,0,0)(1) 4,2

36、,0,1,0,01.TTC12000CBXBbx1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z80000-1.35對于極小化的線性規(guī)劃問題的處理：對于極小化的線性規(guī)劃問題的處理：l先化為標準型，即將極小化問題變換為極大化問題，然后利用單先化為標準型，即將極小化問題變換為極大化問題，然后利用單純形方法求解純形方法求解l直接利用單純形方法求解，但是檢驗是否最優(yōu)的準則有所不同，直接利用單純形方法求解，但是檢驗是否最優(yōu)的準則有所不同，即：即： 若某個基本可行解的所有非基變量對應(yīng)的檢驗數(shù)若某個基本可行解的所有非基變量對應(yīng)的檢驗數(shù) （而不是（而不是），），則

37、基本可行解為最優(yōu)解則基本可行解為最優(yōu)解否則采用最大減少原則（而非最大增加原則）來確定換入變量，否則采用最大減少原則（而非最大增加原則）來確定換入變量，即：即： 若若則選取對應(yīng)的非基變量則選取對應(yīng)的非基變量x xm+km+k為換入變量為換入變量 確定了換入變量以后，換出變量仍采用最小比值原則來確定。確定了換入變量以后，換出變量仍采用最小比值原則來確定。 NNB= C-CN0jjm+kmin / 0因因但但所以原問題所以原問題無最優(yōu)解無最優(yōu)解1-1P=01-2.53n 退化解 當(dāng)線性規(guī)劃問題的基本可行解中有一個或多個基變量取零值時，當(dāng)線性規(guī)劃問題的基本可行解中有一個或多個基變量取零值時，稱此基本可

38、行解為退化解。稱此基本可行解為退化解。 產(chǎn)生的原因：在單純形法計算中用最小比值原則確定換出變量時，產(chǎn)生的原因：在單純形法計算中用最小比值原則確定換出變量時，有時存在兩個或兩個以上相同的最小比值有時存在兩個或兩個以上相同的最小比值，那么在下次迭代中就會，那么在下次迭代中就會出現(xiàn)一個甚至多個基變量等于零。出現(xiàn)一個甚至多個基變量等于零。遇到的問題：當(dāng)某個基變量為零，且下次迭代以該基變量作為換遇到的問題：當(dāng)某個基變量為零，且下次迭代以該基變量作為換出變量時，目標函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可出變量時，目標函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可知，任何一個換入變量只能仍取零值，其它基

39、變量的取值保持不知，任何一個換入變量只能仍取零值，其它基變量的取值保持不變）。通過基變換以后的前后兩個退化的基本可行解的坐標形式完變）。通過基變換以后的前后兩個退化的基本可行解的坐標形式完全相同。從幾何角度來解釋，這兩個退化的基本可行解對應(yīng)線性規(guī)全相同。從幾何角度來解釋，這兩個退化的基本可行解對應(yīng)線性規(guī)劃可行域的同一個頂點，劃可行域的同一個頂點，解決的辦法：最小比值原則計算時存在兩個及其以上相同的最小解決的辦法：最小比值原則計算時存在兩個及其以上相同的最小比值時，選取下標最大的基變量為換出變量，按此方法進行迭代一比值時，選取下標最大的基變量為換出變量，按此方法進行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生（

40、攝動法原理）。定能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動法原理）。.54例例8 8、求解下述線性規(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 ,x.55000-242-8030Z-5-60-420

41、-805Z10001001x3212060-2411x13321300-803x500-30-425-800Z11001001x700106-1-2410 x130-1130-3-800 x50-11001001x7000106-1-2410 x60000136-4-3210 x50 x7x6x5x4x3x2x1bXBCB000-242-803C第一次迭代第一次迭代中使用了攝動中使用了攝動法原理，選擇法原理，選擇下標為下標為6的基的基變量變量x6離基。離基?？傻米顑?yōu)解可得最優(yōu)解，目標函數(shù)值，目標函數(shù)值maxZ=，X1,0,1,0,3T.56n 無窮多最優(yōu)解無窮多最優(yōu)解 無窮多最優(yōu)解判別原理：無

42、窮多最優(yōu)解判別原理：若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數(shù)都小于等于零，若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數(shù)都小于等于零，但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例：最優(yōu)表：例：最優(yōu)表：非基變量檢驗非基變量檢驗數(shù)，數(shù)，所以有無窮多所以有無窮多最優(yōu)解。最優(yōu)解。最優(yōu)解集為可行域兩個頂點的凸組合：最優(yōu)解集為可行域兩個頂點的凸組合：C12000CBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z80000-14= 0X(2,3,2,0,0)(1)

43、 4,2,0,1,0,01.TT.57n改進單純形法的特點改進單純形法的特點 利用單純形表求解線性規(guī)劃時，每一次迭代都把整個單純形表計利用單純形表求解線性規(guī)劃時，每一次迭代都把整個單純形表計算一遍，事實上我們關(guān)心的只是以下一些數(shù)據(jù)：算一遍，事實上我們關(guān)心的只是以下一些數(shù)據(jù)：l基本可行解基本可行解 ，其相應(yīng)的目標函數(shù)值，其相應(yīng)的目標函數(shù)值 ，l非基變量檢驗數(shù)非基變量檢驗數(shù) ，及其換入變量，及其換入變量 ， 設(shè)設(shè)主元列元素主元列元素 ，及其換出變量，及其換出變量 ，設(shè)設(shè) 利用它們可得到一組新的基變量以及新的可行基利用它們可得到一組新的基變量以及新的可行基1 1。1-1-1iki-11kik(B b

44、)(B b)min/(B P ) 0, i (B P )(B P )llp改進單純形法改進單純形法-1BX =B b-1BZ=C B b-1NNB=C -C B Nkxxl-1kB P為基變量下標為基變量下標jjkmax / 0, j =為非基變量下標為非基變量下標.58對對任一基本可行解，任一基本可行解，只要知道，上述關(guān)鍵數(shù)據(jù)都可以從只要知道，上述關(guān)鍵數(shù)據(jù)都可以從線性規(guī)劃問題的初始數(shù)據(jù)直接計算出來。因此如何計算基本可行解線性規(guī)劃問題的初始數(shù)據(jù)直接計算出來。因此如何計算基本可行解對應(yīng)的可行基的逆陣成為改進單純形法的關(guān)鍵對應(yīng)的可行基的逆陣成為改進單純形法的關(guān)鍵改進單純形法推導(dǎo)出從可行基變換到改進

45、單純形法推導(dǎo)出從可行基變換到1 1時，到時，到的變換公式。當(dāng)初始可行基為單位矩陣的變換公式。當(dāng)初始可行基為單位矩陣時，變換公式將更具有優(yōu)時，變換公式將更具有優(yōu)越性，因為這樣可以避免矩陣求逆的麻煩越性，因為這樣可以避免矩陣求逆的麻煩以下推導(dǎo)從到的變換公式：以下推導(dǎo)從到的變換公式：-1B-1B-1B-11B-1B-11B-1BX =B b-1BZ=C B b-1NNB=C -C B N-1kB P.59-1-1-1-1-1-1-11211mB B(B P,B P ,B 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

46、 P ,B P ,B P ,B P )ll-1121k1m(, , , ,B P , , )lleeeee1211mB(P ,P ,P ,P ,P ,P )lll假設(shè)當(dāng)前基假設(shè)當(dāng)前基， 基變換中用非基變量取代基變量基變換中用非基變量取代基變量可得新基可得新基前后二個基相比僅相差一列，且前后二個基相比僅相差一列，且比較以上二式，可得比較以上二式，可得 xl1121k1mB(P,P ,P ,P ,P ,P )llkx其中表示第個元素為其中表示第個元素為1 1，其它元素均為零的單位列向量，其它元素均為零的單位列向量，為主元列元素。為主元列元素。 iei-1kB P.60假設(shè)假設(shè) ，則則1k2k-1K

47、kmkaaB P =aal1klk2klkkm klka1-0aa-a111k1aa0-1a-E(BB )ll-1-111211mB B(, , , ,B P , , )lkleeeee第列第列（換出變量對應(yīng)列（換出變量對應(yīng)列 ）第行第行l(wèi)l所以由所以由-1-1-1-1-1k111kE(B B )BB BE Bllxl主元素主元素.61n改進單純形法的步驟改進單純形法的步驟（1 1）根據(jù)給出的線性規(guī)劃問題的標準型，確定初始基變量和初）根據(jù)給出的線性規(guī)劃問題的標準型，確定初始基變量和初始可行基。求初始可行基始可行基。求初始可行基B B的逆陣的逆陣-1-1，得初始基本可行解，得初始基本可行解。 （

48、2 2）計算單純形乘子）計算單純形乘子 ，得目標函數(shù)當(dāng)前值，得目標函數(shù)當(dāng)前值（3 3）計算非基變量檢驗數(shù)，計算非基變量檢驗數(shù)，若若N N00，則當(dāng)前解已是最優(yōu)解，停止計算；否則轉(zhuǎn)下一步。，則當(dāng)前解已是最優(yōu)解，停止計算；否則轉(zhuǎn)下一步。（4 4）根據(jù)，確定非基變量為換入變量，根據(jù)，確定非基變量為換入變量，計算計算, ,若若00，則問題沒有有限最優(yōu)解，停止計算，則問題沒有有限最優(yōu)解，停止計算，否則轉(zhuǎn)下一步。否則轉(zhuǎn)下一步。-1B=C B-1NNBN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB P.62（5 5） 根據(jù)根據(jù)

49、 ，確定基變量，確定基變量 為換出變量。為換出變量。 （6 6） 用替代用替代 得新基得新基1 1，由變換公式，由變換公式計算新基的逆陣計算新基的逆陣1 1-1-1，求出新的基本可行解，求出新的基本可行解 其中為變換矩陣，構(gòu)造方法是：其中為變換矩陣，構(gòu)造方法是： 從一個單位矩陣出發(fā)，把換出變量從一個單位矩陣出發(fā)，把換出變量 在基在基B B中的對應(yīng)列的單位中的對應(yīng)列的單位 向量，替換成換入變量向量，替換成換入變量 對應(yīng)的系數(shù)列向量對應(yīng)的系數(shù)列向量 ，并做如下變形，并做如下變形， 主元素主元素 （應(yīng)在主對角線上）取倒數(shù)，其它元素除以主元素（應(yīng)在主對角線上）取倒數(shù)，其它元素除以主元素 并取相反數(shù)。并

50、取相反數(shù)。重復(fù)（重復(fù)（2 2）（）（6 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.63 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(B b)(B b)min/(B P ) 0 =(B P )(B P )ll初始基初始基maxZ=CXAX=bX0新基新基.64 例例9 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.65 （2 2）計