-16-
第二章 整数规划
§1 概论
1.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，
变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：
1
o
变量全限制为整数时，称纯（完全）整数规划。
2
o
变量部分限制为整数的，称混合整数规划。
1.2 整数规划特点
（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例 1 原线性规划为
21
min xxz +=
0,0,542
2121
≥≥=+ xxxx
其最优实数解为：
4
5
min,
4
5
,0
21
=== zxx 。
③有可行解（当然就存在最优解），但最优解值变差。
例 2 原线性规划为
21
min xxz +=
0,0,642
2121
≥≥=+ xxxx
其最优实数解为：
2
3
min,
2
3
,0
21
=== zxx 。
若限制整数得：
2min,1,1
21
=
== zxx 。
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类：
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系
统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子
集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称
为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，
剩余15页未读，继续阅读
资源评论
帅气的alex
- 粉丝: 0
- 资源: 1
最新资源
- 基于Java技术的ASC学业支持中心并行项目开发设计源码
- 基于Java和微信支付的wxmall开源卖票商城设计源码
- 基于Java和前端技术的东软环保公众监督系统设计源码
- 基于Python、HTML、CSS的crawlerdemo软件工程实训爬虫设计源码
- 基于多智能体深度强化学习的边缘协同任务卸载方法设计源码
- 基于BS架构的Java、Vue、JavaScript、CSS、HTML整合的毕业设计源码
- 基于昇腾硬件加速的AI大模型性能优化设计源码
- 基于Plpgsql与Python FastAPI的mini-rbac-serve权限管理系统后端设计源码
- 基于SpringBoot的轻量级Java快速开发源码
- 基于Python开发的物流调度算法设计源码
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
