文章目录
一、分支定界法求整数规划示例
使用 分支定界法 求如下整数规划 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1, x_2 \geq 0 \ 并且为整数 \end{cases}\end{array}二、求整数规划的松弛问题及最优解
求上述整数规划 (
\rm IP ) 的松弛问题 (
\rm LP ) : 去掉整数限制即可得到一个一般的线性规划 ;
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}可以使用单纯形法求上述线性规划的最优解 , 本次使用图示法 , 求的最优化 ;
使用图示法解得上述 松弛问题 最优解
\begin{cases} \rm x_1 = \cfrac{18}{11} \approx 1.64 \\\\ \rm x_2 = \cfrac{40}{11} \approx 3.64 \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - \cfrac{218}{11} \approx -19.8如果上述 松弛问题 最优解 是整数 , 则该整数线性规划的最优解就是 松弛问题 的最优解 ;
上述 松弛问题
\rm LP 最优解不是整数 , 这里需要进行 分支 操作 , 分成两个 分支松弛问题
\rm LP1 和
\rm LP2 ;
三、第一次分支操作
分支操作 : 任选一个 非整数解变量
x_i , 在 松弛问题 中加上约束 ,
x_i \leq [x_i] 和
x_i \geq [x_i] + 1 , 形成 两个新的 松弛问题 , 就是两个分支 ;
选择 非整数取值的变量
x_1 = \cfrac{18}{11} \approx 1.64 , 作为分支变量 ,
x_i \leq [x_i] 对应的 分支新增约束条件是
x_1 \leq 1 ;
x_i \geq [x_i] + 1 对应的 分支新增约束条件是
x_1 \geq 2 ;
在
\rm LP1 分支松弛问题中加入
x_1 \leq 1 条件后为 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}求上述
\rm LP1 分支的最优解
\begin{cases} \rm x_1 = 1 \\\\ \rm x_2 = 3 \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - 16\rm LP1 分支的界就是
-16 ;
在
\rm LP2 分支松弛问题中加入
x_1 \geq 2 条件后为 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}求上述
\rm LP2 分支的最优解
\begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = \cfrac{10}{3} \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - \cfrac{56}{3} \approx -18.7\rm LP2 分支的目标值是
-18.7 ;
\rm LP1 分支的最优解时整数 , 界 是
-16 ,
\rm LP2 分支目标值还不是整数 , 因此需要继续分支 ;
判定某个分支 松弛问题 是否继续向下分支的依据 :
① 根据整最优解是否是整数判定 : 首先看 分支 松弛问题 最优解 是否是整数 , 如果是那就停下来 , 如果不是继续向下分支 ;
② 根据界的优劣判定 ( 定界思想 ) : 是否继续向下分支 , 还需要看 界 的值 , 通过该 界 的值 , 讨论是否继续向下分支 ;
- 分支条件 : 如果 本分支的界 比 另外一个分支的界 要好 , 则继续分支下去 ;
- 不分支条件 : 如果本分支的界比另外一个分支的界差 , 那么本分支就不再向下分支了 ;
四、第二次分支操作
\rm LP2 继续向下分支 ,
x_1 变量已经是整数变量了 ,
这里 选择 非整数取值的变量
x_2 = \cfrac{10}{3} \approx 3.33 , 作为分支变量 ,
x_i \leq [x_i] 对应的 分支新增约束条件是
x_2 \leq 3 ;
x_i \geq [x_i] + 1 对应的 分支新增约束条件是
x_2 \geq 4 ;
这里得到了
\rm LP2 分支下的两个 分支松弛问题
\rm LP21 和
\rm LP22 ;
在
\rm LP21 分支松弛问题中加入
x_2 \leq 3 条件后为 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_2 \leq 3 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}求上述
\rm LP21 分支的最优解
\begin{cases} \rm x_1 = \cfrac{12}{5} = 2.4 \\\\ \rm x_2 = 3 \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - 17.4\rm LP21 分支的最优解不是整数 , 而且比
\rm LP1 分支的界
-16 要好 , 可需要继续分支 ;
在
\rm LP22 分支松弛问题中加入
x_2 \geq 4 条件后为 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_2 \geq 4 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}上述
\rm LP22 分支 没有可行解 , 直接停止 ;
五、第三次分支操作
\rm LP21 继续向下分支 ,
这里 选择 非整数取值的变量
x_1 = \cfrac{12}{5} = 2.4 , 作为分支变量 ,
x_i \leq [x_i] 对应的 分支新增约束条件是
x_1 \leq 2 ;
x_i \geq [x_i] + 1 对应的 分支新增约束条件是
x_1 \geq 3 ;
这里得到了
\rm LP21 分支下的两个 分支松弛问题
\rm LP211 和
\rm LP212 ;
在
\rm LP211 分支松弛问题中加入
x_1 \leq 2 条件后为 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1 \leq 2 \\\\ \rm x_2 \leq 3 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}求上述
\rm LP211 分支的最优解
\begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = 3 \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - 17\rm LP21 分支的最优解是整数 , 而且比
\rm LP1 分支的界
-16 要好 , 是当前最好的 界 ;
因此这里将 界 更新为
-17 ;
在
\rm LP212 分支松弛问题中加入
x_1 \geq 3 条件后为 :
\begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1 \geq 3 \\\\ \rm x_2 \leq 3 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array}求上述
\rm LP212 分支的最优解
\begin{cases} \rm x_1 =3 \\\\ \rm x_2 = 2.5 \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - 15.5定界 :
\rm LP212 分支的最优解不是整数 , 其目标值
- 15.5 要比当前的界
-17 要差 , 因此该分支直接裁减掉 ;
六、整数规划最优解
该整数规划
\rm IP 的最优解
\begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = 3 \end{cases} , 将上述最优解代入约束方程 ,
得到整数规划最小值
\rm min W = -x_1 -5 x_2 = - 17分支记录如下 :
