2009-7-26 1
运 筹 学 Operations Research
§ 4.1 整数规划整数规划（ IP,integer programming）,决策变量的全部或部分取整数值的线性规划,
分类：
1.纯整数规划（ IP,AIP,all integer programming）,全部决策变量均取整数值的整数规划,

njx
bAxts
xcz
IP
j
T
,,2,1,,0
..
m a x
:)(
整数
2009-7-26 2
运 筹 学 Operations Research
2.混合整数规划（ MIP,mixed integer programming）,决策变量的一部分取整数值的整数规划,


Nnjx
nNjx
bAxts
xcz
M I P
j
j
T
\},,2,1{,0
},,2,1{,,0
..
m a x
:)(
整数问,（ MIP） 与 (LP),(IP)有何关系？
2009-7-26 3
运 筹 学 Operations Research
3.0-1规划（ 0-1 programming）,njx
j,,2,1,1,0

njx
bAxts
xcz
B I P
j
T
,,2,1,1,0
..
m a x
:)(
2009-7-26 4
运 筹 学 Operations Research
且总价值最大？积不穿过背包的容积，能使得装入物品的总体入背包中，才问：应如何选择物品装，价值为
，种物品的体积为第的背包中种物品装入容积为今将例
.,,2,1
.1
njc
ajbm
j
j

解：令
njjx j,,2,1,,0,1


否则，
种物品，装入第

njx
bxats
xcz
j
n
j
jj
n
j
jj
,,2,1,1,0
..
m a x
1
1
则
▌
2009-7-26 5
运 筹 学 Operations Research
§ 4.1 over