拉格朗日松弛

1、Page1拉格朗日松弛算法- The Lagrangian Relaxation MethodPageOutline21. 基本原理及用途2. 如何应用3. 简单例子4. 在实际问题中的应用5. 难点探讨Page 引入拉格朗日松弛算法3n 拉格朗日松弛是求解下界的一种方法n 拉格朗日松弛应用于求解 约束规划问题目标函数值增大最优值上界下界gapPagen 为什么拉格朗日松弛可以求得下界？基本原理4将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性，使得问题容易求解。拉格朗日松弛后变换为：IP的最优解是LR的一个可行解，所以，原问题：拉格朗日乘子（非负）Page基本原理5g(x): 原

2、问题Def g(x):原问题的可行域f(x): 松弛后的问题Def f(x): 松弛问题的可行域Page用途6n 为什么拉格朗日松弛 popular ? 第一，对于线性整数规划问题，将难约束吸收到目标函数后，问题变得容易求解。 第二，实际的计算结果证实拉格朗日松弛方法所给的下界相当不错，且计算时间可以接受。同时，可以进一步利用拉格朗日松弛的基本原理构造基于拉格朗日松弛的启发式算法。不一定是可行解，但是可以求得下界 获得可行解（上界）/最优解（最优值）为什么拉格朗日松弛 popular ？PageOutline71. 基本原理及用途2. 如何应用3. 简单例子4. 在实际问题中的应用5. 难点探

3、讨Page如何应用8n 如何选取松弛的条件？原则：该条件去掉后使得问题容易求解。n 如何选择最优的拉格朗日乘子？原问题的拉格朗日松弛为：原问题的拉格朗日对偶为：最好的下界Page如何应用凹函数9凹函数（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）Page如何应用梯度法10梯度法：在某一点，沿梯度方向搜索，能找到函数的极值点。ABC步骤：任给一个初始出发点，设为X0，X0X1（2）计算该点当前梯度（导数） y；（3）修改当前参数 X1=X0+d* y（4）计算该点当前梯度（导数） y； 重复（1）设定一个步长d；一元函数Page如何应用次梯度法11次梯度法：在某一点，沿次梯度方向搜索，

4、能找到函数的极值点。 为 的一个可行解次梯度不唯一步骤：STEP1:STEP2: ， 否则，步长：Page如何应用步长12为原问题的一个上界，可以由一个可行解的目标值确定，也可以通过估计的方法得到。可随t 的变化逐步修正。原问题的下界， 在给定的若干步没有变化时，则取其一半。Page如何应用停止原则13（1）迭代次数不超过 T。这是一种最为简单的原则，但解的质量无法保证。停止原则：（2） 。这是最为理想的状态，此时， 达到拉格朗日对偶的最优解。在实际计算中，由于问题的复杂性和计算机本身的计算误差，这样的结果难达到，常常用 来代替。（3） 可变时，这种情况表示已得到原问题的最优解。最优值为 。（

5、4） 在规定的步数内变化不超过一个给定的值。这时认为目标值不可能再变化，因此，停止运算。PageOutline141. 基本原理及用途2. 如何应用3. 简单例子4. 在实际问题中的应用5. 难点探讨Page简单例子15Page简单例子16Page简单例子17 Starting with ZUP=6,=2 and i=0 for i=1,2,3, 迭代三次。 求出每次迭代的下界和拉格朗日乘子。TX)(=0，0，0，0101312111=+=LBZTS）1 ，1 ，1（1=423061=-=TTT）4，4，4（0，）1 ，1 ，1（40，0，02= +)max(= 原约束：Page简单例子181

6、234643212+-=xxxxMinTX)(=1 ，1 ，1 ，1221234162-=+-=LBZTS）2，1，1（2-=3826）2（62=-=TTT）03434（0，）2，1，1（384，4，43,= -+)max(=Page简单例子1938311383243213+3-=xxxxMinTX)(=0，0，0，1323823=+3-=LBZTS）1 ，0（30=821263=-=TTT）03434（0，）1 ，0，0（80，34，344,= +)max(=PageOutline201. 基本原理及用途2. 如何应用3. 简单例子4. 在实际问题中的应用5. 难点探讨Page实际问题中的应

7、用原问题21复杂约束：船舶必须在到港之后靠泊Page实际问题中的应用松弛后的问题22Page实际问题中的应用松弛后的问题23三维指派问题二维指派问题匈牙利法Page 24实际问题中的应用获得可行解的启发式算法停止准则1停止准则2Page实际问题中的应用25将次梯度法扩展为拉格朗日松弛启发式算法。每更改一次拉格朗日乘子，求出一个下界，构造启发式算法修改不可行解，得到一个上界。目标函数值增大最优值上界下界gapPageOutline261. 基本原理及用途2. 如何应用3. 简单例子4. 在实际问题中的应用5. 难点探讨Page难点探讨27（1）松弛条件的选取。将复杂的约束条件松弛，复杂指的是该约束导致模型在多项式时间内不能求解。一个问题的计算时间 m(n