拉格朗日松弛算法.ppt

该【拉格朗日松弛算法 】是由【tanfengdao】上传分享，文档一共【63】页，该文档可以免费在线阅读，需要了解更多关于【拉格朗日松弛算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。拉格朗日松弛算法
目标值
基于数学规划: 分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。
其它算法：分解法、组合算法等的目标值。
最优值
现代优化算法：禁忌搜索法、模拟退火法、遗传算法、蚁群算法等的目标值。
下界算法：线性规划松弛、拉格朗日松弛等的目标值。
01
03
05
02
04
06
例子1: 线性规划松弛: 在中,将整数约束松弛为实数, 称其为的线性规划松弛:
:
此类算法适合于整数规划问题中,决策变量为较大整数的情形.
此类算法分两阶段: 第一阶段为求松弛后线性规划问题的最优解; 第二阶段为将解整数化,并考虑可行性.
1
注:
2
例2: 对偶规划松弛方法的对偶形式为:
注:
其中Y为决策变量.
由对偶理论知和有相同的最优值,至于采用其中的哪个模型求解的下界,需比较哪个计算简单.
01
当()中的约束太多时,代理松弛一个约束
02
代替()中的K个约束
03
极端情况可以用一个代替全部
04
注: 代理松弛法保证目标函数,整数规划约束不变, 显然,由代理松弛法求得的解不一定可行
例3. 代理松弛法:
例4. 拉格朗日松弛方法
基本原理: 将目标函数中造成问题难的约束吸 收到目标函数中,并保持目标函数的线性,使问题容易求解.
Q:为什么对此类方法感兴趣?
A: (1). 在一些组合优化中,若在原问题中减少一些约束,则使得问题求解难度大大降低.(我们把这类约束称为难约束).
(2). 实际的计算表明此种方法所得到的结果相当不错.
3
2
4
1
松弛的定义（）: 问题
其中, 为的可行域.
整数规划模型:
满足下列性质时,称为的一个松弛(relaxation).
可行解区域兼容:
目标函数兼容:
基于规划论的松弛方法
问题描述: 设 ,所有 ,且每一列对应一个费用 , 表示第j列覆盖第i行,要求在最小的费用下选择一些列,使其覆盖所有的行.
01
松弛问题:
02
set covering problem
松弛模型:
以上问题很容易求得最优解