鋼鐵工業(yè)中無委托板坯匹配問題的模型與優(yōu)化算法研究.pdf

1、該文根據(jù)無委托板坯匹配問題的特點，考慮上述的實際因素和約束及目標(biāo)要求，建立了一個整數(shù)規(guī)劃數(shù)學(xué)模型。該數(shù)學(xué)模型與廣義指派問題(GeneralizedAssignmentProblem)數(shù)學(xué)模型既相似又有差別。相似點在于兩個問題都是要求將對象(板坯、客戶)找到一種關(guān)系(匹配、指派)。不同點在于廣義指派問題要求所有的客戶必須都被指派，而無委托板坯匹配問題首先要考慮板坯能否匹配，然后將能匹配的板坯盡可能的匹配給合同，所以板坯允許剩余，但剩余帶有

2、懲罰。由于無委托板匹配數(shù)學(xué)模型的簡單情況可以歸結(jié)為廣義指派問題，而廣義指派問題是NP-hard問題，所以無委托板坯匹配問題也是NP-hard問題。 由于該問題是一個大規(guī)模組合最優(yōu)化問題，變量和約束數(shù)目眾多。通過分析其可行解的約束和變量之間的關(guān)系，應(yīng)用約束傳播技術(shù)在不影響解的質(zhì)量的情況下有效地降低了問題求解規(guī)模。 拉格朗日松弛算法是一種基于最優(yōu)化的近似算法，已成功地用于求解多類NP-hard組合最優(yōu)化問題。它具有較好的方向

3、迭代性，以及算法的自我評價性。本文針對模型特點，提出兩種拉格朗日松弛算法的求解策略：1)松弛模型中板坯分配唯一性約束，松弛問題分解為基于合同的背包子問題。對于每一個子問題，應(yīng)用動態(tài)規(guī)劃求解；2)松弛模型中合同需求量約束，松弛問題分解為基于板坯的子問題，應(yīng)用最負(fù)費用枚舉策略求解子問題最優(yōu)解。兩種策略乘子的更新均采用次梯度方法。 上述兩種拉格朗日松弛算法的程序用C++語言編寫，并在PentiumⅣ主頻3.0GHZ的計算機上進行實驗仿