整数规划割平面法分枝定界法.ppt

运 筹 学; §1 整数规划问题; 下面我们举例说明对于整数规划问题，用“四舍五入”取整，或“舍尾取整”方法，是行不通的。 例1 现有甲、乙两种货物拟用集装箱托运，每件货物的体积、重量、可获利润，以及集装箱的托运限制如下表：;这里货物的件数只能是整数，所以这是一个纯整数规划。若先不考虑整数限制，可求得问题的最优解为： x1=4.8，x2=0， maxZ=96 由于x1=4.8不符合整数要求，所以该解不是整数规划的最优解。 是否可以将非整数解用“四舍五入”方法处理呢？事实上，如果将x1=4.8，x2=0近似为x1=5，x2=0，则该解不符合体积限制条件⑵： 5x1+4x2≤24 因而它不是最优解； 那么用“舍尾取整”方法处理又如何呢？将x1=4.8，x2=0 “舍尾取整”为x1=4，x2=0，显然满足各约束条件，因而它是整数规划问题的可行解，但它不是整数最优解。因为它对应的目标函数值Z=80，而x1=4，x2=1这个解亦是可行解，但它对应的目标函数值Z=90。 由此例看出，简单的处理方法常常得不到整数规划的最优解，甚至得不到可行解。 如何求得这类问题的整数最优解呢？到目前为止，整数规划还没有一种很满意的和有效的解法。现在用以求解整数规划的方法基本都是将整数规划变为一系列线性规划来求解的。我们将介绍两种方法——割平面法和分枝定界法。 ;§2 割平面法; 割平面法的关键在于如何确定切割方程，使之能对可行域进行真正的切割，而且切去部分不含有整数解点。 下面讨论切割方程的求法。;从而 fi-ΣfijXj≤0 ⑸ 取⑸式作为切割方程。因为任何整数可行解都满足这个方程，所以把它加到原问题的约束中，它能够对原可行域进行切割，而不会切割掉整数解。;;;现在我们来看看切割方程 3x3+x4 ≥3 的几何意义。 例3对应的线性规划为 maxZ=x1+x2 -x1+x2≤1　 3x1+x2≤4　 x1,x2≥0; 在求解实际问题中，割平面法经常会遇到收敛很慢的情况，但若和其它方法，如分枝定界法，联合使用，一般能收到比较好的效果。; §3 分枝定界法; 例2 求解下面整数规划 maxZ=40x1+90x2 ⑴ 9x1+ 7x2≤56　 ⑵ 7x1+20x2≤70　 ⑶ x1,x2≥0　　　　⑷ 　　　　 x1,x2　整数 　　 ⑸;;整个分枝定界过程如下图所示：; 用分枝定界法求解整数规划的步骤可总结如下： 步骤1：求解与整数规划相对应的线性规划L，若L无可行解，则整数规划也没有可行解，计算停；若L的最优解是整数解，则该解即为整数规划的最优解，计算停；若L的最优解不是整数解，则转步骤2。 步骤2（分枝）在L的最优解中任选一个不符合整数条件的变量XBi，其值为（B-1b)i，[（B-1b)i ]为小于（B-1b)i的最大整数，构造两个约束条件 XBi ≤ [（B-1b)i ]和XBi≥ [（B-1b)i ] +1 将这两个约束条件分别加在问题L的约束条件上，形成两个子问题L1和L2，并求解L1和L2 。 步骤3（定界 ）取整数解中最大目标值为界限值Z(下界)，如果计算中尚无整数解，则取Z=-∞。检查分枝Li，若它的最优解不是整数解，且Zi＞Z，则重复步骤2，若Zi≤Z，则Li不再分枝。 重复步骤2、步骤3，直至所有分枝都不能再??解为止，这时界限值Z对应的整数解即为原问题的最优解。 用分枝定界法可解纯整数规划问题和混合整数规划问题。它比穷举法优越，因为它仅在一部分可行的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可