第五章拉格朗日松弛算法VIP免费

拉格朗日松弛算法基于规划论的松弛方法拉格朗日松弛理论拉格朗日松弛的进一步讨论拉格朗日松弛算法主要内容:目标值最优值基于数学规划:分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。现代优化算法：禁忌搜索法、模拟退火法、遗传算法、蚁群算法等的目标值。其它算法：分解法、组合算法等的目标值。下界算法：线性规划松弛、拉格朗日松弛等的目标值。例子1:线性规划松弛:在5.1.1中,将整数约束松弛为实数,称其为5.1.1的线性规划松弛:min5.1.1,...TLPnZcxAxbstxZmin5.1.2,...TLPnZcxAxbstxR1.定理5.1.1:2.此类算法适合于整数规划问题中,决策变量为较大整数的情形.3.此类算法分两阶段:第一阶段为求松弛后线性规划问题的最优解;第二阶段为将解整数化,并考虑可行性.LPIPZZ注:例2:对偶规划松弛方法:5.1.2的对偶形式为:max5.1.3,...TDPTnZybAycstyR其中Y为决策变量.注:由对偶理论知,5.1.2和5.1.3有相同的最优值,至于采用其中的哪个模型求解5.1.1的下界,需比较哪个计算简单.例3.代理松弛法:当(5.1.1)中的约束太多时,代理松弛一个约束代替(5.1.1)中的K个约束极端情况可以用一个代替全部111()kknKKijjijkkaxb1,1kknijjijaxbkK111()nmmijjijkkaxb注:代理松弛法保证目标函数,整数规划约束不变,显然,由代理松弛法求得的解不一定可行例4.拉格朗日松弛方法基本原理:将目标函数中造成问题难的约束吸收到目标函数中,并保持目标函数的线性,使问题容易求解.Q:为什么对此类方法感兴趣?A:(1).在一些组合优化中,若在原问题中减少一些约束,则使得问题求解难度大大降低.(我们把这类约束称为难约束).(2).实际的计算表明此种方法所得到的结果相当不错.5.1基于规划论的松弛方法松弛的定义（5.1.1）:问题整数规划模型:min5.1.1,...TIPnZcxAxbstxZ:min()RRRxSRPZzx满足下列性质时,称为5.1.1的一个松弛(relaxation).(1)可行解区域兼容:(2)目标函数兼容:(),TRcxzxxSRSS其中,为5.1.1的可行域.S例5.1.1setcoveringproblem问题描述:设,所有,且每一列对应一个费用,表示第j列覆盖第i行,要求在最小的费用下选择一些列,使其覆盖所有的行.()ijmnAa{0,1}ija(1)jcjn1ija11min()..1,1{0,1},1nscjjjnijjjjzcxSCstaximxjn松弛问题:111min{(1)}()..{0,1},10nmnLRSCjjiijjjijjzcxaxLRSCstxjn松弛模型:11min()..{0,1},10nmLRSCjjijijzdxLRSCstxjn1mjjiijidca以上问题很容易求得最优解1,0*0,jdxother5.2拉格朗日松弛理论min,():..,.TIPnZcxAxbIPstBxdxZ难约束（简单约束）{|,}nSxZAxbBxd()min{()}:,...TTLRnZcxbAxLRBxdstxZ（简单约束）原整数规划问题拉格朗日松弛{|}nLRSxZBxd定理5.2.1LR同下整数规划问题(5.2.1)有相同的复杂性,且若IP可行解非空，则:0,()LRIPzzmin..(5.2.1)TncxstBxdxZ()min{()}:,...TTTLRnZcAxbLRBxdstxZ（简单约束）min,():..,.TIPnZcxAxbIPstBxdxZ难约束（简单约束）证明:注:定理5.2.1说明拉格朗日松弛是IP问题的一个下界,但我们应该求与IP最接近的下界,即:0()max{()}LDLRLDzz定义5.2.1若,满足以下条件,则称D为凸集.,xyD(1),01xyD1(){|,1}iiiiiiConQPPR{|1,2,}iQPi对于离散点集,其凸包定义为:显然Con(Q)为凸集.定理5.2.2若拉格朗日对偶问题的目标值有限,则min{|,()}{|,}TLDnzcxAxbxConQQxBxdxZ其中：证明:()()()min()min()min[()]TTTLRxQTTTxConQTTxConQzcAxbcAxbcxbAx设Con(Q)的极点为,极方向为则:{|}kxkK{|}jrjJ,,()0min()(),:TTjTTTTkTkxQifjJcArcAxbcxbAxotherkK由LD问...