| 求解无容量设施选址问题的半拉格朗日松弛新方法 |
| |
| 引用本文： | 张惠珍,魏欣,马良.求解无容量设施选址问题的半拉格朗日松弛新方法[J].运筹学学报,2015,19(4):37-47. |
| |
| 作者姓名： | 张惠珍 魏欣 马良 |
| |
| 作者单位： | 1. 上海理工大学管理学院, 上海 200093; 2.上海理工大学超网络(中国)研究中心, 上海 200093 |
| |
| 基金项目： | 1.国家自然科学基金(No.71401106);2.上海市教育委员会科研创新项目(No.14YZ090);
3.上海市一流学科建设项目(No.S1201YLXK);4.高等学校博士学科点专项科研基金联合资助课题(No.20123120120005);
5.上海高校青年教师培养资助计划(No.slg12010);6.沪江基金(No.A14006) |
| |
| 摘 要： | 无容量设施选址问题Un-capacitated Facility Location, UFL是应用于诸多领域的经典组合优化难题, 半拉格朗日松弛方法是求解UFL问题的一种精确方法. 分析了半拉格朗日松弛方法在求解UFL问题时所具有的性质, 在此基础上, 对求解UFL问题的半拉格朗日松弛方法进行了一定的理论完善, 并探讨了提高半拉格朗日松弛方法求解性能的有效途径.数值计算结果表明：改进方法具有明显的可行性和有效性.
|
| 关 键 词： | 无容量设施选址 拉格朗日松弛 半拉格朗日松弛 原始-对偶最优解 |
| 收稿时间： | 2014-11-24 |
A new semi-Lagrangian relaxation method to solvethe un-capacitated facility location problem |
| |
| ZHANG Huizhen,WEI Xin,MA Liang.A new semi-Lagrangian relaxation method to solvethe un-capacitated facility location problem[J].OR Transactions,2015,19(4):37-47. |
| |
| Authors: | ZHANG Huizhen WEI Xin MA Liang |
| |
| Institution: | 1.School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Center for Supernetworks Research, University of Shanghai for Science and Technology, Shanghai 200093, China |
| |
| Abstract: | The un-capacitated facility location (UFL) problem is a classical combinatorial optimization hard problem and has been applied in various fields. The semi-Lagrangian relaxation method is one of the exact solution methods to the UFL. In this paper, the mathematical nature of the SLR applied to solve the UFL is further studied. Based on this, the SLR applied to solve the UFL is improved from the theoretical point of view, and the approach is also discussed to enhance its
computational capability. The numerical results show that the improvement proposed in this paper is feasible and effective. |
| |
| Keywords: | Un-capacitated facility location Lagrangian relaxation Semi-Lagrangian relaxation Primal-dual optimal solution |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
