第8章_松弛算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Chapter 8:,拉格朗日松弛算法,8.1,基于规划论的松弛方法,8.2,拉格朗日松弛理论,8.3,拉格朗日松弛的进一步讨论,8.4,拉格朗日松弛算法,8.5,应用案例,:,能力约束单机排序问题,主要内容,:,目标值,最优值,基于数学规划,:,分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。,现代优化算法：禁忌搜索法、模拟退火法、遗传算法、蚁群算法等的目标值。,其它算法：分解法、组合算法等的目标值。,下界算法：线性规划松弛、拉格朗日松弛等的目标值。,例子,1:,线性规划松弛,:,在,7.1.1,中,将整数约束松弛为实数,称其为,7.1.1,的线性规划松弛,:,注,:,定理,7.1.1:,此类算法适合于整数规划问题中,决策变量为较大整数的情形,.,此类算法分两阶段,:,第一阶段为求松弛后线性规划问题的最优解,;,第二阶段为将解整数化,并考虑可行性,.,例,2:,对偶规划松弛方法,:7.1.2,的对偶形式为,:,其中,Y,为决策变量,.,注,:,由对偶理论知,7.1.2,和,7.1.3,有相同的最优值,至于采用其中的哪个模型求解,7.1.1,的下界,需比较哪个计算简单,.,例,3.,代理松弛法,:,当,(7.1.1),中的约束太多时,代理松弛一个约束,代替,(7.1.1),中的,K,个约束,极端情况可以用一个代替全部,注,:,代理松弛法保证目标函数,整数规划约束不变,显然,由代理松弛法求得的解不一定可行,例,4.,拉格朗日松弛方法,基本原理,:,将目标函数中造成问题难的约束吸 收到目标函数中,并保持目标函数的线性,使问题容易求解,.,Q:,为什么对此类方法感兴趣,?,A:(1).,在一些组合优化中,若在原问题中减少一些约束,则使得问题求解难度大大降低,.(,我们把这类约束称为难约束,).,(2).,实际的计算表明此种方法所得到的结果相当不错,.,7.1,基于规划论的松弛方法,松弛的定义（,7.1.1,）,:,问题,整数规划模型,:,满足下列性质时,称为,7.1.1,的一个松弛,(relaxation).,可行解区域兼容,:,目标函数兼容,:,其中,为,7.1.1,的可行域,.,例,7.1.1 set covering problem,问题描述,:,设,所有,且每一列对应一个费用,表示第,j,列覆盖第,i,行,要求在最小的费用下选择一些列,使其覆盖所有的行,.,松弛问题,:,松弛模型,:,以上问题很容易求得最优解,7.2,拉格朗日松弛理论,原整数规划问题,拉格朗日松弛,定理,7.2.1 LR,同下整数规划问题,(7.2.1),有相同 的复杂性,且若,IP,可行解非空，则,:,证明,:,注,:,定理,7.2.1,说明拉格朗日松弛是,IP,问题的一个下界,但我们应该求与,IP,最接近的下界,即,:,定义,7.2.1,若,满足以下条件,则称,D,为凸集,.,对于离散点集,其凸包定义为,:,显然,Con(Q,),为凸集,.,定理,7.2.2,若拉格朗日对偶问题的目标值有限,则,证明,:,设,Con(Q,),的极点为,极方向为 则,:,由,LD,问题有限,则有,:,上述问题等价于,:,整理得,:,其对偶问题为,:,即有,:,推论,7.2.1:,对于任给,c,整数规划问题,IP,和拉 格 朗日对偶问题,LD,的目标值相等的充要条件为,:,证,:,显然有,从而有,:,再由定理,7.2.2:,若对任何,c,有,则问题得证,.,例,7.2.1,假设整数规划问题,IP,第一个约束为复杂约束,其拉格朗日松弛后的模型,LR,为,:,4,3,2,1,1,2,3,4,l,2,l,1,l,4,l,3,E,D,C,B,A,7.2.3,图解示意,下降方向,最优解,(7,2),(3,4),-29,(7.5,1),(4,0),-32,(8,0),(4,0),-32,单位化下降方向,:,最优值只能在,(4,0),和,(3,4),两点得到,过这两点的直线方程,:y+x4=16.,其垂直方向为,:,综合有,:,例,7.2.2(,继,7.2.1),例,7.2.1,中,4,3,2,1,1,2,3,4,D,C,B,4,3,2,1,1,2,3,4,D,C,B,S1,S2,由推论,7.2.1,可以知道,由两个因素有关,:,第一个因素是目标函数中的,C,推论,7.2.1,要求对所有的,C,满足,S1=S2,但也可能存在某个,C,使得,第二个因素是可行解的区域,.,由上面的图形可知,SI,和,S2,不同,所以存在一个,C,使得 不为零,如在例,7.2.1,中,在 达到拉格朗日对偶问题的最优值,其最优解为,(4,0);,其一个最优解也为,(4,0).,由此我们可以知道,即使拉格朗日松弛在某个 下达到的最优解为原问题的可行解,我们也不能断言,.,除非此时,.,定理,7.2.3,若线性规划松弛问题,LP,存在可行解,则,注,:,此定理说明,拉格朗日松弛对偶后的目标值 是,IP,问题的一个下界,且不比 差,.,定理,7.2.3,的充要条件是存在 和 使得,:,证明,：、充分性：,、必要性：,记为问题的最优解，为问题的最优解，则：,例,7.2.3(,继例,7.2.1),时,为问题的一个可行解,此时,:,一般情况下,可大致估计,:,7.3.,拉格朗日松弛的进一步讨论,目的,:,对非标准的拉格朗日形式讨论,.,一、等号约束的松弛,二、,LR,最优解和,LP,最优解的关系,具体例见例,7.3.1,。,定理,7.3.1,的充要条件为：,三、拉格朗日松弛的整数性,定义,7.3.1,若,LR,的最优解与其整数约束无关，则称该问题具有整数性，即：,定理,7.3.2,若,LR,具有整数性，则,四、拉格朗日分解,7.4,拉格朗日松弛算法,7.4.1,次梯度算法（,subgradient,optimization,）,定义：,（,凹函数）函数 满足以下条件称为凹函数,定理,7.4.1,若,LR,的可行解集合,Q,为有限个实数点集，则以下函数为凹函数,定理,7.4.1,函数为凹函数的充要条件为：,证明 必要性：设 为凹函数，则,H,为凸集,为边界点,所以存在过 和法方向 的支撑超平面 满足,:,充分性,:,A,B,C,定义,7.4.2,若 为凹函数,在 向量满足,:,则称 为 在 的一个次梯度,所有的次梯度集合记为,:,定理,7.4.3,若 为凹函数,为 的充要条件为,定理,7.4.4,设,LR,的可行解集合,Q,由有限个整数点组成,其极点为 有,:,证明,:,注,:,若 不是最大值点,则相交的两个同目标值的平面 满足,且,两平面的法方向交角不超过,90,度,.,当 不是光滑点是,在 的邻域内,当 充分小时,存在,使得,:,由 内所有次梯度夹角不超过,90,度,有,由上面的讨论可得,次梯度优化算法,如下,:,STEP1:,任选初始拉格朗日乘子,STEP2:,对,从 中任选一个次梯度,若 则停,否则 重复,STEP2.,注,:,1,、的选取,:,2,、停止准则：,7.4.2,拉格朗日启发式算法,Step1:,拉格朗日次梯度法求,IP,下界,Step2:,对所求解可行化,例,7.4.1,假设集合覆盖问题,SC,通过前面的松弛得到一个解,当其不可行时即存在,i,使得,一个可行化方法是求,k,满足,重复以上步骤,直到所有行都被覆盖,.,集合覆盖问题的拉格朗日松弛算法,:,Step1:,初始化,Step2:,计算,Step3:,若所有行被覆盖,stop;or,记 表示第,i,行没有被覆盖,在没有被覆盖的行中任选一行,k,计算,Step4:,例,7.4.2,对集合覆盖问题,假设,:,最优解为,:,第三行没有被覆盖,在可覆盖第三行中选费用最小的列,7.5,案例应用 能力约束单机排序问题,约束条件,(1):,产品需求两约束,约束条件,(2):,个时段产能约束,约束条件,(3):,准备时间,下算法的基本思想是将 中较大权数所对应的产品尽可能早地生产,Step1:,当 时,依时段,t,能力 约束,(2),将 尽可能往前安排直到 全部 生产,可能出现以下几种情况,:(a),若 的全部需求没有全部生产,且时段,t,的能力足以满足 的生产准备，则以时段,t,的最大余能力生产 ，剩余未能生产的分到 时段，返回,step1;(b),若的全部需求已生产，则当 时停止，否则 返回,step1;(c),若 没有全部产出，且无法在该时段生产，则,返回,step1;,Step0:,从第一时段 开始,;,Step2:,若 则 返回,step2.,算法,能力约束排序问题的拉格朗日松弛算法,求解以上,LRP,问题分以下两步,:,(1),对给定的,求下子问题,(SUBP),(2),对所有 求,定理,7.5.2,对于充分大,T,若 已知且非负,则,SUBP,一定有以下形式的最优解,注,:,由此定理可知,求,SUBP,最优解只要判断,若 为满足,(4),的最优解,则下向量为,LRP,的次梯度,.,Step0:,为算法,A,求得的目标值,Step1:,解,SUBP,以,(4),式分别求每个产品的最优 值,再由,(5),求其次梯度,若不满足判定准则,则,Step2:,若所求到的解为,WCS,可行解,停,;,否则将其 可行化,.,算法,B:,