01.11.2單純形法的進(jìn)一步討論(2)

1、運(yùn) 籌 學(xué) Operations Research1.11.2 單純形法的進(jìn)一步討論（2）2022/7/201運(yùn) 籌 學(xué) Operations Research回顧：非退化的基本可行解 退化的基本可行解非退化的線性規(guī)劃問題退化的線性規(guī)劃問題2022/7/202Th1 對非退化的線性規(guī)劃問題施行單純形法，必可經(jīng)過有限次迭代（轉(zhuǎn)軸）得到其最優(yōu)解或判明其無最優(yōu)解. Th2 對退化的線性規(guī)劃問題施行單純形法，有可能在有限次迭代內(nèi)無法終止.運(yùn) 籌 學(xué) Operations Research證明： 2022/7/203運(yùn) 籌 學(xué) Operations Research2022/7/204運(yùn) 籌 學(xué) Ope

2、rations Research轉(zhuǎn)軸前后，基本可行解和相應(yīng)的目標(biāo)函數(shù)值 都沒有改變！如此，單純形法的施行有可能陷入一個從初始可行基開始，經(jīng)過若干次轉(zhuǎn)軸，又返回到原基的“死循環(huán)”（cycling），而永遠(yuǎn)得不到最優(yōu)解或判明無最優(yōu)解. 2022/7/205運(yùn) 籌 學(xué) Operations Research一個著名的例子.1955年，E. M. Beale2022/7/206運(yùn) 籌 學(xué) Operations Research2022/7/207運(yùn) 籌 學(xué) Operations Research2022/7/208運(yùn) 籌 學(xué) Operations Research2022/7/209運(yùn) 籌 學(xué) Ope

3、rations Research 至此，轉(zhuǎn)軸過程返回到第一張單純形表，出現(xiàn)“死循環(huán)”.若再按照上述樞軸元的選取規(guī)則繼續(xù)轉(zhuǎn)軸，則轉(zhuǎn)軸會一直進(jìn)行下去而永不終止.當(dāng)然，不會得到最優(yōu)解. 2022/7/2010運(yùn) 籌 學(xué) Operations Research一個避免“死循環(huán)”的方法：1976年，R. G. Bland，Bland規(guī)則（Blands rule） 令2022/7/2011運(yùn) 籌 學(xué) Operations ResearchTh3（有限終止性）對任意（退化和非退化的）線性規(guī)劃問題施行帶Bland規(guī)則的單純形法，必可經(jīng)過有限次轉(zhuǎn)軸得到其最優(yōu)解或判明其無最優(yōu)解. 例（續(xù)） 2022/7/2012運(yùn) 籌 學(xué) Operations Research2022/7/2013運(yùn) 籌 學(xué) Operations Research2022/7/2014運(yùn) 籌 學(xué) Operations Research2022/7/2015運(yùn) 籌 學(xué) Operations Research注：（1）利用帶Bland規(guī)則的單純形法的轉(zhuǎn)軸的次數(shù)比直接利用單純形法要多. （2）在