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

單純形法的幾種特殊情況第二章§4幾種特殊情況迭代次數(shù)基變量CBx1x2s1s2s3a1b比值2030000-M0s1s2a100-M31010001001001100-111503040150/10—40/1zjcj-zj-M-M00M-M20+M30+M00-M0-40M1x2s2a1300-M3/1011/100001001007/100-1/100-1115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M303+M/100M-M11+7/10M0-3-M/100-M0450-25M2x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304zjcj-zj20303+M/1011+7M/10M-M00-3-M/10-11-7M/10-M0780-4M2§4幾種特殊情況

從第二次迭代的檢驗(yàn)數(shù)都小于零來(lái)看，可知第2次迭代所得的基本可行解已經(jīng)是最優(yōu)解了，其最大的目標(biāo)函數(shù)值為780-4M。我們把最優(yōu)解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三個(gè)約束方程得x1+x2-0+4=40,即有：x1+x2=36≤40.并不滿(mǎn)足原來(lái)的約束條件3，可知原線(xiàn)性規(guī)劃問(wèn)題無(wú)可行解，或者說(shuō)其可行解域?yàn)榭占?dāng)然更不可能有最優(yōu)解了。像這樣只要求線(xiàn)性規(guī)劃的最優(yōu)解里有人工變量大于零，則此線(xiàn)性規(guī)劃無(wú)可行解。二、無(wú)界解在求目標(biāo)函數(shù)最大值的問(wèn)題中，所謂無(wú)界解是指在約束條件下目標(biāo)函數(shù)值可以取任意的大。下面我們用單純形表來(lái)求第二章中的例子。例2、用單純形表求解下面線(xiàn)性規(guī)劃問(wèn)題。

3§4幾種特殊情況

迭代次數(shù)基變量CBx1x2s1s2b比值11000s1s2001-110-3201161—zjcj-zj0000110001x1s2101-1100-13119zjcj-zj1-11002-101填入單純形表計(jì)算得：解：在上述問(wèn)題的約束條件中加入松馳變量，得標(biāo)準(zhǔn)型如下：4§4幾種特殊情況

從單純形表中，從第一次迭代x2的檢驗(yàn)數(shù)等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最優(yōu)解。同時(shí)我們也知道如果進(jìn)行第2次迭代，那么就選x2為入基變量，但是在選擇出基變量時(shí)遇到了問(wèn)題：=-1,=-1,找不到大于零的比值來(lái)確定出基變量。事實(shí)上如果我們碰到這種情況就可以斷定這個(gè)線(xiàn)性規(guī)劃問(wèn)題是無(wú)界的，也就是說(shuō)在此線(xiàn)性規(guī)劃的約束條件下，此目標(biāo)函數(shù)值可以取得無(wú)限大。從1次迭代的單純形表中，得到約束方程：移項(xiàng)可得：5§4幾種特殊情況

由于M可以是任意大的正數(shù)，可知此目標(biāo)函數(shù)值無(wú)界。上述的例子告訴了我們?cè)趩渭冃伪碇凶R(shí)別線(xiàn)性規(guī)劃問(wèn)題是無(wú)界的方法：在某次迭代的單純形表中，如果存在著一個(gè)大于零的檢驗(yàn)數(shù)，并且該列的系數(shù)向量的每個(gè)元素aij(i=1,2,…,m)都小于或等于零，則此線(xiàn)性規(guī)劃問(wèn)題是無(wú)界的，一般地說(shuō)此類(lèi)問(wèn)題的出現(xiàn)是由于建模的錯(cuò)誤所引起的。三、無(wú)窮多最優(yōu)解例3、用單純形法表求解下面的線(xiàn)性規(guī)劃問(wèn)題。6§4幾種特殊情況

解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來(lái)求解。填入單純形表計(jì)算得：7§4幾種特殊情況迭代次數(shù)基變量CBx1x2s1s2s3b比值50500000s1s2s3000111002101001001300400250300/1400/1250/1zjcj-zj00000505000001s1s2x200501010-12001-1010015015025050/1150/2—zjcj-zj0500050500000125002x1s2x2500501010-100-211010015050250—50/1250/1zjcj-zj5050500000-5000150008§4幾種特殊情況

這樣我們求得了最優(yōu)解為x1=50,x2=250,s1=0,s2=50,s3=0,此線(xiàn)性規(guī)劃的最優(yōu)值為15000。這個(gè)最優(yōu)解是否是惟一的呢？由于在第2次迭代的檢驗(yàn)數(shù)中除了基變量的檢驗(yàn)數(shù)等于零外，非基變量s3的檢驗(yàn)數(shù)也等于零，這樣我們可以斷定此線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。不妨我們把檢驗(yàn)數(shù)也為零的非基變量選為入基變量進(jìn)行第3次迭代。可求得另一個(gè)基本可行解，如下表所示：迭代次數(shù)基變量CBx1x2s1s2s3b50500003x1s3x25005010-11000-211012-1010050200zjcj-zj5050500000-500015000從檢驗(yàn)數(shù)可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最優(yōu)解9§4幾種特殊情況

四、退化問(wèn)題在單純形法計(jì)算過(guò)程中，確定出基變量時(shí)有時(shí)存在兩個(gè)以上的相同的最小比值，這樣在下一次迭代中就有了一個(gè)或幾個(gè)基變量等于零，這稱(chēng)之為退化。例4.用單純形表，求解下列線(xiàn)性規(guī)劃問(wèn)題。解：加上松馳變量s1,s2,s3化為標(biāo)準(zhǔn)形式后，填入單純形表計(jì)算得：10§4幾種特殊情況迭代次數(shù)基變量CBx1x2x3s1s2s3b比值203/20000s1s2s30001-101002010101110012432/14/23/1zjcj-zj000000203/200001x1s2s32001-10100021-210021-101201—0/21/2zjcj-zj2-20000023/2-20042x1x2s3200101/201/20011/2-11/200001-112012/(1/2)0/(1/2)—zjcj-zj201010001/20-10411§4幾種特殊情況

在以上的計(jì)算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2為最小比值，導(dǎo)致在第1次迭代中出現(xiàn)了退化，基變量s2=0。又由于在第1次迭代出現(xiàn)了退化，基變量s2=0，又導(dǎo)致第2次迭代所取得的目標(biāo)函數(shù)值并沒(méi)有得到改善，仍然與第1次迭代的一樣都等于4。像這樣繼續(xù)迭代而得不到目標(biāo)函數(shù)的改善，當(dāng)然減低了單純形算法的效率，但一般來(lái)說(shuō)還是可以得到最優(yōu)解的。像本題繼續(xù)計(jì)算如下：12§4幾種特殊情況迭代次數(shù)基變量CBx1x2x3s1s2s3b比值203/20003x1x3s323/201-10100021-2100001-112012/1—1/1zjcj-zj213/2-13/200-101-3/2044x1x3s123/201-1001-10210-120001-11221zjcj-zj213/201/210-100-1/2-1513§4幾種特殊情況得到了最優(yōu)解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最優(yōu)值為5。但有時(shí)候當(dāng)出現(xiàn)退化時(shí)，即使存在最優(yōu)解，而迭代過(guò)程總是重復(fù)解的某一部分迭代過(guò)程，出現(xiàn)了計(jì)算過(guò)程的循環(huán)，目標(biāo)函數(shù)值總是不變，永遠(yuǎn)達(dá)不到最優(yōu)解。下面一個(gè)是由E.Beale給出的循環(huán)的例子。例5目標(biāo)函數(shù)：minf=－（3/4）x4+