该文根据无委托板坯匹配问题的特点，考虑上述的实际因素和约束及目标要求，建立了一个整数规划数学模型。该数学模型与广义指派问题(GeneralizedAssignmentProblem)数学模型既相似又有差别。相似点在于两个问题都是要求将对象(板坯、客户)找到一种关系(匹配、指派)。不同点在于广义指派问题要求所有的客户必须都被指派，而无委托板坯匹配问题首先要考虑板坯能否匹配，然后将能匹配的板坯尽可能的匹配给合同，所以板坯允许剩余，但剩余带有惩罚。由于无委托板匹配数学模型的简单情况可以归结为广义指派问题，而广义指派问题是NP-hard问题，所以无委托板坯匹配问题也是NP-hard问题。 由于该问题是一个大规模组合最优化问题，变量和约束数目众多。通过分析其可行解的约束和变量之间的关系，应用约束传播技术在不影响解的质量的情况下有效地降低了问题求解规模。 拉格朗日松弛算法是一种基于最优化的近似算法，已成功地用于求解多类NP-hard组合最优化问题。它具有较好的方向迭代性，以及算法的自我评价性。本文针对模型特点，提出两种拉格朗日松弛算法的求解策略：1)松弛模型中板坯分配唯一性约束，松弛问题分解为基于合同的背包子问题。对于每一个子问题，应用动态规划求解；2)松弛模型中合同需求量约束，松弛问题分解为基于板坯的子问题，应用最负费用枚举策略求解子问题最优解。两种策略乘子的更新均采用次梯度方法。 上述两种拉格朗日松弛算法的程序用C++语言编写，并在PentiumⅣ主频3.0GHZ的计算机上进行实验仿真。涉及到的实验数据均来自于钢铁企业生产实际。计算结果表明两种拉格朗日松弛算法对于求解无委托板坯匹配问题都是有效的。LR1算法的两个平均对偶间隙指标分别大约为0.2％和0.1％，平均计算时间大约为252秒；LR2算法的两个平均对偶间隙指标分别大约为0.7％和0.5％，平均计算时间大约为15秒。LR1算法能够得到很好的对偶间隙，但是耗时较多。虽然LR2算法比LR1算法运算时间短，平均对偶间隙却比LR1效果差。