《运筹学》课程教学讲义（Operations Research）第六章（6.1）整数规划

运筹学讲义 §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 规划

运筹学讲义 x,=0,,j=1,2 注:(1)小偷!(2)求解:redy算法 例2(下料问题)今利用一批钢材下零件,有关数据如下表所示: 材可下零方式 件的 件的数量 B1B2…B2需求量 A2 A b 零件的单价 问:应如何安排下料,才能使得既满足零件的需求量,又费用最省? 解:设采用下料方式B,下料的钢材的数量为x,j=1,2,…,n,则可建立如下数学模型 mn st b,i=1,2,…,m,l x≥0,整数,j=1,2,…,n 例3(分派问题, assignment problem)今分派n个工人W1,W2,…,Wn去从事n项工作J12J2…J 已知工人W从事工作J,的胜任指数(即工作效率)为c,,j=12,…,n.试求一个分派方案,使得 每个工人都从事一项工作,每项工作都有一个工人承担,且总胜任指数最大 解:令

运 筹 学 讲 义 2          = =  =   = = x j n st a x b z c x j n j j j n j j j 0,1, 1,2, , . . max 1 1  .▌ 注：（1）小偷！（2）求解：Greedy 算法. 例 2（下料问题）今利用一批钢材下零件，有关数据如下表所示： 问：应如何安排下料，才能使得既满足零件的需求量，又费用最省？ 解：设采用下料方式 Bj 下料的钢材的数量为 x j , j = 1,2,  ,n ，则可建立如下数学模型           = = = =   = = x j n st a x b i m z c x j i n j ij j n j j j 0, , 1,2, , . . , 1,2, , min 1 1   整数 .▌ 例 3（分派问题，assignment problem）今分派 n 个工人 W W Wn , , , 1 2  去从事 n 项工作 n J , J , , J 1 2  . 已知工人 Wi 从事工作 j J 的胜任指数（即工作效率）为 cij ,i, j = 1,2,  ,n .试求一个分派方案，使得 每个工人都从事一项工作，每项工作都有一个工人承担，且总胜任指数最大. 解：令

运筹学讲义 ∫分派工人H从事工作 0,否则, ,i,j=1,2 则可建立0-1规划 nax二 Cix s.∑x1=1=12…,n x x=0,1,=12,…,n 注:分派问题实际上是一种特殊形式的运输问题(见§1.1例3) 例4(设施选址问题, facility location) 原有电厂 年用煤量年固定费用 今有m座煤矿 b 内1 2 h2 |要新建一个 年产量a单位运费40>厂址有个b b 问:应如何选址设厂并组织运输,才能既满足新旧电厂的用煤量,又使得年运行费用(包括固定 费用和运费)最少? ∫,厂址j被选中 解:令y-0,否则, x=每年煤矿i运往电厂j的煤的数量,i=1,2,…,m,j=1,2,…,n, 则可建立整数规划

运 筹 学 讲 义 3 i j n W J x i j ij , , 1,2, , 0, , 1, , =     = 否则 分派工人 从事工作 ， 则可建立 0-1 规划            = = = = = = =    = = = = x i j n x j n st x i n z c x ij m i ij n j ij m i n j ij ij 0,1, , 1,2, , 1, 1,2, , . . 1, 1,2, , max 1 1 1 1    .▌ 注：分派问题实际上是一种特殊形式的运输问题（见§1.1 例 3）. 例 4（设施选址问题，facility location） 问：应如何选址设厂并组织运输，才能既满足新旧电厂的用煤量，又使得年运行费用（包括固定 费用和运费）最少？ 解：令 j n j y j , 1,2, , 0, 1, =     = 否则， 厂址 被选中， ， xij = 每年煤矿 i 运往电厂 j 的煤的数量， i = 1,2,  ,m, j = 1,2,  ,n ， 则可建立整数规划

运筹学讲义 min 2= h+∑hy+∑∑ st a1,=1,2 ∑∑∑ xu=by,j=1, 2, y x20,=12,…m,j=1,2 注:混合整数规划

运 筹 学 讲 义 4                   = = = = = = = = = = = + +       = = = = = = = x i m j n y j n x by j n x b y st x a i m z h h y c x j j j m i ij m i i n j j i n j ij m i n j ij ij n j j j 0, 1,2, , , 1,2, , 0,1, 1,2, , , 1,2, , 1 . . , 1,2, , min 1 0 1 0 1 1 1 1 0 0      .▌ 注：混合整数规划