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

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

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

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

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

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

6、的函數(shù)值將這一根本可行解代入目的函數(shù)，可求得相應(yīng)的目的函數(shù)值其中分別表示基變量和非基變量所對應(yīng)的價(jià)值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )要斷定能否曾經(jīng)到達(dá)最大值，只需將代入目的函數(shù)，使目的函數(shù)用非基變量表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中 稱為非基變量N的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。假設(shè)N的每一個(gè)檢驗(yà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ī)劃問題假設(shè)某個(gè)根本可行解所對應(yīng)的檢驗(yàn)向量，假設(shè)某個(gè)根本可行解所對應(yīng)的檢驗(yàn)向量，那么這個(gè)根本可行解就是最優(yōu)解。那么這個(gè)根本可行解就是最優(yōu)解。定理定理2 2：無窮多最優(yōu)解判別定理：無窮多最優(yōu)解判別定理 假設(shè)是一個(gè)根本可行解，所對應(yīng)的檢驗(yàn)向量假設(shè)是一個(gè)根本可行解，所對應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)，其中存在

8、一個(gè)檢驗(yàn)數(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 根本可行解的改良根本可行解的改良 假設(shè)現(xiàn)行的根本可行解不是最優(yōu)解，即在檢驗(yàn)向量 中存在正的檢驗(yàn)數(shù)，那么需在原根本可行解的根底上尋覓一個(gè)新的根本可行解，并使目的函數(shù)值有所改善。詳細(xì)做法是：先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量將它的值從零增至正值，再從原來的基變量中確定一個(gè)換出變量，使

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

10、換入變量，即假設(shè)基變量為換入變量，即假設(shè) 那么選取對應(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+( )xl 換出變量確實(shí)定換出變量確實(shí)定 最小比值原那么最小比值原那么l 假設(shè)確定為換入變量，方程假設(shè)確定為換入變量，方程l l 其中為中與對應(yīng)的系數(shù)列向量。其中為中與對應(yīng)的系數(shù)列向量。l 如今需在

11、如今需在 中確定一個(gè)基變量為換出變量。中確定一個(gè)基變量為換出變量。l 當(dāng)由零漸漸添加到某個(gè)值時(shí)，當(dāng)由零漸漸添加到某個(gè)值時(shí)， 的非負(fù)性能夠被突破。的非負(fù)性能夠被突破。l 為堅(jiān)持解的可行性，可以按最小比值原那么確定換出變量：為堅(jiān)持解的可行性，可以按最小比值原那么確定換出變量：l 假設(shè)假設(shè)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那么選取對應(yīng)的基變量那么選取對應(yīng)的基變量 為換出變

12、量。為換出變量。 xlBX 定理定理3 3：無最優(yōu)解判別定理：無最優(yōu)解判別定理 假設(shè)假設(shè) 是一個(gè)根本可行解，有一個(gè)檢驗(yàn)數(shù)是一個(gè)根本可行解，有一個(gè)檢驗(yàn)數(shù) ，但是，那么該線性規(guī)劃問題無最優(yōu)解。但是，那么該線性規(guī)劃問題無最優(yōu)解。1B bX=0-1m+kB P0m+k0證：令證：令 ，那么得新的可行解，那么得新的可行解將上式代入將上式代入由于由于 , , 故當(dāng)故當(dāng)+時(shí)，時(shí)，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、換求改良了的根本可行解 假設(shè)是線性規(guī)劃 的可行基，那么令非基變量，那么基變量?？傻酶究尚薪?。 1B bX=0BNXA X =b(B N )bXmaxZ=CX,AX=b,X0B-1-1NX(I,BN )=BbX用逆陣左乘約束方程組的兩端，等價(jià)于對方程組施以一系列用逆陣左乘約束方程組的兩端，等價(jià)于對方程組施以一系列的初等的初等“行變換。變換的結(jié)果是將系數(shù)矩陣中的可行基變換成行變換。變換的結(jié)果是將系數(shù)矩陣中的可行基變換成單位矩陣單位矩陣I I，把非基變量系數(shù)列向量構(gòu)成的矩陣變換成，把，把非基變量系數(shù)列向量構(gòu)成的矩陣變換成，把資源向量資源向量b b變換成。變換成。1B1BX =B b1B N1B

14、bNX =0且改良了的根本可行解只是在的基變量的根底上用一個(gè)換入變量替代其中一個(gè)換出變量，其它的基變量依然堅(jiān)持不變。這些基變量的系數(shù)列向量是單位矩陣I中的單位向量。為了求得改良的根本可行解 ，只需對增廣矩陣 施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對應(yīng)的單位向量即可。由于行初等變換后的方程組與原約束方程組 或同解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àn)檢驗(yàn) 能否最優(yōu)。能否最優(yōu)。檢驗(yàn)向量檢驗(yàn)向量 由于由于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所對應(yīng)的所對應(yīng)的系數(shù)列向量系數(shù)列向量 變換成換出變量變換成換出變量x4x4所對應(yīng)的單位向量所對應(yīng)的單位向量 , , 留意堅(jiān)持基變量留意堅(jiān)持基變量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添加了， 再轉(zhuǎn)向步驟(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àn)檢驗(yàn) 能否最優(yōu)。能否最優(yōu)。檢驗(yàn)向量檢驗(yàn)向量由于，由于，所以仍不是最優(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求改良了的根本可行解求改良了的根本可行解 對約束方程組的增廣矩陣施以初等行變換，使換入變量所對應(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=xC =(5,2,-1)015-133x22 第二行乘以第

22、二行乘以/第一行減以第二行的第一行減以第二行的/倍倍可得改良的根本可行解。 ，基變量，非基變量根本可行解目的函數(shù)值 比Z=15添加了，再轉(zhuǎn)向步驟(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àn) 能否最優(yōu)。檢驗(yàn)向量由于一切檢驗(yàn)數(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)，在單純形法的求解過程中，有以下重要目的：每一個(gè)根本可行解的檢驗(yàn)向量根據(jù)檢驗(yàn)向量

24、可以確定所求得的根本可行解能否為最優(yōu)解。假設(shè)不是最優(yōu)又可以經(jīng)過檢驗(yàn)向量確定適宜的換入變量。每一個(gè)根本可行解所對應(yīng)的目的函數(shù)值經(jīng)過目的函數(shù)值可以察看單純形法的每次迭代能否能使目的函數(shù)值有效地添加，直至求得最優(yōu)目的函數(shù)為止。 在單純形法求解過程中，每一個(gè)根本可行解都以某個(gè)經(jīng)過初等行變換的約束方程組中的單位矩陣為可行基。當(dāng)=時(shí)，-1=，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b 可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡單的表格，即單純形表來完成：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、試?yán)脝渭冃伪砬罄?、試?yán)脝渭冃伪砬罄? 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換入變量，換出變量，為主元進(jìn)展旋轉(zhuǎn)變換換入變量，換出變量，為主元進(jìn)展旋轉(zhuǎn)變換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、量，換入變量，換出變量，/ /為主元進(jìn)展旋轉(zhuǎn)變換為主元進(jìn)展旋轉(zhuǎn)變換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ù)，可以令可以令那么那么這兩個(gè)線性規(guī)劃問題具有一樣的可行域和最優(yōu)解，這兩個(gè)線性規(guī)劃問題具有一樣的可行域和最優(yōu)解，只是目的函數(shù)相差一個(gè)符號而已。只是目的函數(shù)相差一個(gè)符號而已。 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的檢驗(yàn)數(shù)4=0，由無窮多最優(yōu)解判別定理，本例的線性規(guī)劃問題存在無窮多最優(yōu)解?，F(xiàn)實(shí)上假設(shè)以x4為換入變量，以x3為換出變量，再進(jìn)展一次迭代，可得一下單純形表：最優(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àn)?zāi)芊褡顑?yōu)的準(zhǔn)那么有所不同直接利用單純形方法求解，但是檢驗(yàn)?zāi)芊褡顑?yōu)的準(zhǔn)那么有所不同，即：即： 假設(shè)某個(gè)根本可行解的一切非基變量對應(yīng)的

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

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

33、迭代一定能防止循環(huán)景象的產(chǎn)生攝動(dòng)法原理。例例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 第一次迭代第一次迭代中運(yùn)用了攝動(dòng)中運(yùn)用了攝動(dòng)法原理，選擇法原理，選擇下標(biāo)為下標(biāo)為6的基的基變量變量x6離基。離基?？傻米顑?yōu)解可得最優(yōu)解 ，目的函數(shù)值，目的函數(shù)值maxZ=，X1,0,1,0,3Tn 無窮多最優(yōu)解無窮多最優(yōu)解 無窮多最優(yōu)

35、解判別原理：假設(shè)線性規(guī)劃問題某個(gè)根本可行解一切的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例：最優(yōu)表：非基變量檢驗(yàn)數(shù)，所以有無窮多最優(yōu)解。最優(yōu)解集為可行域兩個(gè)頂點(diǎn)的凸組合：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改良單純形法的特點(diǎn)改良單純形法的特點(diǎn)n 利用單純形表求解線性規(guī)劃時(shí)，每一次迭利用單純形表求解線性規(guī)劃時(shí)，每一次迭代都把整個(gè)單純

36、形表計(jì)算一遍，現(xiàn)實(shí)上我們關(guān)懷代都把整個(gè)單純形表計(jì)算一遍，現(xiàn)實(shí)上我們關(guān)懷的只是以下一些數(shù)據(jù)：的只是以下一些數(shù)據(jù)：n根本可行解根本可行解 ，其相應(yīng)的目的函數(shù)值，其相應(yīng)的目的函數(shù)值 ，n非基變量檢驗(yàn)數(shù)非基變量檢驗(yàn)數(shù) ，及其換入，及其換入變量變量 ，n 設(shè)設(shè)n主元列元素主元列元素 ，及其換出變量，及其換出變量 ，n設(shè)設(shè)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為基變量下標(biāo)為基變量下標(biāo)jjkmax / 0, j =為非基變量下標(biāo)為非基變量下標(biāo)對任一根本可行解，只需知道，上述關(guān)鍵數(shù)據(jù)都可以從線性規(guī)劃問題的初始數(shù)據(jù)直接計(jì)算出來。因此如何計(jì)算根本可行解對應(yīng)的可行基的逆陣成為改良單純形法的關(guān)鍵改良單純形法推導(dǎo)出從可行基變換到1時(shí)，到的變換公式。當(dāng)初始可行基為單位矩陣時(shí)，變換公式將更具有優(yōu)越性，由于這樣可以防止矩陣求逆的費(fèi)事以下推導(dǎo)從到的變換公式：-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假設(shè)當(dāng)前基，假設(shè)當(dāng)前基， 基變換中用非基變量取代基變量基變換中用非基變量取代基變量可得新基可得新基前后二個(gè)基相比僅相差一列，且前后二個(gè)基相比僅相差一列，且比較以上二式，可得比較以上二式，可得 xl1121k1mB(P,P ,P ,P ,P ,P )llkx其中表示第個(gè)元素為其中表示第個(gè)元素為1 1，其它元素均

39、為零的單位列向量，其它元素均為零的單位列向量，為主元列元素。為主元列元素。 iei-1kB P假設(shè) ，那么1k2k-1KkmkaaB 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主元素主元素n改良單純形法的步驟改良單純形法的步驟n1 1根據(jù)給出的線性規(guī)劃問題的規(guī)范型，根據(jù)給出的線性規(guī)劃問題的規(guī)范型，確定初始基變量和初始可行基。求初始可行基確定

40、初始基變量和初始可行基。求初始可行基B B的逆陣的逆陣-1-1，得初始根本可行解，得初始根本可行解n。 n2 2計(jì)算單純形乘子計(jì)算單純形乘子 ，得目的函數(shù)，得目的函數(shù)當(dāng)前值當(dāng)前值n 3 3 計(jì) 算 非 基 變 量 檢 驗(yàn) 數(shù)計(jì) 算 非 基 變 量 檢 驗(yàn) 數(shù)，n假設(shè)假設(shè)N0N0，那么當(dāng)前解已是最優(yōu)解，停頓，那么當(dāng)前解已是最優(yōu)解，停頓計(jì)算；否那么轉(zhuǎn)下一步。計(jì)算；否那么轉(zhuǎn)下一步。n4 4 根據(jù)，確定非基變根據(jù)，確定非基變量為換入變量，計(jì)算量為換入變量，計(jì)算, ,假設(shè)假設(shè)00，那么問題沒有有限最優(yōu)解，停頓計(jì)算，那么問題沒有有限最優(yōu)解，停頓計(jì)算，n否那么轉(zhuǎn)下一步。否那么轉(zhuǎ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，由變換公式，由變換公式計(jì)算新基的逆陣計(jì)算新基的逆陣1-11-1，求出新的根本可行解，求出新的根本可行解 其中為變換矩陣，構(gòu)造方法是：其中為變換矩陣，構(gòu)造方法是： 從一個(gè)單位矩陣出發(fā)，把換出變量從一個(gè)單位矩陣出發(fā)，把換出變量 在基在基B B中的對應(yīng)列的單位中的對應(yīng)列的單位 向量，交換成換入變量向量，交換成換入變量 對應(yīng)的系數(shù)列向量對應(yīng)的系數(shù)列向量 ，并做

42、如下變形，并做如下變形， 主元素主元素 應(yīng)在主對角線上取倒數(shù)，其它元素除以主元素應(yīng)在主對角線上取倒數(shù)，其它元素除以主元素 并取相反數(shù)。并取相反數(shù)。反復(fù)反復(fù)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計(jì)算單純行乘子 目的函數(shù)當(dāng)前值 3非基變量檢驗(yàn)數(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 選擇換入變量選擇換入變量 故故 為換入