【运筹学】分支定界法 ( 分支定界法求整数规划示例 ) ★★

使用 分支定界法 求如下整数规划 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 , x 2 ≥ 0   并 且 为 整 数 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​,x2​≥0 并且为整数​​

求上述整数规划 ( I P \rm IP IP ) 的松弛问题 ( L P \rm LP LP ) : 去掉整数限制即可得到一个一般的线性规划 ;

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​,x2​≥0​​

可以使用单纯形法求上述线性规划的最优解 , 本次使用图示法 , 求的最优化 ;

使用图示法解得上述 松弛问题 最优解 { x 1 = 18 11 ≈ 1.64 x 2 = 40 11 ≈ 3.64 \begin{cases} \rm x_1 = \cfrac{18}{11} \approx 1.64 \\\\ \rm x_2 = \cfrac{40}{11} \approx 3.64 \end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​x1​=1118​≈1.64x2​=1140​≈3.64​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 218 11 ≈ − 19.8 \rm min W = -x_1 -5 x_2 = - \cfrac{218}{11} \approx -19.8 minW=−x1​−5x2​=−11218​≈−19.8

如果上述 松弛问题 最优解 是整数 , 则该整数线性规划的最优解就是 松弛问题 的最优解 ;

上述 松弛问题 L P \rm LP LP 最优解不是整数 , 这里需要进行 分支 操作 , 分成两个 分支松弛问题 L P 1 \rm LP1 LP1 和 L P 2 \rm LP2 LP2 ;

分支操作 : 任选一个 非整数解变量 x i x_i xi​ , 在 松弛问题 中加上约束 , x i ≤ [ x i ] x_i \leq [x_i] xi​≤[xi​] 和 x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi​≥[xi​]+1 , 形成 两个新的 松弛问题 , 就是两个分支 ;

选择 非整数取值的变量 x 1 = 18 11 ≈ 1.64 x_1 = \cfrac{18}{11} \approx 1.64 x1​=1118​≈1.64 , 作为分支变量 ,

x i ≤ [ x i ] x_i \leq [x_i] xi​≤[xi​] 对应的 分支新增约束条件是 x 1 ≤ 1 x_1 \leq 1 x1​≤1 ;

x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi​≥[xi​]+1 对应的 分支新增约束条件是 x 1 ≥ 2 x_1 \geq 2 x1​≥2 ;

在 L P 1 \rm LP1 LP1 分支松弛问题中加入 x 1 ≤ 1 x_1 \leq 1 x1​≤1 条件后为 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≤ 1 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​≤1x1​,x2​≥0​​

求上述 L P 1 \rm LP1 LP1 分支的最优解 { x 1 = 1 x 2 = 3 \begin{cases} \rm x_1 = 1 \\\\ \rm x_2 = 3 \end{cases} ⎩⎪⎨⎪⎧​x1​=1x2​=3​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 16 \rm min W = -x_1 -5 x_2 = - 16 minW=−x1​−5x2​=−16

L P 1 \rm LP1 LP1 分支的界就是 − 16 -16 −16 ;

在 L P 2 \rm LP2 LP2 分支松弛问题中加入 x 1 ≥ 2 x_1 \geq 2 x1​≥2 条件后为 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​≥2x1​,x2​≥0​​

求上述 L P 2 \rm LP2 LP2 分支的最优解 { x 1 = 2 x 2 = 10 3 \begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = \cfrac{10}{3} \end{cases} ⎩⎪⎪⎨⎪⎪⎧​x1​=2x2​=310​​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 56 3 ≈ − 18.7 \rm min W = -x_1 -5 x_2 = - \cfrac{56}{3} \approx -18.7 minW=−x1​−5x2​=−356​≈−18.7

L P 2 \rm LP2 LP2 分支的目标值是 − 18.7 -18.7 −18.7 ;

L P 1 \rm LP1 LP1 分支的最优解时整数 , 界 是 − 16 -16 −16 ,

L P 2 \rm LP2 LP2 分支目标值还不是整数 , 因此需要继续分支 ;

判定某个分支 松弛问题 是否继续向下分支的依据 :

① 根据整最优解是否是整数判定 : 首先看 分支 松弛问题 最优解 是否是整数 , 如果是那就停下来 , 如果不是继续向下分支 ;

② 根据界的优劣判定 ( 定界思想 ) : 是否继续向下分支 , 还需要看 界 的值 , 通过该 界 的值 , 讨论是否继续向下分支 ;

L P 2 \rm LP2 LP2 继续向下分支 , x 1 x_1 x1​ 变量已经是整数变量了 ,

这里 选择 非整数取值的变量 x 2 = 10 3 ≈ 3.33 x_2 = \cfrac{10}{3} \approx 3.33 x2​=310​≈3.33 , 作为分支变量 ,

x i ≤ [ x i ] x_i \leq [x_i] xi​≤[xi​] 对应的 分支新增约束条件是 x 2 ≤ 3 x_2 \leq 3 x2​≤3 ;

x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi​≥[xi​]+1 对应的 分支新增约束条件是 x 2 ≥ 4 x_2 \geq 4 x2​≥4 ;

这里得到了 L P 2 \rm LP2 LP2 分支下的两个 分支松弛问题 L P 21 \rm LP21 LP21 和 L P 22 \rm LP22 LP22 ;

在 L P 21 \rm LP21 LP21 分支松弛问题中加入 x 2 ≤ 3 x_2 \leq 3 x2​≤3 条件后为 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 2 ≤ 3 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​≥2x2​≤3x1​,x2​≥0​​

求上述 L P 21 \rm LP21 LP21 分支的最优解 { x 1 = 12 5 = 2.4 x 2 = 3 \begin{cases} \rm x_1 = \cfrac{12}{5} = 2.4 \\\\ \rm x_2 = 3 \end{cases} ⎩⎪⎪⎨⎪⎪⎧​x1​=512​=2.4x2​=3​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 17.4 \rm min W = -x_1 -5 x_2 = - 17.4 minW=−x1​−5x2​=−17.4

L P 21 \rm LP21 LP21 分支的最优解不是整数 , 而且比 L P 1 \rm LP1 LP1 分支的界 − 16 -16 −16 要好 , 可需要继续分支 ;

在 L P 22 \rm LP22 LP22 分支松弛问题中加入 x 2 ≥ 4 x_2 \geq 4 x2​≥4 条件后为 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 2 ≥ 4 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​≥2x2​≥4x1​,x2​≥0​​

上述 L P 22 \rm LP22 LP22 分支 没有可行解 , 直接停止 ;

L P 21 \rm LP21 LP21 继续向下分支 ,

这里 选择 非整数取值的变量 x 1 = 12 5 = 2.4 x_1 = \cfrac{12}{5} = 2.4 x1​=512​=2.4 , 作为分支变量 ,

x i ≤ [ x i ] x_i \leq [x_i] xi​≤[xi​] 对应的 分支新增约束条件是 x 1 ≤ 2 x_1 \leq 2 x1​≤2 ;

x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi​≥[xi​]+1 对应的 分支新增约束条件是 x 1 ≥ 3 x_1 \geq 3 x1​≥3 ;

这里得到了 L P 21 \rm LP21 LP21 分支下的两个 分支松弛问题 L P 211 \rm LP211 LP211 和 L P 212 \rm LP212 LP212 ;

在 L P 211 \rm LP211 LP211 分支松弛问题中加入 x 1 ≤ 2 x_1 \leq 2 x1​≤2 条件后为 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 1 ≤ 2 x 2 ≤ 3 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​≥2x1​≤2x2​≤3x1​,x2​≥0​​

求上述 L P 211 \rm LP211 LP211 分支的最优解 { x 1 = 2 x 2 = 3 \begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = 3 \end{cases} ⎩⎪⎨⎪⎧​x1​=2x2​=3​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 17 \rm min W = -x_1 -5 x_2 = - 17 minW=−x1​−5x2​=−17

L P 21 \rm LP21 LP21 分支的最优解是整数 , 而且比 L P 1 \rm LP1 LP1 分支的界 − 16 -16 −16 要好 , 是当前最好的 界 ;

因此这里将 界 更新为 − 17 -17 −17 ;

在 L P 212 \rm LP212 LP212 分支松弛问题中加入 x 1 ≥ 3 x_1 \geq 3 x1​≥3 条件后为 :

m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 1 ≥ 3 x 2 ≤ 3 x 1 , x 2 ≥ 0 \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} minW=−x1​−5x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​≥−25x1​+6x2​≤30x1​≤4x1​≥2x1​≥3x2​≤3x1​,x2​≥0​​

求上述 L P 212 \rm LP212 LP212 分支的最优解 { x 1 = 3 x 2 = 2.5 \begin{cases} \rm x_1 =3 \\\\ \rm x_2 = 2.5 \end{cases} ⎩⎪⎨⎪⎧​x1​=3x2​=2.5​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 15.5 \rm min W = -x_1 -5 x_2 = - 15.5 minW=−x1​−5x2​=−15.5

定界 : L P 212 \rm LP212 LP212 分支的最优解不是整数 , 其目标值 − 15.5 - 15.5 −15.5 要比当前的界 − 17 -17 −17 要差 , 因此该分支直接裁减掉 ;

该整数规划 I P \rm IP IP 的最优解 { x 1 = 2 x 2 = 3 \begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = 3 \end{cases} ⎩⎪⎨⎪⎧​x1​=2x2​=3​ , 将上述最优解代入约束方程 ,

得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 17 \rm min W = -x_1 -5 x_2 = - 17 minW=−x1​−5x2​=−17

分支记录如下 :