整数规划和规划学习教案.pptx

整数规划是什么?
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
/共25页
第七页，共26页。
解: 设每周生产Ⅰ、Ⅱ号杯各 百箱,则有如下数学模型
返回
Mathematical modeling
第8页/共25页
第八页，共26页。
例3：设整数规划问题如下
·完全枚举法
Mathematical modeling
第9页/共25页
第九页，共26页。
现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。
故按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。
求得（2，2）（3，1）点为最大值，。
在求解整数规划问题时，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。
返回
Mathematical modeling
第10页/共25页
第十页，共26页。
对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系
统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子
集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称
为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
·分支定界法
Mathematical modeling
第11页/共25页
第十一页，共26页。
例4 用分支定界法求以下整数规划
Mathematical modeling
第12页/共25页
第十二页，共26页。
Mathematical modeling
第13页/共25页
第十三页，共26页。
开始
V0 X1=,X2=;Z0=
X2≤3
X2≥4
V1 X1=3,X2=3,Z2=39
V2 X1=,X2=4,Z1=41
X1≥2
X1≤1
V3 X1=1,X2=, Z4=
V6 X1=0,X2=5,Z6=40
V5 X1=1,X2=4,Z5=37
V4 不可行
X2≤4
X2≥5
Mathematical modeling
第14页/共25页
第十四页，共26页。
·0-1整数规划
-1整数规划？
-1整数规划法？
0-1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。
正如计算机只懂得0,1两个数，1代表是，0代表否。同样的，在0-1整数规划中的0和1并不是真真意义上的数，而是一个衡量事件是否发生的标准。一般来说，我们在从多个事物中选出其中一部分，在一定的条件下求解最优情况时可以采用0-1整数规划法。
Mathematical modeling
第15页/共25页
第十五页，共26页。
例5一个旅行者要到某地作两周的带包旅行,装背包时,他发现除了已装的必需物件外,,(这里用打分数的办法表示价值)如下表所示,问旅行者应该选取哪些物件为好？
Mathematical modeling
第16页/共25页
第十六页，共26页。
解：建立模型为
Mathematical modeling
第17页/共25页
第十七页，共26页。
Mathematical modeling
第18页/共25页
第十八页，共26页。
由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解： 找到x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。
Mathematical modeling
第19页/共25页
第十九页，共26页。
例6 求解下列0-1规划问题
Mathematical modeling
第20页/共25页
第二十