基于改進(jìn)PSRS的并行0-1規(guī)劃算法研究及其應(yīng)用.pdf

1、并行計(jì)算技術(shù)的發(fā)展與成熟為最優(yōu)化問(wèn)題的快速求解帶來(lái)了新的機(jī)遇和挑戰(zhàn)。隨著并行計(jì)算機(jī)與并行算法理論的發(fā)展，近年來(lái)，并行0-1整數(shù)規(guī)劃求解算法的研究與應(yīng)用引起極大關(guān)注，并取得了大量研究成果。
　　 本文對(duì)0-1整數(shù)規(guī)劃問(wèn)題的模型和現(xiàn)有的求解方法進(jìn)行了研究與分析，詳細(xì)討論了該問(wèn)題的有效求解方法:目標(biāo)排序法。分析了該方法的核心計(jì)算所在，并討論了該算法進(jìn)行任務(wù)劃分的可能性。再對(duì)PSRS方法進(jìn)行了改進(jìn)，將該方法引入0-1整數(shù)規(guī)劃的求解中，并

2、針對(duì)其特殊性對(duì)PSRS的排序步驟和結(jié)果進(jìn)行了修改，完成了0-1整數(shù)規(guī)劃問(wèn)題求解任務(wù)的均衡劃分。用改進(jìn)的PSRS和目標(biāo)排序法設(shè)計(jì)了一個(gè)求解0-1整數(shù)規(guī)劃問(wèn)題的并行算法。為驗(yàn)證算法有效性，通過(guò)建立物流配送中心選址問(wèn)題的0-1規(guī)劃模型，并采用所提算法求解該模型，數(shù)值試驗(yàn)結(jié)果表明，所提算法能有效求解大規(guī)模0-1規(guī)劃問(wèn)題，且具有較好的加速比和可擴(kuò)展性。
　　 綜上，本文闡述了基于目標(biāo)排序和改進(jìn)PSRS設(shè)計(jì)0-1整數(shù)規(guī)劃并行求解算法的思想和