x1 = 4，x2 = 0 是可行解，但不是最优解
因为
x1 = 4，x2 = 0时，z = 80
而可行解 x1 = 4，x2 = 1时，z = 90
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:4
5.2 整数规划的类型 整数规划按变量取值的不同，可以分为以下几类：
1. 纯整数规划：所有的变量都取整数值； 2. 混合整数规划：部分变量取整数值； 3. 0—1规划：所有变量只取0，1两个值； 4. 0—1混合规划：部分变量只取0，1两个值。
2 1,
9 14 x1 x2
x2
x2 0
51
14 1
3
x 1 , x 2 取整数
解S得：
A:
x1
3 2
,
x2
10 3
z 29 6
浙江理工大学 经济管理学院
X2 5
4
A( 3 , 10 ) 23
3
2
S
1
1
2
管理运筹学
Page:10
X
3
1
wxj
Page:11
对S分枝：
X2
构造约束：
5
x1 2 和
x1 1
形成分枝问题S1 和S2，得解B和C
3 10
4
A( , ) 23
3
7
C (1, )
2
3
B (2, 23 ) 9
B:(229,3 );z491 C:(17 3), ;z130
浙江理工大学 经济管理学院
1 S2
1
管理运筹学
S1
2
3
X1
wxj
Page:12
A:
S x1=3/2,x2=10/3
Z=29/6
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:9
当所有最低一层子问题出现以下三种情况时，分枝定界法终止： 1. 子问题无可行解； 2. 子问题已获得整数解； 3. 子问题的目标函数值未达到下界。
浙江理工大学 经济管理学院
管理运筹学
wxj
例
max z x 1 x 2
s
.t
.
x1 x
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:3
Max z = 20x1 +10x2 St. 5x1 +4x2 24 2x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整数
（1）若 x1 = 4.8 ，x2 = 0
x1 = 5 ，x2 = 0 不是可行解；
（2）若 x1 = 4.8 ，x2 = 0
5
10
托运限制 24
13
问两种货物各托运多少箱，可使获得的利润最大？
解： 设x1 , x2 分别为甲、乙两种货物的托运箱数，则模型为：
Max z = 20x1 +10x2 St. 5x1 +4x2 24
2x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整数
暂不考虑整数约束，求得最优解为 x1 = 4.8 ，x2 = 0， Max z = 96
浙江理工大学 经Page:5
整数规划（Integer Programming） 问题的一般形式
m a x ( m i n ) z c 1 x 1 c 2 x 2 c n x n
s.t.
a11x1a12x2 a1nxn (.)b1
a21x1a22x2 a2nxn (.)b2
管理运筹学
wxj
Page:8
分枝定界法基本思想：
首先不考虑变量的整数约束，求解相应的线性规划问题：
Max z = CX
z0
AX = b
X0
DC
下界
整数解 z11
Max z = CX AX = b
xr Ir X0
Max z = CX
z12
AX = b
xr Ir+1
X0
O Ir xr Ir+1
A
分枝
F:(2),2;z4
浙江理工大学 经济管理学院
3 10
4
A( , ) 23
3
2
F(2,2)
1 S2
S122
1
2
管理运筹学
S11无可行解
浙江理工大学 经济管理学院
3 10
4
A( , ) 23
3
2
D(1343,2)
1 S2
1
管理运筹学
S12
2
3
X1
wxj
Page:14
A:
S x1=3/2,x2=10/3
Z=29/6
z 29 6
z4
x1 1
C:
S2 x1=1,x2=7/3
Z=10/3
x1 2
B:
S1 x1=2,x2=23/9
am1x1am2x2 am nxn (.)bm
x1, x1 , xn中部分或全部取整数
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:6
整数规划与其松弛问题
当放弃整数约束时得到的线性规 划称为整数规划的松弛问题。
整数规划的可行域是松弛问题的 可行域，反之不成立。
浙江理工大学 经济管理学院
管理运筹学
每一次分枝得到的子问题的 最优目标函数值都要比上一 层问题的最优目标函数值小， 或者相等。
定界
z2…1 ... …z..2.2 …z23 ...
若z21 z11，z22 z11，则无须继续分枝
…z.2.4.
利用定界，可以终止许多 不必要的分枝过程。
如果在分枝过程中得到新的整数解且该整数解的目标函数值大于已 记录的下界，则应将较大的整数解的目标函数值代替原来的下界。
Z=41/9
z 41 9
z4
x2 2
x2 3
z 61 14
z4
D:
S12
x1=33/14,x2=2 Z=61/14
S11 无可行解
浙江理工大学 经济管理学院
管理运筹学
wxj
对S12分枝：
X2
构造约束：
5
x1 3
和 x1 2
形成分枝问题S121 和S122，得解E和F
E:(3),1 ;z4
浙江理工大学 经济管理学院
Page:1
管
整 数
理
规运
划筹
学
管理运筹学
wxj
Page:2
第五章 整数规划
5.1 整数规划问题的提出
例5-1 某厂拟用集装箱托运甲、乙两种货物。每箱的体积、重量、 可获利润以及托运所受限制如下表所示：
货物
体积（m3/箱） 重量（kg/箱） 利润（百元/箱
）
甲
5
2
20
乙
4
z 29 6
z4
x1 1
x1 2
C:
S2 x1=1,x2=7/3 Z=10/3
B:
S1 x1=2,x2=23/9
Z=41/9
z 41 9
z4
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:13
对S1分枝：
X2
构造约束：
5
x2 3 和
x2 2 形成分枝问题S11 和S12，得解D
D:(1 34 3,2);z1 64 1
wxj
Page:7
5.3 整数规划的解法
5.3.1 混合整数规划的求解---分枝定界方法
分枝：当 xi bi不符合整数要求时，构造
两个约束条件：
xib i 和 xib i 1
加入松弛问题分别形成两个子问题（分枝）
定界：当子问题获得整数规划的一个可行 解，则它的目标函数值就构成一个界限
浙江理工大学 经济管理学院