第四章 整数规划与分配问题
§ 1．整数规划的特点及作用
§ 2．分配问题与匈牙利法
§ 3．分枝定界法
§ 4．割平面法
§ 5．应用举例
§ 1．整数规划的特点及应用
在实际问题中，全部或部分变量的取值必须是整数。
比如人或机器是不可分割的，选择建厂地点可以设置逻辑
变量等。
在一个线性规划问题中要求全部变量取整数值的，称
纯整数线性规划或简称 纯整数规划 ；只要求一部分变量
取整数值的，称为 混合整数规划 。
对整数规划问题求解，有人认为可以不考虑对变量的
整数约束，作为一般线性规划问题求解，当解为非整数时，
用四舍五入或凑整方法寻找最优解，我们从下面的例子说
明这样的方法是不合适的。
例 1,求下述整数规划问题的最优解
?
?
?
?
?
?
??
??
??
且均取整数值,0,
5.45.0
143 2
23m a x
21
21
21
21
xx
xx
xx
xxz
解,如果不考虑整数约束（称为整数规划问题的 松弛
问题 ）用图解法得最优解为（ 3.25,2.5）
考虑到整数约束，用凑整法求解
时，比较四个点（ 4,3）,（ 4,2）,
（ 3,3）（ 3,2），前三个都不是可行
解，第四个虽然是可行解，但 z=13 不
是最优。实际问题的最优解为（ 4,1）
这时 z*= 14。
逻辑 （ 0-1） 变量在建立数学模型中的作用
1,m 个约束条件中只有 k 个起作用
设 m 个约束条件可以表示为,
),,1(
1
mibxa i
n
j
jij ????
?
定义逻辑变量
?
?
??
个约束条件起作用，假定第
个约束条件不起作用，假定第
0
1
i
iy
i
又设 M 为任意大的正数，则约束条件可以改写为,
?
?
?
?
?
?????
???
?
kmyyy
Mybxa
m
ii
n
j
jij
?
21
1
定义逻辑变量,
?
?
?
?
，其它
，假定约束右端项为
0
1 i
i
b
y
此时约束条件可以改写为,
?
?
?
?
?
????
? ??
??
121
11
r
r
i
ii
n
j
jij
yyy
ybxa
?
2,约束条件的右端项可能是 r 个值中的某一个
r
n
j
jij bbbxa 或或或 ?21
1
??
?
即
3,两组条件满足其中一组
若 x1≤4，则 x2≥1（ 第一组条件 ）；否则当 x1>4 时，
x2≤3（ 第二组条件 ）,
定义逻辑变量,
）（
组条件起作用，第
组条件不起作用，第
2,1
0
1
?
?
?
?
? i
i
i
y i
又设 M 为任意大正数，则问题可表达为,
?
?
?
?
?
?
?
?
?
??
??
??
??
??
1
3
4
1
4
21
22
21
12
11
yy
Myx
Myx
Myx
Myx
需注意，当约束
为大于时，右端
项中用减号。
4,用以表示含固定费用的函数
用 xj 代表产品 j 的生产数量，其生产费用函数表示为
??
?
?
?
?
??
?
)0( 0
)0(
)(
j
jjjj
jj x
xxcK
xC
其中 Kj 是同产量无关的生产准备费用，问题的目标是使
所有产品的总生产费用为最小，即
?
?
?
n
j
jj xCz
1
)(m a x
定义逻辑变量（表示是否生产产品 j ）
??
?
?
?
?
?
?
00
01
j
j
j x
x
y
，
，
又设 M 为任意大正数，为了表示上述定义，引入约束,
jj Myx ?
显然，当 xj> 0 时,yj=1。
将目标函数与约束条件合起来考虑有,
? ?
??
?
?
?
?
??
?? ?
?
1 0
0
m i n
1
或
j
jj
n
j
jjjj
y
Myx
yKxcz
由此看出，当 xj = 0 时，为使 z 极小化，应有 yj = 0
习题 4.2
§ 2．分配问题与匈牙利法
一、问题的提出与数学模型
分配问题 也称 指派问题 （ assignment problem），
是一种特殊的整数规划问题。假定有 m 项任务分配给 m
个人去完成，并指定每人完成其中一项，每项只交给其中
一个人去完成，应如何分配使总的效率为最高。
如果完成任务的效率表现为资源消耗，考虑的是如何
分配任务使得目标极小化；如果完成任务的效率表现为生
产效率的高低，则考虑的是如何分配使得目标函数极大化。
在分配问题中，利用不同资源完成不同计划活动的效
率通常用表格形式表示为效率表，表格中数字组成 效率
矩阵 。
例 2,有一份说明书，要分别翻译成英、日、德、俄
四种文字，交甲、乙、丙、丁四个人去完成。因各人专长
不同，使这四个人分别完成四项任务总的时间为最小。效
率表如下,
效率矩阵用 [aij] 表示，为
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
913154
11161413
814415
79102
][
ij
a
定义逻辑变量
）；（
项任务个人去完成第，不分配第
项任务个人去完成第，分配第
mjmi
ji
ji
x ij
,,1,,1
0
1
?? ??
?
?
?
?
则分配问题的数学模型写为,
?
?
?
?
?
?
?
?
?
?
?
???
??
??
?
?
?
? ?
?
?
? ?
),,1;,,1( 1 0
),,1( 1
),,1( 1
m i n
1
1
1 1
mjmix
mjx
mix
xaz
ij
m
i
ij
m
j
ij
m
i
m
j
ijij
??
?
?
或
二、匈牙利法
用表上作业法来求解分配问题时，单位运价表即效率
表，产销平衡表中产量和销量都设为 1 即可。
匈牙利数学家克尼格（ Konig ）求解分配问题的计算
方法被成为 匈牙利法,他证明了如下两个定理,
定理 1 如果从分配问题效率矩阵 [aij] 的每一行元素中
分别减去（或加上）一个常数 ui (被称为该行的位势 )，从
每一列分别减去（或加上）一个常数 vj（被称为该列的位
势），得到一个新的效率矩阵 [bij]，若其中 bij = aij-ui-vj，
则 [bij] 的最优解等价于 [aij] 的最优解。
定理 2 若矩阵 A 的元素可分成,0,与非,0,两部
分，则覆盖,0,元素的最少直线数等于位于不同行不同
列的,0,元素的最大个数。
结合例 2 说明 匈牙利法的计算步骤
第一步：找出效率矩阵每行的最小元素，并分别
从每行中减去。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
59110
0532
410011
5780
4
11
4
2
913154
11161413
814415
79102
m i n
第二步：找出矩阵每列的最小元素，分别从各列中减
去。
0 5 0 0 m i n
54110
0032
45011
5280
59110
0532
410011
5780
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
第三步：经过上述两步变换后，矩阵的每行每列至少
都有了一个零元素。下面确定能否找出 m 个位于不同行
不同列的零元素的集合（该例中 m=4），也就是看要覆
盖上面矩阵中的所有零元素，至少需要多少条直线。
1,从第一行开始，若该行只有一个零元素，就对这
个零元素打上（ ），对打括号的零元素所在的列画一条
线，若该行没有零元素或者有两个以上零元素（已划去的
不算在内），则转下一行，依次进行到最后一行。
2,从第一列开始，若该列只有一个零元素，就对这个
零元素打上（ ）（同样不考虑已划去的零元素），再对
打括号的零元素所在行画一条直线。若该列没有零元素或
有两个以上零元素，则转下一列，依次进行到最后一列为
止。
3,重复上述步骤 1,2，可能出现三种情况,
① 效率矩阵每行都有打括号的零元素，只要对应这些
元素令 xij= 1 就找到了最优解。
② 打括号的零元素个数少于 m,但未被划去的零元
素之间存在闭回路，这时顺着闭回路的走向，对每个间隔
的零元素打一个括号，然后对所有打括号的零元素所在行
（或列）画一条直线，同样得到最优解。
③ 矩阵中所有零元素或被划去，或打上括号，但打括
号的零元素少于 m,这时转入第四步。
第四步：按定理 1 进行如下变换
1,从矩阵未被直线覆盖的数字中找出一个最小的 k ；
2,对矩阵中的每行，当该行有直线覆盖时，令 ui= 0，
无直线覆盖的，令 ui= k ；
3,对矩阵中有直线覆盖的列，令 vj= -k，对无直线覆
盖的列，令 vj= 0 ；
4,从原矩阵的每个元素 aij中分别减去 ui 和 vj 。
第五步：回到第三步，反复进行，直到矩阵的每一行
都有一个打括号的零元素为止，即找到最优分配方案。
由于调整后的矩阵中新出现了一个零，因此对打括号
的元素重新进行调整，得到如下矩阵，这时只要把打括号
元素所对应的决策变量取值为 1，就得到最优解。
该问题中，最优值为,4+4+9+11=28h
习题 4.3
三、两点说明
1,分配问题中人数和工作任务不相等时
当人数多于工作任务数时，可以添加假想任务使得人
数与工作任务数相同，因为工作任务是假想的，因此完成
这些任务的时间是零。当任务数多于人数时，可添加假想
的人。这样的方法和运输问题中处理的方法类似。
2,当问题目标变为求极大时
? ?
? ?
?
m
i
m
j
ijij xaz
1 1
m a x
可改写为
? ?
? ?
???
m
i
m
j
ijij xaz
1 1
)(m i n
此时效率矩阵中元素都变为了负值，可利用定理 1，
使效率矩阵中全部元素都变为非负的，就可以利用匈牙利
法进行求解。
作业 4.4 4.5
§ 3．分枝定界法
记待解的整数规划问题为 A, 相应的线性规划问题
(去掉了整数约束, 即松弛问题 )为 B, 整数规划的最优解
为 z*。
分枝定界法的基本思想,
（ 1）先不考虑整数条件，即先求解相应线性规划 B
的最优解。若得到的是整数解，则问题得到解决 ;否则，
这个非整数解必是原整数规划问题 A 的最优解 z* 的上界，
记为 ；而 A 的任一整数解，可以看作的一个下界，记
为 。
z
z
（ 2）从得到的 B 的最优解中，任选一个非整数的变
量 xk,在 B 中增加约束条件 xk≤[ xk ] 构成一个新的线性
规划问题 B1，它实际上是 B 的一个分枝；在 B 中增加另
一约束条件 xk≤[ xk ]+1，又得到一个 B 的分支，记为 B2；
分别求出 B1 和 B2的最优解，判断这两个解是否是最优解，
若是，问题得到解决；若不是，调整 和,将它们再分
枝，直到求出最优整数解为止。
z z
分枝定界法实质是将 B 的可行域分成若干子区域 (称
为分枝 )，逐渐减小 和增大,最终求出 z*。 z z
例, 用分枝定界法求解整数规划问题,
?
?
?
?
?
?
??
??
??
取整数 0,
5.45.0
1432
23m a x,
21
21
21
21
xx
xx
xx
xxzA
解, （ 1）求解对应的松弛问题 B
?
?
?
?
?
?
??
??
??
0,
5.45.0
1432
23m a x,
21
21
21
21
xx
xx
xx
xxzB 其最优解为,
5.2,25.3 21 ?? xx
最优值为,
75.14?z
目前最优值为 z=14.75,令 =14.75； z
现在还没有任何整数解，可以令（ 0,0）作为初始整
数解，因此有 =0 。
z
（ 2）定界
（ 3）分枝
将线性规划问题 B 分为两枝。
在 B 的最优解中，任选一个非整数变量，如 x2=2.5 ；
因 x2 的最优整数解只可能是 x2≤2 或 x2≥3,故在 B 中分
别增加约束条件,B 加上约束条件 x2≤2,记为 B1； B加
上约束条件 x2≥3,记为 B2 。这样，将分解成两个子问题
B1 和 B2（即两枝）。
?
?
?
?
?
?
?
?
?
??
??
??
0,
2
5.45.0
1432
23m a x,
21
2
21
21
211
xx
x
xx
xx
xxzB
?
?
?
?
?
?
?
?
?
??
??
??
0,
3
5.45.0
1432
23m a x,
21
2
21
21
212
xx
x
xx
xx
xxzB
这样松弛问题 B 变为了求解下述两个问题,
B 分解为 B1 和 B2,
B1 的最优解为,
x1=3.5,x2=2,z=14.5
B2 的最优解为,
x1=2.5,x2=3,z=13.5
定界,这时两个问题的最优值中较大的一个是 14.5,
比原来的上界要小，因此修改上界，令 。 5.14?z
又由于目前没有出现更好的整数界，所以下界仍然是
0 。
分枝,选取最优值教大的子问题优先进行分枝，将 B1
分解为 B11和 B12 两个子问题。
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
3
2
5.45.0
1432
23m a x,
21
1
2
21
21
2111
xx
x
x
xx
xx
xxzB
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
4
2
5.45.0
1432
23m a x,
21
1
2
21
21
2112
xx
x
x
xx
xx
xxzB
B11和 B12 两个子问题的可行域为,
继续分枝定界，求解得最优解（ 4,1），最优解为 14。
§ 4．割平面法
§ 5．应用举例
§ 1．整数规划的特点及作用
§ 2．分配问题与匈牙利法
§ 3．分枝定界法
§ 4．割平面法
§ 5．应用举例
§ 1．整数规划的特点及应用
在实际问题中，全部或部分变量的取值必须是整数。
比如人或机器是不可分割的，选择建厂地点可以设置逻辑
变量等。
在一个线性规划问题中要求全部变量取整数值的，称
纯整数线性规划或简称 纯整数规划 ；只要求一部分变量
取整数值的，称为 混合整数规划 。
对整数规划问题求解，有人认为可以不考虑对变量的
整数约束，作为一般线性规划问题求解，当解为非整数时，
用四舍五入或凑整方法寻找最优解，我们从下面的例子说
明这样的方法是不合适的。
例 1,求下述整数规划问题的最优解
?
?
?
?
?
?
??
??
??
且均取整数值,0,
5.45.0
143 2
23m a x
21
21
21
21
xx
xx
xx
xxz
解,如果不考虑整数约束（称为整数规划问题的 松弛
问题 ）用图解法得最优解为（ 3.25,2.5）
考虑到整数约束，用凑整法求解
时，比较四个点（ 4,3）,（ 4,2）,
（ 3,3）（ 3,2），前三个都不是可行
解，第四个虽然是可行解，但 z=13 不
是最优。实际问题的最优解为（ 4,1）
这时 z*= 14。
逻辑 （ 0-1） 变量在建立数学模型中的作用
1,m 个约束条件中只有 k 个起作用
设 m 个约束条件可以表示为,
),,1(
1
mibxa i
n
j
jij ????
?
定义逻辑变量
?
?
??
个约束条件起作用，假定第
个约束条件不起作用，假定第
0
1
i
iy
i
又设 M 为任意大的正数，则约束条件可以改写为,
?
?
?
?
?
?????
???
?
kmyyy
Mybxa
m
ii
n
j
jij
?
21
1
定义逻辑变量,
?
?
?
?
，其它
，假定约束右端项为
0
1 i
i
b
y
此时约束条件可以改写为,
?
?
?
?
?
????
? ??
??
121
11
r
r
i
ii
n
j
jij
yyy
ybxa
?
2,约束条件的右端项可能是 r 个值中的某一个
r
n
j
jij bbbxa 或或或 ?21
1
??
?
即
3,两组条件满足其中一组
若 x1≤4，则 x2≥1（ 第一组条件 ）；否则当 x1>4 时，
x2≤3（ 第二组条件 ）,
定义逻辑变量,
）（
组条件起作用，第
组条件不起作用，第
2,1
0
1
?
?
?
?
? i
i
i
y i
又设 M 为任意大正数，则问题可表达为,
?
?
?
?
?
?
?
?
?
??
??
??
??
??
1
3
4
1
4
21
22
21
12
11
yy
Myx
Myx
Myx
Myx
需注意，当约束
为大于时，右端
项中用减号。
4,用以表示含固定费用的函数
用 xj 代表产品 j 的生产数量，其生产费用函数表示为
??
?
?
?
?
??
?
)0( 0
)0(
)(
j
jjjj
jj x
xxcK
xC
其中 Kj 是同产量无关的生产准备费用，问题的目标是使
所有产品的总生产费用为最小，即
?
?
?
n
j
jj xCz
1
)(m a x
定义逻辑变量（表示是否生产产品 j ）
??
?
?
?
?
?
?
00
01
j
j
j x
x
y
，
，
又设 M 为任意大正数，为了表示上述定义，引入约束,
jj Myx ?
显然，当 xj> 0 时,yj=1。
将目标函数与约束条件合起来考虑有,
? ?
??
?
?
?
?
??
?? ?
?
1 0
0
m i n
1
或
j
jj
n
j
jjjj
y
Myx
yKxcz
由此看出，当 xj = 0 时，为使 z 极小化，应有 yj = 0
习题 4.2
§ 2．分配问题与匈牙利法
一、问题的提出与数学模型
分配问题 也称 指派问题 （ assignment problem），
是一种特殊的整数规划问题。假定有 m 项任务分配给 m
个人去完成，并指定每人完成其中一项，每项只交给其中
一个人去完成，应如何分配使总的效率为最高。
如果完成任务的效率表现为资源消耗，考虑的是如何
分配任务使得目标极小化；如果完成任务的效率表现为生
产效率的高低，则考虑的是如何分配使得目标函数极大化。
在分配问题中，利用不同资源完成不同计划活动的效
率通常用表格形式表示为效率表，表格中数字组成 效率
矩阵 。
例 2,有一份说明书，要分别翻译成英、日、德、俄
四种文字，交甲、乙、丙、丁四个人去完成。因各人专长
不同，使这四个人分别完成四项任务总的时间为最小。效
率表如下,
效率矩阵用 [aij] 表示，为
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
913154
11161413
814415
79102
][
ij
a
定义逻辑变量
）；（
项任务个人去完成第，不分配第
项任务个人去完成第，分配第
mjmi
ji
ji
x ij
,,1,,1
0
1
?? ??
?
?
?
?
则分配问题的数学模型写为,
?
?
?
?
?
?
?
?
?
?
?
???
??
??
?
?
?
? ?
?
?
? ?
),,1;,,1( 1 0
),,1( 1
),,1( 1
m i n
1
1
1 1
mjmix
mjx
mix
xaz
ij
m
i
ij
m
j
ij
m
i
m
j
ijij
??
?
?
或
二、匈牙利法
用表上作业法来求解分配问题时，单位运价表即效率
表，产销平衡表中产量和销量都设为 1 即可。
匈牙利数学家克尼格（ Konig ）求解分配问题的计算
方法被成为 匈牙利法,他证明了如下两个定理,
定理 1 如果从分配问题效率矩阵 [aij] 的每一行元素中
分别减去（或加上）一个常数 ui (被称为该行的位势 )，从
每一列分别减去（或加上）一个常数 vj（被称为该列的位
势），得到一个新的效率矩阵 [bij]，若其中 bij = aij-ui-vj，
则 [bij] 的最优解等价于 [aij] 的最优解。
定理 2 若矩阵 A 的元素可分成,0,与非,0,两部
分，则覆盖,0,元素的最少直线数等于位于不同行不同
列的,0,元素的最大个数。
结合例 2 说明 匈牙利法的计算步骤
第一步：找出效率矩阵每行的最小元素，并分别
从每行中减去。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
59110
0532
410011
5780
4
11
4
2
913154
11161413
814415
79102
m i n
第二步：找出矩阵每列的最小元素，分别从各列中减
去。
0 5 0 0 m i n
54110
0032
45011
5280
59110
0532
410011
5780
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
第三步：经过上述两步变换后，矩阵的每行每列至少
都有了一个零元素。下面确定能否找出 m 个位于不同行
不同列的零元素的集合（该例中 m=4），也就是看要覆
盖上面矩阵中的所有零元素，至少需要多少条直线。
1,从第一行开始，若该行只有一个零元素，就对这
个零元素打上（ ），对打括号的零元素所在的列画一条
线，若该行没有零元素或者有两个以上零元素（已划去的
不算在内），则转下一行，依次进行到最后一行。
2,从第一列开始，若该列只有一个零元素，就对这个
零元素打上（ ）（同样不考虑已划去的零元素），再对
打括号的零元素所在行画一条直线。若该列没有零元素或
有两个以上零元素，则转下一列，依次进行到最后一列为
止。
3,重复上述步骤 1,2，可能出现三种情况,
① 效率矩阵每行都有打括号的零元素，只要对应这些
元素令 xij= 1 就找到了最优解。
② 打括号的零元素个数少于 m,但未被划去的零元
素之间存在闭回路，这时顺着闭回路的走向，对每个间隔
的零元素打一个括号，然后对所有打括号的零元素所在行
（或列）画一条直线，同样得到最优解。
③ 矩阵中所有零元素或被划去，或打上括号，但打括
号的零元素少于 m,这时转入第四步。
第四步：按定理 1 进行如下变换
1,从矩阵未被直线覆盖的数字中找出一个最小的 k ；
2,对矩阵中的每行，当该行有直线覆盖时，令 ui= 0，
无直线覆盖的，令 ui= k ；
3,对矩阵中有直线覆盖的列，令 vj= -k，对无直线覆
盖的列，令 vj= 0 ；
4,从原矩阵的每个元素 aij中分别减去 ui 和 vj 。
第五步：回到第三步，反复进行，直到矩阵的每一行
都有一个打括号的零元素为止，即找到最优分配方案。
由于调整后的矩阵中新出现了一个零，因此对打括号
的元素重新进行调整，得到如下矩阵，这时只要把打括号
元素所对应的决策变量取值为 1，就得到最优解。
该问题中，最优值为,4+4+9+11=28h
习题 4.3
三、两点说明
1,分配问题中人数和工作任务不相等时
当人数多于工作任务数时，可以添加假想任务使得人
数与工作任务数相同，因为工作任务是假想的，因此完成
这些任务的时间是零。当任务数多于人数时，可添加假想
的人。这样的方法和运输问题中处理的方法类似。
2,当问题目标变为求极大时
? ?
? ?
?
m
i
m
j
ijij xaz
1 1
m a x
可改写为
? ?
? ?
???
m
i
m
j
ijij xaz
1 1
)(m i n
此时效率矩阵中元素都变为了负值，可利用定理 1，
使效率矩阵中全部元素都变为非负的，就可以利用匈牙利
法进行求解。
作业 4.4 4.5
§ 3．分枝定界法
记待解的整数规划问题为 A, 相应的线性规划问题
(去掉了整数约束, 即松弛问题 )为 B, 整数规划的最优解
为 z*。
分枝定界法的基本思想,
（ 1）先不考虑整数条件，即先求解相应线性规划 B
的最优解。若得到的是整数解，则问题得到解决 ;否则，
这个非整数解必是原整数规划问题 A 的最优解 z* 的上界，
记为 ；而 A 的任一整数解，可以看作的一个下界，记
为 。
z
z
（ 2）从得到的 B 的最优解中，任选一个非整数的变
量 xk,在 B 中增加约束条件 xk≤[ xk ] 构成一个新的线性
规划问题 B1，它实际上是 B 的一个分枝；在 B 中增加另
一约束条件 xk≤[ xk ]+1，又得到一个 B 的分支，记为 B2；
分别求出 B1 和 B2的最优解，判断这两个解是否是最优解，
若是，问题得到解决；若不是，调整 和,将它们再分
枝，直到求出最优整数解为止。
z z
分枝定界法实质是将 B 的可行域分成若干子区域 (称
为分枝 )，逐渐减小 和增大,最终求出 z*。 z z
例, 用分枝定界法求解整数规划问题,
?
?
?
?
?
?
??
??
??
取整数 0,
5.45.0
1432
23m a x,
21
21
21
21
xx
xx
xx
xxzA
解, （ 1）求解对应的松弛问题 B
?
?
?
?
?
?
??
??
??
0,
5.45.0
1432
23m a x,
21
21
21
21
xx
xx
xx
xxzB 其最优解为,
5.2,25.3 21 ?? xx
最优值为,
75.14?z
目前最优值为 z=14.75,令 =14.75； z
现在还没有任何整数解，可以令（ 0,0）作为初始整
数解，因此有 =0 。
z
（ 2）定界
（ 3）分枝
将线性规划问题 B 分为两枝。
在 B 的最优解中，任选一个非整数变量，如 x2=2.5 ；
因 x2 的最优整数解只可能是 x2≤2 或 x2≥3,故在 B 中分
别增加约束条件,B 加上约束条件 x2≤2,记为 B1； B加
上约束条件 x2≥3,记为 B2 。这样，将分解成两个子问题
B1 和 B2（即两枝）。
?
?
?
?
?
?
?
?
?
??
??
??
0,
2
5.45.0
1432
23m a x,
21
2
21
21
211
xx
x
xx
xx
xxzB
?
?
?
?
?
?
?
?
?
??
??
??
0,
3
5.45.0
1432
23m a x,
21
2
21
21
212
xx
x
xx
xx
xxzB
这样松弛问题 B 变为了求解下述两个问题,
B 分解为 B1 和 B2,
B1 的最优解为,
x1=3.5,x2=2,z=14.5
B2 的最优解为,
x1=2.5,x2=3,z=13.5
定界,这时两个问题的最优值中较大的一个是 14.5,
比原来的上界要小，因此修改上界，令 。 5.14?z
又由于目前没有出现更好的整数界，所以下界仍然是
0 。
分枝,选取最优值教大的子问题优先进行分枝，将 B1
分解为 B11和 B12 两个子问题。
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
3
2
5.45.0
1432
23m a x,
21
1
2
21
21
2111
xx
x
x
xx
xx
xxzB
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
4
2
5.45.0
1432
23m a x,
21
1
2
21
21
2112
xx
x
x
xx
xx
xxzB
B11和 B12 两个子问题的可行域为,
继续分枝定界，求解得最优解（ 4,1），最优解为 14。
§ 4．割平面法
§ 5．应用举例
