單純形法大M法求解線性規(guī)劃問(wèn)題

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

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

3、達(dá)到其基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。最優(yōu)基本可行解的最佳途徑。 單純形法的一般步驟如下：?jiǎn)渭冃畏ǖ囊话悴襟E如下： （1 1）尋找一個(gè)初始的基本可行解。）尋找一個(gè)初始的基本可行解。 （2 2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)， 則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。 （3 3）移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解，）移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解， 然后轉(zhuǎn)會(huì)到步驟（然后轉(zhuǎn)會(huì)到步驟（2 2）。）。 編輯ppt4n 確定初始的基本可行解確定初始的基本可

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

5、m+2m+2， P Pn n) )為非基變量為非基變量x xm+1m+1，x xm+2m+2， xxn n的的 系數(shù)列向量構(gòu)成的矩陣。系數(shù)列向量構(gòu)成的矩陣。 編輯ppt5所以約束方程所以約束方程 就可以表示為就可以表示為BBNNXAX=(BN)=BX+NX=bX 用可行基的逆陣用可行基的逆陣-1-1左乘等式兩端，再通過(guò)移項(xiàng)可推得：左乘等式兩端，再通過(guò)移項(xiàng)可推得：若令所有非基變量若令所有非基變量, , 則基變量則基變量由此可得初始的基本可行解由此可得初始的基本可行解1B bX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =0編輯ppt6l 問(wèn)題：?jiǎn)栴}： 要判斷要判斷m m

6、個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事。個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事。基由系數(shù)矩陣中基由系數(shù)矩陣中m m個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。但是要判斷但是要判斷m m個(gè)系數(shù)列向量是否線性無(wú)關(guān)并非易事。個(gè)系數(shù)列向量是否線性無(wú)關(guān)并非易事。 即使系數(shù)矩陣中找到了一個(gè)基即使系數(shù)矩陣中找到了一個(gè)基B B，也不能保證該基恰好是可行基。，也不能保證該基恰好是可行基。因?yàn)椴荒鼙ＷC基變量因?yàn)椴荒鼙ＷC基變量B B= =-1-1b0b0。 為了求得基本可行解為了求得基本可行解 ，必須求基的逆陣，必須求基的逆陣-1-1。但是求逆陣但是求逆陣-1-1也是一件麻煩的事。也

7、是一件麻煩的事。l 結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中設(shè)法得到一個(gè)結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中設(shè)法得到一個(gè)m m階單位矩陣階單位矩陣I I作為初始作為初始可行基，可行基，1B bX=0-1-1-1BNBNNBAX=bBX +NX =bX =B b-B NXX =0,X =B b編輯ppt7 若在化標(biāo)準(zhǔn)形式前，約束方程中有若在化標(biāo)準(zhǔn)形式前，約束方程中有“”不等式，不等式，那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量使不等式變那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個(gè)非負(fù)新變量，稱(chēng)為成等式以外，還必須在左端再加上一個(gè)非負(fù)新變量，稱(chēng)為人工變量人工變量 若在化標(biāo)

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

9、解是否最優(yōu)判斷現(xiàn)行的基本可行解是否最優(yōu) 假如已求得一個(gè)基本可行解假如已求得一個(gè)基本可行解將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值其中分別表示基變量和其中分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )編輯ppt9要判定是否已經(jīng)達(dá)到最大值，只需將要判定是否已經(jīng)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量基變量表示，即：表示，

10、即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中其中 稱(chēng)為非基變量稱(chēng)為非基變量N N的檢驗(yàn)向量，它的各個(gè)分量稱(chēng)為檢驗(yàn)數(shù)。若的檢驗(yàn)向量，它的各個(gè)分量稱(chēng)為檢驗(yàn)數(shù)。若N N的每一個(gè)檢驗(yàn)數(shù)均小的每一個(gè)檢驗(yàn)數(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

11、b+(C -C B N)X編輯ppt10定理定理1 1：最優(yōu)解判別定理：最優(yōu)解判別定理 對(duì)于線性規(guī)劃問(wèn)題對(duì)于線性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。則這個(gè)基本可行解就是最優(yōu)解。定理定理2 2：無(wú)窮多最優(yōu)解判別定理：無(wú)窮多最優(yōu)解判別定理 若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)，其中存在一個(gè)檢驗(yàn)數(shù)m+km+k=0=0，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N01B bX=0-1NNB

12、=C -C B N0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )x編輯ppt11n 基本可行解的改進(jìn)基本可行解的改進(jìn) 如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗(yàn)向量如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗(yàn)向量 中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：做法是： 先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值），變量變成基變量（

13、將它的值從零增至正值）， 再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）?；兞浚▽⑺闹祻恼禍p至零）。由此可得一個(gè)新的基本可行解，由由此可得一個(gè)新的基本可行解，由 可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加?？芍?，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x編輯ppt12 換入變量和換出變量的確定換入變量和換出變量的確定：l換入變量的確定換入變量的確定 最大增加原則最大增加原則 假設(shè)檢驗(yàn)向量假設(shè)檢驗(yàn)向量 ， 若其中

14、有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用些，通常要用“最大增加原則最大增加原則”，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量為換入變量，即若變量為換入變量，即若 則選取對(duì)應(yīng)的則選取對(duì)應(yīng)的 為換入變量，為換入變量， 由于且為最大，由于且為最大， 因此當(dāng)由零增至正值，因此當(dāng)由零增至正值，可使目標(biāo)函數(shù)值可使目標(biāo)函數(shù)值 最大限度的增加。最大限度的增加。-1NNBm+1m+2n=C -C B N=(,)jjm+kmax / 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1

15、,nnxxZC B b+( )x編輯ppt13l 換出變量的確定換出變量的確定 最小比值原則最小比值原則 如果確定為換入變量，方程如果確定為換入變量，方程其中為中與對(duì)應(yīng)的系數(shù)列向量。其中為中與對(duì)應(yīng)的系數(shù)列向量?，F(xiàn)在需在現(xiàn)在需在 中確定一個(gè)基變量為換出變量。中確定一個(gè)基變量為換出變量。 當(dāng)由零慢慢增加到某個(gè)值時(shí)，當(dāng)由零慢慢增加到某個(gè)值時(shí)， 的非負(fù)性可能被打破。的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：為保持解的可行性，可以按最小比值原則確定換出變量： 若若B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)min/(B

16、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則選取對(duì)應(yīng)的基變量則選取對(duì)應(yīng)的基變量 為換出變量。為換出變量。 xlBX編輯ppt14 定理定理3 3：無(wú)最優(yōu)解判別定理：無(wú)最優(yōu)解判別定理 若若 是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù) ，但是，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。但是，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。1B bX=0-1m+kB P0m+k0證：令證：令 ，則得新的可行解，則得新的可行解將上式代入將上式代入因?yàn)橐驗(yàn)?, , 故當(dāng)故當(dāng)+時(shí)，時(shí)，Z+Z+。-1-1-1-1Bm+

17、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+k0編輯ppt15n 用初等變換求改進(jìn)了的基本可行解用初等變換求改進(jìn)了的基本可行解 假設(shè)是線性規(guī)劃假設(shè)是線性規(guī)劃 的可行基，則的可行基，則令非基變量，則基變量。令非基變量，則基變量?？傻没究尚薪饪傻没究尚薪?。 1B bX=0BNXA X =b(B N )bXmaxZ=CX,AX=b,X0B-1-1NX(I,BN )=BbX用逆陣左乘約束方程組的兩端，等價(jià)于對(duì)方程組施以一系列用逆陣左乘約束方程組的兩端，等價(jià)于對(duì)方程組施以一系列的初等的初等

18、“行變換行變換”。變換的結(jié)果是將系數(shù)矩陣中的可行基變換成。變換的結(jié)果是將系數(shù)矩陣中的可行基變換成單位矩陣單位矩陣I I，把非基變量系數(shù)列向量構(gòu)成的矩陣變換成，把，把非基變量系數(shù)列向量構(gòu)成的矩陣變換成，把資源向量資源向量b b變換成。變換成。1B1BX =B b1B N1B bNX =0編輯ppt16且改進(jìn)了的基本可行解只是在的基變量的基礎(chǔ)上用一個(gè)換且改進(jìn)了的基本可行解只是在的基變量的基礎(chǔ)上用一個(gè)換入變量替代其中一個(gè)換出變量，其它的基變量仍然保持不變。這些入變量替代其中一個(gè)換出變量，其它的基變量仍然保持不變。這些基變量的系數(shù)列向量是單位矩陣基變量的系數(shù)列向量是單位矩陣I I中的單位向量。為了求得

19、改進(jìn)的基中的單位向量。為了求得改進(jìn)的基本可行解本可行解 ，只需對(duì)增廣矩陣，只需對(duì)增廣矩陣 施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對(duì)施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量即可。應(yīng)的單位向量即可。由于行初等變換后的方程組由于行初等變換后的方程組與原約束方程組與原約束方程組 或同解或同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N )=bXX編輯ppt17123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x012210A=341018b7 C

20、 = ( 5 , 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 編輯ppt18(2) 檢驗(yàn)檢驗(yàn) 是否最優(yōu)。是否最優(yōu)。檢驗(yàn)向量檢驗(yàn)向量 因?yàn)橐驗(yàn)? 1=3=3，3 3=4 =4 均大于零，均大于零，所以

21、不是最優(yōu)解。所以不是最優(yōu)解。X =(0,0,0,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)T編輯ppt19（3）基本可行解的改進(jìn)基本可行解的改進(jìn) 選取換入變量選取換入變量因?yàn)橐驗(yàn)閙ax3max3，4=44=4，取，取x x3 3為換入變量。為換入變量。 選取換出變量選取換出變量 且且 ， 選取選取x x4 4為換出變量為換出變量. .8 78

22、min,2 12X = (0,0,0,8, 7 )T11382Bb=,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 編輯ppt20（4）求改進(jìn)了的基本可行解求改進(jìn)了的基本可行解 對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量x x3 3所對(duì)應(yīng)的所對(duì)應(yīng)的系數(shù)列向量系數(shù)列向量 變換成換出變量變換成換出變量x x4 4所對(duì)應(yīng)的單位向量所對(duì)應(yīng)的單位向量 , , 注意保持基

23、變量注意保持基變量x x5 5的系數(shù)列向量的系數(shù)列向量 為單位向量不變。為單位向量不變。32P =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 第一行除以第一行除以第二行減去第一行第二行減去第一行編輯ppt21可得改進(jìn)的基本可行解。可得改進(jìn)的基本可行解。 ，基變量，基變量，非基變量。非基變量?；究尚薪饣究尚薪饽繕?biāo)函數(shù)值目標(biāo)函數(shù)值易見(jiàn)目標(biāo)函數(shù)值比原來(lái)的易見(jiàn)目標(biāo)函數(shù)值比原來(lái)的Z=

24、-1Z=-1增加了，增加了， 再轉(zhuǎn)向步驟再轉(zhuǎn)向步驟(2)(2)3510B=(P P )=0113BBN25N411x1xC =(3,1)10422X =,X = x,B=,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編輯ppt22（2）檢驗(yàn)檢驗(yàn) 是否最優(yōu)。是否最優(yōu)。檢驗(yàn)向量檢驗(yàn)向量因?yàn)椋驗(yàn)?，所以仍不是最?yōu)解。所以仍

25、不是最優(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)T13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 110 編輯ppt23（3）基本可行解的改進(jìn)基本可行解的改進(jìn) 選取換入變量選取換入變量因?yàn)椋閾Q入變量。因?yàn)?，取為換入變量。 選取換出變量選取換出變量且且 ，選取為換出變量選取為換出變量. .433min,1/2 5/25/2X = (0

26、,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=B b-B P x =-xx35/2 編輯ppt24（4）求改進(jìn)了的基本可行解求改進(jìn)了的基本可行解 對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量所對(duì)應(yīng)對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量所對(duì)應(yīng)的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量 , , 112P =5250P1 X1x5x11111104110

27、4 2222665-12-11030135555223172-101 5555 66-12105555 13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 第二行乘以第二行乘以/第一行減以第二行的第一行減以第二行的/倍倍編輯ppt25可得改進(jìn)的基本可行解。可得改進(jìn)的基本可行解。 ，基變量，基變量，非基變量非基變量基本可行解基本可行解目標(biāo)函數(shù)值目標(biāo)函數(shù)值 比比Z=15Z=15增加了，再轉(zhuǎn)向步增加了，再轉(zhuǎn)向步驟驟(2)(2)3110B=(P P )=012B3BN4N1523-117xC =(3,5)x105555

28、X =,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-12301310225555編輯ppt26（2）檢驗(yàn)檢驗(yàn) 是否最優(yōu)。是否最優(yōu)。檢驗(yàn)向量檢驗(yàn)向量因?yàn)樗袡z驗(yàn)數(shù)均小于零，因?yàn)樗袡z驗(yàn)數(shù)均小于零，所以是最優(yōu)解，所以是最優(yōu)解，-1NNB24523-1555=C-CBN =(2,-1,1)-(3,5)6-

29、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-126x5555編輯ppt27p表格單純形法表格單純形法通過(guò)例我們發(fā)現(xiàn)，在單純形法的求解過(guò)程中，有下列重要指標(biāo)：通過(guò)例我們發(fā)現(xiàn)，在單純形法的求解過(guò)程中，有下列重要指標(biāo)：l 每一個(gè)基本可行解的檢驗(yàn)向量每一個(gè)基本可行解的檢驗(yàn)向量根據(jù)檢驗(yàn)向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不根據(jù)檢驗(yàn)向量可以確

30、定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過(guò)檢驗(yàn)向量確定合適的換入變量。是最優(yōu)又可以通過(guò)檢驗(yàn)向量確定合適的換入變量。l 每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值通過(guò)目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值通過(guò)目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加，直至求得最優(yōu)目標(biāo)函數(shù)為止。有效地增加，直至求得最優(yōu)目標(biāo)函數(shù)為止。 在單純形法求解過(guò)程中，每一個(gè)基本可行解都以在單純形法求解過(guò)程中，每一個(gè)基本可行解都以某個(gè)經(jīng)過(guò)初等行某個(gè)經(jīng)過(guò)初等行變換的變換的約束方程組中的單位矩陣約束方程組中的單位矩陣為可行基。為可行基。當(dāng)當(dāng)= =時(shí)，時(shí)，

31、-1-1= =，易知：，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b編輯ppt28 可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡(jiǎn)單的表格，可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡(jiǎn)單的表格，即單純形表來(lái)完成：即單純形表來(lái)完成：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 編輯ppt29例例2 2、試?yán)脝渭冃伪砬罄⒃嚴(yán)脝渭冃伪砬罄? 1中的最優(yōu)解解：中的最優(yōu)解解：得初始的單純形表：得初始的單純形表：C = (5 ,2 ,3 ,1,1)12210

32、8(Ab)=341017123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x0NNB=C-C NBZ=C b初始基本可行解，初始基本可行解，Z= -1Z= -1，X =(0,0,0,8, 7)T122108x4-130400-1Z341017x51x1x2x3x4x5bXBCB523-11C編輯ppt30換入變量，換出變量，為主元進(jìn)行旋轉(zhuǎn)變換換入變量，換出變量，為主元進(jìn)行旋轉(zhuǎn)變換3x4x基本可行解，基本可行解，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2111/204x331-40-2015Z5/230-1/

33、213x51x1x2x3x4x5bXBCB523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCB523-11C8/27/1編輯ppt31最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值 617X,0,0,055T換入變量，換出變量，換入變量，換出變量，/ /為主元進(jìn)行旋轉(zhuǎn)變換為主元進(jì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/5x

34、15x1x2x3x4x5bXBCB523-11C編輯ppt32例例3 3、用單純形方法求解線性規(guī)劃問(wèn)題、用單純形方法求解線性規(guī)劃問(wèn)題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令可以令則則這兩個(gè)線性規(guī)劃問(wèn)題具有相同的可行域和最優(yōu)解，這兩個(gè)線性規(guī)劃問(wèn)題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。 121324125jminZ=-x -2xxx4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ編輯ppt33010103x220012-12x3

35、0-010103x224/1101004x303/1010103x40_101004x300000-18Z100-212x11100-206Z2/1100-212x50120000Z8/2120018x50 x1x2x3x4x5bXBCB12000C最優(yōu)解最優(yōu)值最優(yōu)解最優(yōu)值X2,3,2,0,0TmaxZ =8 or minZ=-82/23/1-編輯ppt34 因?yàn)榉腔兞恳驗(yàn)榉腔兞縳 x4 4的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)4 4=0=0，由無(wú)窮多最優(yōu)解判別定理，本例，由無(wú)窮多最優(yōu)解判別定理，本例的線性規(guī)劃問(wèn)題存在無(wú)窮多最優(yōu)解。事實(shí)上若以的線性規(guī)劃問(wèn)題存在無(wú)窮多最優(yōu)解。事實(shí)上若以x x4 4為換入變量，以為

36、換入變量，以x x3 3為為換出變量，再進(jìn)行一次迭代，可得一下單純形表：換出變量，再進(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,0,0)(1) 4,2,0,1,0,01.TTC12000CBXBbx1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z80000-1編輯ppt35對(duì)于極小化的線性規(guī)劃問(wèn)題的處理：對(duì)于極小化的線性規(guī)劃問(wèn)題的處理：l先化為標(biāo)準(zhǔn)型，即將極小化問(wèn)題變換為極大化問(wèn)題，然后利用單先化為標(biāo)準(zhǔn)型，即將極小化問(wèn)題變換為極

37、大化問(wèn)題，然后利用單純形方法求解純形方法求解l直接利用單純形方法求解，但是檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同，直接利用單純形方法求解，但是檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同，即：即： 若某個(gè)基本可行解的所有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)若某個(gè)基本可行解的所有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) （而不是（而不是），），則基本可行解為最優(yōu)解則基本可行解為最優(yōu)解否則采用最大減少原則（而非最大增加原則）來(lái)確定換入變量，否則采用最大減少原則（而非最大增加原則）來(lái)確定換入變量，即：即： 若若則選取對(duì)應(yīng)的非基變量則選取對(duì)應(yīng)的非基變量x xm+km+k為換入變量為換入變量 確定了換入變量以后，換出變量仍采用最小比值原則來(lái)確定。確定了換入變量以后，換

38、出變量仍采用最小比值原則來(lái)確定。 NNB= C-CN0jjm+kmin / 0因因但但所以原問(wèn)題所以原問(wèn)題無(wú)最優(yōu)解無(wú)最優(yōu)解1-1P=01-2編輯ppt53n 退化解 當(dāng)線性規(guī)劃問(wèn)題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí)，當(dāng)線性規(guī)劃問(wèn)題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí)，稱(chēng)此基本可行解為退化解。稱(chēng)此基本可行解為退化解。 產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí)，產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí)，有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值，那么在下次迭代中就會(huì)，那么在下次迭代中就會(huì)出現(xiàn)一個(gè)甚至多個(gè)基變量等于零。出現(xiàn)一個(gè)甚

39、至多個(gè)基變量等于零。遇到的問(wèn)題：當(dāng)某個(gè)基變量為零，且下次迭代以該基變量作為換出遇到的問(wèn)題：當(dāng)某個(gè)基變量為零，且下次迭代以該基變量作為換出變量時(shí)，目標(biāo)函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可知，變量時(shí)，目標(biāo)函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可知，任何一個(gè)換入變量只能仍取零值，其它基變量的取值保持不變）。任何一個(gè)換入變量只能仍取零值，其它基變量的取值保持不變）。通過(guò)基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同。通過(guò)基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同。從幾何角度來(lái)解釋?zhuān)@兩個(gè)退化的基本可行解對(duì)應(yīng)線性規(guī)劃可行域從幾何角度來(lái)解釋?zhuān)@兩個(gè)退化的基本可行解對(duì)應(yīng)線性規(guī)

40、劃可行域的同一個(gè)頂點(diǎn)，的同一個(gè)頂點(diǎn)，解決的辦法：最小比值原則計(jì)算時(shí)存在兩個(gè)及其以上相同的最小比解決的辦法：最小比值原則計(jì)算時(shí)存在兩個(gè)及其以上相同的最小比值時(shí)，選取下標(biāo)最大的基變量為換出變量，按此方法進(jìn)行迭代一定值時(shí)，選取下標(biāo)最大的基變量為換出變量，按此方法進(jìn)行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動(dòng)法原理）。能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動(dòng)法原理）。編輯ppt54例例8 8、求解下述線性規(guī)劃問(wèn)題：、求解下述線性規(guī)劃問(wèn)題：解：解：引入松弛變量引入松弛變量化標(biāo)準(zhǔn)型化標(biāo)準(zhǔn)型123412341234 3jmaxZ=3x -80 x +2x -24xx -32x -4x36x 0 x -24x - x 6x 0 x

41、 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編輯ppt55000-242-8030Z-5-60-420-805Z10001001x3212060-2411x13321300-803x500-30-425-800Z11001001x700106-1-2410 x130-1130-3-800 x50-11001001x7000106-1-2410 x60000136-4-3210 x50 x7x6x

42、5x4x3x2x1bXBCB000-242-803C第一次迭代第一次迭代中使用了攝動(dòng)中使用了攝動(dòng)法原理，選擇法原理，選擇下標(biāo)為下標(biāo)為6的基的基變量變量x6離基。離基?？傻米顑?yōu)解可得最優(yōu)解，目標(biāo)函數(shù)值，目標(biāo)函數(shù)值maxZ=，X1,0,1,0,3T編輯ppt56n 無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解 無(wú)窮多最優(yōu)解判別原理：無(wú)窮多最優(yōu)解判別原理：若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。例：最優(yōu)表：例：最優(yōu)

43、表：非基變量檢驗(yàn)非基變量檢驗(yàn)數(shù)，數(shù)，所以有無(wú)窮多所以有無(wú)窮多最優(yōu)解。最優(yōu)解。最優(yōu)解集為可行域兩個(gè)頂點(diǎn)的凸組合：最優(yōu)解集為可行域兩個(gè)頂點(diǎn)的凸組合：C12000CBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z80000-14= 0X(2,3,2,0,0)(1) 4,2,0,1,0,01.TT編輯ppt57n改進(jìn)單純形法的特點(diǎn)改進(jìn)單純形法的特點(diǎn) 利用單純形表求解線性規(guī)劃時(shí)，每一次迭代都把整個(gè)單純形表計(jì)利用單純形表求解線性規(guī)劃時(shí)，每一次迭代都把整個(gè)單純形表計(jì)算一遍，事實(shí)上我們關(guān)心的只是以下一些數(shù)據(jù)：算一遍，事實(shí)上我們關(guān)心的只是以下一些數(shù)據(jù)：l基本

44、可行解基本可行解 ，其相應(yīng)的目標(biāo)函數(shù)值，其相應(yīng)的目標(biāo)函數(shù)值 ，l非基變量檢驗(yàn)數(shù)非基變量檢驗(yàn)數(shù) ，及其換入變量，及其換入變量 ， 設(shè)設(shè)主元列元素主元列元素 ，及其換出變量，及其換出變量 ，設(shè)設(shè) 利用它們可得到一組新的基變量以及新的可行基利用它們可得到一組新的基變量以及新的可行基1 1。1-1-1iki-11kik(B b)(B b)min/(B P ) 0, i (B P )(B P )llp改進(jìn)單純形法改進(jìn)單純形法-1BX =B b-1BZ=C B b-1NNB=C -C B Nkxxl-1kB P為基變量下標(biāo)為基變量下標(biāo)jjkmax / 0, j =為非基變量下標(biāo)為非基變量下標(biāo)編輯ppt58

45、對(duì)對(duì)任一基本可行解，任一基本可行解，只要知道，上述關(guān)鍵數(shù)據(jù)都可以從只要知道，上述關(guān)鍵數(shù)據(jù)都可以從線性規(guī)劃問(wèn)題的初始數(shù)據(jù)直接計(jì)算出來(lái)。因此如何計(jì)算基本可行解線性規(guī)劃問(wèn)題的初始數(shù)據(jù)直接計(jì)算出來(lái)。因此如何計(jì)算基本可行解對(duì)應(yīng)的可行基的逆陣成為改進(jìn)單純形法的關(guān)鍵對(duì)應(yīng)的可行基的逆陣成為改進(jìn)單純形法的關(guān)鍵改進(jìn)單純形法推導(dǎo)出從可行基變換到改進(jìn)單純形法推導(dǎo)出從可行基變換到1 1時(shí)，到時(shí)，到的變換公式。當(dāng)初始可行基為單位矩陣的變換公式。當(dāng)初始可行基為單位矩陣時(shí)，變換公式將更具有優(yōu)時(shí)，變換公式將更具有優(yōu)越性，因?yàn)檫@樣可以避免矩陣求逆的麻煩越性，因?yàn)檫@樣可以避免矩陣求逆的麻煩以下推導(dǎo)從到的變換公式：以下推導(dǎo)從到的變換

46、公式：-1B-1B-1B-11B-1B-11B-1BX =B b-1BZ=C B b-1NNB=C -C B N-1kB P編輯ppt59-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 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è)

47、基相比僅相差一列，且前后二個(gè)基相比僅相差一列，且比較以上二式，可得比較以上二式，可得 xl1121k1mB(P,P ,P ,P ,P ,P )llkx其中表示第個(gè)元素為其中表示第個(gè)元素為1 1，其它元素均為零的單位列向量，其它元素均為零的單位列向量，為主元列元素。為主元列元素。 iei-1kB P編輯ppt60假設(shè)假設(shè) ，則則1k2k-1KkmkaaB P =aal1klk2klkkm klka1-0aa-a111k1aa0-1a-E(BB )ll-1-111211mB B(, , , ,B P , , )lkleeeee第列第列（換出變量對(duì)應(yīng)列（換出變量對(duì)應(yīng)列 ）第行第行l(wèi)l所以由所以由-1

48、-1-1-1-1k111kE(B B )BB BE Bllxl主元素主元素編輯ppt61n改進(jìn)單純形法的步驟改進(jìn)單純形法的步驟（1 1）根據(jù)給出的線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型，確定初始基變量和初始）根據(jù)給出的線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型，確定初始基變量和初始可行基。求初始可行基可行基。求初始可行基B B的逆陣的逆陣-1-1，得初始基本可行解，得初始基本可行解。 （2 2）計(jì)算單純形乘子）計(jì)算單純形乘子 ，得目標(biāo)函數(shù)當(dāng)前值，得目標(biāo)函數(shù)當(dāng)前值（3 3）計(jì)算非基變量檢驗(yàn)數(shù)，計(jì)算非基變量檢驗(yàn)數(shù)，若若N N00，則當(dāng)前解已是最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)下一步。，則當(dāng)前解已是最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)下一步。（4 4）根據(jù)，確

49、定非基變量為換入變量，根據(jù)，確定非基變量為換入變量，計(jì)算計(jì)算, ,若若00，則問(wèn)題沒(méi)有有限最優(yōu)解，停止計(jì)算，則問(wèn)題沒(méi)有有限最優(yōu)解，停止計(jì)算，否則轉(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編輯ppt62（5 5） 根據(jù)根據(jù) ，確定基變量，確定基變量 為換出變量。為換出變量。 （6 6） 用替代用替代 得新基得新基1 1，由變換公式，由變換公式計(jì)算新基的逆陣計(jì)算新基的逆陣1 1-1-1，求出新的基本可行解，求出新的基本可行解 其中為變換矩陣，構(gòu)造方法是：其中為變

50、換矩陣，構(gòu)造方法是： 從一個(gè)單位矩陣出發(fā)，把換出變量從一個(gè)單位矩陣出發(fā)，把換出變量 在基在基B B中的對(duì)應(yīng)列的單位中的對(duì)應(yīng)列的單位 向量，替換成換入變量向量，替換成換入變量 對(duì)應(yīng)的系數(shù)列向量對(duì)應(yīng)的系數(shù)列向量 ，并做如下變形，并做如下變形， 主元素主元素 （應(yīng)在主對(duì)角線上）取倒數(shù)，其它元素除以主元素（應(yīng)在主對(duì)角線上）取倒數(shù)，其它元素除以主元素 并取相反數(shù)。并取相反數(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-1

51、kB Pxlkxkal編輯ppt63 B=I-1BNX =B b,X0-1B=C BZ=bNN=C -Nkx換入換入-1kB P無(wú)界解無(wú)界解換出換出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新基新基編輯ppt64 例例9 9、試用改進(jìn)單純形法求解、試用改進(jìn)單純形法求解解：解：（）觀察法確定（）觀察法確定，為基變量為基變量 為非基變量為非基變量 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編輯ppt65 （