文档介绍：第第
四四 • 整数规划
章章 • 整数规划的分支定界法
•0-1整数规划
整整 隐枚举法
数数 匈牙利算法
规规
划划
引例：
问问
题题
引引 且为整数
当不要求解为整数时，对应的线性规划问题最优解为：
出出 X1=, x2=
整数解如何获得?
能否用将线性规划问题解中不满足整数的解取整的办法获得整
数解呢？
，每箱的体积重
量可获得的利润及托运所受的限制如表1所示。问每次
两种货物各托运多少箱，可使得获得的利润最大？
问问 货物 每箱体积 每箱重量 每箱利润(
(米3) (百斤) 百元)
题题 甲 5220
引引 乙 4510
出出 托运限制 24 13
线性规划模型：
假设xx12, 分别为两种货物托运的箱数
maxzxx 2012 10
54xx12 24
st.. 2 x12 5 x 13
且为整数
xx12,0
若在线性规划模型中，变量限制为整数，则
整 称为整数线性规划。
数
规 整数规划分类
划 变量全限制为整数的，为纯(完全)整数规
定 划。
义 特例：0-1整数规划
变量部分限制为整数的，为混合整数规
划。
作图法求解例1
Z=90
+ Z=96
+ + + +
(,0)
整整 定义：去掉整数条件得到的问题为整数规划问题的松弛问题。
数数 整数规划的松弛问题是一个线性规划问题，其
可行域是一个凸集，任何两个可行解的凸组合
规规 都是可行解；
划划 整数规划可行解的集合是其松弛问题可行域的
一个子集。任何两个可行解的凸组合不一定满
解解 足整数条件，因而不一定为可行解；
的 整数规划的可行解一定是其松弛问题的可行解
的 ，反之，不成立。
特特 所以整数规划的最优解不优于松弛问题的最优
点点 解( 引申含义是什么？ )。
整整
数数 原线性规划有最优解，当自变量限制为整数
规 后，其整数规划解出现下述情况；
规 ①原线性规划最优解全是整数，则整数规
划划 划最优解与线性规划最优解一致。
②原最优解变为非可行解。
解解 整数规划最优解不能按照实数最优解简单取整
的的 而获得。
特特
点点
握
整整 1．割平面法——主要求解纯整数线性规划(不要求掌
数 )
数 2．分支定界法——可求纯或混合整数线性规划
规规 3．隐枚举法——求解0-1整数规划
划划 ① 过滤隐枚举法
② 分支隐枚举法
求求 4．匈牙利法——解决指派问题(0-1规划特殊情形)
解解 5．蒙特卡洛法——求解各种类型规划(不要求掌握)
方方 6. 分支切割方法(不要求掌握)
7. 启发式算法(不要求掌握)
法法
分支定界法是求整数规划的一种常用的有效的
方法，既能解决纯整数规划的问题，也能解决
分分 混合整数规划的问题。
支支 问题(A)如下：
Max z = c1 x1 + c2 x2 + … + cn xn
定定