x2 8 7 6 5 4 3 p 2 1 0 1 2 3 4 5 6 x1
选 x1进行分枝： (P1) x1 3 x2 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 x1 (P2) x1
4
为空集
P p1
（P1）
Min Z= x1+4x2 x1+2x2 6 x1,x2 0 ，x1 3 整数
解：如果令xi=1表示登山队员携 带物品i，xi=0表示登山队员不携 带物品i，则问题表示成0-1规划:
Max Z= 20x1+15x2 +18x3 +14x4
+8x5 +4x6 +10x7
s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1或xi=0 i=1,2,….7
s.t. 3x1+4x2 12
用单纯形法可解得相应的松驰问题的最 优解（6/5，21/10），Z=111/10为各分 枝的上界。
分枝：X1 1,x1 2
x2 4 3 2
P1
1 0
1
P2 2
3
4
x1
两个子问题：
（P1）Max
Z=4x1+3x2
4x1+2x2 9
s.t. 3x1+4x2 12 x1,x2 0 ， x1 1
例 3-1 ：一登山队员做登山准备， 他需要携带的物品有：食品，氧 气，冰镐，绳索，帐篷，照相机 和通讯设备，每种物品的重要性 系数和重量如下：假定登山队员 可携带最大重量为25公斤。
序号
1
2
3
4
5
6
7
物品 食品 氧气 冰镐 绳索 帐篷 相机 设备 重量 重要 系数 5 20 5 15 2 18 6 14 12 8 2 4 4 10
解：如果令xj=1表示携带物品j， xj=0表示不携带物品j，则问题表 示成0-1规划:
Max Z = Σcjxj s.t. Σajxj b
xj=0
或1
数学模型 整数规划(IP)的一般数学模型: Max (min) Z = Σcjxj
s.t. Σaijxj bi(i=1,2,…m)
xj 0且部分或全部是整数
，整数
用单纯形法可解得相应的（P1）的最优 解（1，9/4） Z=10(3/4)
（P2）Max
Z=4x1+3x2 4x1+2x2 9
s.t. 3x1+4x2 12 x1,x2 0 ， x1 2
，整数
用单纯形法可解得相应的（P2）的 最优解（2，1/2） Z=9(1/2)
再对（P1）分枝：X1 1
若松驰问题无可行解，则原整数 规划问题也无可行解，计算结束。
若松驰问题有最优解，但其各分量不全 是整数，则这个解不是原整数规划的最 优解，转下一步。 从不满足整数条件的基变量中任选 一 个xl进行分枝，它必须满足xl [xl ] 或xl [xl ] +1中的一个，把这两个约束条件加 进原问题中，形成两个互不相容的子问 题（两分法）。
第三章
整数规划
3-1
整数规划问题
整数规划是一类要求变量取整数值 的数学规划，可分成线性和非线性 两类。 根据变量的取值性质，又可以 分为全整数规划，混合整数规划， 0-1整数规划等。
整数规划是数学规划中 一个较弱的分支，目前只能 解中等规模的线性整数规划 问题，而非线性整数规划问 题，还没有好的办法。
s.t. 2x1+ x2 8
用单纯形法可解得（P4）的最优解 （2，2）Z=10
X1
4
X2 1
P2:无可行解
P:(10/3,4/3) Z=26/3 X1 3 P1:(3,3/2) Z=9
P3:无可行解
X2
2
P4:(2,2) Z=10
原问题的最优解（2，2） Z=10
(P3) x2 1无可行解 (P4) x2
2
Pp 4
（P3）
Min Z= x1+4x2 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数 s.t. 2x1+ x2 8
无可行解。
（P4）
Min Z= x1+4x2 x1+2x2 6 x1,x2 0， x1 3 ，x2 2整数
s.t. 2x1+ x2 8
用单纯形法可解得（P1）的最优解
（3，3/2）Z=9
（P2） Min Z= x1+4x2 s.t. 2x1+ x2 8
x1+2x2 6
x1,x2 0 x1 4 无可行解。 整数
对(P1) x1 3 选 x2进行分枝： x2 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 x1
例3-2 背包问题( Knapsack
Problem)
一个旅行者,为了准备旅行的必须用品,要 在背包内装一些最有用的东西,但有个数 限制,最多只能装b公斤的物品,而每件物 品只能整个携带,这样旅行者给每件物品 规定了一个“价值”以表示其有用的程度, 如果共有n件物品,第j件物品aj公斤,其价 值为cj.问题变成:在携带的物品总重量不 超过b公斤条件下,携带哪些物品,可使总 价值最大?
定界：把满足整数条件各分枝的最优目 标函数值作为上（max）（下(min)）界， 用它来判断分枝是保留还是剪枝。 剪枝：把那些子问题的最优值与界值比 较，凡不优或不能更优的分枝全剪掉， 直到每个分枝都查清为止。
例5-6 用分枝定界法求解：
Max Z=4x1+3x2 4x1+2x2 9 x1,x2 0 且为整数
X2 2 P : (1,2) Z=10 3
X2
3 P : (0,3)
4
Z=9
原问题的最优解（1，2） Z=10
例5-7 用分枝定界法求解：
Min Z= x1+4x2 x1+2x2 6 x1,x2 0 且取整数
s.t. 2x1+ x2 8
用单纯形法可解得相应的松驰问题的最 优解（10/3，4/3），Z=26/3为各分枝的 下界。
解法概述
当人们开始接触整数规划问题时， 常会有如下两种初始想法： 因为可行方案数目有限，因此经 过一一比较后，总能求出最好方案， 例如，背包问题充其量有2n-1种方式； 连线问题充其量有n!种方式；实际 上这种方法是不可行。
设想计算机每秒能比较 1000000个方式，那么要比较 完20!（大于2*1018）种方式， 大约需要800年。比较完260 种方式，大约需要360世纪。
D
B(9.2,2.4)
假如能求出可行域的“整点凸包”（包 含所有整点的最小多边形OEFGHIJ），则 可在此凸包上求线性规划的解，即为原问 题的解。但求“整点凸包”十分困难。
x2 5 4 3 2 1 O 1 2 3 4 5
D J I
I(2,4)
H
G F 6 E 7 A8 9
B(9.2,2.4)
10
（P1）两个子问题：
（P4）Max Z=4x1+3x2 4x1+2x2 9 x1,x2 0 ,x1 1,
x2
s.t. 3x1+4x2 12
3整数
用单纯形法可解得相应的（P4）的最优 解（0，3） Z=9
X1
2
P2:(2,1/2) Z=9(1/2)
P:(6/5,21/10) Z=111/10 X1 1 P1:(1,9/4) Z=10(3/4)
先放弃变量的整数性要求，解一 个线性规划问题，然后用“四舍五 入”法取整数解，这种方法，只有 在变量的取值很大时，才有成功的 可能性，而当变量的取值较小时， 特别是0-1规划时，往往不能成功。
例3-3
求下列问题：
Max Z=3x1+13x2
s.t.2x1+9x2 40 11x1-8x2 82
D
I(2,4)
B(9.2,2.4)
X1 2 X2 3 X1 6 P X2
P1
P2 P3
X1
ห้องสมุดไป่ตู้3
X1
X2 2
4
P4
7
X2
3
P5
假如放弃整数要求后，用单纯形法 求得最优解，恰好满足整数性要求， 则此解也是原整数规划的最优解。 以上描述了目前解整数规划问题 的两种基本途径。
分枝定界解法 （Branch and Bound Method)
原问题的松驰问题：任何整数规划 （IP），凡放弃某些约束条件（如整数 要求）后，所得到的问题（P） 都称为 （IP）的松驰问题。
最通常的松驰问题是放弃变 量的整数性要求后，（P）为线性 规划问题。
分枝定界法步骤
一般求解对应的松驰问题，可能 会出现下面几种情况： 若所得的最优解的各分量恰好是 整数，则这个解也是原整数规划 的最优解，计算结束。
x1
假如把可行域分解成五个互不相交的子问题P1 P2 P3 P4 P5之和, P3 P5的定义域都是空集,而放弃 整数要求后P1最优解I(2,4),Z1=58 P2最优解 (6,3),Z2=57 P4最优解(98/11,2),Z4=52(8/11)
x2 5 4 3 2 P1 P2 P4 5 6 7 A8 9 10 x1 1 O 1 2 3 4
x2 4 P4 3 2 1 0
（P3） x2 2
（P4） x2 3
P1
P3 1
P2 2
3
4
x1
（P1）两个子问题：
（P3）Max Z=4x1+3x2 4x1+2x2 9 x1,x2 0 ,x1 1,