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

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

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

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