Page拉格朗日松弛算法-TheLagrangianRelaxationMethod1PageOutline2Page 引入拉格朗日松弛算法n 拉格朗日松弛是求解下界的一种方法n 拉格朗日松弛应用于求解约束规划问题目标函数值增大最优值上界下界gap3Pagen 为什么拉格朗日松弛可以求得下界？基本原理将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性，使得问题容易求解。拉格朗日松弛后变换为：IP的最优解是LR的一个可行解，所以，原问题：拉格朗日乘子（非负）4Page基本原理g(x):原问题Defg(x):原问题的可行域f(x):松弛后的问题Deff(x):松弛问题的可行域5Page用途n 为什么拉格朗日松弛popular? 第一，对于线性整数规划问题，将难约束吸收到目标函数后，问题变得容易求解。 第二，实际的计算结果证实拉格朗日松弛方法所给的下界相当不错，且计算时间可以接受。同时，可以进一步利用拉格朗日松弛的基本原理构造基于拉格朗日松弛的启发式算法。不一定是可行解，但是可以求得下界获得可行解（上界）/最优解（最优值）为什么拉格朗日松弛popular？6PageOutline7
