第二章 整数规划
§1 概论
1.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型
中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往
往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：
1
o
变量全限制为整数时，称纯（完全）整数规划。
2
o
变量部分限制为整数的，称混合整数规划。
3
o
变量只能取 0 或 1 时，称之为 0-1 整数规划。
整数规划特点
（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例 1 原线性规划为
s.t.
其最优实数解为： 。
③有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优
值。
例 2 原线性规划为
s.t.
其最优实数解为： 。
若限制整数得： 。
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类：
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统
-11-
剩余7页未读，继续阅读
资源评论
xzmuly2013-01-08很好很强大 正是我所需要的- xietingfeng8302013-09-24感觉没有水晶球好用
落雪无痕ycf2016-01-12感觉还可以吧。
