整数规划模型的Matlab程序实现

顾文亚　孟祥瑞

摘 要：整数规划是线性规划的基础上，对部分或全部决策变量为整数的最优化问题的模型、算法及应用等研究，是运筹学和管理科学中应用最基本的模型之一。大多数整数规划问题的计算求解存在实际的困难，求解一般线性规划的方法无法求解整数规划。为加深学生的理解，提高动手能力，本文介绍了一般整数规划和0-1整数规划的Matlab命令，并给出具体的实例。

关键词：整数规划 0-1整数规划 割平面法 分枝定界法 Matlab

中图分类号：O221.4 文献标识码：A 文章编号：1672-3791（2018）12（c）-0009-02

整数规划是在线性规划的基础上，给一些或全部决策变量附加取整约束得到的。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变量仅限于0或1[1-3]。

若按线性规划的方法来求解整数规划问题，最优解如果不是整数，似乎把已得的非整數解舍入化整就可以了。但实际上化整后的数一般不是最优解，所以整数规划有自身特有的方法来求解。目前比较成功又流行的方法是分枝定界法和割平面法[4，5]。求解0-1规划的常用方法是枚举法和隐枚举法[6]，对各种特殊问题还有一些特殊方法，例如求解指派问题的匈牙利法[7，8]。

1 整数规划的Matlab函数

3 结语

直接调用Matlab R2014a工具箱，只须编写很简单的几行程序代码，即可实现对整数规划，包括对0-1整数规划的求解，且结果可靠，计算精度高，避免了应用其他语言程序过于复杂、调试困难等缺点，提高了计算效果。

参考文献

[1] 顾文亚，孟祥瑞，陈允杰.运筹学（上）[M].镇江：江苏大学出版社，2015.

[2] Ping-Qi PAN.Linear Programming Computation[M].Berlin Heidlberg：Springer Verlag，2014.

[3] Williams，H.Paul.Logic and integer programming[M]. Berlin Heidlberg：Springer Verlag，2009.

[4] R.E. Gomory. Outline of an algorithm for integer solutions to linear programs[J]. Bulletin of the American Mathematical Society，1958，64（5）：275-278.

[5] A.H. Land， A.G. Doig.An automatic method of solving discrete programming problems[J].Econometrica，1960，28（3）：497-520.

[6] E Balas，F Glover，S Zionts. An Additive Algorithm for Solving Linear Programs with Zero-One Variable[J]. Operations Research，1965，13（4）：517-549.

[7] Harold W. Kuhn. The Hungarian Method for the assignment problem[J].Naval Research Logistics Quarterly，1955（2）：83-97.

[8] Harold W. Kuhn. Variants of the Hungarian method for assignment problems[J].Naval Research Logistics Quarterly，1956（3）：253-258.

[9] 温正.MATLAB科学计算[M].北京：清华大学出版社， 2017.