拉格朗日松弛课件.ppt

《拉格朗日松弛课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、样的结果难达到，常常用来代替。（3）可变时，这种情况表示已得到原问题的最优解。最优值为。（4）在规定的步数内变化不超过一个给定的值。这时认为目标值不可能再变化，因此，停止运算。13Outline1.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨14简单例子15简单例子16简单例子StartingwithZUP=6,β=2andi=0fori=1,2,3,迭代三次。求出每次迭代的下界和拉格朗日乘子。原约束：17简单例子18简单例子19Outline1.基本原理及用途2.如何应用3.简单例子4.在实

6、际问题中的应用5.难点探讨20实际问题中的应用—原问题复杂约束：船舶必须在到港之后靠泊21实际问题中的应用—松弛后的问题22实际问题中的应用—松弛后的问题三维指派问题二维指派问题匈牙利法23实际问题中的应用获得可行解的启发式算法停止准则1停止准则224实际问题中的应用将次梯度法扩展为拉格朗日松弛启发式算法。每更改一次拉格朗日乘子，求出一个下界，构造启发式算法修改不可行解，得到一个上界。目标函数值增大最优值上界下界gap25Outline1.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨26难点探讨

7、（1）松弛条件的选取。将复杂的约束条件松弛，复杂指的是该约束导致模型在多项式时间内不能求解。一个问题的计算时间m(n)不大于问题大小n的多项式倍数。（2）拉格朗日松弛启发式算法的设计。松弛后获得的解不可行，需要修改，不同问题的修改方法不同。27Thanks冯媛君2011.11.1428293031