§1整数规划的特点及作用

整数线性规划的几种类型
• 纯整数线性规划 • 混合整数线性规划 • 0-1型整数线性规划 例如选择投资项目问题（0-1规划问题）
• 整数规划的例子
– 例1：求下述整数规划问题的最优解：
Maxz 3x1 2 x2
2 x1 3 x2 14 s.t. x1 0.5 x2 4.5 x , x 0且 取 数 均 整 值 1 2

第四章 整数规划与分配问题
•§1.整数规划的的特点及作用 •§2.分配问题与匈牙利法 •§3.分枝定界法
§1.整数规划的特点及作用
• 整数规划数学模型的一般形式
一部分或全部决策变量取整数值的规划问题 ——整数规划 整数规划中不考虑整数条件是对应的规划问题 ——该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 ——整数线性规划
整数规划 最优解
A3
A
*
B
0 1 2 3 4 5 6 7
C 8
逻辑变量在整数规划建模中的作用
1、m个约束条件中只有k个起作用。
a
j 1
n
ij
x j bi
(i 1, 2,..., m )
定义
1 第i个约束不起作用 yi 0 否则 则上述条件可以表示成
aij x j bi Myi j 1 y y ... y m k 2 m 1
则上述条件可以表示成
3、 两组条件中满足其中的一组 若 x1 4, 则 x2 1，若 x1 4, 则 x2 3
定义
1 第i组条件不起作用 yi 0 第i组条件起作用
i=1,2
则问题可以表示为 x1 4 y1 M x2 1 y1 M x1 4 y2 M x 3 y M 2 2 y1 y2 1
• 解的特点
整数线性规划及其松弛问题比较，前者 的最优解的目标函数值不会优于后者的。 例：考虑下面的整数规划问题
max z x1 4 x2 2 x1 3 x2 3 s.t x1 2 x2 8 x , x 0且取整数 1 2
从图上分析：
A1
P
wenku.baidu.com
A2 A4
n
2、 约束条件的右端可能是r个值中的某一个
a
j 1
n
ij
x j b1 or b2 ... or br
定义
1 约束右端项为bi yi 0 否则
aij x j bi yi i 1 j 1 y y ... y 1 1 2 r
n r
4 用以表示含固定费用的函数
K j c j x j ( x j 0) 总费用 C j ( x j ) ( x j 0) 0 n 目标函数是总费用最小min z C j ( x j )
定义
1, x j 0 yj 0, x j 0
• 整数线性规划一般形式：
max(min) z c j x j
j 1 n
n
( a )
(b) aij x j ( , )bi j 1 (c ) xj 0 x , x , , x 中部分或全部取整数 ( d ) n 1 2
• 整数规划的例子
– 例2：某服务部门各时段（每2小时为一时段） 需要的服务员人数见下表。按规定服务员连续 工作8小时为一班。现要求安排服务员的工作 时间，使服务部门服务员总数最少。
时段
1
2
3
4
5
6
7
8
服务员 10 最少人数
8
9
11 13 8
5
3
解：设在第j时段开始上班的人数为x j ，则
min z x1 x2 x3 x4 x5 x1 10 x1 x2 8 x1 x2 x3 9 x1 x2 x3 x4 11 x2 x3 x4 x5 13 x3 x4 x5 8 x4 x5 5 x5 3 x1 , x2 , x3 , x4 , x5 0, 且为整数
j 1
则目标函数可以表示成 min z (c x K y ) j j j j
j 1
n
x j My j s .t . x j 0 y j 0,1
2. 整数规划问题的特征与性质 特征—变量整数性要求 来源 问题本身的要求 引入的逻辑变量的需要 性质—可行域是离散集合