運(yùn)籌學(xué)-第一章-單純形法進(jìn)一步討論

1、單純形法進(jìn)一步討論,竇志武,云南財(cái)經(jīng)大學(xué) 物流學(xué)院,單純形法的進(jìn)一步討論－人工變量法,人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。,例： min z=2x1+

2、3x2 max z=-2x1-3x2+0x3 s.t x1+x2? 3 標(biāo)準(zhǔn)化 s.t x1+x2 -x3=3 x1+2x2 = 4 ? x1+2x2=4 x1?0, x2?0 xj?0, (j=1,2,3,4),,,m

3、ax z=-2x1-3x2+0x3 -M x4-M x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj?0, (j=1,2,3,4,5),,引進(jìn)人工變量，及M——非常大正系數(shù)，模型轉(zhuǎn)變?yōu)?這種處理方法稱為大M法，以下則

4、可完全按單純形法求解。,1．大M法,單純形法的進(jìn)一步討論－人工變量法,單純形法的進(jìn)一步討論－人工變量法,例1.10 用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。,單純形法的進(jìn)一步討論－人工變量法,故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：,其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型

5、，計(jì)算結(jié)果見下表。,單純形法的進(jìn)一步討論－人工變量法,,,→,→,,→,單純形法的進(jìn)一步討論－人工變量法,例1.11 用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。,單純形法的進(jìn)一步討論－人工變量法,故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：,其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模

6、型，計(jì)算結(jié)果見下表。,單純形法的進(jìn)一步討論－人工變量法,,,→,,→,,單純形法的進(jìn)一步討論－人工變量法,,→,,單純形法的進(jìn)一步討論－兩階段法,用計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替M,可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。,第一階段： 在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：,對(duì)上述模型求解（單純形法），若ω=0,說(shuō)明問題存在基可行解，可以進(jìn)行第二個(gè)階段；否則，原問題無(wú)可行解，停止運(yùn)算。,單純形法的進(jìn)一步討論－兩階段

7、法,第一階段的線性規(guī)劃問題可寫為：,第一階段單純形法迭代的過(guò)程見下表,單純形法的進(jìn)一步討論－兩階段法,,,→,,→,,單純形法的進(jìn)一步討論－兩階段法,第二階段： 在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表（用單純形法計(jì)算）。,例：,單純形法的進(jìn)一步討論－兩階段法,,,→,第二階段：,∴最優(yōu)解為（4 1 9 0 0），目標(biāo)函數(shù) Z = 2,單純形法的進(jìn)一步

8、討論,通過(guò)大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。,無(wú)可行解,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,C,,,,,,,,,,,,,,,,,,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1

9、x2 x3 x4 x5 x6 x7 x8,θ,0-M-M,x4x7x8,643,1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0

10、 0 -1 0 1,6/1-3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0-M-2,x4x7x2,343,1 0 2 1 0 1 0 -11 0 -1 0 -1

11、 0 1 00 1 -1 0 0 -1 0 1,3/14/1-,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3-M-2,x1x7x2,313,1 0 2 1 0 1

12、0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,,,例,單純形法的進(jìn)一步討論,運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。,單純形法的進(jìn)一步

13、討論,無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。 無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問題的可行域?yàn)榭占?無(wú)最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮?。o(wú)最優(yōu)解也稱為有限最優(yōu)解，或無(wú)界解。 判別方法：無(wú)最優(yōu)解判別定理　　在求解極大化的線性規(guī)劃問題過(guò)程中，若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所

14、對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題 無(wú)最優(yōu)解,無(wú)最優(yōu)解,因 但 所以原問題無(wú)最優(yōu)解,單純形法的進(jìn)一步討論,退化,即計(jì)算出的 θ（用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是退化（會(huì)產(chǎn)生退化解）。 為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個(gè)簡(jiǎn)便有效的規(guī)則（攝動(dòng)法原理

15、）： ⑴ 當(dāng)存在多個(gè) 時(shí)，選下標(biāo)最小的非基變量為換入變量；(2) 當(dāng)θ值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換出變量。,單純形法的進(jìn)一步討論,無(wú)窮多最優(yōu)解,若線性規(guī)劃問題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問題有無(wú)窮多最優(yōu)解。例３：最優(yōu)表：非基變量檢驗(yàn)數(shù)　　　，所以有無(wú)窮多最優(yōu)解。,單純形法的進(jìn)一步討論,單純形法的進(jìn)一

16、步討論,解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。3）無(wú)界解判別：某個(gè) k>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無(wú)界解。4）無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí)，則表明原線性規(guī)劃無(wú)可行解。5）退化解的判別：存在某個(gè)基變量為零的