割平面加速策略的探究与改进

马春苗 谭希丽

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

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

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

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

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

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

【参考文献】

[1]胡运权，等.运筹学基础及应用（第五版）[M].北京：高等教育出版社，2008.

[2]吕一兵，万仲平.一种求解线性二层规划的割平面方法[J].数学的实践与认识，2012（21）.

[3]李裕梅，连晓峰，徐美萍，曹显兵.整数规划中割平面法的研究[J].数学的实践与认识，2011（11）.

[4]刘振航，王全文，吴振奎.割平面法的改进[J].天津轻工业学院学报，2003（S1）.

【作者简介】

马春苗（1995～），女，吉林长春人，硕士在读。研究方向：概率极限理论与应用。

谭希丽（1974～），女，吉林长春人，教授，博士，硕士生导师。研究方向：概率极限理论与应用。