整数线性规划ILP

第7章 整数线性规划（ILP） 在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些具体问题常要求解答是整数。我们称这样的线性规划问题为整数线性规划问题（Integer Linear Programming 简记为ILP）,整数规划是近20年来发展起来的规划论的一个分支。
一、数线性规划问题的提出 整数规划中如果所有的变量都限制为（非负）整数，就称为纯整数规划（Pure ILP）,如果仅一部分变量限制为整数，就称为混合整数规划（Mixed ILP）,整数规划的一个特例就是0—1规划，他的变量仅取0或1。
整数线性规划问题举例 1、  投资决策问题 某部门在今后五年中可用于投资的资金总额为B万元，有n(n 2)个可以投资的项目，假定每个项目最多投资一次，第j个项目所需投资资金为 万元，获得的利润为 万元， 问如何选择投资项目，才能使获得的总利润最大。
设获得的总利润为z，则上述问题的数学模型为：

显然上述是一个决策变量只能取0或1的整数规划问题，这样的整数规划问题称为0——1规划。决策变量取0或1这个约束可以用一个非线性约束来代替：
2、  某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获得的利润及托运所受的限制入下表：

解：设 分别为甲乙两种货物的托运箱数，设获得的总利润为z，则上述问题的数学模型为：
3、旅行售货员问题（货郎担问题）


第一组约束条件表示各个城市恰好进入一次，第二约束条件表示各个城市恰好离开一次，第三组约束条件用以防止出现对于一个互不连通的旅行路线圈。 显然这是一个混合整数规划问题。
二、整数线性规划问题的求解 ——割平面法
（1）       基本思想 给出整数规划
可先求其对应的线性规划问题

  （2）割平面法求解ILP问题的一般步骤




三、整数线性规划问题的求解 ——分枝定界法（Branch and Bound Method）
1）基本思想 分枝定界法求解整数规划问题的基本思想是：通过分枝枚举来寻找最优解。实施的作法是：首先不考虑对变量的整数要求，求解相应的线性规划问题，如求得的最优解不符合整数要求，则把原问题分解为两部分，每一部分都增加新的约束条件以减小原线性规划问题的可行域。通过不断地分解，逐步逼近满足要求的最优解，直到求得最优解。在这个过程中包括了"分枝"和"定 界"两个关键步骤。
（2）分枝定界法求解ILP问题的一般步骤 根据分枝定界法的基本思想，人们归纳总结出了分枝定界法求解整数规划问题的一般步骤，这里以求目标函数值最大化问题为例加以说明：  给出整数规划
可先求其对应的线性规划问题





分枝定界法可用于解纯整数规划问题，也可以用于求混合整数规划问题。在20世纪60年代初由Land和Dong提出经Dakin修正的，其优点是方法灵活并且十分便于计算机求解，所以现在它已成为求解整数规划的重要方法之一，目前已成功地应用于求解整数规划问题、生产进度表问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。分枝定界法比穷举法优越，因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小，但若变量数目很大，其计算工作量也是相当可观的。因此，它有时也需要与其他方法(如切割平面法)配合使用，效率更高一些。  
四、ILP问题的计算机求解

整数线性规划ILP