1、單純形法的循環(huán)問題和解決方法摘要：單純形法是解決線性規(guī)劃的最普遍的方法，但是在出現(xiàn)退化問題的時(shí)候很容易出現(xiàn)循環(huán)現(xiàn)象。本文對(duì)循環(huán)問題進(jìn)行了分析，并給出了解決循環(huán)問題的幾種方法。關(guān)鍵字：單純形法 循環(huán)問題單純形法的循環(huán)問題在單純形法計(jì)算過程中，基變量有時(shí)存在兩個(gè)以上相同的最小比值，在下一 次的迭代中就有一個(gè)或幾個(gè)基變量等于零，這稱之為退化。單純形法迭代過程中選取出基變量，若多于一個(gè)可選者就會(huì)出現(xiàn)退化，當(dāng)出 現(xiàn)這樣情況，選擇出基變量不當(dāng)?shù)脑?，就可能?dǎo)致迭代過程中基的反復(fù)，即迭代 過程的循環(huán)，這樣目標(biāo)函數(shù)值永遠(yuǎn)達(dá)不到最優(yōu)解。這種問題就是單純形法的循環(huán) 問題。出現(xiàn)循環(huán)問題的原因退化是循環(huán)的必要條件，當(dāng)線

2、形規(guī)劃中出現(xiàn)退化的基本可行解時(shí)，如果進(jìn)基， 出基變量選取準(zhǔn)則不合理就有可能出現(xiàn)循環(huán)現(xiàn)象。例子: TOC o 1-5 h z 1.min f (x) = 一一x + 20 x 一一x + 4x122 34x -15 x - x + 6 x + x = 02 12345x 一 10 x - x + 2 x + x = 02 122 346x Z 0仃 T2.7)迭 代 次 數(shù)基變量CBX1x2x3x4x5x6x7b比 值3/4-201/2-4000X501/2-15-16100000X601/2-10-1/2201000X7000100011Zj0000000Cj-zj3/4 -201/2-400

3、0迭X1 x2 x3 x4 x5 x6 x7代基變b比次量CB3/4-201/2-4000值數(shù)X13/41-30-212200001X60051/2-4-11000X70001000111Zj3/4 -45/2 -3/293/200Cj-zj05/22-13-3/200迭X1 x2 x3 x4 x5 x6 x7代基變b比次量CB3/4-201/2-4000值數(shù)X13/4101-12-460002X2-2001 1/10 -4/5-1/51/5000X70001000111Zj3/4 -20 -5/4711/20Cj-zj007/4-11-1-1/20迭X1 x2 x3 x4 x5 x6 x7代

4、基變b比次量CB3/4-201/2-4000值數(shù)X31/2101-12-460003X2-20-1/10 102/51/5-2/5 000X70-1001246111/12Zj5/2 -201/2-14-6110Cj-zj-7/400106-110迭X1 x2 x3 x4 x5 x6 x7代次數(shù)基變量CB3/4-201/2-4000b比 值X31/2-230102-60004X4-4-1/45/2011/2-1000X702-3000-2611Zj Cj-zj03/45 -251/20-40-111-100迭 代基變X1x2x3x4x5x6x7b比次數(shù)量CB3/4-201/2-4000值X50

5、-1151/201-3005X4-41/4-5-1/4101/2000X7000100011Zj Cj-zj-17/420-401-1/2-4000-2200迭 代 次 數(shù)基變量CBX1x2x3x4x5x6x7b比 值3/4-201/2-4000X501/2-15-16100006X601/2-10-1/2201000X7000100011Zj0000000Cj-zj3/4-201/2-4000在上面的例子中，每次迭代出現(xiàn)多個(gè)候選的出基變量時(shí)，我們都是選取最上 面行的基變量作為出基變量，最后還是出現(xiàn)了循環(huán)。有學(xué)者證明：迭代出現(xiàn)循環(huán) 的最小迭代次數(shù)是6次，因此上面的例子已經(jīng)是出現(xiàn)循環(huán)的最簡單的例

6、子。不難 發(fā)現(xiàn)在出現(xiàn)循環(huán)現(xiàn)象時(shí)，每次迭代至少有兩個(gè)基變量取零值，且其中至少有一個(gè) 變量是候選的出基變量。解決循環(huán)的方法退化是循環(huán)的必要條件，要避免循環(huán)要么是考慮如何在退化的情況下采取措 施使循環(huán)不會(huì)發(fā)生，要么是從根本上消除退化現(xiàn)象。1、攝動(dòng)法就是從根本上消除退化現(xiàn)象，將原規(guī)劃進(jìn)行攝動(dòng)處理，使之成為 一個(gè)非退化的規(guī)劃問題。線形規(guī)劃存不存在退化的基本可行解，重要是和右端常 數(shù)b有關(guān)。攝動(dòng)法用向量b（E） = b + 6ja來代替原規(guī)劃P中的b得到一個(gè)新的規(guī)劃P（ ）；j=1其中a,是系數(shù)矩陣的列向量，6是一個(gè)非常小的正數(shù)可以證明：當(dāng)6是個(gè)很小的正數(shù)時(shí)，P（ 6 ）是不會(huì)退化的；當(dāng)6 f0時(shí)，P（

7、6 ） 的最優(yōu)解就是原問題P的最優(yōu)解。實(shí)際計(jì)算時(shí)并不需要引入6，還是進(jìn)行P的基變換，不過要注意現(xiàn)在選取出y, + L 6 jy.基變量的指標(biāo)是 min -2旦，其中y是某次迭代中右端常數(shù)向 y .k 0, i = 1. my *0量的第i行值，y., y分別是某次迭代中系數(shù)矩陣第i行第j列和第i行第k列 的值攝動(dòng)法考慮了收斂速度的問題，但遇到多個(gè)候選出基變量時(shí)，計(jì)算機(jī)計(jì)算比 較費(fèi)時(shí)，在實(shí)用上該方法不是一個(gè)理想的方法。2、Bland方法是最簡單，應(yīng)用最廣的避免循環(huán)的方法，該方法只是對(duì)進(jìn)基 和出基的準(zhǔn)則作了一些修改：首先把松弛變量（剩余變量）、人工變量都用xj表示，一般松弛變量（剩余 變量）的下標(biāo)

8、號(hào)列在決策變量之后，人工變量的下標(biāo)號(hào)列在松弛變量（剩余變量） 之后，在計(jì)算中：選取進(jìn)基變量時(shí)，在所有檢驗(yàn)數(shù)大于零的非基變量中，選取相應(yīng)下標(biāo)最小者 進(jìn)基；選取出基變量時(shí)，如果出現(xiàn)多個(gè)候選者，即存在兩個(gè)和兩個(gè)以上最小比值時(shí)， 選取下標(biāo)最小者出基；該方法計(jì)算簡單但迭代次數(shù)比較多，現(xiàn)在有很多學(xué)者在對(duì)Bland方法進(jìn)行改 進(jìn)，提出改進(jìn)的選基準(zhǔn)則，主要是加快目標(biāo)函數(shù)下降的速度。比如有的人提出： 開始把變量重新排序，使得c1=c2=. 0是線形規(guī)劃的初始基本可行解，且經(jīng)檢驗(yàn) 不是最優(yōu)解，那么，在候選進(jìn)基變量中選擇一個(gè)是初始基變量的變量進(jìn)基：（1） 若這樣的初始基變量有兩個(gè)以上，則任選一個(gè)進(jìn)基：（2）若候選進(jìn)基變量都不是 初始基變量，也任選其中一個(gè)進(jìn)基，同時(shí)在候選出基變量中選擇一個(gè)是初始基變 量的變量出基：（1）若這樣的初始基變量有兩個(gè)以上，則任選其中一個(gè)出基，若 候選出基變量都不是初始基變量，也任選其中一個(gè)出基。ii當(dāng)有多個(gè)檢驗(yàn)數(shù)是正數(shù)時(shí)，若相應(yīng)的基本可行解最多只有一個(gè)基變量取0 值，則取最大檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量出基；若相應(yīng)的基本可行解有多于一個(gè)基變 量取0值，則用Bland方法，選對(duì)應(yīng)變量中下標(biāo)最小者為進(jìn)基變量。參考文獻(xiàn)周勤學(xué)，丘兆福.Bland避免循環(huán)的單純形法的改進(jìn)J.中南大學(xué)學(xué) 報(bào).1989.3李思惠.單純形法求解LP問題克服循環(huán)的一種方法及