单位文秘网 2021-07-20 08:22:07 点击: 次
摘 要:整数规划是线性规划的基础上,对部分或全部决策变量为整数的最优化问题的模型、算法及应用等研究,是运筹学和管理科学中应用最基本的模型之一。大多数整数规划问题的计算求解存在实际的困难,求解一般线性规划的方法无法求解整数规划。为加深学生的理解,提高动手能力,本文介绍了一般整数规划和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.
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-241-67960-1.html
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用