線性規(guī)劃的可行點(diǎn)算法.pdf

1、該文研究的是線性規(guī)劃的可行點(diǎn)算法,一個(gè)由線性規(guī)劃的內(nèi)點(diǎn)算法衍生而來的算法.線性規(guī)劃的內(nèi)點(diǎn)算法是一個(gè)在線性規(guī)劃的可行域內(nèi)部迭代前進(jìn)的算法.有各種各樣的內(nèi)點(diǎn)算法,但所有的內(nèi)點(diǎn)算法都有一個(gè)共同點(diǎn),就是在解的迭代改進(jìn)過程中,要保持所有迭代點(diǎn)在可行域的內(nèi)部,不能到達(dá)邊界.當(dāng)內(nèi)點(diǎn)算法中的迭代點(diǎn)到達(dá)邊界時(shí),現(xiàn)行解至少有一個(gè)分量取零值.根據(jù)線性規(guī)劃的靈敏度分析理論,對(duì)線性規(guī)劃問題的現(xiàn)行解的某些分量做輕微的擾動(dòng)不會(huì)改變線性規(guī)劃問題的最優(yōu)解.故我們可以用一

2、個(gè)很小的正數(shù)賦值于現(xiàn)行解中等于零的分量,繼續(xù)計(jì)算,就可以解出線性規(guī)劃問題的最優(yōu)解.這種對(duì)內(nèi)點(diǎn)算法的迭代點(diǎn)到達(dá)邊界情況的處理就得到了線性規(guī)劃的可行點(diǎn)算法.它是一個(gè)在可行域的內(nèi)部迭代前進(jìn)求得線性規(guī)劃的最優(yōu)解的算法.在此算法中,只要迭代點(diǎn)保持為可行點(diǎn).該文具體以仿射尺度算法和原始-對(duì)偶內(nèi)點(diǎn)算法為研究對(duì)象,考慮這兩種算法中迭代點(diǎn)到達(dá)邊界的情況,得到相對(duì)應(yīng)的'仿射尺度可行點(diǎn)算法'和'原始-對(duì)偶可行點(diǎn)算法'.在用理論證明線性規(guī)劃的可行點(diǎn)算法的可行性