第四章 整数规划
整数规划的难度远大于一般线性规划
?管理与人文学院 忻展红
1999,4
2
4.1 整数规划简介
? 要求所有 xj 的解为整数，称为纯整数规划
? 要求部分 xj 的解为整数，称为混合整数规划
? 对应没有整数解要求的线性规划称之为松弛问题
? 整数规划的解是可数个的，最优解不一定发生在极点
? 整数规划的最优解不会优于其松弛问题的最优解
?
?
?
?
?
??
????
?
?
?
?
?
njx
mibxa
ts
xcxf
j
n
j
ijij
n
j
jj
,,2,1,0
,,2,1,),(
..
)(m a x ( m i n )
1
1
?
?
且为整数
3
4.2 整数规划的分枝定界法
4.2.1 思路与解题步骤
? 只解松弛问题
1、在全部可行性域上解松弛问题
– 若松弛问题最优解为整数解，则其也是整数规划的
最优解
2,分枝过程
– 若松弛问题最优解中某个 xk=bk 不是整数，令 ? bk ?
为 bk 的整数部分
– 构造两个新的约束条件 xk?? bk ? 和 xk?? bk ?+1，分
别加于原松弛问题，形成两个新的整数规划
3、求解分枝的松弛问题 — 定界过程
– 设两个分枝的松弛问题分别为问题 1 和问题 2,它
们的最优解有如下情况
4
表 4.2.1 分枝问题解可能出现的情况
序号 问题 1 问题 2 说 明
1 无可行解 无可行解 整数规划无可行解
2 无可行解 整数解 此整数解即最优解
3 无可行解 非整数解 对问题 2 继续分枝
4 整数解 整数解 较优的一个为最优解
5 整数解，目标函
数优于问题 2
非整数解 问题 1 的解即最优解
6 整数解 非整数解，目标
函数优于问题 1
问题 1 停止分枝 ( 剪
枝 ),其整数解为界，
对问题 2 继续分枝
情况 2,4,5 找到最优解
情况 3 在缩减的域上继续分枝定界法
情况 6 问题 1 的整数解作为 界 被保留，用于以后与问题 2 的后
续分枝所得到的解进行比较，结论如情况 4 或 5
5
4.2.2 分枝定界法举例
例 4.1.1
?
?
?
?
?
?
??
??
??
且为整数 0,
7 2
1342
46)(m a x
21
21
21
21
xx
xx
xx
xxxf
解,松弛问题的最优解为 x1=2.5,x2=2,OBJ=23
由 x1=2.5 得到两个分枝如下：
?
?
?
??
?
?
?
?
??
??
??
且为整数
问题
0,
2
7 2
1342
I
46)(m a x
21
1
21
21
21
xx
x
xx
xx
xxxf
?
?
?
??
?
?
?
?
??
??
??
且为整数
问题
0,
3
7 2
1342
II
46)(m a x
21
1
21
21
21
xx
x
xx
xx
xxxf
6
表 4.2.3 分枝问题的松弛解
问题 I 问题 II
x 1 2 3
x 2 9 / 4 1
f ( x ) 21 22
问题 II的解即原整数问题的最优解
可能存在两个分枝都是非整数解的情况，则需要两边同时
继续分枝，直到有整数解出现，就可以进行定界过程
当存在很多变量有整数约束时，分枝即广又深，在最坏情
况下相当于组合所有可能的整数解
一般整数规划问题属于一类未解决的难题,NP-complete，
只有少数特殊问题有好的算法，如 任务分配问题, 匹配问题
7
4.6 任务分配问题
例 4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他
们完成。若规定每人必须完成且只完成一项任务，而每人
完成每项任务的工时耗费如表 4.6.1，问如何分配任务使完
成四项任务的总工时耗费最少？
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
1,0
,,2,1 1
,,2,1 1
)(m i n
1
1
1 1
ij
m
i
ij
m
j
ij
m
i
m
j
ijij
x
mjx
mix
xaxf
?
?
任务
工时 A B C D 人员
人员
甲 10 9 7 8 1
乙 5 8 7 7 1
丙 5 4 6 5 1
丁 2 3 4 5 1
任务 1 1 1 1
8
任务分配问题的数学模型
模型中,xij 为第 i 个工人分配去做第 j 项任务；
aij 为第 i 个工人为完成第 j 项任务时的工时消耗；
{aij}m?m 称为 效率矩阵
?
?
?
?
?
?
?
mji
ji
ji
x ij
,,2,1,
0
1
?
项任务个工人未分配去做第当第
项任务个工人分配去做第当第
? 运输问题是任务分配问题的松弛问题
? 任务分配问题不但是整数规划，而且是 0?1规划
? 任务分配问题有 2m个约束条件，但有且只有 m个非零解
，是自然 高度退化 的
? 任务分配是 两部图 的 匹配问题,有著名的 匈牙利算法
下面介绍一种适合手算的算法 (出自清华教科书 )
9
4.6.1 清华算法
定理 1 如果从效率矩阵 {aij}m?m中每行元素分别减去一个常数 ui，
从每列元素分别减去一个常数 vj, 所得新的效率矩阵 {bij}m?m
的任务分配问题的最优解等价于原问题的最优解。
证明：略
定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方
阵内所有零元素的最少直线数等于位于不同行、不同列的零
元素的最多个数。
证明：略
清华算法的 基本思路,
? 根据 定理 1 变换效率矩阵，使矩阵中有足够多的零。若
矩阵中存在 m 个不同行不同列的零，就找到了最优解
? 若覆盖变换后的效率矩阵零元素的直线少于 m 条，就尚
未找到最优解，设法进一步变换矩阵，增加新的零
10
清华算法的步骤：例 4.6.1
第一步,变换效率矩阵，使每行每列至少有一个零
– 行变换,找出每行最小元素，从该行各元素中减去之
– 列变换,找出每列最小元素，从该列各元素中减去之
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2210
0201
1230
0023
3210
1201
2230
)1(023
543)2(
56)4(5
778)5(
8)7(910
换
变
列
换
变
行
第二步,检查覆盖所有零元素的直线是否为 m条
划线规则
1、逐行检查,若该行只有一个未标记的零，对其加 ( )标记，将
( )标记元素同行同列上其它的零打上 *标记。若该行有二个以上
未标记的零，暂不标记，转下一行检查，直到所有行检查完；
11
清华算法的步骤：例 4.6.1
2、逐列检查,若该列只有一个未标记的零，对其加 ( )标记，将 ( )标
记元素同行同列上其它的零打上 *标记。若该列有二个以上未标记的
零，暂不标记，转下一列检查，直到所有列检查完；
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
221*0
0201
123)0(
0023
查
检
列
逐
查
检
行
逐
3、重复 1,2后，可能出现三种情况：
a,每行都有一个 (0)，显然已找到最优解，令对应 (0)位置的 xij=1；
b,仍有零元素未标记，此时，一定存在某些行和列同时有多个零，
称为 僵局状态,因为无法采用 1,2 中的方法继续标记。
4,打破僵局 。令未标记零对应的同行同列上其它未标记零的个数为
该零的 指数,选 指数最小 的先标记 ( )；采用这种方法直至所有零都
被标记，或出现 情况 a，或 情况 c 。
12
清华算法的步骤：例 4.6.1
c,所有零都已标记,但标有 ( )的零的个数少于 m；
开始 划线过程,
?对没有标记 ( ) 的行打 ?
?对打 ?行上所有其它零元素对应的列打 ?
?再对打 ?列上有 ( ) 标记的零元素对应的行打 ?
?重复 ???，直至无法继续
?对没有打 ?的行划 横线,对所有 打 ?的列划 垂线
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
?
?
划线后会出现两种情况：
(1) 标记 ( )的零少于 m个，但划有 m
条直线，说明矩阵中已存在 m 个不
同行不同列的零，但打破僵局时选
择不合理，没能找到。回到 b 重新
标记；
(2) 少于 m条直线，到 第三步 ；
13
清华算法的步骤：例 4.6.1
第三步,进一步变换 ；
?在未划线的元素中找 最小者,设为 ?
?对未被直线覆盖的各元素减去 ?
?对两条直线交叉点覆盖的元素加上 ?
?只有一条直线覆盖的元素保持不变
以上步骤实际上仍是利用 定理 1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0202
0120
0024
1?
第四步,抹除所有标记，回到 第二步,重新标记 ；
14
解
优
最
列
逐
行
逐
记
标
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
11)0(*0
)0(2*02
*012)0(
*0)0(24
清华算法的步骤：例 4.6.1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0202
0120
0024
1?
答：最优分配方案为 x13= x21= x34 = x42 =1，其余为 0，
即甲 ?C，乙 ?A，丙 ?D，丁 ?B,OBJ=20
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0202
0120
*0)0(24
记
标
列
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
110*0
0202
*012)0(
*0)0(24
局
僵
破
打 ??
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
15
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6 0 2 0
5 0 4 0
0 3 0 1
0 2 0 0
局
僵
破
打
4.6.2 关于清华算法的适用条件
? 要求所有 aij ?0
– 若某些 aij <0,则利用定理 1 进行变换，使所有 bij ? 0
? 目标函数为 min型
– 对于 max型目标函数，将效率矩阵中所有 aij 反号，则等
效于求 min型问题；再利用定理 1 进行变换，使所有 bij
? 0，则可采用清华算法
打破僵局时选择不当的结果：
?
? ?
?
?
?
?
?
结果仅出现 3 个标记
( )，但却划出 4 条线，
说明什么？！ ??
?
?
?
?
?
6 0 2 *0
5 0 4 *0
0 3 0 1
*0 2 *0 )0(
局
僵
破
打
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6 *0 2 *0
5 )0( 4 *0
0 3 0 1
*0 2 *0 )0(
局
僵
破
打
?
?
?
?
?
?
?
6 *0 2
5 )0( 4
*0 3 )0(
*0 2 *0
局
僵
破
打
16
线性规划有关的英文词汇
? Operational/operations research 运筹学
? Linear programming 线性规划 Feasible domain 可行域
? Convex set 凸集 Basic feasible solutions 基础可行解
? Simplex algorithm 单纯型法 Pivot 主元 Pivoting 主元变换
? Revised,dual simplex algorithm 修正、对偶单纯型法
? Relative cost 相对成本 (机会成本 ) Shadow price 影子价格
? Slack,Surplus,Artificial variable 松弛，剩余，人工变量
? Unbounded,Infeasible,Degenerate solution 无界解,无可行解,退化解
? Duality 对偶性 Primal,dual problem 原问题，对偶问题
? Complementary slackness 互补松弛 Sensitivity analysis 灵敏度分析
? Ttransportation problem 运输问题
? Assignment problem 任务分配 (指派 ) 问题
? Bipartite matching 两部图匹配 Hungarian method 匈牙利算法
整数规划的难度远大于一般线性规划
?管理与人文学院 忻展红
1999,4
2
4.1 整数规划简介
? 要求所有 xj 的解为整数，称为纯整数规划
? 要求部分 xj 的解为整数，称为混合整数规划
? 对应没有整数解要求的线性规划称之为松弛问题
? 整数规划的解是可数个的，最优解不一定发生在极点
? 整数规划的最优解不会优于其松弛问题的最优解
?
?
?
?
?
??
????
?
?
?
?
?
njx
mibxa
ts
xcxf
j
n
j
ijij
n
j
jj
,,2,1,0
,,2,1,),(
..
)(m a x ( m i n )
1
1
?
?
且为整数
3
4.2 整数规划的分枝定界法
4.2.1 思路与解题步骤
? 只解松弛问题
1、在全部可行性域上解松弛问题
– 若松弛问题最优解为整数解，则其也是整数规划的
最优解
2,分枝过程
– 若松弛问题最优解中某个 xk=bk 不是整数，令 ? bk ?
为 bk 的整数部分
– 构造两个新的约束条件 xk?? bk ? 和 xk?? bk ?+1，分
别加于原松弛问题，形成两个新的整数规划
3、求解分枝的松弛问题 — 定界过程
– 设两个分枝的松弛问题分别为问题 1 和问题 2,它
们的最优解有如下情况
4
表 4.2.1 分枝问题解可能出现的情况
序号 问题 1 问题 2 说 明
1 无可行解 无可行解 整数规划无可行解
2 无可行解 整数解 此整数解即最优解
3 无可行解 非整数解 对问题 2 继续分枝
4 整数解 整数解 较优的一个为最优解
5 整数解，目标函
数优于问题 2
非整数解 问题 1 的解即最优解
6 整数解 非整数解，目标
函数优于问题 1
问题 1 停止分枝 ( 剪
枝 ),其整数解为界，
对问题 2 继续分枝
情况 2,4,5 找到最优解
情况 3 在缩减的域上继续分枝定界法
情况 6 问题 1 的整数解作为 界 被保留，用于以后与问题 2 的后
续分枝所得到的解进行比较，结论如情况 4 或 5
5
4.2.2 分枝定界法举例
例 4.1.1
?
?
?
?
?
?
??
??
??
且为整数 0,
7 2
1342
46)(m a x
21
21
21
21
xx
xx
xx
xxxf
解,松弛问题的最优解为 x1=2.5,x2=2,OBJ=23
由 x1=2.5 得到两个分枝如下：
?
?
?
??
?
?
?
?
??
??
??
且为整数
问题
0,
2
7 2
1342
I
46)(m a x
21
1
21
21
21
xx
x
xx
xx
xxxf
?
?
?
??
?
?
?
?
??
??
??
且为整数
问题
0,
3
7 2
1342
II
46)(m a x
21
1
21
21
21
xx
x
xx
xx
xxxf
6
表 4.2.3 分枝问题的松弛解
问题 I 问题 II
x 1 2 3
x 2 9 / 4 1
f ( x ) 21 22
问题 II的解即原整数问题的最优解
可能存在两个分枝都是非整数解的情况，则需要两边同时
继续分枝，直到有整数解出现，就可以进行定界过程
当存在很多变量有整数约束时，分枝即广又深，在最坏情
况下相当于组合所有可能的整数解
一般整数规划问题属于一类未解决的难题,NP-complete，
只有少数特殊问题有好的算法，如 任务分配问题, 匹配问题
7
4.6 任务分配问题
例 4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他
们完成。若规定每人必须完成且只完成一项任务，而每人
完成每项任务的工时耗费如表 4.6.1，问如何分配任务使完
成四项任务的总工时耗费最少？
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
1,0
,,2,1 1
,,2,1 1
)(m i n
1
1
1 1
ij
m
i
ij
m
j
ij
m
i
m
j
ijij
x
mjx
mix
xaxf
?
?
任务
工时 A B C D 人员
人员
甲 10 9 7 8 1
乙 5 8 7 7 1
丙 5 4 6 5 1
丁 2 3 4 5 1
任务 1 1 1 1
8
任务分配问题的数学模型
模型中,xij 为第 i 个工人分配去做第 j 项任务；
aij 为第 i 个工人为完成第 j 项任务时的工时消耗；
{aij}m?m 称为 效率矩阵
?
?
?
?
?
?
?
mji
ji
ji
x ij
,,2,1,
0
1
?
项任务个工人未分配去做第当第
项任务个工人分配去做第当第
? 运输问题是任务分配问题的松弛问题
? 任务分配问题不但是整数规划，而且是 0?1规划
? 任务分配问题有 2m个约束条件，但有且只有 m个非零解
，是自然 高度退化 的
? 任务分配是 两部图 的 匹配问题,有著名的 匈牙利算法
下面介绍一种适合手算的算法 (出自清华教科书 )
9
4.6.1 清华算法
定理 1 如果从效率矩阵 {aij}m?m中每行元素分别减去一个常数 ui，
从每列元素分别减去一个常数 vj, 所得新的效率矩阵 {bij}m?m
的任务分配问题的最优解等价于原问题的最优解。
证明：略
定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方
阵内所有零元素的最少直线数等于位于不同行、不同列的零
元素的最多个数。
证明：略
清华算法的 基本思路,
? 根据 定理 1 变换效率矩阵，使矩阵中有足够多的零。若
矩阵中存在 m 个不同行不同列的零，就找到了最优解
? 若覆盖变换后的效率矩阵零元素的直线少于 m 条，就尚
未找到最优解，设法进一步变换矩阵，增加新的零
10
清华算法的步骤：例 4.6.1
第一步,变换效率矩阵，使每行每列至少有一个零
– 行变换,找出每行最小元素，从该行各元素中减去之
– 列变换,找出每列最小元素，从该列各元素中减去之
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2210
0201
1230
0023
3210
1201
2230
)1(023
543)2(
56)4(5
778)5(
8)7(910
换
变
列
换
变
行
第二步,检查覆盖所有零元素的直线是否为 m条
划线规则
1、逐行检查,若该行只有一个未标记的零，对其加 ( )标记，将
( )标记元素同行同列上其它的零打上 *标记。若该行有二个以上
未标记的零，暂不标记，转下一行检查，直到所有行检查完；
11
清华算法的步骤：例 4.6.1
2、逐列检查,若该列只有一个未标记的零，对其加 ( )标记，将 ( )标
记元素同行同列上其它的零打上 *标记。若该列有二个以上未标记的
零，暂不标记，转下一列检查，直到所有列检查完；
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
221*0
0201
123)0(
0023
查
检
列
逐
查
检
行
逐
3、重复 1,2后，可能出现三种情况：
a,每行都有一个 (0)，显然已找到最优解，令对应 (0)位置的 xij=1；
b,仍有零元素未标记，此时，一定存在某些行和列同时有多个零，
称为 僵局状态,因为无法采用 1,2 中的方法继续标记。
4,打破僵局 。令未标记零对应的同行同列上其它未标记零的个数为
该零的 指数,选 指数最小 的先标记 ( )；采用这种方法直至所有零都
被标记，或出现 情况 a，或 情况 c 。
12
清华算法的步骤：例 4.6.1
c,所有零都已标记,但标有 ( )的零的个数少于 m；
开始 划线过程,
?对没有标记 ( ) 的行打 ?
?对打 ?行上所有其它零元素对应的列打 ?
?再对打 ?列上有 ( ) 标记的零元素对应的行打 ?
?重复 ???，直至无法继续
?对没有打 ?的行划 横线,对所有 打 ?的列划 垂线
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
?
?
划线后会出现两种情况：
(1) 标记 ( )的零少于 m个，但划有 m
条直线，说明矩阵中已存在 m 个不
同行不同列的零，但打破僵局时选
择不合理，没能找到。回到 b 重新
标记；
(2) 少于 m条直线，到 第三步 ；
13
清华算法的步骤：例 4.6.1
第三步,进一步变换 ；
?在未划线的元素中找 最小者,设为 ?
?对未被直线覆盖的各元素减去 ?
?对两条直线交叉点覆盖的元素加上 ?
?只有一条直线覆盖的元素保持不变
以上步骤实际上仍是利用 定理 1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0202
0120
0024
1?
第四步,抹除所有标记，回到 第二步,重新标记 ；
14
解
优
最
列
逐
行
逐
记
标
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
11)0(*0
)0(2*02
*012)0(
*0)0(24
清华算法的步骤：例 4.6.1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0202
0120
0024
1?
答：最优分配方案为 x13= x21= x34 = x42 =1，其余为 0，
即甲 ?C，乙 ?A，丙 ?D，丁 ?B,OBJ=20
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0202
0120
*0)0(24
记
标
列
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
110*0
0202
*012)0(
*0)0(24
局
僵
破
打 ??
?
?
?
?
?
?
?
?
?
?
?
?
221*0
*02)0(1
123)0(
*0)0(23
15
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6 0 2 0
5 0 4 0
0 3 0 1
0 2 0 0
局
僵
破
打
4.6.2 关于清华算法的适用条件
? 要求所有 aij ?0
– 若某些 aij <0,则利用定理 1 进行变换，使所有 bij ? 0
? 目标函数为 min型
– 对于 max型目标函数，将效率矩阵中所有 aij 反号，则等
效于求 min型问题；再利用定理 1 进行变换，使所有 bij
? 0，则可采用清华算法
打破僵局时选择不当的结果：
?
? ?
?
?
?
?
?
结果仅出现 3 个标记
( )，但却划出 4 条线，
说明什么？！ ??
?
?
?
?
?
6 0 2 *0
5 0 4 *0
0 3 0 1
*0 2 *0 )0(
局
僵
破
打
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6 *0 2 *0
5 )0( 4 *0
0 3 0 1
*0 2 *0 )0(
局
僵
破
打
?
?
?
?
?
?
?
6 *0 2
5 )0( 4
*0 3 )0(
*0 2 *0
局
僵
破
打
16
线性规划有关的英文词汇
? Operational/operations research 运筹学
? Linear programming 线性规划 Feasible domain 可行域
? Convex set 凸集 Basic feasible solutions 基础可行解
? Simplex algorithm 单纯型法 Pivot 主元 Pivoting 主元变换
? Revised,dual simplex algorithm 修正、对偶单纯型法
? Relative cost 相对成本 (机会成本 ) Shadow price 影子价格
? Slack,Surplus,Artificial variable 松弛，剩余，人工变量
? Unbounded,Infeasible,Degenerate solution 无界解,无可行解,退化解
? Duality 对偶性 Primal,dual problem 原问题，对偶问题
? Complementary slackness 互补松弛 Sensitivity analysis 灵敏度分析
? Ttransportation problem 运输问题
? Assignment problem 任务分配 (指派 ) 问题
? Bipartite matching 两部图匹配 Hungarian method 匈牙利算法
