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

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

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