范数下无容量限制设施选址逆问题的求解方法

摘要：

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解.对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的.研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法.两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界.数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率.

关键词：无容量限制设施选址问题、逆问题、行生成算法、启发式算法

所属期刊栏目：31

分类号：O221.7(运筹学)

资助基金：国家自然科学基金;中国科学院青年创新促进会项目;国家自然科学基金

在线出版日期：2022-08-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：86-92