1.4.1退化、循環(huán)和防止循環(huán)的方法

《1.4.1退化、循環(huán)和防止循環(huán)的方法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1.5退化、循環(huán)和防止循環(huán)的方法1.5.1退化和退化引起的循環(huán)前面曾定義過退化問題(定義1.6)。對于退化問題，可能引起迭代循環(huán)現(xiàn)象，相應(yīng)的迭代叫做退化迭代。下面用例子來說明退化引起的循環(huán)現(xiàn)象。例1.13求解下列線性規(guī)劃問題標(biāo)準(zhǔn)后用單純形表法求解如下10-57-9-24000000001(1/2)1/21-11/2-3/20-5/2-1/20910100010001001010-57-9-240001000001100-11（4）11-52518-8-182-1-2010001-0-005341-204-2000410

2、-57-9-2400010-570001100010(1/2)1/2-1/2-4-24-3/4-1/43/411/41/4-11/400100-00029/2-98-27/4-53/40-9-5700012-11010100-8(2)0-3/21/2011/2-5/20001-0-0-29001815-930最后兩步迭代的單純形表如下:10-57-9-240000-240001-41/218-3/202-1/20010100-9(1)0001-0-022-93-2100240000001(1/2)1/21-11/2-3

3、/20-5/2-1/20910100010001001010-57-9-240004發(fā)現(xiàn)第六次迭代的結(jié)果與初始的一致，循環(huán)發(fā)生了。從上例可看出，采用單純形法求解退化問題可能發(fā)生循環(huán)現(xiàn)象，這會使得計(jì)算機(jī)死機(jī)。退化迭代有如下特點(diǎn)：1.退化迭代中基在不斷變化，但基本可行解不變；2.退化迭代中目標(biāo)函數(shù)值不變；3.退化迭代可能發(fā)生循環(huán)現(xiàn)象。那么退化問題是怎樣發(fā)生的呢？1.5.2防止循環(huán)的方法退化現(xiàn)象很難避免，我們只有設(shè)法避免循環(huán)的發(fā)生。防止循環(huán)的方法1.攝動法在各約束條件右手邊加上不同的微小攝動項(xiàng)，避免產(chǎn)生退化的頂點(diǎn)。2.Bla

4、nd法則a.換入基變量時(shí)，取入基，其中；b.換出基變量時(shí)，若有多于一個的最小比值，則取下標(biāo)最小者出基。攝動法在編程方面存在困難，Bland法則可操作性強(qiáng)。對于例1.13,前五次換基都符合Bland法則，第六次換基時(shí)，仍采用最大檢驗(yàn)數(shù)法則，取入基，這違反了Bland法則第一條。若根據(jù)Bland法則，從第六次換基開始的單純形表如下：410-57-9-240000-240001-4(1/2)18-3/202-1/20010100-910001-01022-93-21002400100001010-4-33-2-1(1)82-

5、2100-12-2001--100-271-440-200010-921101020300140-2100-50-221110-300-420-18-1用Bland法則能保證避免發(fā)生循環(huán)，上例只再進(jìn)行一次迭代就求得了最優(yōu)解最優(yōu)目標(biāo)函數(shù)值z*=1。這里我們不但避免了循環(huán)，求得了最優(yōu)解，而且最優(yōu)基本可行解是非退化的，盡管本問題是退化問題。習(xí)題1.6(2)p51用Bland法則求解。4