網(wǎng)絡(luò)優(yōu)化中的整數(shù)規(guī)劃算法研究.pdf

1、該文主要研究求解網(wǎng)絡(luò)優(yōu)化中的整數(shù)規(guī)劃、背包、線性規(guī)劃等問題的新算法及其高效并行算法.針對求解線性規(guī)劃松弛算法在選取松弛變量時存在的不足,提出了線性規(guī)劃問題有最優(yōu)解的一個必要條件,將該必要條件應(yīng)用于線性規(guī)劃松弛算法中松弛變量的選取上,對松弛算法進行了改進.在此基礎(chǔ)上,提出了一種基于Cluster結(jié)構(gòu)的并行松弛算法,與線性規(guī)劃同類并行算法對比,該算法具有更好的并行性和求解效率.最近,有學(xué)者提出了一種算法,它適于求解約束個數(shù)很多但變量個數(shù)較少

2、的線性規(guī)劃問題.該文根據(jù)其在數(shù)據(jù)和操作上各個步驟的相關(guān)性,將該算法在主從式消息傳遞接口環(huán)境下并行化,設(shè)計了一個求解該類問題的并行算法,理論分析和實驗結(jié)果表明本算法具有良好的并行性和可擴展性.整數(shù)規(guī)劃是離散算法和NP問題研究中的核心問題之一,如何提高實際應(yīng)用中大規(guī)模整數(shù)規(guī)劃問題的求解效率具有十分重要的理論和實際意義.利用二分網(wǎng)格作為幾何工具,將傳統(tǒng)二分搜索推廣應(yīng)用到整數(shù)規(guī)劃問題的可行域中,提出一種求解整數(shù)規(guī)劃的新算法.該算法不僅能夠克服分

3、枝限界算法和割平面算法求解系數(shù)呈指數(shù)增長的整數(shù)規(guī)劃實例時存在的實質(zhì)性困難,而且其高可并行性可望為一般大規(guī)模整數(shù)規(guī)劃的精確求解提供新的可選方案.將該算法的設(shè)計思想用于求解與整數(shù)規(guī)劃有密切關(guān)系的無界背包問題,得到一種求解該問題的新算法.新算法對于固定物品數(shù)背包實例的求解時間僅為問題輸入規(guī)模L的線性函數(shù),這一結(jié)果表明新算法明顯改進了動態(tài)規(guī)劃和分枝限界算法的相關(guān)性能.并行計算是解決等式背包問題的有效方法之一.該文深入研究了背包問題并行算法的研究