Chapter4整数规划 Integer Programming) 本章主要内容： ·整数规划的特点及应用 。分支定界法 ·分配问题与匈牙利法
Chapter4 整数规划 ( Integer Programming ) 整数规划的特点及应用 分支定界法 分配问题与匈牙利法 本章主要内容：
整数规划的特点及应用 Page2 整数规划（简称：P) 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。不考虑整数条件，由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题。若该松弛问 题是一个线性规划，则称该整数规划为整数线性规划。 整数线性规划数学模型的一般形式： maxZ(或minZ)=∑c,x, 20,x=bi=12m x,≥0(0=1.2.n)且部分或全部为整数
整数规划的特点及应用 Page 2 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。不考虑整数条件，由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题。若该松弛问 题是一个线性规划，则称该整数规划为整数线性规划。 整数线性规划数学模型的一般形式： = = = = = = 且部分或全部为整数 或 0 (j 1.2 n) ( 1.2 ) max ( min ) 1 1 j n j ij j i n j j j x a x b i m Z Z c x
整数规划的特点及应用 Page 3 整数线性规划问题的种类： ·纯整数线性规划：指全部决策变量都必须取整数值的整数 线性规划。 ·混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。 ·0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划
整数规划的特点及应用 Page 3 整数线性规划问题的种类： 纯整数线性规划：指全部决策变量都必须取整数值的整数 线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划
整数规划的特点及应用 Page 4 整数规划的典型例子 例4.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费c,见下表： B1 B2 B3 B4 年生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 > 6 1 2 200 A4 4 5 2 5 200 年需求量 350 400 300 150 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万 元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用 最少
整数规划的特点及应用 Page 4 整数规划的典型例子 例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1 ,B2 ,B3 ,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费cij，见下表： B1 B2 B3 B4 年生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 年需求量 350 400 300 150 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万 元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用 最少
整数规划的特点及应用 Page 5 解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量： 若建工厂 若不建工厂 (i=1,2) 再设x为由A运往B的物资数量，单位为千吨；表示总费用， 单位万元。 则该规划问题的数学模型可以表示为：
整数规划的特点及应用 Page 5 解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量： ( 1,2) 0 1 = y = i i 若不建工厂 若建工厂 再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用， 单位万元。 则该规划问题的数学模型可以表示为：
整数规划的特点及应用 Page 6 mimz=22,+200,+1500 x1+x21+x31+x41=350 x12+x22+x32+x42=400 X13+X23+x33+x43=300 x14+x24+x34+x4=150 〉 混合整数规划问题 x11+x12+x13+x14=400 s.t x21+x2+x23+x24=600 x31+x32+x33+x34=200y1 x1+x42+x3+x4=200y2 x≥0(i,j=1,2,3,4) y:=0,1(i=1,2)
整数规划的特点及应用 Page 6 = = = + + + = + + + = + + + = + + + = + + + = + + + = + + + = + + + = = + + = = 0,1 ( 1,2) 0 ( , 1,2,3,4) 200 200 600 400 150 300 400 350 . min [1200 1500 ] 4 1 4 2 4 3 4 4 2 3 1 3 2 3 3 3 4 1 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 1 4 2 4 3 4 4 4 1 3 2 3 3 3 4 3 1 2 2 2 3 2 4 2 1 1 2 1 3 1 4 1 4 1 4 1 1 2 y i x i j x x x x y x x x x y x x x x x x x x x x x x x x x x x x x x x x x x s t z c x y y i ij i j ij ij 混合整数规划问题
整数规划的特点及应用 Page 7 例4.2现有资金总额为B。可供选择的投资项目有n个，项目 j所需投资额和预期收益分别为a和c(j=1,2,n),此外由 于种种原因，有三个附加条件： ·若选择项目1，就必须同时选择项目2。反之不一定 ·项目3和4中至少选择一个； ·项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大
整数规划的特点及应用 Page 7 例4.2 现有资金总额为B。可供选择的投资项目有n个，项目 j所需投资额和预期收益分别为aj和cj（j＝1,2,.,n），此外由 于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大
整数规划的特点及应用 Page 8 解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令x表示第j个项目的决策选择，记为： 对项目投资 对项目不投资 j=1,2m 投资问题可以表示为： max =2c,x j=1 公sa 2≥x S.t x3+x4≥1 x5+x6+x7=2 x,=0或者1 (j=1,2,.n)
整数规划的特点及应用 Page 8 解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为： ( 1,2,., ) 0 1 j n j j xj = = 对项目 不投资 对项目 投资 投资问题可以表示为： = = + + = + = = = x 或 者 （ n） x x x x x x x a x B s t z c x j n j j j n j j j 0 1 j 1,2, 2 1 . max 5 6 7 3 4 2 1 1 1
整数规划的特点及应用 Page 9 例4.3指派问题或分配问题。人事部门欲安排四人到四个不 同岗位工作，每个岗位一个人。经考核四人在不同岗位的成 绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作 A B D 人员 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 19 90 丁 86 90 80 88
整数规划的特点及应用 Page 9 例4.3 指派问题或分配问题。人事部门欲安排四人到四个不 同岗位工作，每个岗位一个人。经考核四人在不同岗位的成 绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88
整数规划的特点及应用 Page 10 设 分配第人做工作时 不分配第人做工作时 数学模型如下： maxZ=85x11+92x12+73x13+90x14+95x21+87x22+ +78x23+95x24+82x31+83x32+79x33+90x34+ +86x41+90x2+80x43+88x44 要求每人做一项工作，约束条件为： x1+x2+x13+X14=1 X21+x22+X23+x24=1 尤31+x32+x3+X34=1 x1+x42+x43+x44=1
整数规划的特点及应用 Page 10 设 = 不分配第人做 工作时 分配第 人做 工作时 i j i j xij 0 1 数学模型如下： 4 1 4 2 4 3 4 4 2 3 2 4 3 1 3 2 3 3 3 4 1 1 1 2 1 3 1 4 2 1 2 2 8 6 9 0 8 0 8 8 7 8 9 5 8 2 8 3 7 9 9 0 max 8 5 9 2 7 3 9 0 9 5 8 7 x x x x x x x x x x Z x x x x x x + + + + + + + + + + + = + + + + + + 要求每人做一项工作，约束条件为： + + + = + + + = + + + = + + + = 1 1 1 1 4 1 4 2 4 3 4 4 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 x x x x x x x x x x x x x x x x