線性規(guī)劃的若干算法研究.pdf

1、線性規(guī)劃的算法研究從幾何上主要可以分為三種類型：一種是單純形類算法，即沿著可行域的邊界按照一定的旋轉(zhuǎn)規(guī)則，從一個頂點(基本可行解)移動到另一個更好的頂點；第二種是內(nèi)點算法，即迭代路徑是在可行域的內(nèi)部進行。第三種是外點法，即迭代點從可行域的外部收斂到原問題的最優(yōu)解。
　　 沿邊界點迭代的經(jīng)典算法是Dantzig的單純形算法。1998年，PAN.P.Q創(chuàng)造性的提出了一種全新的算法-虧基單純形算法，該算法拓展了基的概念，不再要求基為方

2、陣。在此基礎(chǔ)上，本文提出了一種求解線性規(guī)劃問題的虧基-階段大M算法，該算法只需要引入一個人工變量，大大的減少了問題的規(guī)模，并且在迭代過程中還可以提前判斷原問題是否可行，計算實例表明新算法比Dantzig的單純形在判別原問題可行性時更加有效。此外，通過修改進基變量的規(guī)則，提出虧基單純形算法的改進形式，提高了算法的效率并通過實例進行了驗證。
　　 內(nèi)點法是求解線性規(guī)劃問題的多項式時間算法，主要有三類：Karmarkar投影尺度算法、

3、仿射尺度算法、路徑跟蹤法。1990年，印度學(xué)者V.CH VENKAIAH闡述了一種新的內(nèi)點算法，該算法每一步迭代都采用同一個投影矩陣，但有反例說明投影矩陣不變的內(nèi)點算法只能保證收斂到問題的可行解而非最優(yōu)解。本文通過分析投影矩陣的特點，結(jié)合勢函數(shù)法的思想，構(gòu)造了一種新的投影矩陣不變的內(nèi)點算法，該算法可以保證收斂到最優(yōu)解，實例驗證了算法的有效性。
　　 基于對數(shù)罰函數(shù)法的思想，文中提出了一種新的組合方向內(nèi)點算法。新的組合方向內(nèi)點算法

4、在每一步迭代中也是組合目標(biāo)函數(shù)的最速下降方向和“對中方向”，但是各方向的權(quán)系數(shù)是隨機變化的而不是固定不變的，其中最速下降方向是投影矩陣不變的內(nèi)點算法得到的可行下降方向，而對中方向則是通過勢函數(shù)法得到的，并且新的組合算法的投影矩陣只需要計算一次，從而減少了算法的計算量，提高了算法的效率。初步的實例驗證了算法的正確性和有效性。
　　 1993年，Konstantinos Paparrizos闡述了一種外點單純形算法。外點法的兩個主要

5、的計算不足之處是：(1)未明確選擇一個“好的移動方向”；(2)不知是否存在一條通向可行域內(nèi)部的路徑。而一個“好的移動方向”更多的依賴于對偶初始可行基的選擇。對于初始的內(nèi)點可行解本文主要是通過兩階段投影矩陣不變內(nèi)點算法求得，而對于對偶可行基對應(yīng)的正則解，則主要是基于最鈍角的思想，構(gòu)造了對偶一階段算法，該算法采用了無比值原則來確定出基變量，減少了算法的計算量，最后獲得一個較好的對偶可行基對應(yīng)的正則解，從而得到了一種有效地外點單純形算法。