第2章單純形法的幾種特殊情況

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)14幾種特殊情況 . 0,40,30,1501033020max212112121xxxxxxxxxz約束條件目標(biāo)函數(shù)一、無(wú)可行解一、無(wú)可行解 例例1、用單純形表求解下列線性規(guī)劃問題、用單純形表求解下列線性規(guī)劃問題解：在上述問題的約束條件中加入松馳變量、剩余變量、人工變量得到：解：在上述問題的約束條件中加入松馳變量、剩余變量、人工變量得到： 121121121231121231max2030310150,30,40,0.zxxMaxxsxsxxsax x s s s a目標(biāo)函數(shù)約束條件 填入單純形表計(jì)算得：填入單純形表計(jì)算得：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)24幾種特殊

2、情況迭迭代代次次數(shù)數(shù)基變基變量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1zjcj-zj-M -M 0 0 M -M20+M 30+M 0 0 -M 0-40M1x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M 30 3+M/10 0 M -M11+7/10M 0 -3-M/10 0

3、-M 0 450-25M2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304zjcj-zj20 30 3+M/10 11+7M/10 M -M0 0 -3-M/10 -11-7M/10 -M 0780-4M管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)34幾種特殊情況 從第二次迭代的檢驗(yàn)數(shù)都小于零來(lái)看，可知第從第二次迭代的檢驗(yàn)數(shù)都小于零來(lái)看，可知第2次迭代所得的基本可次迭代所得的基本可行解已經(jīng)是最優(yōu)解了，其最大的目標(biāo)函數(shù)值為行解已經(jīng)是最優(yōu)解了，其最大的目標(biāo)函數(shù)值為780-4M。我們把最優(yōu)解。我們把最優(yōu)解x1=30,x2=6,s1=

4、0,s2=0,s3=0,a1=4,代入第三個(gè)約束方程得代入第三個(gè)約束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640. 并不滿足原來(lái)的約束條件并不滿足原來(lái)的約束條件3，可知原線性規(guī)劃問題無(wú)可行解，或者說(shuō)，可知原線性規(guī)劃問題無(wú)可行解，或者說(shuō)其可行解域?yàn)榭占?，?dāng)然更不可能有最優(yōu)解了。其可行解域?yàn)榭占?dāng)然更不可能有最優(yōu)解了。 像這樣只要求線性規(guī)劃的像這樣只要求線性規(guī)劃的最優(yōu)解里有人工變量大于零最優(yōu)解里有人工變量大于零，則此線性規(guī)劃，則此線性規(guī)劃無(wú)可行解無(wú)可行解。二、無(wú)界解二、無(wú)界解 在求目標(biāo)函數(shù)最大值的問題中，所謂無(wú)在求目標(biāo)函數(shù)最大值的問題中，所謂無(wú)界解是指在約束條件下目標(biāo)函數(shù)值可

5、以取界解是指在約束條件下目標(biāo)函數(shù)值可以取任意的大。下面我們用單純形表來(lái)求第二任意的大。下面我們用單純形表來(lái)求第二章中的例子。章中的例子。例例2 2、用單純形表求解下面線性、用單純形表求解下面線性規(guī)劃問題。規(guī)劃問題。 12121212max1,326,0.zxxxxxxx x目標(biāo)函數(shù)約束條件管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)44幾種特殊情況 迭迭代代次次數(shù)數(shù)基基變變量量CBx1 x2 s1 s2b比比值值1 1 0 00s1s2001 -1 1 0-3 2 0 1161zjcj-zj0 0 0 0 1 1 0 001x1s2101 -1 1 0 0 -1 3 119zjcj-zj1 -1 1 00 2

6、 -1 01填入單純形表計(jì)算得：填入單純形表計(jì)算得：解：在上述問題的約束條件中加入松馳變量，得標(biāo)準(zhǔn)型如下：解：在上述問題的約束條件中加入松馳變量，得標(biāo)準(zhǔn)型如下：121211221212max1,326,0.zxxxxsxxsx x s s目標(biāo)函數(shù)約束條件管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)54幾種特殊情況 12a 從單純形表中，從第一次迭代從單純形表中，從第一次迭代x2的檢驗(yàn)數(shù)等于的檢驗(yàn)數(shù)等于2，可知所得的基本可行，可知所得的基本可行解解x1=1,x2=0,s1=0,s2=9不是最優(yōu)解。同時(shí)我們也知道如果進(jìn)行第不是最優(yōu)解。同時(shí)我們也知道如果進(jìn)行第2次迭代，那次迭代，那么就選么就選x2為入基變量，但是在

7、選擇出基變量時(shí)遇到了問題：為入基變量，但是在選擇出基變量時(shí)遇到了問題： =-1, =-1,找找不到大于零的比值來(lái)確定出基變量不到大于零的比值來(lái)確定出基變量。事實(shí)上如果我們碰到這種情況就可以。事實(shí)上如果我們碰到這種情況就可以斷定斷定這個(gè)線性規(guī)劃問題是無(wú)界這個(gè)線性規(guī)劃問題是無(wú)界的，也就是說(shuō)在此線性規(guī)劃的約束條件下，的，也就是說(shuō)在此線性規(guī)劃的約束條件下，此目標(biāo)函數(shù)值可以取得無(wú)限大。從此目標(biāo)函數(shù)值可以取得無(wú)限大。從1次迭代的單純形表中，得到約束方程：次迭代的單純形表中，得到約束方程：22a 移項(xiàng)可得：移項(xiàng)可得：1212121,39.xxsxss121221211212121,39.,0,1,0,9.1

8、21.xxssxsxM sxMxMssMzxxMMM 不妨設(shè)可得一組解：顯然這是線性規(guī)劃的可行解，此時(shí)目標(biāo)函數(shù)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)64幾種特殊情況 ij 由于由于M可以是任意大的正數(shù)，可知此目標(biāo)函數(shù)值無(wú)界?？梢允侨我獯蟮恼龜?shù)，可知此目標(biāo)函數(shù)值無(wú)界。 上述的例子告訴了我們?cè)趩渭冃伪碇凶R(shí)別線性規(guī)劃問題是無(wú)界的方法：上述的例子告訴了我們?cè)趩渭冃伪碇凶R(shí)別線性規(guī)劃問題是無(wú)界的方法：在某次迭代的單純形表中，如果在某次迭代的單純形表中，如果存在著一個(gè)大于零的檢驗(yàn)數(shù)存在著一個(gè)大于零的檢驗(yàn)數(shù) ，并且，并且該列該列的系數(shù)向量的每個(gè)元素的系數(shù)向量的每個(gè)元素aij(i=1,2,m)都小于或等于零都小于或等于零

9、，則此線性規(guī)劃問題，則此線性規(guī)劃問題是無(wú)界是無(wú)界的，一般地說(shuō)此類問題的出現(xiàn)是由于建模的錯(cuò)誤所引起的。的，一般地說(shuō)此類問題的出現(xiàn)是由于建模的錯(cuò)誤所引起的。三、無(wú)窮多最優(yōu)解三、無(wú)窮多最優(yōu)解例例3、用單純形法表求解下面的線性規(guī)劃問題。、用單純形法表求解下面的線性規(guī)劃問題。121212212max5050300,2400,250,0.zxxxxxxxx x目標(biāo)函數(shù)約束條件管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)74幾種特殊情況 解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來(lái)求解。解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來(lái)求解。123121211222312123,max5050300,2400,250,0.s

10、 sszxxxxsxxsxsx xs ss加入松弛變量，我們得到標(biāo)準(zhǔn)形：目標(biāo)函數(shù)約束條件填入單純形表計(jì)算得：填入單純形表計(jì)算得：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)84幾種特殊情況迭迭代代次次數(shù)數(shù)基變基變量量CBx1 x2 s1 s2 s3b比值比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zjcj-zj0 0 0 0 050 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 01150/2zjcj-zj0 50 0 0 5050 0

11、 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1zjcj-zj50 50 50 0 00 0 -50 0 015000管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)94幾種特殊情況 124, 這樣我們求得了最優(yōu)解為這樣我們求得了最優(yōu)解為x1=50,x2=250,s1=0,s2=50,s3=0,此線性規(guī)劃的此線性規(guī)劃的最優(yōu)值為最優(yōu)值為15000。這個(gè)最優(yōu)解是否是惟一的呢？由于在第。這個(gè)最優(yōu)解是否是惟一的呢？由于在第2次迭代的檢驗(yàn)數(shù)次迭代的檢驗(yàn)數(shù)中除了基變量的檢驗(yàn)數(shù)中除了基變量的檢驗(yàn)數(shù) 等于零外，等于零外，非基變量非基變量s3的

12、檢驗(yàn)數(shù)也等的檢驗(yàn)數(shù)也等于零于零，這樣我們可以斷定此線性規(guī)劃問題有無(wú)窮多最優(yōu)解。不妨我們把檢，這樣我們可以斷定此線性規(guī)劃問題有無(wú)窮多最優(yōu)解。不妨我們把檢驗(yàn)數(shù)也為零的非基變量選為入基變量進(jìn)行第驗(yàn)數(shù)也為零的非基變量選為入基變量進(jìn)行第3次迭代。可求得另一個(gè)基本次迭代?？汕蟮昧硪粋€(gè)基本可行解，如下表所示：可行解，如下表所示：迭代迭代次數(shù)次數(shù)基基變變量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50 50 50 0 00 0 -50 0 015000 從檢驗(yàn)數(shù)可知此基本可行解從檢

13、驗(yàn)數(shù)可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最優(yōu)解也是最優(yōu)解管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)104幾種特殊情況 四、退化問題四、退化問題 在單純形法計(jì)算過程中，確定出基變量時(shí)有時(shí)存在兩個(gè)以上的相同的在單純形法計(jì)算過程中，確定出基變量時(shí)有時(shí)存在兩個(gè)以上的相同的最小比值，這樣在下一次迭代中就有了一個(gè)或幾個(gè)基變量等于零，這稱之最小比值，這樣在下一次迭代中就有了一個(gè)或幾個(gè)基變量等于零，這稱之為退化。為退化。例例4.用單純形表，求解下列線性規(guī)劃問題。用單純形表，求解下列線性規(guī)劃問題。解：加上松馳變量解：加上松馳變量s1,s2,s3化為標(biāo)準(zhǔn)形式后，化為標(biāo)準(zhǔn)形式后，填入單

14、純形表計(jì)算得：填入單純形表計(jì)算得：1312131231233max222,24,3,0.zxxxxxxxxxx x x目標(biāo)函數(shù)約束條件管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)114幾種特殊情況迭迭代代次次數(shù)數(shù)基基變變量量CBx1 x2 x3 s1 s2 s3b比值比值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1zjcj-zj0 0 0 0 0 02 0 3/2 0 0 001x1s2s32001 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 12010/21/2zjcj-zj2 -2 0 0

15、 0 00 2 3/2 -2 0 042x1x2s32001 0 1/2 0 1/2 00 1 1/2 - 1 1/2 00 0 0 1 -1 1 2012/(1/2)0/(1/2)zjcj-zj2 0 1 0 1 00 0 1/2 0 -1 04管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)124幾種特殊情況 在以上的計(jì)算中可以看出在在以上的計(jì)算中可以看出在0次迭代中，由于比次迭代中，由于比值值b1/a11=b2/a21=2為最小比值，導(dǎo)致在第為最小比值，導(dǎo)致在第1次迭代中出次迭代中出現(xiàn)了退化，基變量現(xiàn)了退化，基變量s2=0。又由于在第。又由于在第1次迭代出現(xiàn)了次迭代出現(xiàn)了退化，基變量退化，基變量s2=0，又

16、導(dǎo)致第，又導(dǎo)致第2次迭代所取得的目標(biāo)次迭代所取得的目標(biāo)函數(shù)值并沒有得到改善，仍然與第函數(shù)值并沒有得到改善，仍然與第1次迭代的一樣都次迭代的一樣都等于等于4。像這樣繼續(xù)迭代而得不到目標(biāo)函數(shù)的改善，。像這樣繼續(xù)迭代而得不到目標(biāo)函數(shù)的改善，當(dāng)然減低了單純形算法的效率，但一般來(lái)說(shuō)還是可當(dāng)然減低了單純形算法的效率，但一般來(lái)說(shuō)還是可以得到最優(yōu)解的。像本題繼續(xù)計(jì)算如下：以得到最優(yōu)解的。像本題繼續(xù)計(jì)算如下：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)134幾種特殊情況迭迭代代次次數(shù)數(shù)基基變變量量CBx1 x2 x3 s1 s2 s3b比值比值2 0 3/2 0 0 03x1x3s323/201 -1 0 1 0 00 2 1

17、 - 2 1 00 0 0 1 -1 1 2012/11/1zjcj-zj2 1 3/2 -1 3/2 00 -1 0 1 -3/2 044x1x3s123/201 -1 0 0 1 -10 2 1 0 -1 20 0 0 1 -1 1 221zjcj-zj2 1 3/2 0 1/2 10 -1 0 0 -1/2 -15管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)144幾種特殊情況 得到了最優(yōu)解得到了最優(yōu)解x x1 1=1=1，x x2 2=0=0，x x3 3=2=2，s s1 1=1=1，s s2 2=0=0，s s3 3=0=0，其最優(yōu)值為，其最優(yōu)值為5 5。 但有時(shí)候當(dāng)出現(xiàn)退化時(shí)，即使存在最優(yōu)解，而迭

18、代過程總是重復(fù)解的但有時(shí)候當(dāng)出現(xiàn)退化時(shí)，即使存在最優(yōu)解，而迭代過程總是重復(fù)解的某一部分迭代過程，出現(xiàn)了計(jì)算過程的循環(huán)，目標(biāo)函數(shù)值總是不變，永遠(yuǎn)某一部分迭代過程，出現(xiàn)了計(jì)算過程的循環(huán)，目標(biāo)函數(shù)值總是不變，永遠(yuǎn)達(dá)不到最優(yōu)解。達(dá)不到最優(yōu)解。 下面一個(gè)是由下面一個(gè)是由E.Beale給出的循環(huán)的例子。給出的循環(huán)的例子。例例5 5 目標(biāo)函數(shù)目標(biāo)函數(shù) ：min f =min f =（3/43/4）x x4 4+20 x+20 x5 5（1 12 2）x x6 6+6x+6x7 7. . 約束條件：約束條件：x x1 1+ +（1 14 4）x x4 48x8x5 5x x6 6+9x+9x7 7=0=0， x x2 2+ +（1 12 2）x x4 412x12x5 5（1 12 2）x x6 6+3x+3x7 7=0=0， x x3 3+x+x6 6=1=1， x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6，x x7 70.0.管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)154幾種特殊情況 這個(gè)例題的確存在最優(yōu)解，但用一般單純形表法，經(jīng)過這個(gè)例題的確存在最優(yōu)解，但用一般單純形表法，經(jīng)過6 6次迭代后得到的單純形表與第次迭代后得到的單純形表與第0 0次單純形表一樣，而目標(biāo)函數(shù)次單純形表一樣，而目