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

相关文章推荐

博学的双杠 · 电影《红楼梦之金玉良缘》首映，胡玫导演表示“ ...· 4 月前 ·

冷静的豌豆 · android studio怎么导出项目 ...· 5 月前 ·

有爱心的松球 · 崔永元网店食品贵 ...· 9 月前 ·

有爱心的消防车 · 研究生招生 | 香港城市大学（东莞）· 9 月前 ·

性感的青椒 · 解决异常：org.springframewo ...· 1 年前 ·

分支定界法相关概念 :

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

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

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

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

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

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

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

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

( 2 ) 分支与定界 :

任选一个非整数解变量 f 1 , f 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, x_2 \geq 0 \ 并且为整数 \end{cases}\end{array} m a x Z = x 1 + x 2 s . t ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 1 4 x 1 + 9 x 2 ≤ 5 1 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 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} m a x Z = x 1 + x 2 s . t ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 1 4 x 1 + 9 x 2 ≤ 5 1 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 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 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} m a x Z = x 1 + x 2 s . t ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 1 4 x 1 + 9 x 2 ≤ 5 1 − 6 x 1 + 3 x 2 ≤ 1 x 1 ≤ 1 x 1 , x 2 ≥ 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 \geq 2 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} m a x Z = x 1 + x 2 s . t ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 1 4 x 1 + 9 x 2 ≤ 5 1 − 6 x 1 + 3 x 2 ≤ 1 x 1 ≥ 2 x 1 , x 2 ≥ 0

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

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