新浪博客

割平面法（Cutting-plane method）

2016-12-21 11:02阅读：

http://blog.sina.cn/dpool/blog/u/2877414080

本文资料整理于李荣钧编著的《运筹学导论》，仅供个人研究学习、整理之用。
相比于分枝定界法，割平面法目的更明确，效果更佳。分枝定界法会产生一系列的子问题，而割平面则是把原问题（MILP或ILP）转换为对应的LP问题后，逐次构造约束条件把部分不含整数解的可行域割掉，不产生更多的子问题，而是逐渐收缩可行域。


分枝定界法和割平面法，每次产生子问题或割平面后，都要重新求解新的线性规划问题（如采用单纯形法求解），因此可以想象，求解MILP和ILP的时间会比LP的时间长。
割平面法（Cutting-plane <wbr>method）
割平面法（Cutting-plane <wbr>method）

割平面法（Cutting-plane <wbr>method）
割平面法（Cutting-plane <wbr>method）
割平面法（Cutting-plane <wbr>method）
割平面法（Cutting-plane <wbr>method）

我的更多文章

下载客户端阅读体验更佳

APP专享