Lagrange松弛水平優(yōu)化方法及其在煉鋼-連鑄生產(chǎn)調(diào)度問題中的應(yīng)用研究.pdf

1、高效的優(yōu)化方法對于工業(yè)生產(chǎn)調(diào)度有著重要的實(shí)際意義，但依據(jù)計(jì)算復(fù)雜性理論，大多數(shù)生產(chǎn)調(diào)度問題都屬于強(qiáng)NP難問題，因而全局優(yōu)化算法難以應(yīng)用于復(fù)雜的實(shí)際生產(chǎn)調(diào)度問題。Lagrange松弛方法通過利用調(diào)度問題的可分離結(jié)構(gòu)，采用分解與協(xié)調(diào)策略，能在可接受的時(shí)間范圍內(nèi)得到高質(zhì)量的解，同時(shí)給出問題的下界（相對于最小化問題）以評價(jià)解的質(zhì)量，因而被公認(rèn)為是解決復(fù)雜調(diào)度問題的一個(gè)有效途徑。
　　Lagrange松弛方法利用Lagrange乘子松弛優(yōu)化

2、問題的特定耦合約束，將其引入到目標(biāo)函數(shù)之中，從而得到一個(gè)與乘子對應(yīng)的Lagrange松弛問題，一般通過次梯度算法求解Lagrange對偶問題得到最優(yōu)乘子，從而得到原問題的下界。在次梯度算法的每次迭代中，需精確求解松弛問題得到次梯度來更新乘子，然后基于松弛問題的解，依據(jù)啟發(fā)式方法構(gòu)造一個(gè)可行解，同時(shí)保留最好的可行解作為原問題的解。然而，Lagrange松弛方法存在如下問題:(1)傳統(tǒng)次梯度算法的收斂條件因過于嚴(yán)格而在實(shí)際應(yīng)用中難以實(shí)現(xiàn)，導(dǎo)

3、致人為設(shè)置終止條件，使得算法無法收斂到對偶問題最優(yōu)值（即原問題下界）;(2)次梯度算法的震蕩現(xiàn)象導(dǎo)致收斂速度慢;(3)次梯度算法因每次迭代都需精確求解松弛問題導(dǎo)致算法效率低。本文針對上述問題進(jìn)行了優(yōu)化理論的研究，提出了改進(jìn)的Lagrange松弛方法，并將其應(yīng)用于煉鋼-連鑄生產(chǎn)調(diào)度問題，取得的主要成果如下:
　　1.針對傳統(tǒng)次梯度算法的收斂條件因過于嚴(yán)格而難以實(shí)現(xiàn)的問題，通過引入Brannlund水平控制策略，提出了次梯度水平算法，

4、給出了算法在無需問題特殊信息（如初始迭代點(diǎn)與最優(yōu)點(diǎn)的距離）的條件下的可實(shí)現(xiàn)收斂條件，以及算法的收斂性和收斂率的分析與證明。
　　本文將基于Brannlund水平控制策略的Lagrange松弛方法應(yīng)用于煉鋼-連鑄生產(chǎn)靜態(tài)調(diào)度問題。由于Lagrange松弛方法的求解質(zhì)量和效率與問題的數(shù)學(xué)模型密切相關(guān)，因此，本文基于冶煉和精煉階段的設(shè)備能力約束（不同爐次在同一設(shè)備上不能產(chǎn)生作業(yè)沖突）的松弛策略，研究了基于兩種數(shù)學(xué)模型的求解方法:(1)建

5、立了基于大M法的混合整數(shù)規(guī)劃（Mixed Integer Programming，MIP）模型，給出了求解松弛問題的線性規(guī)劃方法，針對迭代過程中存在無界松弛解的情況，給出了保證松弛解有界的充要條件，提出了避免無界的方法;(2)建立了基于時(shí)間索引變量的0-1整數(shù)規(guī)劃(Integer Programming，IP)模型，考慮到連鑄約束特點(diǎn)，分別提出了基于爐次單元、澆次單元和連鑄機(jī)單元的三種松弛策略以及求解松弛問題的多項(xiàng)式動(dòng)態(tài)規(guī)劃方法。基于實(shí)

6、際鋼鐵生產(chǎn)數(shù)據(jù)的仿真實(shí)驗(yàn)結(jié)果表明，基于IP模型方法的求解質(zhì)量和效率優(yōu)于基于MIP模型的方法;在基于IP模型的方法中，基于連鑄機(jī)單元的松弛策略的求解質(zhì)量最好，但基于爐次單元的松弛策略的求解效率最高。
　　2.針對傳統(tǒng)次梯度算法收斂速度慢的問題，通過分析兩種造成收斂速度慢的震蕩現(xiàn)象，引入條件-偏轉(zhuǎn)次梯度，結(jié)合次梯度水平算法，提出了條件-偏轉(zhuǎn)次梯度水平算法，給出了算法的收斂性和收斂率的分析與證明?；诮?jīng)典問題的數(shù)值實(shí)驗(yàn)結(jié)果表明，條件-偏

7、轉(zhuǎn)次梯度次梯度水平算法顯著地提高了Lagrange松弛方法的效率。
　　針對帶有不同精煉工序的（柔性作業(yè)型）煉鋼-連鑄生產(chǎn)調(diào)度問題，建立了基于時(shí)間索引變量的0-1整數(shù)規(guī)劃模型，采用冶煉和精煉階段的設(shè)備能力松弛策略，將基于條件-偏轉(zhuǎn)次梯度水平算法的Lagrange松弛方法應(yīng)用于煉鋼-連鑄生產(chǎn)調(diào)度問題?；趯?shí)際鋼鐵生產(chǎn)數(shù)據(jù)的仿真實(shí)驗(yàn)結(jié)果表明，條件-偏轉(zhuǎn)次梯度水平算法顯著地提高了Lagrange松弛方法求解煉鋼-連鑄生產(chǎn)調(diào)度問題的效率。

8、
　　3.針對傳統(tǒng)次梯度算法因每次迭代都需精確求解松弛問題導(dǎo)致效率低的問題，通過引入近似次梯度，使其可以近似求解松弛問題，結(jié)合條件-偏轉(zhuǎn)次梯度水平算法，提出了條件-偏轉(zhuǎn)近似次梯度水平算法，稱基于此算法的Lagrange松弛方法為Lagrange松弛水平方法，并給出了算法的收斂性和收斂率的證明，以及松弛問題的近似誤差與對偶問題最優(yōu)值之間的關(guān)系，為評估近似解提供了理論依據(jù)。
　　本文將Lagrange松弛水平方法應(yīng)用于加工時(shí)間可

9、變的煉鋼-連鑄生產(chǎn)重調(diào)度問題。首先，基于時(shí)間索引變量，建立了適用于不同擾動(dòng)的重調(diào)度問題的混合整數(shù)規(guī)劃模型;其次，采用基于爐次和連鑄機(jī)單元的松弛策略，提出了針對加工時(shí)間可變的松弛問題的多項(xiàng)式動(dòng)態(tài)規(guī)劃算法，在此基礎(chǔ)上，進(jìn)一步提出了誤差可控的近似優(yōu)化方法?；趯?shí)際鋼鐵生產(chǎn)數(shù)據(jù)的仿真實(shí)驗(yàn)結(jié)果表明，基于連鑄機(jī)單元和爐次單元松弛策略的方法的求解質(zhì)量差別很小，但前者的效率要略高于后者。此外，不同誤差水平下的仿真實(shí)驗(yàn)結(jié)果表明，條件-偏轉(zhuǎn)次梯度水平算法顯