整数规划模型的Matlab程序实现
时间:2022-03-05 08:23:03 浏览次数:次
摘 要:整数规划是线性规划的基础上,对部分或全部决策变量为整数的最优化问题的模型、算法及应用等研究,是运筹学和管理科学中应用最基本的模型之一。大多数整数规划问题的计算求解存在实际的困难,求解一般线性规划的方法无法求解整数规划。为加深学生的理解,提高动手能力,本文介绍了一般整数规划和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.
推荐访问: 整数 模型 规划 程序 Matlab[整数规划模型的Matlab程序实现]相关文章
- 浅谈丢番图方程x~3±1=3qPy~2的整数解
- 非线性回归模型方法与灰色系统理论模型方法在大坝位移预测中的应用
- 标准模型哲学之思
- 基于AHP模型高校行政人员工作考核评价的研究
- 基于DS/AHP模型的学生综合成绩评估体系设计
- 打牢基础,建立模型,创新提高,实现梦想
- 简单模型在物理教学中的建立
- 在全市“十四五”规划编制工作推进会议上的讲话
- 论森林调查规划设计
- 试论风景园林规划设计
- 论校园网络规划设计的若干问题
- 论市政给排水规划设计与分析
- 试论10kV配电网规划设计方法
- 论高校图书馆新馆的规划设计
- 浅论园林景观中园路的作用、类型与规划设计
- 2023年度人生规划书3篇【通用文档】
- 汇编程序设计总结报告
- 自动洗衣机PLC程序设计与故障分析
- 基于CCS环境的DSP程序开发及运行
- 基于Android的智能家居程序开发与研究
- 细谈高三物理常见题型的程序化解题思维步骤
- 程序员年度总结范文11篇
- Web程序设计思政课程建设研究
- Karel在面向对象程序设计课程教学中的应用
- 微程序设计技术及其在计算机组成原理教学中作用的探讨
- 2023年终程序员个人工作总结(3篇)