4 x1 5 x2 200 (1 y) M 3x1 5 x2 180 yM
互斥约束的推广
从下述p个约束条件中恰好选择q个约束条件
a x
j 1 ij
n
j
bi (i 1, 2,
, p)
0 选第i个约束条件 yi (i 1, , p) 1 不选第i个约束条件
要决策的是每个项目是否需要投资
对项目j投资 1 xj ，(j = 1, 0 对项目j不投资
,n)
例2：组合投资问题。
max z c j x j
j 1
n
a j x j B 0-1整数规划 j 1 x x 1 s.t. 2 3 x x x 2 5 6 7 x j 1或0( j 1, 2..., n)
整数规划建模举例
例2：组合投资问题。 某财团有 B 万元的资金，经过其考察选中 n 个投资 项目，其中第 j 个项目需投资金额为 a j 万元，预 计获利 c j（ j 1,2...,n）万元，由于种种原因， 有两个附加条件：第一，项目2和项目3至少选择一 个；第二项目5，6，7恰好选择两个。问应如何选 择项目使得总收益最大？
资源 A B 单台利润 产品 甲 2 5 6 乙 1 7 5 现有量 9 35
问如何安排甲、乙两产品的产量，使利润为最大。
解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 纯整数规划 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整数
n aij x j bi Myi j 1 (i 1, 2, p yi p q i 1
, p)
互斥约束的推广
从下述p个约束条件中恰好选择q个约束条件
a x
j 1 ij
n
j
bi (i 1, 2,
, p)
0 选第i个约束条件 yi (i 1, , p) 1 不选第i个约束条件
n aij x j bi Myi j 1 (i 1, 2, p yi p q i 1
, p)
例3 固定费用问题
服装公司租用生产线拟生产T恤、衬衫和裤子。 每年可用劳动力8200h，布料8800m2。
劳动力 布料 售价 可变成本 生产线租金(万) T恤 3 0.8 250 100 20 衬衫 2 1.1 400 180 15 裤子 6 1.5 600 300 10
5 4 3 2 1 2x1 + x2 =9
• • • • (3,3)
•
•
1
•
•
2
•
•
3
(3
1 7 ,2 ) 9 9
•
4
5x1 +7 x2 =35
x1
对于决策变量少，可行的整数解又较少时，这种枚 举法有时是可行的，并且也是有效的。 但对于大型的整数规划问题，可行的整数解数量很 多，用枚举法求解是不可能的。
0 1 2 3
0 ~ 15
x可取0 ~ 9之间的整数
x 2 x1 2 x2 2 x3 2 x4 9 x1 , x2 , x3 , x4 0或1
0 1 2 3
第四节 指派问题
例1
甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工 作，每项工作只由一人完成，问如何指派总时间最短？
n
整数规划建模举例
例3：某产品有n 个区域市场，各区域市场的需 求量为 bj 吨/月；现拟在m 个地点中选址建生产厂， 一个地方最多只能建一家工厂；若选 i 地建厂， 生产能力为 ai 吨/月，其运营固定费用为Fi 元/月； 已知址i至j区域市场的运价为 cij 元/吨。如何选址 和安排调运，可使总费用最小？ 解：选址建厂与否是个0-1型决策变量， 设 yi =1，选择第 i 址建厂， yi=0，不选择第 i 址建厂； 计划从 i 址至区域市场 j 的运输运量xij为实数型决 策变量。
三、分支定界法
不考虑整数限制先求出相应松弛问题的最优解， 若松弛问题无可行解，则ILP无可行解； 若求得的松弛问题最优解符合整数要求，则是 ILP的最优解； 若不满足整数条件，则任选一个不满足整数条件 的变量 xi0 来构造新的约束添加到松弛问题中形 成两个子问题

0 0 xi xi ; xi xi 1
第三节 0-1变量的使用
例1 投资问题
有600万元投资5个项目，收益如表，求利润最大的方案？
项目 I II III IV V 投资额 210 300 150 130 260 项目收益 160 210 60 80 180 项目 I、II、III 中选 1 项 项目 III、IV 之中选 1 项 选项目 V 必先选项目 I 约束条件
解： 引入0-1变量xij ，
xij =1：第i人做第j项工作
xij =0：第i人不做第j项工作
• 一人只能完成一项任务
x11 x12 x13 x14 1 x21 x22 x23 x24 1 x31 x32 x33 x34 1 x41 x42 x43 x44 1
x1 M 1 y1 x2 M 2 y 2
x3 M 3 y 3
例4 逻辑变量
x可取0,3,5,7中的一个
x 3 x1 5 x2 7 x3 x1 x2 x3 1 x 0或1(i 1, 2,3) i
例5 二进制变量
x4 x3 x2 x1
2 x1 2 x2 2 x3 2 x4
P 1 , z1
P2 , z2
z1 z2
应该优先选取P2进行分支。
分支定界法求解举例
max z x1 x2 9 51 x1 14 x2 14 1 s.t. 2 x1 x2 3 x1 , x2 0且取整
x2
3 2 1
7 (1, ) 3
3 10 , 2 3
(2, 23 ) 9 ( 33 , 2) 14
0
1
2
3
x1
10 4，所以子问题被剪枝，ILP最优解为(2,2)或(3,1)最优值为4. 3
LP 0 ： x1 3 10 29 , x2 ,Z 2 3 6
x1 ≥ 2
LP 2 ： 23 41 x1 2, x2 ,Z 9 9
任务
时间 人员
A 3 6 2 9
B 5 8 5 2
C 8 5 8 5
D 4 4 5 2
甲 乙 丙 丁
• 一项任务只由一个人完成
x11 x21 x31 x41 1 x12 x22 x32 x42 1 x13 x23 x33 x43 1 x14 x24 x34 x44 1
松弛问题最优解满足整数要求，则该最优解为整数 规划最优解；
一、舍入化整法
为了满足整数解的要求，自然想到“舍入”或“截尾”处理，
以得到与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能 超出了可行域，成为非可行解；或者虽是可行解，却不是最 优解。
二、枚举整数法
x2
假设：yj=1，要租用生产线j yj=0，不租用生产线j
第j 种服装生产量xj
max Z 150x1 220x 2 300x3 200000 y1 150000 y 2 100000 y3 3x1 2 x 2 6 x3 8200 0.8 x 1.1x 1.5 x 8800 1 2 3 s.t. x1 , x 2 , x3 0, 且取整数 y , y , y 0或1 1 2 3


全部决策变量的取值都为整数，则称为全（纯）整数规划
仅要求部分决策变量的取值为整数，则称为混合整数规划 要求决策变量只取0或1值，则称0-1整数规划
整数规划的一般模型
max(或 min) ci xi
i 1 n
n ai xi b (或 b 或 b) s.t. i 1 x 0, 且为整数或部分为整数 i
混合整数规划

特征—变量整数性要求 来源
问题本身的要求 引入的逻辑变量的需要

性质—可行域是离散集合
第二节 整数线性规划求解
整数规划 松弛的线性规划
max c x Ax b s.t. x 0, x为整数

max c x Ax b s.t. x 0

整数规划可行解是松弛问题可行域中的整数格点 松弛问题无可行解，则整数规划无可行解； ILP最优值小于或等于松弛问题的最优值
i 1, 2, , n
应用与实例

Hale Waihona Puke 在现实生活中，经常遇到一些需要变量取整数才 有实际意义的问题，例如制定计划、规划时需要 确定工人的人数，设备的台数等。 许多有名的最优化问题，如旅行商问题、背包问 题、下料问题、工序安排问题等，也都可以归结 为整数规划问题。

整数规划建模举例
例1：某企业利用材料和设备生产甲乙产品，其工艺消耗 系数和单台产品的获利能力如下表所示：
例2、互斥约束问题
• 例如某种工序的约束条件为：
• 企业也可以考虑一种新的加工工序：
4 x1 5x2 200
3x1 5x2 180
• 这两个工序只能选其一，是互相排斥的。引入0—1变量y，令
1 采用原工序 y 0 采用新工序
• 互斥问题可由下述的条件来代替，其中M是充分大的数。
整数规划
教学要求：
掌握线性整数规划的建模方法，特别是0-1变量的运用
掌握指派问题的求解方法 了解整数规划的求解方法