
简单介绍分支界定法与割平面法.doc
2页简单介绍分支界定法与割平面法 缺点: 某些变量要求整数 不能运用到对数,指数函数中 分支界定法: 分枝定界法是一个用处非常广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不一样分支定界法的根本思想是对有约束条件的最优化问题的所有可行解〔数目有限〕空间进展搜索该算法在详细执行时,把全部可行的解空间不断分割为越来越小的子集〔称为分支〕,并为每个子集内的解的值计算一个下界或上界〔称为定界〕在每次分支后,对但凡界限超出可行解值那些子集不再做进一步分支这样,解的许多子集〔即搜索树上的许多结点〕就可以不予考虑了,从而缩小了搜索范围这一过程一直进展到找出可行解为止,该可行解的值不大于任何子集的界限 分枝定界法已经成功地应用于求解整数规划问题、消费进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题 割平面法: 它的根本思想和分枝界定法根本上一致,首先不考虑变量的整数约束,利用单纯形法求解出线性规划的最优解,假设得到的解是整数那么这个最优解就是原来问题的最优解,假设最优解不是整数解,那么就用一张平面将原来的含有最优解的非整数点但不包含整数可行解的点的那一局部可行域切割掉,也就是在原来的整数线性规划的根底上增加适当的线性约束不等式,这个约束不等式就叫切割不等式当其取等号时就是割平面了。
此后,继续解这个新得到的整数线性规划,假设得到的新最优解是整数,运算就停顿,假设不是整数那么继续增加适当的线性约束不等式,直到求出的解满足最优整数要求为止 通过构造一系列平面来切割掉不含有任何整数可行解的局部,最终获得一个具有整数坐标的顶点的可行域,而该顶点恰好是原整数规划的最优解割平面法的关键在于,如何构造切割不等式,使增加该约束后能到达真正的切割而且没有切割掉任何整数可行解 单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解,直到检验数满足最优性条件为止单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解,直到检验数满足最优性条件为止 第 页 共 页。












