马春苗 谭希丽

【摘 要】整数规划在数学规划中具有重要的地位。整数规划求解的重要方法之一就是割平面法。在使用割平面法求解整数规划时，寻找Gomory约束是最为关键的一步，如何选取较好的Gomory约束，以便加快收敛速度是目前研究的重要课题。

【关键词】整数规划;割平面法;割平面方程;改进方案

【中图分类号】G642  【文献标识码】A  【文章编号】1671-8437（2020）16-0253-02

整数规划是数学规划的一个重要的分支，在工业、商业、运输、经济管理和军事等领域中都有重要的应用。割平面法是求解整数规划的一种重要方法。目前，多数运筹学教科书关于割平面法的讲解不够深入、细致，在解题时不能够灵活应用，经常切割很多次仍找不到最优解，即遇到向最优解收敛很慢的情形，学生普遍认为割平面不如分支界定法有效。然而，实际情况并非如此，灵活运用割平面法可以使得整数规划的求解过程更加容易[1]。最近，仍有许多学者在对割平面法进行研究，并发现该方法也有很好的效果。本文对割平面法做进一步深入的研究，以让割平面法能够更灵活地被运用。

1   割平面法求解问题的思路

综上所述，本文主要讨论了两种割平面法的改进方案，并对两种方案进行了对比。一种是用割平面法求解时，利用已知、已得信息，将这些超平面的线性组合生成新的Gomory约束，并取代原来的系统约束，从而较快地得到最优解。另一种是在用割平面法求解问题时，选取非整数解变量中分数部分最大的一个基变量，取相应行的约束，推导出该行的Gomory约束[4]。……