第8章松弛算法.ppt
Chapter 8:拉格朗日松弛算法8.1 基于规划论的松弛方法基于规划论的松弛方法8.2 拉格朗日松弛理论拉格朗日松弛理论8.3 拉格朗日松弛的进一步讨论拉格朗日松弛的进一步讨论8.4 拉格朗日松弛算法拉格朗日松弛算法8.5 应用案例应用案例:能力约束单机排序问题能力约束单机排序问题主要内容:目标值最优值基于数学规划:分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。现代优化算法：禁忌搜索法、模拟退火法、遗传算法、蚁群算法等的目标值。其它算法：分解法、组合算法等的目标值。下界算法：线性规划松弛、拉格朗日松弛等的目标值。例子1:线性规划松弛:在7.1.1中,将整数约束松弛为实数,称其为7.1.1的线性规划松弛:min7.1.2,.TLPnZc xAxbstxR注:1.定理7.1.1:2.此类算法适合于整数规划问题中,决策变量为较大整数的情形.3.此类算法分两阶段:第一阶段为求松弛后线性规划问题的最优解;第二阶段为将解整数化,并考虑可行性.LPIPZZ例2:对偶规划松弛方法:7.1.2的对偶形式为:max7.1.3,.TDPTnZy bA ycstyR其中Y为决策变量.注:由对偶理论知,7.1.2和7.1.3有相同的最优值,至于采用其中的哪个模型求解7.1.1的下界,需比较哪个计算简单.例3.代理松弛法:当(7.1.1)中的约束太多时,代理松弛一个约束代替(7.1.1)中的K个约束极端情况可以用一个代替全部111()kknKKi jjijkkaxb 1,1kkni jjijaxbkK111()nmmi jjijkkaxb 注:代理松弛法保证目标函数,整数规划约束不变,显然,由代理松弛法求得的解不一定可行例4.拉格朗日松弛方法基本原理:将目标函数中造成问题难的约束吸 收到目标函数中,并保持目标函数的线性,使问题容易求解.Q:为什么对此类方法感兴趣?A:(1).在一些组合优化中,若在原问题中减少一些约束,则使得问题求解难度大大降低.(我们把这类约束称为难约束).(2).实际的计算表明此种方法所得到的结果相当不错.7.1 基于规划论的松弛方法松弛的定义（7.1.1）:问题整数规划模型:min7.1.1,.TIPnZc xAxbstxZ:min()RRRx SRPZzx满足下列性质时,称为7.1.1的一个松弛(relaxation).(1)可行解区域兼容:(2)目标函数兼容:(),TRc xzxxS RSS其中,为7.1.1的可行域.S例7.1.1 set covering problem问题描述:设 ,所有 ,且每一列对应一个费用 ,表示第j列覆盖第i行,要求在最小的费用下选择一些列,使其覆盖所有的行.()ijm nAa0,1ija(1)jcjn 1ija 11min().1,10,1,1nscjjjni jjjjzc xSCsta ximxjn松弛问题:111min(1)().0,1,10nmnLRSCjjiijjjijjzc xa xLRSCst xjn松弛模型:11min().0,1,10nmLRSCjjijijzd xLRSCst xjn1mjjiijidca以上问题很容易求得最优解1,0*0,jdxother7.2 拉格朗日松弛理论min,():.,.TIPnZc xAxbIPstBxdxZ难约束（简单约束）|,nSxZAxb Bxd()min():,.TTLRnZc xbAxLRBxdstxZ（简单约束）原整数规划问题拉格朗日松弛|nLRSxZBxd定理7.2.1 LR同下整数规划问题(7.2.1)有相同 的复杂性,且若IP可行解非空，则:0,()LRIPzzmin.(7.2.1)Tnc xst BxdxZ()min():,.TTTLRnZcA xbLRBxdstxZ（简单约束）min,():.,.TIPnZc xAxbIPstBxdxZ难约束（简单约束）证明:注:定理7.2.1说明拉格朗日松弛是IP问题的一个下界,但我们应该求与IP最接近的下界,即:0()max()LDLRLDzz定义7.2.1 若 ,满足以下条件,则称D为凸集.,x yD(1),01xyD1()|,1iiiiiiCon QPPR|1,2,iQP i对于离散点集 ,其凸包定义为:显然Con(Q)为凸集.定理7.2.2 若拉格朗日对偶问题的目标值有限,则min|,()|,TLDnzc x Axb xCon QQx Bxd xZ其中：证明:()()()min()min()min()TTTLRx QTTTx Con QTTx Con QzcA xbcA xbc xbAx设Con(Q)的极点为 ,极方向为 则:|kxkK|jrjJ,()0min()(),:TTjTTTTkTkx Qif jJcA rcA xbc xbAxother kK 由LD问题有限,则有:000max()maxmin()TTkTkLDLRk Kzzc xbAx Tj存在，jJ,使得(c-A)r0上述问题等价于:max(),.()0,0LDTkTkTTjzc xbAxkKstcA rjJ 整理得:max(),.,0LDTkTkTjTjzAxbc xkKstArc rjJ 其对偶问题为:min()1.()0,;0,.kLDkjjk Kj Jkk Kkjkkkk Kk Kk KkjzcTxrstAxrbkKjJ即有:()min.TLDx Con Qzc xstAxb推论推论7.2.1:对于任给c,整数规划问题IP和拉 格 朗日对偶问题LD的目标值相等的充要条件为:(|)()|nnCon QxRAxbCon QxRAxb证:显然有|()|nnQxRAxbCon QxRAxb(|)()|)()|nnnCon QxRAxbCon Con QxRAxbCon QxRAxb从而有:再由定理7.2.2:(|)()|minminnnTTIPLDx Con Qx RAx bx Con Qx RAx bzc xzc x若对任何c有 ,则问题得证.IPLDzz例7.2.1 假设整数规划问题IP12121212122min 7224520227.7.2.224IPzxxxxxxxxstxxxZ 第一个约束为复杂约束,其拉格朗日松弛后的模型LR为:121212122()min(7)(22)4 520227.27.2.34LRzxxxxxxstxxxZ 43211234l2l1l4l3EDCBA41(,)1717T7.2.3图解示意下降方向最优解 (7,2)(3,4)-29 (7.5,1)(4,0)-32 (8,0)(4,0)-32()LRz0121(7,22)T12(),()Txx(,*)LRzx22722(,)53655365T单位化下降方向:2272212lim(,)(,)5553655365TT最优值只能在(4,0)和(3,4)两点得到,过这两点的直线方程:y+x4=16.其垂直方向为:41(,)1717T22722411,(,)9171753655365T综合有:1290119()()281992889LRLDLRzzz 例7.2.2(继7.2.1)例7.2.1中 (2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,0)TTTTTTTTQ 12121(|24)2()|24nnSCon QxRxxSCon QxRxx 43211234DCB1224xx 43211234DCB1224xx S1S2由推论7.2.1可以知道,由两个因素有关:第一个因素是目标函数中的C,推论7.2.1要求对所有的C满足S1=S2,但也可能存在某个C使得 IPLDzzIPLDzz第二个因素是可行解的区域.由上面的图形可知,SI和S2不同,所以存在一个C,使得 不为零,如在例7.2.1中,在 达到拉格朗日对偶问题的最优值,其最优解为(4,0);,其一个最优解也为(4,0).由此我们可以知道,即使拉格朗日松弛在某个 下达到的最优解为原问题的可行解,我们也不能断言 .除非此时 .IPLDzz8289LDz 1928IPz IPLDzz0定理7.2.3 若线性规划松弛问题LP存在可行解,则LPLDIPzzz注:此定理说明,拉格朗日松弛对偶后的目标值 是IP 问题的一个下界,且不比 差.LDzLPz定理7.2.3 的充要条件是存在 和 使得:IPLDzz*0*|,nxxZAxb Bxd112212*()(0)(*,*)*(*)(*)(0)TTTLRbAxzxc xbAxz 证明：、充分性：212(*)(*,*)*TLDLRLRIPzzzxc xz、必要性：记为问题的最优解，为问题的最优解，则：*x*(*)*(*)(*)(*,*)*(*)(*)(*,*)TTLDLRLRTIPLRzzc xbAxzzxzbAxzzx*(*)(*)(*,*)IPLDTLRzzbAxzzx12*(*),(*)(*,*)TLRbAxzzx 记：212(*,*)*(*)(*)TTLRzxc xbAxz则：例7.2.3(继例7.2.1)时,为问题的一个可行解,此时:1*9*(4,0)x 121*(*)(44)9(*,*)*(*)882828(*)99TLRbAxzxc xbAxz 21288099IPLDzz其中，有，故：一般情况下,可大致估计:121*(*)(44),2(*,*)*(*)284(*)TLRbAxzxc xbAxz 32(*)322840,4LRIPLDzzz 2于是：故：7.3.拉格朗日松弛的进一步讨论目的:对非标准的拉格朗日形式讨论.一、等号约束的松弛121212()()()(),ijjiijjiijjiiiijjiiijjiiiijjiiiia xba xba xbba xba xba x nj=1nnj=1j=1nnnj=1j=1j=1将等号约束写成标准形式：，把两个约束吸收到目标函数有：若令则 无非负约束。二、LR最优解和LP最优解的关系()()TIPxIPc xzTLRn+对于给定的0，z()=minc x+(b-Ax)（LR）s.t.BxdxZ的最优解为问题可行，并不能有具体例见例7.3.1。定理7.3.1 的充要条件为：IPLDzz*0*()0,(*)(*,*)TLRxIPbAxzzx存在，为可行解，使得：三、拉格朗日松弛的整数性定义7.3.1 若LR的最优解与其整数约束无关，则称该问题具有整数性，即：()min().()()min().TTLRnTTLRLnzc xbAxBxdstxZLRLRLzc xbAxBxdstxR与线性松弛最优解相同。定理7.3.2 若LR具有整数性，则LDIPzz四、拉格朗日分解1minminmin().,()min(7.3.8).TIPTTTIPnnnTTLRnzc xzc xc xxyAxbAxbAxbxystBydstBxdstBydx yZxZx yZzc xxzandAxbstxZ2()min(7.3.9).TLRnyBydstyZ1212()()max()()LRLRIPLDLRLRzzzzzz有：其对偶形式：7.4 拉格朗日松弛算法7.4.1 次梯度算法（subgradient optimization）定义：（凹函数）函数 满足以下条件称为凹函数 1:mg RR(1)()(1)(),mgxyg xg yx yR定理7.4.1 若LR的可行解集合Q为有限个实数点集，则以下函数为凹函数()min()|TTLRzc xbAxxQ定理7.4.1 函数为凹函数的充要条件为：1*,(,),(*)()(*)mTmTmxRsssg xg xsxxxR 使得：证明 必要性：设 为凹函数，则()g x112211221212121212(,)|()(,),(,)(,)(1)(,)(1),(1):(1)()(1)()(1)Hx zzg xandx zxzHx zxzxxzzgxxg xg xzz有:满足H为凸集,为边界点,所以存在过 和法方向 的支撑超平面 满足:(*,(*)xg x(*,(*)xg xs(*)()(*)Tmg xg xsxxxR 充分性
