匈牙利算法解二次分配问题的方法与其分析比较.pdf

第19卷第1期 运 筹 与 管 理 V01．19，No．1 ANDMANAGEMENTSCIENCE Feb．2010 2010年2月 OPERATIONSRESEARCH 几种基于匈牙利算法求解二次分配 问题的方法及其分析比较 张惠珍， 马良 (上海理工大学管理学院，上海200093) 摘要：二次分配问题(Quadraticassignment 化模型和下界计算方法，是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础，根据现 有QAP对偶上升下界计算方法中的具体操作，提出几种可行的QAP对偶上升计算新方法。最后。通过求解QA- PLIB中的部分实例，深入分析其运行结果，详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操 作可较大程度地提高目标函数最优解的下界增长速度，这为基于匈牙利算法求解二次分配问题的方法的改进莫 定了基础。 关键词：二次分配问题；下界；线性化；匈牙利算法 中图分类号：0224 文章标识码：A 文章编号：1007—3221(2010)Ol-0092—08 oftheSolutionMethodsfortheQuadratic Analysis EmpiricalComparative ProblemBasedonthe Assignment HungarianAlgorithm ZHANG Hui-zhen，MALiang and 200093，China) (SchoolofManagement，Une腮ityofShanghaifo，．ScienceTechnology，Shanghai aNP—hardcombinatorial lineariza- Abstract：Quadraticassignmentproblem(QAP)is optimizationproblem．The thelowerboundsfor arethe for it．Inthis achier- tionofthe the QAP，and QAP keywayssolving paper，several ofthe andthe abledualascentsolutionmethodsforthe are basedonthelinearization QAPproposed QAP speci- fied ofthecurrentdualascent forthe feWofselectedinstancesinthe implementation approachQAP．Then．a are the testedresultsarefurther which QAPLIBtested，andcorresponding studied．Furthermore，theprocesses in