[运筹学] 整数编程、分支与边界总结 ( 整数编程 | 分支与边界 | 整数编程问题 | 松弛问题 | 分支与边界 | 分支与边界概念 | 分支与边界步骤 )★★★
文章目录
- 一、整数规划
-
- 1、整数规划概念
- 2、整数规划分类
- 二、整数规划示例
- 三、整数规划解决的核心问题
- 四、整数规划问题解的特征
- 五、整数规划问题 与 松弛问题 示例
- 六、分支定界法
-
- 1、整数规划概念
- 2、分支定界法求解整数规划步骤
- 3、分支定界理论分析
- 七、分支过程示例
- 八、分支定界法求整数规划示例
-
- 1、分支定界法求整数规划示例
- 2、求整数规划的松弛问题及最优解
- 3、第一次分支操作
- 4、第二次分支操作
- 5、第三次分支操作
- 6、整数规划最优解
一、整数规划
1、整数规划概念
线性规划 使用 单纯形法求解 , 线性规划中的 运输规划 使用 表上作业法 求解 ;
之前讨论的都是线性规划问题 , 非线性规划如何求解 , 没有给出具体的方法 ;
整数规划问题 : 要求 一部分 或 全部 决策变量 取值整数 的规划问题 , 称为整数规划 ;
整数规划问题的松弛问题 : 不考虑 整数变量条件 , 剩余的 目标函数 和 约束条件 构成的线性规划问题 称为 整数规划问题的松弛问题 ;
整数线性规划 : 如果上述 整数规划问题的松弛问题 是线性规划 , 则称该整数规划为 整数线性规划 ;
整数规划与之前的线性规划多了一个约束条件 , 变量大于等于
, 并且都是整数 ;
整数线性规划数学模型一般形式 :
2、整数规划分类
整数线性规划分为以下几类 : ① 纯整数线性规划 , ② 混合整数线性规划 , ③ 0-1 型整数线性规划 ;
① 纯整数线性规划 : 全部决策变量都 必须取值整数 的 整数线性规划 ;
② 混合整数线性规划 : 决策变量中有一部分 必须 取整数值 , 另一部分 可以不 取值整数值 的 整数线性规划 ;
③ 0-1 型整数线性规划 : 决策变量 只能取值
或
的整数线性规划 ;
二、整数规划示例
资金总额
, 有
个投资项目 , 项目
所需的投资金额 是
, 预期收益是
,
;
投资还有以下附加条件 :
① 如果投资项目
, 必须投资项目
; 反之如果投资项目
, 没有限制 ;
② 项目
和 项目
必须至少选
个 ;
③ 项目
只能选择
个 ;
决策变量分析 : 选择合适的 决策变量 与 决策变量取值 ;
选取变量 , 使得变量的一组取值 , 能更好对应线性规划问题的解决方案 ;
每个项目有对应的两个选择 , 投资 / 不投资 , 分别使用
和
表示 ;
令
表示第
个项目的投资选择 , 投资
, 不投资
; (
)
投资额约束条件 : 所有的投资总额不能超过
,
;
分析条件 ① : 投资项目
, 必须投资项目
, 此时
; 投资项目
可以投资项目
, 可以不投资项目
, 同时投资的情况上面已经分析过 , 分析后者
; 综合上述两种情况就有
;
分析条件 ② : 项目
和 项目
必须至少选
个 , 两者选择一个 , 或者都选择 , 二者相加之和是
或
; 有约束方程
;
分析条件 ③ : 项目
只能选择
个 , 则三者相加等于
即可 ; 约束方程
;
投资问题可以表示为以下线性规划 :
根据 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 ) 博客中的整数线性规划概念 , 上述线性规划是 整数线性规划 ;
上述整数线性规划 的 松弛问题 是一个线性规划 , 可以使用单纯形法对其进行求解 , 求出最优解后 , 可能是小数 , 那么如何得到整数问题的最优解 , 不能进行简单的四舍五入 ;
三、整数规划解决的核心问题
给出 整数规划问题 ,
先求该 整数规划的松弛问题 的解 ,
松弛问题就是不考虑整数约束 , 将整数线性规划当做普通的线性规划 , 使用单纯形法求出其最优解 ;
简单的将其松弛问题最优解上下取整 , 得到的四个值 , 可能 不在可行域中 , 选择的整数解 , 必须在可行域中 ;
根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;
四、整数规划问题解的特征
整数规划问题解的特征 :
① 整数规划问题 与 松弛问题 可行解集合关系 : 整数规划问题 可行解集合 , 是该整数规划问题的 松弛问题 可行解集合 的子集 , 任意两个可行解的 凸组合 , 不一定满足整数约束条件 , 不一定是可行解 ;
② 整数规划问题 与 松弛问题 最优解关系 : 整数规划问题的可行解 一定是 其 松弛问题的可行解 , 松弛问题的可行解不一定是整数规划问题的可行解 , 整数规划问题的最优解 不会优于 松弛问题的最优解 ;
松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ;
五、整数规划问题 与 松弛问题 示例
假设有如下整数规划问题 :
上述整数规划问题对应的松弛问题 : 松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ;
使用图解法 , 解上述 松弛问题 的最优解为
此时目标函数值
简单的将其松弛问题最优解上下取整 , 得到的四个点 , 如上图的四个红色点 , 都不在可行域中 , 选择的整数解 , 必须在可行域中 ;
根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;
穷举法 ( 有局限性 ) : 直接看上图中可行域内的整数点 , 然后再逐一代入目标函数 , 得到一个 整数规划问题 的最优解 , 但是这种方法无法推广应用 , 如果点的个数比较多 , 如几万个 , 变量的维数多 , 如
个约束变量 , 这种方法肯定不适用 ;
整数规划问题的求解方法有 : ① 分支定界法 , ② 割平面法 ;
推荐使用 分支定界法 ;
六、分支定界法
1、整数规划概念
分支定界法相关概念 :
分支 : 将一个问题不断细分为 若干子问题 , 之后逐个讨论子问题 ;
定界 : 分支很多的情况下 , 需要讨论的情况也随之增多 , 这里就需要定界 , 决定在什么时候不在进行分支 ; 满足 ① 得到最优解 , ② 根据现有条件可以排除最优解在该分支中 , 二者其一 , 就可以进行定界 ;
定界的作用是 剪掉没有讨论意义的分支 , 只讨论有意义的分支 ;
2、分支定界法求解整数规划步骤
分支定界法求解整数规划步骤 :
( 1 ) 求 整数规划 的 松弛问题 最优解 :
如果 该 最优解就 是整数 , 那么得到整数规划最优解 ;
如果 该 最优解 不是整数 , 那么转到下一个步骤 分支 与 定界 ;
( 2 ) 分支 与 定界 :
任选一个 非整数解变量
, 在 松弛问题 中加上约束 :
和
形成 两个新的 松弛问题 , 就是两个分支 ;
上述分支 , 分的越细致 , 限制条件越多 , 同时 最优解的质量就越差 ;
新的分支松弛问题特征 :
- 原问题求 最大值 时 , 目标值 是 分支问题 的上界 ;
- 原问题求 最小值 时 , 目标值 是 分支问题 的下界 ;
分支
的最优解是
, 将最优解代入目标函数后得到最优值
;
分支
的最优解是
, 将最优解代入目标函数后得到最优值
;
如果目标函数求最大值 , 那么就讨论
谁更大 ;
检查 分支松弛问题 的 解 及 目标函数值 :
① 得到最优整数解 : 如果该分支的 解 是 整数 , 并且 目标函数值 大于等于 其它分支的目标值 , 则剪去其它分支 , 停止计算 ;
② 没有得到最优整数解 : 如果该分支的 解 是 小数 , 并且 目标函数值 大于 整数解的目标值 , 需要 继续进行分支 , 直到得到最优解 ;
3、分支定界理论分析
假设考虑 分支
松弛问题 , 每次都要给问题找到一个界 , 开始先使用观察法找到一个界 , 找到一个整数解
, 将该解代入目标函数 , 然后在 不断地计算中, 修改该界 ;
假设 分支
松弛问题 目标函数 求最大值 ,
如果求解 分支
松弛问题 最优解 恰好也是一个整数解
, 如果
, 此时需要重新定界 , 将
作为新的界来讨论 ;
根据新的界来看 分支
松弛问题是否需要讨论 , 求出 分支
的最优解 对应的 目标函数最优值
;
如果 分支
的最优值 小于 分支
的最优值
, 此时分支
不用再进行分支了 , 再进行分支 , 其最优值会越来越差 ;
定界法的作用是将不符合条件的分支剪去 ;
七、分支过程示例
如上篇博客 【运筹学】整数规划 ( 整数规划问题解的特征 | 整数规划问题 与 松弛问题 示例 ) 中 , 求解如下 整数规划 解 :
其对应的松弛问题是 : 去掉整数解限制 ;
分支都是基于松弛问题进行的 , 为松弛问题分支 , 组成两个新的松弛问题 ;
下图是求解结果 ( 图解法 ) :
最优解
, 分别为
添加
和
约束 , 形成两个新的线性规划 ;
分支
整数规划 : 添加
约束 , 即
;
分支
整数规划 : 添加
约束 , 即
;
这样就将一个线性规划 , 分解成了两个问题分支 , 分别找两个分支问题的所有整数解 ;
整数规划的整数解 , 肯定在上述两个分支之一中 , 中间将一部分可行域排除在外了 , 就是下图中两个红色箭头之间的可行域部分 , 被排除掉的部分肯定没有整数解 , 都是小数 ;
八、分支定界法求整数规划示例
1、分支定界法求整数规划示例
使用 分支定界法 求如下整数规划 :
2、求整数规划的松弛问题及最优解
求上述整数规划 (
) 的松弛问题 (
) : 去掉整数限制即可得到一个一般的线性规划 ;
可以使用单纯形法求上述线性规划的最优解 , 本次使用图示法 , 求的最优化 ;
使用图示法解得上述 松弛问题 最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
如果上述 松弛问题 最优解 是整数 , 则该整数线性规划的最优解就是 松弛问题 的最优解 ;
上述 松弛问题
最优解不是整数 , 这里需要进行 分支 操作 , 分成两个 分支松弛问题
和
;
3、第一次分支操作
分支操作 : 任选一个 非整数解变量
, 在 松弛问题 中加上约束 ,
和
, 形成 两个新的 松弛问题 , 就是两个分支 ;
选择 非整数取值的变量
, 作为分支变量 ,
对应的 分支新增约束条件是
;
对应的 分支新增约束条件是
;
在
分支松弛问题中加入
条件后为 :
求上述
分支的最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
分支的界就是
;
在
分支松弛问题中加入
条件后为 :
求上述
分支的最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
分支的目标值是
;
分支的最优解时整数 , 界 是
,
分支目标值还不是整数 , 因此需要继续分支 ;
判定某个分支 松弛问题 是否继续向下分支的依据 :
① 根据整最优解是否是整数判定 : 首先看 分支 松弛问题 最优解 是否是整数 , 如果是那就停下来 , 如果不是继续向下分支 ;
② 根据界的优劣判定 ( 定界思想 ) : 是否继续向下分支 , 还需要看 界 的值 , 通过该 界 的值 , 讨论是否继续向下分支 ;
- 分支条件 : 如果 本分支的界 比 另外一个分支的界 要好 , 则继续分支下去 ;
- 不分支条件 : 如果本分支的界比另外一个分支的界差 , 那么本分支就不再向下分支了 ;
4、第二次分支操作
继续向下分支 ,
变量已经是整数变量了 ,
这里 选择 非整数取值的变量
, 作为分支变量 ,
对应的 分支新增约束条件是
;
对应的 分支新增约束条件是
;
这里得到了
分支下的两个 分支松弛问题
和
;
在
分支松弛问题中加入
条件后为 :
求上述
分支的最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
分支的最优解不是整数 , 而且比
分支的界
要好 , 可需要继续分支 ;
在
分支松弛问题中加入
条件后为 :
上述
分支 没有可行解 , 直接停止 ;
5、第三次分支操作
继续向下分支 ,
这里 选择 非整数取值的变量
, 作为分支变量 ,
对应的 分支新增约束条件是
;
对应的 分支新增约束条件是
;
这里得到了
分支下的两个 分支松弛问题
和
;
在
分支松弛问题中加入
条件后为 :
求上述
分支的最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
分支的最优解是整数 , 而且比
分支的界
要好 , 是当前最好的 界 ;
因此这里将 界 更新为
;
在
分支松弛问题中加入
条件后为 :
求上述
分支的最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
定界 :
分支的最优解不是整数 , 其目标值
要比当前的界
要差 , 因此该分支直接裁减掉 ;
6、整数规划最优解
该整数规划
的最优解
, 将上述最优解代入约束方程 ,
得到整数规划最小值
分支记录如下 :
上一篇: 整数规划问题