線性規(guī)劃的組合方向算法.pdf

1、線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。線形規(guī)劃是在滿足線性約束下實(shí)現(xiàn)目標(biāo)值最優(yōu)的數(shù)學(xué)理論和方法。目前線性規(guī)劃已經(jīng)廣泛應(yīng)用軍事、經(jīng)濟(jì)、管理、工程等方面，為決策者在有限的人力、物力、財(cái)力的情況下做出決策提供可靠的科學(xué)依據(jù)。因此，如何更快并準(zhǔn)確的計(jì)算線性規(guī)劃問(wèn)題成為一個(gè)很有吸引力的，也很有必要的課題。1947年，G.B.Dantzig首次提出了求解線性規(guī)劃問(wèn)題的單純形算法。單純形

2、算法由于其規(guī)則簡(jiǎn)便，且能很好的解決線性規(guī)劃問(wèn)題，成為了線性規(guī)劃問(wèn)題的經(jīng)典算法。自此之后，線性規(guī)劃問(wèn)題的算法大致可以分為兩類：一類是傳統(tǒng)的沿著可行域的可行邊方向前進(jìn)，從一個(gè)極點(diǎn)到鄰接的另一個(gè)極點(diǎn)，最終得到規(guī)劃問(wèn)題的最優(yōu)解；另一類則是不按照傳統(tǒng)的迭代方法，即不嚴(yán)格的按照可行下降(上升)邊方向迭代，而是從可行域的內(nèi)部或者外部行進(jìn)，而多數(shù)的算法是選擇從可行區(qū)域內(nèi)部行進(jìn)，從而最終找到最優(yōu)解。在第一類算法中，主要的工作是主元的選擇規(guī)則上，目前得到較

3、多認(rèn)可的除了單純形算法的主元規(guī)則，還有基于最鈍角的選主元規(guī)則，以及最陡邊的列主元規(guī)則。而在第二類算法中，主要是通過(guò)選擇不同于可行下降(上升)邊方向的可行方向來(lái)實(shí)現(xiàn)可行域的內(nèi)部穿越，從而最終實(shí)現(xiàn)最優(yōu)解的尋找。這類算法對(duì)于求解大規(guī)模的線性規(guī)劃問(wèn)題有著一定的優(yōu)勢(shì)，因?yàn)樵擃愃惴ㄍ軌虮荛_(kāi)很多極點(diǎn)，從而減少迭代次數(shù)，但內(nèi)點(diǎn)法一旦問(wèn)題即將達(dá)到最優(yōu)解時(shí)，將顯示出其收斂速度慢的劣勢(shì)，而第一類的單純形算法卻在初期的迭代中耗費(fèi)太長(zhǎng)時(shí)間。
　　 本

4、文將要描述的算法是一種基于組合方向的算法，該算法從一個(gè)極點(diǎn)出發(fā)，通過(guò)一個(gè)組合方向，使該基本可行解迭代到可行域的一個(gè)高維界面，然后通過(guò)純化過(guò)程(即通過(guò)降維)，使該高維界面上的可行解逐漸迭代成一個(gè)基本可行解，如此反復(fù)使最后得到的基本可行解滿足最優(yōu)解的判定標(biāo)準(zhǔn)，這樣也就得到了一個(gè)最優(yōu)解。使用該類算法即能夠減少迭代次數(shù)，同時(shí)盡可能的規(guī)避內(nèi)點(diǎn)法的一些弱點(diǎn)，如后期迭代收斂速度過(guò)低的情況。而針對(duì)線性問(wèn)題規(guī)模擴(kuò)大后，極有可能出現(xiàn)退化產(chǎn)生的停駐現(xiàn)象，引入