【无标题】_分枝定界法和割平面法的区别

作者：IT小白 | 2024-03-10 19:10:24

踩

分枝定界法和割平面法的区别

本期我们进行运筹学之整数规划的讲解，我们将对割平面法和分支定界法的基础知识进行一个简单的回顾，并介绍求解割平面法的Python相关代码以及分支定界法的MATLAB和Python相关代码，以帮助大家利用工具快速求解整数规划问题，做到事半功倍。话不多说，我们一起来看看吧！

一、基础知识

1、整数线性规划的数学模型及解的特点

★ 整数线性规划模型的一般形式

★ 整数线性规划的类型

★ 解的特点

★ 求解方法分类

（1）割平面法—可求纯或混合整数线性规划；

（2）分支定界法—可求纯或混合整数线性规划；

（3）隐枚举法—求解“0-1”整数规划；

（4）匈牙利法—求解指派问题（“0-1”整数规划特殊情形）。

割平面法和分支定界法都是精确算法，在组合优化领域用于寻求最优组合方案，二者利用各自的方法不断增加约束、缩小解空间，再通过单纯形法得出新的解空间下的最优解，最后判断新解是否为整数，不是则继续迭代。本期我们将对割平面法和分支定界法的求解步骤及其算法实现进行介绍。

★ 算法比较

2、割平面法

★ 基本思路

先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止；如果得到的最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)，而把所有的整数解都保留下来，故称新增加的约束条件为割平面。当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

★ 求解流程

3、分支定界法

分支定界法是一种搜索与迭代的方法，是在枚举法基础上的改进，其关键是分支和定界。所谓分支，是将非整数值的决策变量分割为与之最接近的两个整数，分列条件，加入原问题中，形成两个后继问题，分别求解，从而把全部可行解空间反复地分割为越来越小的子集；所谓定界，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么它的目标函数值就是一个界限，可以作为衡量处理其他分支的一个依据。“分支”为整数规划最优解的出现缩减了搜索范围，而“定界”则可以提高搜索的效率。

设有最大化的整数规划问题A，它的松弛问题为问题B。从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z* 的上界，记作z ；而z 的任意可行解的目标函数值将是z 的一个下界z 。分枝定界法就是把B的可行域分成子区域，逐步减小z 和增大z ，最终求到z* 。其求解流程如下：