線性規(guī)劃既約空間算法的研究.pdf

1、本文基于潘平奇教授提出的最優(yōu)解的啟發(fā)式特征刻劃，利用攝動技術(shù)建立了一個新的單人工變量一階段過程。所進行的初步數(shù)值實驗表明，新算法優(yōu)于經(jīng)典算法。 本文基于潘平奇教授提出的Nested Pricing規(guī)則，給出了既約梯度算法的一個新變種。并將其推廣到有界變量線性規(guī)劃模型的求解。 本文將Kallio和Porteus的一類算法加以推廣，發(fā)展了一類稱之為原始既約空間主元算法的新算法．并將Kallio和Porteus的假設條件減弱，

2、在非退化的假設下證明了這類算法的有限性．并在此基礎上進一步給出了對偶既約空間主元算法。 本文還提出了原始和對偶既約空間內(nèi)點算法，并在非退化的假設下證明了原始既約空間內(nèi)點算法的收斂性．這是一類特別有發(fā)展?jié)摿Φ男滤惴?，其每次迭代對應一個基，因而兼具主元算法和內(nèi)點算法的特性；而每次迭代所需計算量比仿射尺度內(nèi)點算法少得多，且當?shù)c接近最優(yōu)解時更穩(wěn)定，可以獲得高精度的解．本文的初步數(shù)值實驗結(jié)果表明，原始既約空間內(nèi)點算法遠優(yōu)于原始仿射尺度