运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

运筹学(最优化理论)学习笔记 | 列生成法

运维开发网 https://www.qedev.com 2021-04-11 16:09 出处:51CTO 作者:mb5fd86d8699f84
本文是孙小玲教授整数规划教学视频的学习笔记以一个实际问题为例引出列生成算法。Cutting stockproblem 切割下料问题假设工厂有标准长度为218cm的钢管,现有客户需要44个长度为81cm的钢管,3个长度为70cm的钢卷,48个长度为68cm的钢卷。请问如何将标准长度为218cm的钢管进行切割,才能保证所使用标准长度钢管的数目最小?切法1:将1个标准长度的钢管切成1个81cm的钢管切法

本文是孙小玲教授整数规划教学视频的学习笔记

以一个实际问题为例引出列生成算法。

Cutting stockproblem 切割下料问题

假设工厂有标准长度为218cm的钢管,现有客户需要44个长度为81cm的钢管,3个长度为70cm的钢卷,48个长度为68cm的钢卷。请问如何将标准长度为218cm的钢管进行切割,才能保证所使用标准长度钢管的数目最小?

切法1:将1个标准长度的钢管切成1个81cm的钢管

切法2:将1个标准长度的钢管切成1个70cm的钢管

切法3:将1个标准长度的钢管切成1个68cm的钢管

……

切法n:

可能各位也发现上述3种切法有点浪费材料,但这么切一定能满足要求,所以可以作为文末求解该问题时的初始解

还可以有好多种切法,文章的最后会对该问题进行求解。

 

切割下料问题经典的数学模型如下所示:

运筹学(最优化理论)学习笔记 | 列生成法

但是这个数学模型从计算角度和理论角度而言效率不高。

主要原因是这个数学模型的线性松弛问题LP很差(即LP问题的解与原问题的解相差很大)。事实上,松弛问题LP的界为

改进的数学模型

符号:

虽然上述模型看起来比第一个模型简单了,但是我们并不知道一共有多少种切法,所以这个模型无法用显式表达出来。

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

运筹学(最优化理论)学习笔记 | 列生成法

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号