关于线性化技术的二次分配问题求解新方法.pdfVIP

第30卷第3期 系统工程理论与实践 V01．30，No．3 2010年3月 SystemsEngineering—TheoryPracticeMar．，2010 文章编号：100m6788(2010)03．0527—07中图分类号：022 文献标志码：A 基于线性化技术的二次分配问题求解新方法 张惠珍，马良 (上海理工大学管理学院，上海200093) 摘要： 文章在对已有二次分配问题(QAP)线性化模型深入研究的基础上，提出一种二次分配问 题线性化新方法，进而给出了对称二次分配问题的线性化模型．最后，通过求解二次分配基准问题 库(QAPLIB)中的部分实例说明了该线性化新方法的有效性和重要性． 关键词：二次分配问题；线性化；模型；线性松弛 Anewsolutionmethodforthe quadraticassignmentproblem onthelinearization based technique ZHANG Hui-zhen，MALiang of of forScienceand (SchoolManagement，UniversityShanghai Technology,Shanghai200093，China) Abstract：Inthis newlinearizationofthe based paper，a quadraticassignment proposed problem(QAP)is onthe onthecurrentvarious linearizationofthe study QAPfinearizations．Furthermore，thesymmetric fewofselectedinstancesinthe quadraticassignmentproblem(SQAP)isdiscussed．Finally,a QAPLIB are the resultsshowthatitisfeasibleand in tested，and experimental importantsolvingQAPbyusing thenew linearization technique． relaxation Keywords：quadraticassignmentproblem；linearization；formulation；linear 1引言 将QAP应用于电子元件的布局，并进行了实验【2】．自此，随着人们对QAP的不断探索和认识，QAP已被广 泛应用于许多实际问题，如打字机键盘和控制面板设计，经济活动，调度问题，统计分析，及化学反应分析和 考古学等1214J，但工厂位置选址问题是其应用最多的领域． 二次分配问题属于经典组合优化难题，不存在￡一近似度的多项式时间近似算法(Eo)t5_6】．该问题一 C=(q)∈蹰似”，其中，向表示设施i和歹之间的流量，％表示地点i和歹之间的距离，q，表示设施i位 于位置J所需的花费．要求给每个设施分配到—个地点，并使设备之间的总费用最小：