【运筹学】整数规划 ( 整数规划示例 | 整数规划解决的核心问题 )

一、整数规划示例

资金总额 B \rm B B , 有 n n n 个投资项目 , 项目 j j j 所需的投资金额 是 a j a_j aj​ , 预期收益是 c j c_j cj​ , j = 1 , 2 , ⋯   , n j = 1,2,\cdots,n j=1,2,⋯,n ;

投资还有以下附加条件 :

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

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

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

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

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

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

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

投资额约束条件 : 所有的投资总额不能超过 B \rm B B , ∑ j = 1 n a j x j ≤ B \sum_{j = 1}^{n} a_{j} x_j \leq B ∑j=1n​aj​xj​≤B ;

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

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

分析条件 ③ : 项目 5 , 6 , 7 5,6,7 5,6,7 只能选择 2 2 2 个 , 则三者相加等于 2 2 2 即可 ; 约束方程 x 5 + x 6 + x 7 = 2 x_5 + x_6 + x_7 = 2 x5​+x6​+x7​=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   ) \begin{array}{lcl} \rm maxZ = \sum_{j = 1}^{n} c_j x_j \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} a_{j} x_j \leq B \\\\ \rm x_2 \geq x_1 \\\\ \rm x_3 + x_4 \geq 1 \\\\ \rm x_5 + x_6 + x_7 = 2 \\\\ \rm x_j = 0 , 1 \ \ \ ( \ j = 1, 2, \cdots , n \ ) \end{cases}\end{array} maxZ=∑j=1n​cj​xj​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​∑j=1n​aj​xj​≤Bx2​≥x1​x3​+x4​≥1x5​+x6​+x7​=2xj​=0,1   ( j=1,2,⋯,n )​​

根据 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 ) 博客中的整数线性规划概念 , 上述线性规划是 整数线性规划 ;

上述整数线性规划 的 松弛问题 是一个线性规划 , 可以使用单纯形法对其进行求解 , 求出最优解后 , 可能是小数 , 那么如何得到整数问题的最优解 , 不能进行简单的四舍五入 ;

二、整数规划解决的核心问题

给出 整数规划问题 ,

先求该 整数规划的松弛问题 的解 ,

松弛问题就是不考虑整数约束 , 将整数线性规划当做普通的线性规划 , 使用单纯形法求出其最优解 ;

简单的将其松弛问题最优解上下取整 , 得到的四个值 , 可能 不在可行域中 , 选择的整数解 , 必须在可行域中 ;

根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;