鋼板二維切割問題的研究.pdf

1、本文研究的目的在于改進(jìn)在鋼鐵企業(yè)中二維切割問題的優(yōu)化模型。所做的主要工作在于加強(qiáng)模型所能表達(dá)的功能和針對優(yōu)化問題的算法求解的改進(jìn)。本文研究的二維切割問題是十分有意義的，由于當(dāng)產(chǎn)品的數(shù)量比較大的時候，在進(jìn)行切割規(guī)劃時即使微小的改進(jìn)也能導(dǎo)致節(jié)省大量的原材料和能源。 解決此類切割問題，盡管有許多的方法可以使用，但在本文中只研究了一種針對大規(guī)模切割問題非常有效的求解算法——列生成。此算法事先產(chǎn)生初始切割模式并將它作為變量插入到模型中。此

2、算法能考慮到每種可行切割模式，其最主要的貢獻(xiàn)在于當(dāng)切割模式的數(shù)量巨大時，能給出切割模式的長度的界限。而在其它所提出的算法中，控制切割模式的長度是非常困難的。 通過參考文獻(xiàn)給出基準(zhǔn)結(jié)果。使用列生成算法解決我們所提出的模型，通過與文獻(xiàn)原始問題比較發(fā)現(xiàn)在庫存板的利用率上有很大提高。另外，在模型中提出了諸如Guillotine切割和產(chǎn)品優(yōu)先權(quán)等特性。然而，在模型中增加這些特性會增加收斂時間。 本文只是利用Wang所提出的啟發(fā)式得

3、到列生成的初始解，應(yīng)用動態(tài)規(guī)劃求解二維切割問題的子問題——背包問題。實(shí)質(zhì)上，對于其它解決此類問題的數(shù)學(xué)啟發(fā)式做進(jìn)一步研究是非常有意義的。分類優(yōu)化理論用于優(yōu)化切割模式長度被證明是有價值的。其減少優(yōu)化時間的貢獻(xiàn)主要在于剔除一些不必要的松弛變量和模型中的不必要約束。因此它能計算出盡可能緊的界，這點(diǎn)非常重要。然而，太緊的界可能剔除解空間中有用的部分。如果那樣，最好也只能得到次優(yōu)解。 在PentiumⅢ系列主頻1000的計算機(jī)上，使用C+