整数规划与规划PPT学习教案.pptx

会计学
1
整数规划与规划
2
例 1
第1页/共33页
3
例 2 背包问题
第2页/共33页
4
整数规划特点
(1)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
原线性规划最优解不全是整数，则整数规划最优解小于原线性规划最优解（max）或整数规划最优解大于原线性规划最优解（min）。
整数规划无可行解。
(2)整数规划最优解不能按照实数最优解简单取整而获得。
第3页/共33页
5
整数规划求解方法分类
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。
第4页/共33页
6
整数规划-分枝定界法
对有约束条件的最优化问题的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
第5页/共33页
7
例题演示
例 3 求解下述整数规划
.
A
B
先不考虑整数限制，即解相应的线性规划，得最优解为：
第6页/共33页
8
显然它不符合整数条件。这时Z是问题A的最优目标函数值Z*的上界，记作 。而 显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作
，即
第7页/共33页
9
分支
因为 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 进行分枝，把可行集分成2个子集：
因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：
第8页/共33页
10
再定界：
对问题B1再进行分枝得问题B11和B12，它们的最优解为:
再定界： ，并将B12剪枝。
对问题B2再进行分枝得问题B21和B22，它们的最优解为:
无可行解。
将 剪枝，于是可以断定原问题的最优解为：
第9页/共33页