運籌學-第一章-單純形法進一步討論

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

2、3x2 max z=-2x1-3x2+0x3 s.t x1+x2? 3 標準化 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),,引進人工變量，及M——非常大正系數(shù)，模型轉變?yōu)?這種處理方法稱為大M法，以下則

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

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

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

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

8、討論,通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。,無可行解,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,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,,,例,單純形法的進一步討論,運算到檢驗數(shù)全負為止，仍含有人工變量，無可行解。,單純形法的進一步

13、討論,無最優(yōu)解與無可行解時兩個不同的概念。 無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問題的可行域為空集； 無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目 標函數(shù)達不到最優(yōu)值，即目標函數(shù)在可行域內可以趨于無窮大（或者無窮小）。無最優(yōu)解也稱為有限最優(yōu)解，或無界解。 判別方法：無最優(yōu)解判別定理　　在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗 行存在某個大于零的檢驗數(shù)，但是該檢驗數(shù)所

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

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

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