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

2023-03-28 20:50:36 浏览数 (1)

文章目录

  • 一、分支定界法相关概念
  • 二、分支定界法求解整数规划步骤
  • 三、分支定界理论分析
  • 四、分支过程示例

一、分支定界法相关概念

分支定界法相关概念 :

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

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

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

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

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

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

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

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

( 2 ) 分支 与 定界 :

任选一个 非整数解变量

x_i

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

x_i leq [x_i]

和

x_i geq [x_i] 1

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

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

新的分支松弛问题特征 :

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

分支

1

的最优解是

x^*

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

f_1

;

分支

2

的最优解是

y^*

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

f_2

;

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

f_1, f_2

谁更大 ;

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

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

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

三、分支定界理论分析

假设考虑 分支

1

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

f

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

假设 分支

1

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

如果求解 分支

1

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

f_0

, 如果

f_0 > f

, 此时需要重新定界 , 将

f_0

作为新的界来讨论 ;

根据新的界来看 分支

2

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

2

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

f^*

;

如果 分支

2

的最优值 小于 分支

1

的最优值

f^* leq f^0

, 此时分支

2

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

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

四、分支过程示例

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

begin{array}{lcl} rm maxZ = x_1 x_2 \\ rm s.tbegin{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.tbegin{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

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

分支

1

整数规划 : 添加

x_i leq [x_i]

约束 , 即

x_1 leq 1

;

begin{array}{lcl} rm maxZ = x_1 x_2 \\ rm s.tbegin{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}

分支

2

整数规划 : 添加

x_i geq [x_i] 1

约束 , 即

x_1 geq 2

;

begin{array}{lcl} rm maxZ = x_1 x_2 \\ rm s.tbegin{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}

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

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

变量 博客 函数

0 人点赞