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

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

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

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

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

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