整数线性规划.ppt

教学要求： 整数规划的一般模型 应用与实例 在现实生活中，经常遇到一些需要变量取整数才有实际意义的问题，例如制定计划、规划时需要确定工人的人数，设备的台数等。 许多有名的最优化问题，如旅行商问题、背包问题、下料问题、工序安排问题等，也都可以归结为整数规划问题。 整数规划建模举例 某财团有 万元的资金，经过其考察选中 个投资 项目，其中第 个项目需投资金额为 万元，预 计获利 （ ）万元，由于种种原因， 有两个附加条件：第一，项目2和项目3至少选择一 个；第二项目5，6，7恰好选择两个。问应如何选 择项目使得总收益最大？ * * 整数规划 ?掌握线性整数规划的建模方法，特别是0-1变量的运用 ?了解整数规划的求解方法 ?掌握指派问题的求解方法 整数线性规划定义 要求全部或部分决策变量的取值为整数的规划问题，称为整数规划(Integer Programming)。 要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划(Integer Linear Programming，ILP)。 全部决策变量的取值都为整数，则称为全（纯）整数规划 仅要求部分决策变量的取值为整数，则称为混合整数规划 要求决策变量只取0或1值，则称0-1整数规划 第一节 整数规划问题 整数规划建模举例 5 6 单台利润 35 7 5 B 9 1 2 A 现有量 乙 甲 产品 资源 例1：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示： 问如何安排甲、乙两产品的产量，使利润为最大。 解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整数 纯整数规划 例2：组合投资问题。 要决策的是每个项目是否需要投资 例2：组合投资问题。 0-1整数规划 例3：某产品有n 个区域市场，各区域市场的需求量为 bj 吨/月；现拟在m 个地点中选址建生产厂，一个地方最多只能建一家工厂；若选 i 地建厂，生产能力为 ai 吨/月，其运营固定费用为Fi 元/月；已知址i至j区域市场的运价为 cij 元/吨。如何选址和安排调运，可使总费用最小？ 解：选址建厂与否是个0-1型决策变量， 设 yi =1，选择第 i 址建厂， yi=0，不选择第 i 址建厂； 计划从 i 址至区域市场 j 的运输运量xij为实数型决 策变量。 整数规划建模举例 混合整数规划 特征—变量整数性要求 来源 问题本身的要求 引入的逻辑变量的需要 性质—可行域是离散集合 整数规划 松弛的线性规划 整数规划可行解是松弛问题可行域中的整数格点 ILP最优值小于或等于松弛问题的最优值 第二节 整数线性规划求解 松弛问题无可行解，则整数规划无可行解； 松弛问题最优解满足整数要求，则该最优解为整数规划最优解； 一、舍入化整法 为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能超出了可行域，成为非可行解；或者虽是可行解，却不是最优解。 二、枚举整数法 对于决策变量少，可行的整数解又较少时，这种枚举法有时是可行的，并且也是有效的。 但对于大型的整数规划问题，可行的整数解数量很多，用枚举法求解是不可能的。 5x1 +7 x2 =35 2x1 + x2 =9 ? (3,3) ? ? ? ? ? ? ? ? ? ? x1 x2 1 2 3 1 2 5 3 4 4 三、分支定界法 不考虑整数限制先求出相应松弛问题的最优解， 若松弛问题无可行解，则ILP无可行解； 若求得的松弛问题最优解符合整数要求，则是ILP的最优解； 若不满足整数条件，则任选一个不满足整数条件的变量 来构造新的约束添加到松弛问题中形成两个子问题 依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述过程，直到子问题无解或有整数最优解（被查清）。 在分支的过程中，若当前已经得到的满足整数要求 的最优值为 ，则该 就可是作为一个过滤条 件，对于最优值小于或等于 的子问题无需再分 支，则这样的子问题称为被剪枝。未被剪枝的子问 题需继续分支。 分支定界法的最终子问题要么被查清要么被剪枝。 分支定界法求解举例 0 1 2 3 1 2 3 0 1 2 3 1 2 3 0 1 2 3 1 2 3 x1 ≥ 2 x1 ≤ 1 x2 ≥3 x2≤2 x1