摘要：二次分配问题（QAP）是一种易于表述却难于求解的组合优化难题。将二次分配问题目标函数中的二次项线性化得到与原问题等价的（混合）整数线性化模型,是求解二次分配问题的重要途径,但二次分配问题线性化模型中庞大的变量和约束数,致使利用其求解较大规模的实例仍具有很大困难。通过松弛原有二次分配问题线性化模型中的约束,得到3个求解规模较小且较松弛的模型,提出了一种求解二次分配问题的新方法,并不仅从理论上证明了该方法的正确性,也从实验的角度说明了该方法较以往方法的优越性。

关键词：二次分配问题 线性化 模型 线性松弛 

单位：上海理工大学管理学院 上海200093