整数规划的特点及分类分支定界法0-1规划指派问题本章主要内容：整数规划的特点及分类第一节整数规划的特点及分类整数规划的特点及分类整数规划（简称：ILP） 要求一部分或全部决策变量取整数值的线性规划问题称为整数线性规划。整数线性规划数学模型的一般形式：整数规划的特点及分类整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。整数规划的特点及分类例4.1设整数规划问题如下首先不考虑整数约束，得到对应的线性规划问题整数规划的特点及分类用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6 现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3) 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。枚举法整数规划的特点及分类整数规划问题的求解方法：分支定界法和割平面法匈牙利法（指派问题）第二节分支定界法第三节0-1整数规划0-1型整数线性规划（决策变量只能取值0或1的整数线性规划）背包问题运动员选拔问题选址问题固定费用问题整数规划的应用（0-1规划）例1.（背包问题）一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能携带115kg的物品。现有5件物品，分别重54，35，57，46，19(kg)，其价值依次为7，5，9，6，3。问该旅行者携带哪些物品，使总价值最大？解：设则有：整数规划的应用（0-1规划）例2（运动员选拔问题）某篮球队拟从编号为1,2，…,6的6名预备运动员中挑选出3名正式队员，要求他们的平均身高尽量高。此外，入选运动员还需符合以下条件：（1）至少一名后卫（2）2号与5号至多只能入选1名（3）最多入选一名中锋（4）若2号或4号入选，则6号不能入选整数规划的应用（0-1规划）编号位置身高1中锋1.932中锋1.913前锋1.874前锋1.865后卫1.806后卫1.85（1）至少一名后卫（2）2号与5号至多只能入选1名（3）最多入选一名中锋（4）若2号或4号入选，则6号不能入选整数规划的应用（0-1规划）例3.现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。整数规划的应用（0-1规划）解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：投资问题可以表示为：整数规划的应用（0-1规划）例4（选址问题）现有如图所示的A,B,C,D,E共5个新开发的小区，其间都有主要干道相连接。现为救火的需要，需建立一个消防系统，要求在15分钟内能及时到达任一小区。问如何设置消防站，既能满足消防要求，又使设置的消防站数量最少？整数规划的应用（0-1规划）ACDEB101515202515ABCDEA010153030B100253520C152501530D303515015E302030150整数规划的应用（0-1规划）整数规划的应用（0-1规划）例5.工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。解：这是一