[运筹学] 整数编程、分支与边界总结 ( 整数编程 | 分支与边界 | 整数编程问题 | 松弛问题 | 分支与边界 | 分支与边界概念 | 分支与边界步骤 )★★★

一、整数规划

---

1、整数规划概念

线性规划 使用 单纯形法求解 , 线性规划中的 运输规划 使用 表上作业法 求解 ;

之前讨论的都是线性规划问题 , 非线性规划如何求解 , 没有给出具体的方法 ;

整数规划问题 : 要求 一部分 或 全部 决策变量 取值整数 的规划问题 , 称为整数规划 ;

整数规划问题的松弛问题 : 不考虑 整数变量条件 , 剩余的 目标函数 和 约束条件 构成的线性规划问题 称为 整数规划问题的松弛问题 ;

整数线性规划 : 如果上述 整数规划问题的松弛问题 是线性规划 , 则称该整数规划为 整数线性规划 ;

整数规划与之前的线性规划多了一个约束条件 , 变量大于等于 $0$ , 并且都是整数 ;

整数线性规划数学模型一般形式 :

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}={\sum }_{\mathrm{j}=0}^{\mathrm{n}}{\mathrm{c}}_{\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\sum }_{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{a}}_{\mathrm{i}\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}={\mathrm{b}}_{\mathrm{i}}(\mathrm{i}=1,2,\cdots ,\mathrm{m})\\ \\ {\mathrm{x}}_{\mathrm{j}}\ge 0(\mathrm{j}=1,2,\cdots ,\mathrm{n})部分或全部为整数\end{array}\end{array}$

2、整数规划分类

整数线性规划分为以下几类 : ① 纯整数线性规划 , ② 混合整数线性规划 , ③ 0-1 型整数线性规划 ;

① 纯整数线性规划 : 全部决策变量都 必须取值整数 的 整数线性规划 ;

② 混合整数线性规划 : 决策变量中有一部分 必须 取整数值 , 另一部分 可以不 取值整数值 的 整数线性规划 ;

③ 0-1 型整数线性规划 : 决策变量 只能取值 $0$ 或 $1$ 的整数线性规划 ;

二、整数规划示例

---

资金总额 $\mathrm{B}$ , 有 $n$ 个投资项目 , 项目 $j$ 所需的投资金额 是 $a_j$ , 预期收益是 $c_j$ , $j=1,2,\cdots ,n$ ;

投资还有以下附加条件 :

① 如果投资项目 $1$ , 必须投资项目 $2$ ; 反之如果投资项目 $2$ , 没有限制 ;

② 项目 $3$ 和 项目 $4$ 必须至少选 $1$ 个 ;

③ 项目 $5,6,7$ 只能选择 $2$ 个 ;

决策变量分析 : 选择合适的 决策变量 与 决策变量取值 ;

选取变量 , 使得变量的一组取值 , 能更好对应线性规划问题的解决方案 ;

每个项目有对应的两个选择 , 投资 / 不投资 , 分别使用 $1$ 和 $0$ 表示 ;

令 $x_j$ 表示第 $j$ 个项目的投资选择 , 投资 $1$ , 不投资 $0$ ; ( $j=1,2,\cdots ,n$ )

投资额约束条件 : 所有的投资总额不能超过 $\mathrm{B}$ , ${\sum }_{j=1}^n{a}_j{x}_j\le B$ ;

分析条件 ① : 投资项目 $1$ , 必须投资项目 $2$ , 此时 $x_1=x_2=1$ ; 投资项目 $2$ 可以投资项目 $1$ , 可以不投资项目 $1$ , 同时投资的情况上面已经分析过 , 分析后者 $x_1=1,x_2=0,此时x_1>x_2$ ; 综合上述两种情况就有 $x_2\ge x_1$ ;

分析条件 ② : 项目 $3$ 和 项目 $4$ 必须至少选 $1$ 个 , 两者选择一个 , 或者都选择 , 二者相加之和是 $1$ 或 $2$ ; 有约束方程 $x_3+x_4\ge 1$ ;

分析条件 ③ : 项目 $5,6,7$ 只能选择 $2$ 个 , 则三者相加等于 $2$ 即可 ; 约束方程 $x_5+x_6+x_7=2$ ;

投资问题可以表示为以下线性规划 :

m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a j x j ≤ B x 2 ≥ x 1 x 3 + x 4 ≥ 1 x 5 + x 6 + x 7 = 2 x j = 0 , 1     (   j = 1 , 2 , ⋯   , n   )