了解整数规划在经济和管理中的基本应用方法。
第五章 整数规划
Integer Programming
教学要求：
掌握线性整数规划的建模方法，特别是0-1变量的运用；
了解分支定界求解方法的基本原理；
了解割平面求解方法的基本原理；
整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。
第一节 整数规划的数学模型及解的特点
一、整数规划数学模型 ( Integer programming models )
混合整数规划 Mixed integer programming
纯整数规划 Pure integer programming
0-1 整数规划 0-1 integer programming
纯整数规划
max z = j=1,2,…,n cj xj
. j=1,2,…,n aijxj = bi, i=1,2,…,m
xj ≥ 0, xj integer, j=1,2,…,n
0-1 整数规划
max z = j=1,2,…,n cj xj
. j=1,2,…,n aijxj = bi, i=1,2,…,m
xj = 0 or 1, j=1,2,…,n
二、整数规划的例子
例1 一名登山队员做登山准备，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备，每种物品的重要性系数和重量如表。假定登山队员可携带的最大重量为25公斤。
解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:
max z= 20x1+15x2 +18x3 +14x4 +8x5 +4x6 +10x7
. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25
xi=1或xi=0 i=1,2,….7
10
4
8
14
18
15
20
重要系数
4
2
12
6
2
5
5
重量
设备
相机
帐篷
绳索
冰镐
氧气
食品
物品
7
6
5
4
3
2
1
序号
例2 背包问题( Knapsack Problem)
一个旅行者,为了准备旅行的必须用品,要在背包内装
一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品 公斤,其价值为 .问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?
解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划:
max z = Σcjxj
. Σajxj b
xj=0或1
例3 某公司正在考虑随后4年的投资方案。面对每年有限的资金，公司需要选择最好的方案，使预计收益现值最大化。每种方案的预计收益现值、资金需求和4年内拥有的资金见下表：
x1表示是否扩建工厂，1表示扩建，0表示不扩建。同理，x2,x3,x4依次表示是否扩建仓库、更新机器、新产品研制。
变 量
第1年可用资金40千元，所以相应约束条件为：
同理得后三年的约束
约束条件
当前估算净值最大，即max
目标函数
扩建厂房
扩建仓库
更新机器
新产品研制
收益现值
90
40
10
37
总可用成本
第
1
年资金
15
10
10
15
40
第
2
年资金
20
15
10
50
第
3
年资金
20
20
10
40
第
4
年资金
15
5
4
10
35
项目（千元）
三、解的特点
线性规划松弛(LP relaxation)
整数规划: max z = j=1,2,…,n cj xj
. j=1,2,…,n aijxj = bi, i=1,2,…,m
xj ≥0, xj integer, j=1,2,…,n
线性规划松弛: max z = j=1,2,…,n cj xj
. j=1,2,…,n aijxj = bi, i=1,2,…,m
xj ≥0, j=1,2,…,n
整数规划可行域包含在它的线性规划松弛的可行域中。
整数规划的最大z-值 它的线性规划松弛的最大z-值。
如线性规划松弛的最优解 x* = (x1*, x2*, …, xn*)是整数，则它就是整数规划的最优解。否则，线性规划松弛的最大值 z* = cx* 是整数规划最大值的上界。
0 1 2 3 4 5
0 1 2 3 4 5
求解松弛问题，得到
x=，y=0，z=。
整数不可行。
通过取整和舍尾，可得
x=5，y=0，z=15。不可
行；x=4，y=0，z=12。
可行。
而最优解为x=3,y=1,z
=13
例4 两个变量的整数规划问题
maximize 3x + 4y
subject to 5x + 8y 24
x，y 0 and integer
原问题
去掉整数约束条件，
得线性规划问题，并标准化
最后的单纯形表
在最优表b列各分数中有最大小数部分对应的行中写下非整数解约束方程,即第一行：
第二节 解纯整数规划的割平面法
例5 割平面法的过程
所有系数和常数项分解为整数和正真分数之和，并把整系数 项移到左边
考虑到所有变量为非负整数，所以
这就是割平面约束条件
引入松弛变量化为等式，作为前面单纯形表的最后一行，用对偶单纯形法继续求解
重复上面的过程，直到得到整数解
0
)
(
4
4
3
3
2
1
2
1
£
+
-
x
x
第三节 分支定界法
1．设原整数规划为问题A，其松弛问题为问题B，解问题B 。
2．如问题B没有可行解，即停止。这时问题A也没有解。
3．如求得问题B的最优解，检查它是否满足整数条件。如满足整数
条件，它就是问题A的最优解；如不满足整数条件，转下一步。
4．在问题B的解中，任选一个不符合整数条件的变量xi，如xi的值
是bi，作两个后继问题，它们是对问题B分别增加一个约束条件
（1） （2）
其中， 为不大于 的最大整数。不考虑整数条件，解这
两个后继问题。
5．在现有的、还未分解出后继问题的各可行问题中，选目标函数
值最大的问题。重新称这个问题为问题B，回到步骤3，重复进
行。
例6 用分枝定界法求解：
max z=4x1+3x2
. 3x1+4x2 12
4x1+2x2 9
x1,x2 0 整数
用单纯形法解得相应松驰问题的最优解（6/5，21/10）， z=111/10为各分枝的上界。
0 1 2 3 4
4 3 2 1
x1
x2
分枝：X1 1 , x1 2
P1
P2
子问题P1 :
maxz=4x1+3x2
. 3x1+4x2 12
4x1+2x2 9
x1, x2 0，x1 1
最优解（1，9/4）,
z=10(3/4)
子问题P2：
max z=4x1+3x2
. 3x1+4x2 12
4x1+2x2 9
x1, x2 0，x1 2
最优解（2，1/2）
z=9(1/2)
0 1 2 3 4
4 3 2 1
x1
x2
再对（P1）分枝：x1 1
（P3） x2 2 （P4） x2 3
P1
P2
P3
P4
子问题P3：
max z=4x1+3x2
. 3x1+4x2 12
4x1+2x2 9
x1,x2 0 ,x1 1, x2 2
最优解（1，2） z=10 。
z=10作为下界
把 x1 2一支剪掉。
子问题P4：
max z=4x1+3x2
. 3x1+4x2 12
4x1+2x2 9
x1,x2 0 ,x1 1, x2 3
最优解（0，3） z=9。结束。
x1 2
x2 2
x1 1
x2 3
P1:(1,9/4)
z=10(3/4)
P4: (0,3) z=9
P2:(2,1/2) z=9(1/2)
P3: (1,2) z=10
P:(6/5,21/10) z=111/10
原问题的最优解（1，2） z=10
第四节 0-1型整数规划
一、0-1变量及其应用
例7 如果一个整数变量 x 有上界 u，即
0 x u，
这里
2N u 2N+1，
则 x 可用0-1变量 yi（i=0,1,…,N）表示：
x = i=0,1,…,N 2i yi,
yi = 0 or 1, i=0,1,…,N
max z = 3x1 + 4x2
. x1 5 0 x1 5
2x1 + 3x2 30 0 x2 10
xj 0, xj integer, j=1,2
22 5 23, 23 10 24
x1 = y10 + 2y11 + 4y12
x2 = y20 + 2y21 + 4y22 + 8y23
yij = 0 or 1
max z =3y10 + 6y11 + 12y12+ 4y20 + 8y21 + 16y22 + 32y23
. y10 + 2y11 + 4y12 5
2y10 + 4y11 + 8y12 + 3y20 +6y21 +12y22 +24y23 30
yij = 0 or 1
例8 下面两个约束是相互矛盾：
f(x)-5 0 (1)
f(x) 0 (2)
引入一个整数变量来处理（ M是足够大的数，y 是0-1变量）
-f(x)+5 M（1-y) (3)
f(x) My (4)
当y=1时,(1)(3)无差别,(4)式显然成立;
当y=0时,(2)(4)无差别,(3)式显然成立。
以上方法可以处理绝对值形式的约束：
|f(x)| a (a>0)
此时 f(x) a (5)
f(x) -a (6)
是矛盾约束。类似地，M是足够大数，y 是0-1变量，则
-f(x)+a M（1-y)
f(x)+a My
注意：对 |f(x)| a (a>0) 不必引入0-1变量，因为f(x) a和f(x) -a并不矛盾。
例9 对下列n个约束，
fi(x) 0 ， i=1,2,….n,
引入 n个0-1变量yi，i=1,2,…n。M是足够大的数。
如果希望有k个约束有效，则：
fi(x) M(1-yi) , y1+ y2 + … + yn= k
如果希望至多有k个约束成立，则：
fi(x) M(1-yi), y1+ y2 + … + yn k
如果希望至少有k个约束成立，则：
fi(x) M(1-yi), y1+ y2 + … + yn k
例10 如果f (x)<0成立，则g (x) 0必须成立。
引入0-1变量： f (x) -M(1-y) (*)
g (x) My
如果f (x)<0成立，则y不能为1，否则与（*）矛盾；
所以 y=0, g (x) 0 成立。
例11 Stockco现有资金$14,000，6个投资方案所需的现金和财务净现值累计(NPV)如下表，想使他的NPV最大，问最优策略是什么？
Max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6
5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 14
xj e {0,1} ， for each j = 1 to 6
正好选择三种股票
如果选择股票2，必须也选择股票1
如果选择股票1，那就不能选择股票3
股票4和股票5只能选其一
必须选择股票1，除非NPV累计超过$42000
x1+ x2+ x3+ x4+ x5+ x6=3
x1 x2
x1 + x3 1
x4 + x5 = 1
If NPV < 42 then x1=1.
添加一个约束: x1 (42 – NPV)/42. 因为 NPV is 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6
所以 42x1 42 - (16x1+22x2+12x3+8x4+11x5+19x6)
不允许选择3种股票
Either x1+x2+x3+x4+x5+x6 4 or (1)
x1+x2+x3+x4+x5+x6 2 (2)
增加一个辅助变量 w {0,1} 满足
If w = 1, 条件(1)满足；If w = 0, 条件(2)满足。
因为 w 取 0 或 1, 所以至少有一个约束满足。
增加约束: x1+x2+x3+x4+x5+x6 4w (A)
如果 w=1 那么 x1+x2+x3+x4+x5+x6 4 (1)
注意: 如果w = 0, 上述约束(A)自动满足。
增加约束：x1+x2+x3+x4+x5+x6 2 + 4w (B)
如果 w=0 那么 x1+x2+x3+x4+x5+x6 2 (2)
注意: 如果w = 1, 约束(B)自动满足。
例12 现有一位于城市B5的工厂，其年生产量是30000件，产品被运往A1，A2，A3三个城市的销售中心。经预测该厂产品的需求量将会增长，工厂决定将在B1，B2，B3，B4四个城市中的一个或多个城市中新建工厂以增加生产力。综合考虑在这四个城市中新建工厂的年固定成本和生产能力，以及每件产品从每个工厂送到每个销售中心的运费。问如何选择新的厂址，才能使该工厂每年的总成本最小。
B1
B2
B3
B4
B5
A3
A2
A1
首先做如下假设：
如果在 建新厂， =1；否则， =0。
如果在 建新厂， =1；否则， =0。
如果在 建新厂， =1；否则， =0。
如果在 建新厂， =1；否则， =0。
表示从工厂i到销售中心j的运输量，i=1,…,5；j=1,2,3。
利用已知的数据，年运输成本为：
新工厂年固定成本
总成本
生产能力的约束条件为：
三个销售中心的需求量为：
所以选址模型为：
．
二、0-1型整数规划的解法（隐枚举法）
例13 max z = 3 x1 - 2 x2 + 5 x3
. x1 + 2 x2 - x3 ≤ 2
x1 + 4 x2 + x3 ≤ 4
x1 + x2 ≤ 3
4 x2 + x3 ≤ 6
x1 , x2 , x3 = 0 or 1
最优解
4
3
2
1
z ≥ 0
0
（0，0，0）
6
（1，1，1）
-2
（0，1，0）
删除
条件
约束条件
（0，0，1）
1
（1，1，0）
z ≥ 8
8
（1，0，1）
3
（1，0，0）
3
（0，1，1）
z ≥ 5
5
z
（x1 , x2 , x3）
最优解
4
3
2
1
z ≥ 8
8
（1，0，1）
-2
（0，1，0）
5
（0，0，1）
删除
条件
约束条件
（1，1，1）
0
（0，0，0）
1
（1，1，0）
3
（1，0，0）
3
（0，1，1）
6
z
（x1 , x2 , x3）
第五节 指派问题Assignment Problems
一、指派问题的标准形式及其数学模型
有n个人和n件事。不同人做不同事的费用不一样。每个人一定做一件事，也只能做一件事。应怎样分派任务才能使总的费用最省？
xij = 1，由第 i 人做第 j 事；
xij = 0，否则。
x ij = 1，由建筑公司 Ai 建造商店 Bj；x ij = 0，否则。
i = 1, 2, 3, 4, 5； j = 1, 2, 3, 4, 5
6
10
12
9
6
A5
10
6
14
7
6
A4
7
8
12
9
6
A3
10
14
17
9
7
A2
12
15
7
8
4
A1
B5
B4
B3
B2
B1
新建商店
建筑公司
例14
Min z = 4x11 + 8x12 + 7x13 + 15x14 + 12x15 + 7x21 + 9x22
+17x23 + 14x24 + 10x25 + 6x31 + 9x32 +12x33 + 8x34
+ 7 x35 + 6x41 + 7x42 + 14x43 + 6x44 +10x45 + 6x51
+ 9 x52 + 12x53 + 10x54 + 6x55
. x11 + x12 + x13 + x14 + x15 = 1
x21 + x22 + x23 + x24 + x25 = 1
x31 + x32 + x33 + x34 + x35 = 1
x41 + x42 + x43 + x44 + x45 = 1
x51 + x52 + x53 + x54 + x55 = 1
x11 + x21 + x31 + x41 + x51 = 1
x12 + x22 + x32 + x42 + x52 = 1
x13 + x23 + x33 + x43 + x53 = 1
x14 + x24 + x34 + x44 + x54 = 1
x15 + x25 + x35 + x45 + x55 = 1
各建筑队完成每座厂房所需费用（万元）
6
6
3
5
5
4
6
9
6
7
5
8
2
5
4
3
二、指派问题的匈牙利算法
例15 某市计划在年内修建4座厂房： ， ， ， 。有4个建筑公司 ， ， ， 可以承担这些厂房的建造任务。各个建筑公司建造每座厂房所需要的费用不一样，如下表所示。又因希望尽早把这 4座厂房都建造好，故每个建筑公司都分配一项任务。究竟应该指派哪个公司修建哪个厂，才能使建造4座厂房所花的总费用最少？
效率矩阵
每行元素中减去该行的最小元素
每列元素中减去该列的最小元素
算法原理：设 是一个效率矩阵，若可行解 的n个1所对应的n个 都等于0，则 是最优解。
例15的效率矩阵：
划去C中所有0元素所需要的最少直线数等于C中不同行不同列上0元素的个数
注：最优解不一定唯一！
1，在所有未划去数中找出最小数，设为d；
2，将所有未画去的数都减去d，而对位于两直线交点处的数则加上d。
3，得出最优指派方案。
Sum (xi) = 3
