【运筹学】分支定界法 ( 分支定界法相关概念 | 分支定界法求解整数规划步骤 | 分支定界理论分析 | 分支过程示例 )

韩曙亮

发布于 2023-03-28 20:50:36

9180

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、分支定界法相关概念

分支定界法相关概念 :

分支 : 将一个问题不断细分为若干子问题 , 之后逐个讨论子问题 ;

定界 : 分支很多的情况下 , 需要讨论的情况也随之增多 , 这里就需要定界 , 决定在什么时候不在进行分支 ; 满足 ① 得到最优解 , ② 根据现有条件可以排除最优解在该分支中 , 二者其一 , 就可以进行定界 ;

定界的作用是剪掉没有讨论意义的分支 , 只讨论有意义的分支 ;

二、分支定界法求解整数规划步骤

分支定界法求解整数规划步骤 :

( 1 ) 求整数规划的松弛问题最优解 :

如果该最优解就是整数 , 那么得到整数规划最优解 ;

如果该最优解不是整数 , 那么转到下一个步骤分支与定界 ;

( 2 ) 分支与定界 :

任选一个非整数解变量

x_i

, 在松弛问题中加上约束 :

x_i \leq [x_i]

和

x_i \geq [x_i] + 1

形成两个新的松弛问题 , 就是两个分支 ;

上述分支 , 分的越细致 , 限制条件越多 , 同时最优解的质量就越差 ;

新的分支松弛问题特征 :

原问题求最大值时 , 目标值是分支问题的上界 ;
原问题求最小值时 , 目标值是分支问题的下界 ;

分支

的最优解是

x^*

, 将最优解代入目标函数后得到最优值

f_1

;

分支

的最优解是

y^*

, 将最优解代入目标函数后得到最优值

f_2

;

如果目标函数求最大值 , 那么就讨论

f_1, f_2

谁更大 ;

检查分支松弛问题的解及目标函数值 :

① 得到最优整数解 : 如果该分支的解是整数 , 并且目标函数值大于等于其它分支的目标值 , 则剪去其它分支 , 停止计算 ;

② 没有得到最优整数解 : 如果该分支的解是小数 , 并且目标函数值大于整数解的目标值 , 需要继续进行分支 , 直到得到最优解 ;

三、分支定界理论分析

假设考虑分支

松弛问题 , 每次都要给问题找到一个界 , 开始先使用观察法找到一个界 , 找到一个整数解

, 将该解代入目标函数 , 然后在不断地计算中, 修改该界 ;

假设分支

松弛问题目标函数求最大值 ,

如果求解分支

松弛问题最优解恰好也是一个整数解

f_0

, 如果

f_0 > f

, 此时需要重新定界 , 将

f_0

作为新的界来讨论 ;

根据新的界来看分支

松弛问题是否需要讨论 , 求出分支

的最优解对应的目标函数最优值

f^*

;

如果分支

的最优值小于分支

的最优值

f^* \leq f^0

, 此时分支

不用再进行分支了 , 再进行分支 , 其最优值会越来越差 ;

定界法的作用是将不符合条件的分支剪去 ;

四、分支过程示例

如上篇博客【运筹学】整数规划 ( 整数规划问题解的特征 | 整数规划问题与松弛问题示例 ) 中 , 求解如下整数规划解 :

\begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \ 并且为整数 \end{cases}\end{array}

其对应的松弛问题是 : 去掉整数解限制 ;

\begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}

分支都是基于松弛问题进行的 , 为松弛问题分支 , 组成两个新的松弛问题 ;

下图是求解结果 ( 图解法 ) :

最优解

x_1 = \cfrac{3}{2}

, 分别为

x_1

添加

x_i \leq [x_i]

和

x_i \geq [x_i] + 1

约束 , 形成两个新的线性规划 ;

分支

整数规划 : 添加

x_i \leq [x_i]

约束 , 即

x_1 \leq 1

;

\begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}

分支

整数规划 : 添加

x_i \geq [x_i] +1

约束 , 即

x_1 \geq 2

;

\begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}

这样就将一个线性规划 , 分解成了两个问题分支 , 分别找两个分支问题的所有整数解 ;

整数规划的整数解 , 肯定在上述两个分支之一中 , 中间将一部分可行域排除在外了 , 就是下图中两个红色箭头之间的可行域部分 , 被排除掉的部分肯定没有整数解 , 都是小数 ;