拉格朗日松弛算法教学课件_第1页
拉格朗日松弛算法教学课件_第2页
拉格朗日松弛算法教学课件_第3页
拉格朗日松弛算法教学课件_第4页
拉格朗日松弛算法教学课件_第5页
已阅读5页，还剩58页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

拉格朗日松弛算法主要内容基子规划论的松弛方法拉格朗日松弛狸论拉格朗目松弛的进一步讨论纶一拉格朗目松弛算法基于数学规划:分支定界法、割平标面法、线性规划松弛再对目标函值数可行化等的目标值。现代佑化算法:禁忌搜索法、拟退火法、遗传算法、蚁群算法等的目标值。其它算法:分解法、组合算法等的目标值。下界算法:线性规划松弛、拉格朗最优值日松弛等的目标值。例子1:线性规划松弛:在5.1.1中,将整敝约束松弛为实敝,称其为5.1.1的线性规划松弛mincxAx≥b,5.1.1tx∈Z"-minceAx≥b,5.1.2x∈R汪:1.定理51.1:Zp≤Z2.此类算法适合于整数规划问题中,决策变量为较大整数的情形.3.此类算法分两阶段:第一阶段为求松弛后线性规划问题的最优解;第二阶段为将解整数化,并考虑可行性例2:对偶规划松弛方法:5.1.2的对偶形式为maXyAy≤5.1.3sty∈R".其中Y为决策变量注由对偶理论知,5.1.2和5.1.3有相同的最优值至于采用其中的哪个模型來解5.1.1的下界需比较哪个计算简单例3.代理松弛法当(5.1.1)中的约束太多时,代理松弛一个约束∑b代替(5.1.1)中的K个约束∑ax≥b,k=1…K极端情况可以用一个代替全部Cj-1k=1主:代理松弛法保让目标亟敝,整数规划约束不变,涩然,由代理松弛法求得的解不一定可行例4.拉格朗日松弛方法基本原理:将目标函敝中造成向题难的约束吸收到目标画数中,并保持目标函数的线性,使问题容易求解Q为什么对此类方法感兴趣?A:(1).在一些组合优化中,若在原问题中减少一些约束,则使得向题求解难度大大降低.(我们把这类约柬称为难约柬)(2)实际的汁算表明此种方法所得到的结果相当不错5.1基于规划论的松弛方法整数规划模型:Z。=mincrAx≥b5.1.1x∈Z松弛的定义(5.1.1):向题RP:z=mInz(x)满足下列性质时,称为5.1.1的一个松弛(relaxation)(1)可行解区域兼容:S≤Sa(2)目标函兼容:Cx≥z2(x),Vx∈S其中,S为5.1.1的可行域.13]5.1.1setcoveringproblem向题指述:设A=(an)m所有a1∈0,,且每一列对应个费用c1(j=1…m),=1表示第列覆盖第行,要求在最小的费用下选抒一些列,使其覆義所有的行min∑cx1s∑a1x21,i=1…m{0,1},j松弛向题min∑x+∑1(1-∑ax,)(LRSC)stx,∈{0,1},j=1…n元≥0松弛模型ZLRsc-min>d1

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论