论文部分内容阅读
本文研究的目的在于改进在钢铁企业中二维切割问题的优化模型。所做的主要工作在于加强模型所能表达的功能和针对优化问题的算法求解的改进。本文研究的二维切割问题是十分有意义的,由于当产品的数量比较大的时候,在进行切割规划时即使微小的改进也能导致节省大量的原材料和能源。
解决此类切割问题,尽管有许多的方法可以使用,但在本文中只研究了一种针对大规模切割问题非常有效的求解算法——列生成。此算法事先产生初始切割模式并将它作为变量插入到模型中。此算法能考虑到每种可行切割模式,其最主要的贡献在于当切割模式的数量巨大时,能给出切割模式的长度的界限。而在其它所提出的算法中,控制切割模式的长度是非常困难的。
通过参考文献给出基准结果。使用列生成算法解决我们所提出的模型,通过与文献原始问题比较发现在库存板的利用率上有很大提高。另外,在模型中提出了诸如Guillotine切割和产品优先权等特性。然而,在模型中增加这些特性会增加收敛时间。
本文只是利用Wang所提出的启发式得到列生成的初始解,应用动态规划求解二维切割问题的子问题——背包问题。实质上,对于其它解决此类问题的数学启发式做进一步研究是非常有意义的。分类优化理论用于优化切割模式长度被证明是有价值的。其减少优化时间的贡献主要在于剔除一些不必要的松弛变量和模型中的不必要约束。因此它能计算出尽可能紧的界,这点非常重要。然而,太紧的界可能剔除解空间中有用的部分。如果那样,最好也只能得到次优解。
在PentiumⅢ系列主频1000的计算机上,使用C++语言实现了上述全部算法,并进行实验仿真。实验结果表明列生成算法能够有效地求解二维切割问题。