整数线性规划(ILP)PPT课件

《整数线性规划(ILP)PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章整数线性规划（ILP）在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些具体问题常要求解答是整数。我们称这样的线性规划问题为整数线性规划问题（IntegerLinearProgramming简记为ILP）,整数规划是近20年来发展起来的规划论的一个分支。一、数线性规划问题的提出整数规划中如果所有的变量都限制为（非负）整数，就称为纯整数规划（PureILP）,如果仅一部分变量限制为整数，就称为混合整数规划（MixedILP）,整数规划的一个特例就是0—1规划，他的变量仅取0或1。整数线性规划问题举例1、投资决策问题某部门在今后五年中

2、可用于投资的资金总额为B万元，有n(n2)个可以投资的项目，假定每个项目最多投资一次，第j个项目所需投资资金为万元，获得的利润为万元，问如何选择投资项目，才能使获得的总利润最大。设获得的总利润为z，则上述问题的数学模型为：解：设投资决策变量为问两种货物各托运多少箱，可使得利润最大？解：设分别为甲乙两种货物的托运箱数，设获得的总利润为z，则上述问题的数学模型为：3、旅行售货员问题（货郎担问题）第一组约束条件表示各个城市恰好进入一次，第二约束条件表示各个城市恰好离开一次，第三组约束条件用以防止出现对于一个互不连通的旅行路线圈。显然这是一个混合整数规划

3、问题。二、整数线性规划问题的求解——割平面法（1）基本思想给出整数规划可先求其对应的线性规划问题（2）割平面法求解ILP问题的一般步骤三、整数线性规划问题的求解——分枝定界法（BranchandBoundMethod）1）基本思想分枝定界法求解整数规划问题的基本思想是：通过分枝枚举来寻找最优解。实施的作法是：首先不考虑对变量的整数要求，求解相应的线性规划问题，如求得的最优解不符合整数要求，则把原问题分解为两部分，每一部分都增加新的约束条件以减小原线性规划问题的可行域。通过不断地分解，逐步逼近满足要求的最优解，直到求得最优解。在这个过程中包括了"

4、分枝"和"定界"两个关键步骤。（2）分枝定界法求解ILP问题的一般步骤根据分枝定界法的基本思想，人们归纳总结出了分枝定界法求解整数规划问题的一般步骤，这里以求目标函数值最大化问题为例加以说明： 给出整数规划可先求其对应的线性规划问题分枝定界法可用于解纯整数规划问题，也可以用于求混合整数规划问题。在20世纪60年代初由Land和Dong提出经Dakin修正的，其优点是方法灵活并且十分便于计算机求解，所以现在它已成为求解整数规划的重要方法之一，目前已成功地应用于求解整数规划问题、生产进度表问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。分枝

5、定界法比穷举法优越，因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小，但若变量数目很大，其计算工作量也是相当可观的。因此，它有时也需要与其他方法(如切割平面法)配合使用，效率更高一些。四、ILP问题的计算机求解