第5章整数规划第1，2节 运筹学ppt.pptVIP

第5章 整数规划 第1节 整数规划的数学模型及解的特点 第2节 分支定界法 第3节 割平面法 第4节 0-1整数规划 第5节 指派问题 第1节 整数规划的数学模型及解的特点 整数规划数学模型的一般形式 全部决策变量取整数值的规划问题: ——纯整数规划（Pure Interger Programming,PIP） 部分变量取整数的规划问题: ——混合整数规划（Mixed Interger Programming,MIP） 全部决策变量取0或1的规划问题: ——0-1规划（Binary Interger Programming,BIP） 整数规划中不考虑整数条件所对应的规划问题: ——该整数规划的松弛问题 整数线性规划的几种类型 谢 谢！ *整数规划 * * 整数线性规划一般形式： 中部分或全部取整数 纯整数线性规划 混合整数线性规划 0-1型整数线性规划 整数规划与线性规划的关系 从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。 但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。 举例说明。 例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。 用图解法求出最优解 x1＝3/2, x2 = 10/3 且有Z = 29/6 x1 x2 ⑴ ⑵ 3 3 (3/2,10/3) 现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。 1 2 1 2 (1) (2) 因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。 如上例：其中（2，2）（3，1）点为最大值，Z=4。 目前，常用的求解整数规划的方法有： 分支定界法和割平面法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。 第2节 分支定界法 (branch and bound method) （一）、基本思路 考虑纯整数问题： 整数规划问题的 线性问题： 1、先不考虑整数约束，解( IP )的线性规划问题( LP )，可能得到以下情况之一： ⑴ 若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ⑵ 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ⑶ 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。为讨论方便，设( LP )的最优解为： 2、定界： 记( IP )的目标函数最优值为Z* ,以Z(0) 作为Z* 的上界，记为 ＝ Z(0) 。再用观察法找出一个整数可行解 X′，并以其相应的目标函数值 Z′作为Z* 的下界，记为Z＝ Z′,则有： Z ≤ Z* ≤ 3、分枝： 在( LP )的最优解 X(0)中，任选一个不符合整数条件的变量，例如xj= （不为整数），以 表示不超过 的最大整数。构造两个约束条件 xj≤ 和xj≥ ＋1 如此反复进行，直到得到Z＝Z*＝ 为止，即得最优解 X* 。 将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个问题的松弛问题( LP1)和( LP2) 。 4、修改上、下界：按照以下两点规则进行。 ⑴在各分枝问题中，找出目标函数值最大者作为新的上界； ⑵从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。 5、比较与剪枝 ： 各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。 例：求解整数规划问题A 且为整数 松弛问题B 设问题B的最优目标函数值为 。 整数规划问题A 初始上界 图解法分析： 、 、 、 、 、 、 、 、 、 、 、 0