求解二次分配问题的拉格朗日松弛新方法  

A New Solution Method Based on Lagrangian Relaxation for the Quadratic Assignment Problem

作　　者：张惠珍[1] 李倩[1] Cesar Beltran-Royo 

机构地区：[1]上海理工大学管理学院,上海200093 [2]西班牙胡安卡洛斯大学统计与运筹系,西班牙马德里28933

出　　处：《数学的实践与认识》2016年第18期136-144,共9页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71401106);上海市一流学科建设项目(S1201YLXK);高等学校博士学科点专项科研基金联合资助课题(20123120120005);沪江基金(A14006);上海市教育委员会科研创新项目(14YZ090)

摘　　要：以改进的拉格朗日松弛(Lagrangian relaxation,LR)方法和二次分配问题(quadratic assignment problem,QAP)的线性化模型为基础,给出了求解QAP的拉格朗日松弛新方法,这为有效求解QAP提供了一种新的解决方案.通过求解二次分配基准问题库(QAPLIB)中的实际算例,从实验的角度说明了拉格朗日松弛新方法求解QAP的可行性及存在的不足之处,并对今后进一步的研究工作指明了方向.A new solution method based on Lagrangian relaxation（LR） for the quadratic assignment problem（QAP） is proposed in this paper,which provides a new approach to solve the QAP effectively by using both the improved LR and the QAP linearization.A few of instances in the QAPLIB are solved,the experimental results not only show that it is feasible in solving the QAP by using the new solution method,but also disclose the disadvantages of this solution procedure.Finally,the problems for further studies and improvements on this solution method are put forward.

关 键 词：二次分配问题 拉格朗日松弛 线性化模型 等式约束 

分 类 号：O224[理学—运筹学与控制论]