【运筹学】整数规划 ( 整数规划问题解的特征 | 您所在的位置:网站首页 › 整数解的问题 › 【运筹学】整数规划 ( 整数规划问题解的特征 |
文章目录一、整数规划问题解的特征二、整数规划问题 与 松弛问题 示例一、整数规划问题解的特征 整数规划问题解的特征 : ① 整数规划问题 与 松弛问题 可行解集合关系 : 整数规划问题 可行解集合 , 是该整数规划问题的 松弛问题 可行解集合 的子集 , 任意两个可行解的 凸组合 , 不一定满足整数约束条件 , 不一定是可行解 ; ② 整数规划问题 与 松弛问题 最优解关系 : 整数规划问题的可行解 一定是 其 松弛问题的可行解 , 松弛问题的可行解不一定是整数规划问题的可行解 , 整数规划问题的最优解 不会优于 松弛问题的最优解 ; 松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ; 二、整数规划问题 与 松弛问题 示例假设有如下整数规划问题 : \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}上述整数规划问题对应的松弛问题 : 松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ; \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}使用图解法 , 解上述 松弛问题 的最优解为 \begin{cases} \rm x_1 = \cfrac{3}{2} \\\\ \rm x_2 = \cfrac{10}{3} \end{cases}此时目标函数值 \rm maxZ = x_1 + x_2 = \cfrac{29}{6}![]() 简单的将其松弛问题最优解上下取整 , 得到的四个点 , 如上图的四个红色点 , 都不在可行域中 , 选择的整数解 , 必须在可行域中 ; 根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ; 穷举法 ( 有局限性 ) : 直接看上图中可行域内的整数点 , 然后再逐一代入目标函数 , 得到一个 整数规划问题 的最优解 , 但是这种方法无法推广应用 , 如果点的个数比较多 , 如几万个 , 变量的维数多 , 如 10个约束变量 , 这种方法肯定不适用 ; 整数规划问题的求解方法有 : ① 分支定界法 , ② 割平面法 ; 推荐使用 分支定界法 ; |
CopyRight 2018-2019 实验室设备网 版权所有 |