OR3 1
第六章 整数规划本章要求
理解整数规划的含义
掌握分枝定界法的思想和方法
掌握 0-1变量的含义和用法
掌握指派问题的算法
微机求解
OR3 2
6.1 整数规划问题的提出
决策问题中经常有整数要求，如人数、
件数、机器台数、货物箱数 …… 如何解决？四舍五入不行，枚举法太慢
问题分类,纯整数规划,混合整数规划、
0-1整数规划
专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法
OR3 3
问题举例
某集装箱运输公司，箱型标准体积 24m3，重量
13T,现有两种货物可以装运，甲货物体积 5m3、
重量 2T、每件利润 2000元；乙货物体积 4m3、
重量 5T、每件利润 1000元，如何装运获利最多？
maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数
解此 LP问题，得,X1=4.8,X2=0
显然不是可行解
OR3 4
整数规划图解法
x2
x11 2 3 4 5 6 7
2
3
1 B
A
OR3 5
图解法的启示
A（ 4.8,0）点是 LP问题的可行解，不是 IP问题的可行解,B（ 4,1）才是 IP的最优解
纯整数规划的可行解就是可行域中的整数点
非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化
IP问题的最优解不优于 LP问题的最优解
OR3 6
6.2 分枝定界法
思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解
例 1,maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数解：先不考虑整数要求，解相应的 LP问题，得：
x1=4.8 x2=0 Z=9600 不是可行解
Z=9600是 IP问题的上界，记为,Z=9600
OR3 7
分枝定界法（续）
X1=4.8不符合要求，切掉 4— 5之间的可行域，
可行域变成两块，即原有约束条件再分别附加约束条件 x1 ≤4和 x1 ≥5
原问题分解为两个
maxZ=2000x1+1000x2 maxZ=2000x1+1000x2
5x1+4x2≤24 5x1+4x2≤24
2x1+5x2 ≤13 ( IP1 ) 2x1+5x2 ≤13 (IP2)
x1 ≤4 x1 ≥5
x1.x2 ≥0且为整数 x1.x2 ≥0且为整数
OR3 8
分枝定界法（续）
不考虑整数要求，解相应 LP问题。
解 IP1得,x1=4,x2=1 z=9000
解 IP2得：无可行解此时可以断定 IP问题的下界为 9000，记为 Z=9000
由于目前的分枝末梢最大值是 9000，故
IP问题的上界便是 9000。由于 Z=Z，此时已得 IP问题的最优解，即
x1=4,x2=1,Z=9000
OR3 9
分枝定界法的解题步骤
1、不考虑整数约束，解相应 LP问题
2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步
3、任取一个非整数变量 xi=bi，构造两个新的约束条件,xi ≤[bi],xi ≥ [bi]+1,分别加入到上一个 LP问题，形成两个新的分枝问题。
4、不考虑整数要求，解分枝问题。若整数解的 Z值 >所有分枝末梢的 Z值，则得最优解。否则,取 Z值最大的非整数解，
继续分解,Go to 3 （例题 2讲解）
OR3 10
6.3 0— 1规划问题
某些特殊问题，只做是非选择，故变量设置简化为 0或 1,1代表选择,0代表不选择。
例 4,600万元投资 5个项目，求利润最大的方案？
项目 投资额 项目收益 约束条件
210 160中选 1项
300 210之中选 1项
150 60 选?必先选?
130 80
260 180
OR3 11
求解 0— 1规划的隐枚举法
例 4解：
0 当项目未被选中
1 当项目被选中
max Z=160x1+210x2+60x3+80x4+180x5
210x1+300x2+150x3+130x4+260x5 ≤600?
X1+x2+x3=1?
X3+x4=1?
x5 ≤ x1?
Xj=0或 1 j=1,2,…,5
增加过滤条件,160x1+210x2+60x3+80x4+180x5 ≥ 240?
建模：设 xj=
OR3 12
用隐枚举法解例 4：
(x1,x2,x3,x4,x5） Z值
（ 1,0,0,1,0） 240
（ 1,1,1,1,1）? X
（ 1,1,1,1,0）? X
（ 1,1,1,0,1）? X
（ 1,1,1,0,0）? X
（ 1,1,0,1,1）? X
（ 1,1,0,1,0）? X
（ 1,1,0,0,1）? X
（ 1,1,0,0,0） X
（ 1,0,1,1,1）? X
（ 1,0,1,1,0） X
（ 1,0,0,1,1） 420
………,.
OR3 13
6.4 指派问题
例 8 甲乙丙丁四个人,A,B,D四项任务，不同的人做不同的工作效率不同，
如何指派不同的人去做不同的工作使效率最高？
任务人 时间 A B C D
甲乙丙丁
4 10 7 5
2 7 6 3
3 3 4 4
4 6 6 3
数模,
minZ=ΣΣcijxij
Σxij=1 i=1,…,n
Σxij=1 j=1,…,n
Xij=0或 1
OR3 14
指派问题解法 — 匈牙利法
解：类似运输问题的最小元素法
第一步 造 0—— 各行各列减其最小元素
4 10 7 5 -4 0 6 3 1? 6 2 1?
Cij= 2 7 6 3 -2? 0 5 4 1? 0 5 3 1?
3 3 4 4 -3 0 0 1 1 0? 0 1
4 6 6 3 -3 1 3 3 0 1 3 2?
-1?
第二步 圈 0—— 寻找不同行不同列的 0元素，
圈之。 所在行和列其它 0元素划掉
第三步 打?—— 无?的行打?，打?行上 0列打
,打?列上?行打?，打?行上 0列打? …
OR3 15
指派问题解法 — 匈牙利法（续）
第四步 划线 —— 无?行、打?列划线
第五步 造 0—— 直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的 0元素,Go to 2
0 6 2 1 -1? 5 1 0? 0 4? 0
Cij= 0 5 3 1 -1? 0 4 2 0 3 1 0
0 0 0 1 1? 0 1 2? 0 2
1 3 2 0 2 3 2 2 2 1?
+1
最优解,x13=1,x21=1,x32=1,x44=1 Z=15
OR3 16
相关问题：
非标准型的转化
（ 1） maxZ= ΣΣcijxij?minZ’= ΣΣ(-cij)xij
minZ’’= ΣΣ(M-cij)xij= ΣΣbijxij
M是足够大的常数,新问题的最优解就是原问题的最优解
（ 2）整数规划的计算机求解
OR3 17
整数规划习题课
P222—— 6.11
A B C B D
1 1
2 1
3 1
4 1
5 1
第六章 整数规划本章要求
理解整数规划的含义
掌握分枝定界法的思想和方法
掌握 0-1变量的含义和用法
掌握指派问题的算法
微机求解
OR3 2
6.1 整数规划问题的提出
决策问题中经常有整数要求，如人数、
件数、机器台数、货物箱数 …… 如何解决？四舍五入不行，枚举法太慢
问题分类,纯整数规划,混合整数规划、
0-1整数规划
专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法
OR3 3
问题举例
某集装箱运输公司，箱型标准体积 24m3，重量
13T,现有两种货物可以装运，甲货物体积 5m3、
重量 2T、每件利润 2000元；乙货物体积 4m3、
重量 5T、每件利润 1000元，如何装运获利最多？
maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数
解此 LP问题，得,X1=4.8,X2=0
显然不是可行解
OR3 4
整数规划图解法
x2
x11 2 3 4 5 6 7
2
3
1 B
A
OR3 5
图解法的启示
A（ 4.8,0）点是 LP问题的可行解，不是 IP问题的可行解,B（ 4,1）才是 IP的最优解
纯整数规划的可行解就是可行域中的整数点
非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化
IP问题的最优解不优于 LP问题的最优解
OR3 6
6.2 分枝定界法
思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解
例 1,maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数解：先不考虑整数要求，解相应的 LP问题，得：
x1=4.8 x2=0 Z=9600 不是可行解
Z=9600是 IP问题的上界，记为,Z=9600
OR3 7
分枝定界法（续）
X1=4.8不符合要求，切掉 4— 5之间的可行域，
可行域变成两块，即原有约束条件再分别附加约束条件 x1 ≤4和 x1 ≥5
原问题分解为两个
maxZ=2000x1+1000x2 maxZ=2000x1+1000x2
5x1+4x2≤24 5x1+4x2≤24
2x1+5x2 ≤13 ( IP1 ) 2x1+5x2 ≤13 (IP2)
x1 ≤4 x1 ≥5
x1.x2 ≥0且为整数 x1.x2 ≥0且为整数
OR3 8
分枝定界法（续）
不考虑整数要求，解相应 LP问题。
解 IP1得,x1=4,x2=1 z=9000
解 IP2得：无可行解此时可以断定 IP问题的下界为 9000，记为 Z=9000
由于目前的分枝末梢最大值是 9000，故
IP问题的上界便是 9000。由于 Z=Z，此时已得 IP问题的最优解，即
x1=4,x2=1,Z=9000
OR3 9
分枝定界法的解题步骤
1、不考虑整数约束，解相应 LP问题
2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步
3、任取一个非整数变量 xi=bi，构造两个新的约束条件,xi ≤[bi],xi ≥ [bi]+1,分别加入到上一个 LP问题，形成两个新的分枝问题。
4、不考虑整数要求，解分枝问题。若整数解的 Z值 >所有分枝末梢的 Z值，则得最优解。否则,取 Z值最大的非整数解，
继续分解,Go to 3 （例题 2讲解）
OR3 10
6.3 0— 1规划问题
某些特殊问题，只做是非选择，故变量设置简化为 0或 1,1代表选择,0代表不选择。
例 4,600万元投资 5个项目，求利润最大的方案？
项目 投资额 项目收益 约束条件
210 160中选 1项
300 210之中选 1项
150 60 选?必先选?
130 80
260 180
OR3 11
求解 0— 1规划的隐枚举法
例 4解：
0 当项目未被选中
1 当项目被选中
max Z=160x1+210x2+60x3+80x4+180x5
210x1+300x2+150x3+130x4+260x5 ≤600?
X1+x2+x3=1?
X3+x4=1?
x5 ≤ x1?
Xj=0或 1 j=1,2,…,5
增加过滤条件,160x1+210x2+60x3+80x4+180x5 ≥ 240?
建模：设 xj=
OR3 12
用隐枚举法解例 4：
(x1,x2,x3,x4,x5） Z值
（ 1,0,0,1,0） 240
（ 1,1,1,1,1）? X
（ 1,1,1,1,0）? X
（ 1,1,1,0,1）? X
（ 1,1,1,0,0）? X
（ 1,1,0,1,1）? X
（ 1,1,0,1,0）? X
（ 1,1,0,0,1）? X
（ 1,1,0,0,0） X
（ 1,0,1,1,1）? X
（ 1,0,1,1,0） X
（ 1,0,0,1,1） 420
………,.
OR3 13
6.4 指派问题
例 8 甲乙丙丁四个人,A,B,D四项任务，不同的人做不同的工作效率不同，
如何指派不同的人去做不同的工作使效率最高？
任务人 时间 A B C D
甲乙丙丁
4 10 7 5
2 7 6 3
3 3 4 4
4 6 6 3
数模,
minZ=ΣΣcijxij
Σxij=1 i=1,…,n
Σxij=1 j=1,…,n
Xij=0或 1
OR3 14
指派问题解法 — 匈牙利法
解：类似运输问题的最小元素法
第一步 造 0—— 各行各列减其最小元素
4 10 7 5 -4 0 6 3 1? 6 2 1?
Cij= 2 7 6 3 -2? 0 5 4 1? 0 5 3 1?
3 3 4 4 -3 0 0 1 1 0? 0 1
4 6 6 3 -3 1 3 3 0 1 3 2?
-1?
第二步 圈 0—— 寻找不同行不同列的 0元素，
圈之。 所在行和列其它 0元素划掉
第三步 打?—— 无?的行打?，打?行上 0列打
,打?列上?行打?，打?行上 0列打? …
OR3 15
指派问题解法 — 匈牙利法（续）
第四步 划线 —— 无?行、打?列划线
第五步 造 0—— 直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的 0元素,Go to 2
0 6 2 1 -1? 5 1 0? 0 4? 0
Cij= 0 5 3 1 -1? 0 4 2 0 3 1 0
0 0 0 1 1? 0 1 2? 0 2
1 3 2 0 2 3 2 2 2 1?
+1
最优解,x13=1,x21=1,x32=1,x44=1 Z=15
OR3 16
相关问题：
非标准型的转化
（ 1） maxZ= ΣΣcijxij?minZ’= ΣΣ(-cij)xij
minZ’’= ΣΣ(M-cij)xij= ΣΣbijxij
M是足够大的常数,新问题的最优解就是原问题的最优解
（ 2）整数规划的计算机求解
OR3 17
整数规划习题课
P222—— 6.11
A B C B D
1 1
2 1
3 1
4 1
5 1
