鋼板二維切割問(wèn)題的研究.pdf

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

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

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