几种基于匈牙利算法求解二次分配问题的方法及其分析比较

《几种基于匈牙利算法求解二次分配问题的方法及其分析比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第19卷第1期2010年2月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．19，No．1Feb．2010几种基于匈牙利算法求解二次分配问题的方法及其分析比较张惠珍，马良(上海理工大学管理学院，上海200093)摘要：二次分配问题(Quadraticassignmentproblem，QAP)属于NP—hard组合优化难题。二次分配问题的线性化模型和下界计算方法，是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础，根据现有QAP对偶上升下界计算方法中的具体操作，提出几种可行的QAP对偶上

2、升计算新方法。最后。通过求解QA-PLIB中的部分实例，深入分析其运行结果，详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操作可较大程度地提高目标函数最优解的下界增长速度，这为基于匈牙利算法求解二次分配问题的方法的改进莫定了基础。关键词：二次分配问题；下界；线性化；匈牙利算法中图分类号：0224文章标识码：A文章编号：1007—3221(2010)Ol-0092—08EmpiricalComparativeAnalysisoftheSolutionMethodsfortheQuadraticAssignmentProblemBasedon

3、theHungarianAlgorithmZHANGHui-zhen，MALiang(SchoolofManagement，Un&e腮ityofShanghaifo，．ScienceandTechnology，Shanghai200093，China)Abstract：Quadraticassignmentproblem(QAP)isaNP—hardcombinatorialoptimizationproblem．Thelineariza-tionoftheQAP，andthelowerboundsfortheQAParethekeywaysfor

4、solvingit．Inthispaper，severalachier-abledualascentsolutionmethodsfortheQAPareproposedbasedonthelinearizationoftheQAPandthespeci-fiedimplementationofthecurrentdualascentapproachfortheQAP．Then．afeWofselectedinstancesintheQAPLIBaretested，andthecorrespondingtestedresultsarefurther

5、studied．Furthermore，theprocesseswhichareincludedinthedualascentapproachesandcansignificantlyacceleratethelowerboundsoftheQAParedis—cussedindetail．WhatisstudiedinthispaperlaysafoundationfortheimprovementofthesolutionmethodsfortheQAPbasedontheHungarianalgorithm．Keywords：quadrati

6、cassignmentproblem；lowerbounds；linearization；hungarianalgorithm0引言1957年，Koopmans和Beckmann¨1在考虑经济活动选址问题时，不仅考虑活动位于特定位置的所需花费，而且考虑了活动之间的交互作用，首次提出二次分配问题(Quadraticassignmentproblem，QAP)。该问题一般可描述为：给定n个设施和，1个地点，三个nxn矩阵，即F=(‘)∈历“‘，D=(d口)∈男“。。收稿日期：2008-12—05基金项目：国家自然科学基金资助项目(70871081)；上

7、海市重点学科建设项目资助(S30504)作者简介：张惠珍(1979．)，女，山西人，博士研究生。从事系统工程、智能优化研究；-6良(1964一)，男．上海人，教授、博士生导师，从事系统工程，智能优化研究。第1期张惠珍，等：几种基于匈牙利算法求解二次分配问题的方法及其分析比较93c=(C口)∈劈“1，其中以表示设施i和_『之间的流量，d。表示地点f和J之间的距离，cu表示设施i位于位置_『的所需花费。要求给每个设施分配到一个地点，并使设备之间的总费用最小娈}；丢荟荟口删茗∥“+荟荟c∥。(1)式中q城，=^以，X是所有分配方案的集合，X={石I芝]菇

8、“21，i=1，⋯，凡置∑石F=1，i=1，⋯，儿』=1茗。E{0，1}，f，_『=1，⋯，n}(2)QAP不仅综合了一大