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

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

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

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