文档介绍：运 筹 帷 幄 之 中
决 胜 千 里 之 外
运 筹 学 课 件
整数线性规划
Integer Linear Programming
1
精选ppt
整 数 规 划
整数规划问题与t
注 释
最优解不一定在顶点上达到
最优解不一定是放松问题最优解的邻近整数解
整数可行解远多余于顶点，枚举法不可取
35
精选ppt
分支定界算法
算法思想
算法步骤
算例
注释
36
精选ppt
算 法 思 想
隐枚举法
求解放松问题
最优值比界坏
最优解为整数最优值比界好
最优解为非整
数最优值比界好
分 支
边 界
分 支
舍 弃
37
精选ppt
分支的方法
38
精选ppt
39
精选ppt
40
精选ppt
定 界
当前得到的最好整数解的目标函数值
分支后计算放松的线性规划的最优解
整数解且目标值小于原有最好解的值则替代原有最好解
整数解且目标值大于原有最好解的值则 删除该分支其中无最优解
非整数解且目标值小于原有最好解的值则继续分支
非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解
41
精选ppt
选一分支写出并求解
放松问题，同时从分
支集中删除该分支
判
定是否
为整数
解
初始分支为可行解
集，初始界为无穷大
判
定是否
分支集
空
是停止
当前最好解
为最优解
是
否
42
精选ppt
判定最
优值是否
小于
当前界
判定最
优值是否
小于
当前界
是
否
按非整数变量分
支并加入分支集
否
是
以最优解替代当前最
好解最优值替代当前界
43
精选ppt
算 例
44
精选ppt
45
精选ppt
46
精选ppt
47
精选ppt
注 释
求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。
48
精选ppt
对0-1整数规划分支时
49
精选ppt
分枝问题解可能出现的情况
情况 2, 4, 5 找到最优解
情况 3 在缩减的域上继续分枝定界法
情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4 或 5
50
精选ppt
分枝定界法举例
例4
解：松弛问题的最优解为 x1=, x2=2, OBJ=23
由 x1= 得到两个分枝如下：
51
精选ppt
分枝问题的松弛解
问题II的解即原整数问题的最优解
可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程
当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解
一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题
52
精选ppt
算法思想
算法步骤
算例
割平面算法
53
精选ppt
算 法 思 想
由放松问题的可行域向整数规划的可行域逼近
方法—利用超平面切除
要求
整数解保留
放松问题最优值增加
54
精选ppt
割平面生成方法
条件--保留整数解删除最优解
55
精选ppt
整数可行解
最优基可行解
56
精选ppt
57
精选ppt
58
精选ppt
59
精选ppt
60
精选ppt
61
精选ppt
正则解
62
精选ppt
算 法 步 骤
求放松问题的
最优基可行解
判断是否
为整数解
是停止
得到最优解
否
在单纯性表中加入
一列利用对偶单纯
性算法求最优解
63
精选ppt
算 例
(1,)
64
精选ppt
65
精选ppt
66
精选ppt
67
精选ppt
68
精选ppt
69
精选ppt
70
精选ppt
计 算 软 件
整数变量定义
LinDo
一般整数变量:GIN <Variable>
0-1整数变量: INT <Variable>
LinGo
一般整数变量: ***@GIN( variable_name);
0-1整数变量：***@BIN( variable_name);
算例
71
精选ppt
算 例
max 3 x1+5 x