论文部分内容阅读
经典的半二次指派问题是整数规划,其在交通规划、物流和网络规划等现实生活领域有着广泛的应用。因为半二次指派问题是NP-难的,目前还没有多项式时间的精确解法。本文对半二次指派问题的约束进行适当的选取,给出了初次得到的半二次指派问题的模型。运用拉格朗日对偶的技术,提出了半二次指派问题的全正锥模型,并证明初次得到的半二次指派问题的松弛问题与所提出的全正锥模型的最优值是相等的。因直接求解全正锥优化问题计算难度大,而全正锥包含于半正定锥与非负锥的交所构成的双非负锥,本文利用双非负锥代替全正锥的松弛技巧,提出了半二次指派问题松弛问题的锥模型。更进一步,利用双非负锥优化问题的对偶问题数据结构简单的特性,所以文中运用邻近增广拉格朗日算法求解双非负锥规划问题的对偶问题。本文撷取QAPLIB数据库中的数据产生半二次指派问题,利用邻近乘子交替方向法生成初始点;同时,基于投影算子的强半光滑性质,运用改进的半光滑牛顿-共轭梯度法求解增广拉格朗日算法的子问题。本文应用SDPNAL+软件包进行数值实验,得到了半二次指派问题的较好下界,并对得到的数值结果进行了分析。