整数规划问题
家常糖醋鱼-论文大纲
整数规划问题
要求一部分或全部决策变量必须取整数值的规划问题称为整数规划
(integer prog
ramming，简记IP)。不考虑整数条件，由余下的目标函数和约
束条件构成的规划问题称为该整
数规划问题的松弛问题(slack problem)。若松
弛问题是一个线性规则，则称该整数规划
为整数线性规划
(integer linear programming，简记ILP
分类
整数规划问题按决策变量取值可分为下列几种类型：
1．纯整数规划(pure integer
programming)：指全部决策变量都必须取整数
值的整数规划。有时，也称为全整数规划。
2．混合整数规划(mixed integer programming)：指决策变量中有一部分
必须
取整数值，另一部分可以不取整数值的整数规划。
3．0-1型整数规划(zero—one integer
programming)：指决策变量只能取值
0或1的整数规划
1.3
整数规划的一般形式
2 整数规划问题的计算方法
2.1
分支定界法
分支定界法是在20世纪60年代初由Land
Doing和Dakin等人提出的适合于解
纯整数或混合整数规划问题的方法。
分支定界
法的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符
合整数条件，则增加新约束——缩
小可行域；将原整数规划问题分支——分为两
个子规划，再解子规划的伴随规划，以此类推，最后得到原
整数规划的伴随规划。
这就是所谓的“分支”。
所谓“定界”，是在分支过程中，若某个后
继问题恰巧获得整数规划问题的
一个可行解，那么，它的目标函数值就是一个“界限”，可以作为衡量处
理其它
分支的一个依据。
“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的
效率。
分支定界法的计算步骤
第一步：计算原问题目标函数值的初始上界
第二步：计算原问题目标函数值的初始下界
第三步：增加约束条件将原问题分支
第四步：分别求解一对分支
第五步：修改上、下界
第六步：比较上、下界大小，如有上界＝下界，停止计算，找到最优解，否
则转3
.2 割平面法
割平面法由高莫瑞(Gomory)于1958年提出。其基本思想是放宽
变量的整数
约束，首先求对应的松弛问题最优解，当某个变量ix不满足整数约束时，寻找
一个
约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题
的可行域，最后逼近整数问题
的最优解。
增加的新约束称为割平面方程或切割方程