运筹学讲义 §6.1整数规划 整数规划(IP, Integer programming):决策变量的全部或部分取整数值的线性规划 显然,整数规划去掉对决策变量的整数性要求即为一般线性规划问题 分类: 1.纯(全)整数规划(IP,AIP, accurate( all, pure) Integer programming):全部决策变量均取 整数值的整数规划 (IP): s.I. Ax=b x≥0整数=12…,n 2.混合整数规划(MP, mixed integer programming):决策变量的一部分取整数值的整数规划 max 2=C x s.t. Ax= b (MIP) x≥0,整数j∈N∈{2,…,n x≥0,j∈{2…,n\N 显然,当N=时,(MP)即为标准形线性规划问题(LP):当N={1,2,…,n}时,(MP)即 为纯整数规划(lP) 3.0-1规划(Bo0规划,BIP, Boolean integer programming:x=01,=1,2,…,n max 2=C x (BIP): s.L. Ax=b 0,1, 例1(背包问题, knapsack problem)今将m种物品装入容积为b的背包中.第j种物品的体积为 a,价值为c,j=1,2,…,n,问:应如何选择物品装入背包中,才能使得装入物品的总体积不超 过背包的容积,且总价值最大? 解:令 ∫,装入第j种物品 ,j=1,2,…,n,则可建立0-1规划 0,否则运 筹 学 讲 义 1 §6.1 整数规划 整数规划（IP，integer programming）：决策变量的全部或部分取整数值的线性规划. 显然，整数规划去掉对决策变量的整数性要求即为一般线性规划问题. 分类： 1.纯（全）整数规划（IP，AIP，accurate（all，pure） integer programming）：全部决策变量均取 整数值的整数规划.       = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数  2.混合整数规划（MIP，mixed integer programming）：决策变量的一部分取整数值的整数规划.             = = x j n N x j N n st Ax b z c x MIP j j T 0, {1,2, , } \ 0, , {1,2, , } . . max ( ) :  整数  显然，当 N =  时， (MIP) 即为标准形线性规划问题 (LP) ；当 N = {1,2,  ,n} 时， (MIP) 即 为纯整数规划 (IP) . 3.0-1 规划（Bool 规划，BIP，Boolean integer programming）： x j = 0,1, j = 1,2,  ,n .      = = = = x j n st Ax b z c x BIP j T 0,1, 1,2, , . . max ( ) :  例 1（背包问题，knapsack problem）今将 m 种物品装入容积为 b 的背包中.第 j 种物品的体积为 j a ，价值为 j c ， j = 1,2,  , n ，问：应如何选择物品装入背包中，才能使得装入物品的总体积不超 过背包的容积，且总价值最大？ 解：令 j n j x j , 1,2, , 0, 1, =     = 否则， 装入第 种物品， ，则可建立 0-1 规划