《chaper松弛算法》ppt课件_第1页
《chaper松弛算法》ppt课件_第2页
《chaper松弛算法》ppt课件_第3页
《chaper松弛算法》ppt课件_第4页
《chaper松弛算法》ppt课件_第5页
已阅读5页,还剩43页未读 继续免费阅读

下载本文档

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

文档简介

1、Chapter 7:拉格朗日松弛算法7.1 基于规划论的松弛方法基于规划论的松弛方法7.2 拉格朗日松弛实际拉格朗日松弛实际7.3 拉格朗日松弛的进一步讨论拉格朗日松弛的进一步讨论7.4 拉格朗日松弛算法拉格朗日松弛算法7.5 运用案例运用案例:才干约束单机排序问题才干约束单机排序问题主要内容:目的值最优值基于数学规划: 分支定界法、割平面法、线性规划松弛再对目的函数可行化等的目的值。现代优化算法:忌讳搜索法、模拟退火法、遗传算法、蚁群算法等的目的值。其它算法:分解法、组合算法等的目的值。下界算法:线性规划松弛、拉格朗日松弛等的目的值。例子1: 线性规划松弛: 在7.1.1中,将整数约束松弛为

2、实数, 称其为7.1.1的线性规划松弛:min7.1.2,. .TLPnZc xAxbstxR注: 定理7.1.1: 此类算法适宜于整数规划问题中,决策变量为较大整数的情形. 此类算法分两阶段: 第一阶段为求松弛后线性规划问题的最优解; 第二阶段为将解整数化,并思索可行性.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)中的约束太多时,代理松弛一个约

3、束替代(7.1.1)中的K个约束极端情况可以用一个替代全部111()kknKKi jjijkkaxb 1,1kkni jjijaxbkK111()nmmi jjijkkaxb 注: 代理松弛法保证目的函数,整数规划约束不变, 显然,由代理松弛法求得的解不一定可行例4. 拉格朗日松弛方法根本原理: 将目的函数中呵斥问题难的约束吸 收到目的函数中,并坚持目的函数的线性,使问题容易求解.Q:为什么对此类方法感兴趣?A: (1). 在一些组合优化中,假设在原问题中减少一些约束,那么使得问题求解难度大大降低.(我们把这类约束称为难约束). (2). 实践的计算阐明此种方法所得到的结果相当不错.7.1 基

4、于规划论的松弛方法松弛的定义7.1.1: 问题整数规划模型:min7.1.1,. .TIPnZc xAxbstxZ:min( )RRRx SRPZzx满足以下性质时,称为7.1.1的一个松弛(relaxation).可行解区域兼容:目的函数兼容:( ),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

5、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

6、LR同下整数规划问题(7.2.1)有一样 的复杂性,且假设IP可行解非空,那么:0,( )LRIPzz min. .(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对于

7、离散点集 ,其凸包定义为:显然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 xbA

8、x 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的目的值相等的充要条件为的目的值相等的充要条件为:(|)

9、( )|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为:121212

10、122( )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(,)1717T2

11、2722411,(,)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使得 I

12、PLDzzIPLDzz第二个要素是可行解的区域.由上面的图形可知,SI和S2不同,所以存在一个C,使得 不为零,如在例7.2.1中, ,在 到达拉格朗日对偶问题的最优值,其最优解为(4,0); ,其一个最优解也为(4,0).由此我们可以知道,即使拉格朗日松弛在某个 下到达的最优解为原问题的可行解,我们也不能断言 .除非此时 .IPLDzz8289LDz 1928IPz IPLDzz0定理7.2.3 假设线性规划松弛问题LP存在可行解,那么LPLDIPzzz注:此定理阐明,拉格朗日松弛对偶后的目的值 是IP 问题的一个下界,且不比 差.LDzLPz定理7.2.3 的充要条件是存在 和 使得:IP

13、LDzz*0*|,nxxZAxb Bxd112212* ()(0)( *, *)* (*)( *)(0)TTTLRbAxzxc xbAxz 证明:、充分性:212( *)( *, *)*TLDLRLRIPzzzxc xz、必要性:记为问题的最优解,为问题的最优解,那么:*x*( *)* (*)( *)( *, *)* (*)( *)( *, *)TTLDLRLRTIPLRzzc xbAxzzxzbAxzzx* (*)( *)( *, *)IPLDTLRzzbAxzzx12* (*),( *)( *, *)TLRbAxzzx 记:212( *, *)* (*)( *)TTLRzxc xbAxz则

14、:例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

15、 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的最优解与其整数约束无关,那么称该问题具有整数性,即

16、:( )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有:

17、其对偶形式: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)

18、(,)(1),(1):(1)()(1) ()(1)Hx zzg xandx zxzHx zxzxxzzgxxg xg xzz有:满足H为凸集, 为边境点,所以存在过 和法方向 的支撑超平面 满足:( *, ( *)xg x( *, ( *)xg xs( *)( )( *)Tmg xg xsxxxR 充分性:1212,01, *(1)x xxxx有:1122121212( *)()( *), ( *)()( *)( *)(1)*)()(1) ()( *)()(1) ()TTTg xg xsxxg xg xsxxg xsxxxg xg xg xg xg x则有:即:ABC3S4S( )LRz( )

19、LRz函数示意图定义7.4.2 假设 为凹函数,在 向量满足: 1( ) :mg xRR*mxRmsR( *)(*)( )Tmg xsxxg xxR 那么称 为 在 的一个次梯度,一切的次梯度集合记为: ( )g xs( *)g x*x定理7.4.3 假设 为凹函数, 为 的充要条件为( )g x*xmax ( )|mg xxR0( *)g x 定理7.4.4 设LR的可行解集合Q由有限个整数点组成,其极点为 有: ()kxkK( *)min* ()TTLRk Kzc xbAx* |( *)(), |,1,0( *)TiTiLRiiiiiiLRi IIi zc xbAxiI sbAxs ssz

20、*LR记:则对任意为z ()的次梯度且:证明:*( ) (*)()()() ()( )( *)i TTiTiTiTiTiTiLRLRsbAxbAxc xbAxc xbAxzz 注: 假设 不是最大值点,那么相交的两个同目的值的平面 满足 *1122:()():()()TiTiTjTjc xbAxDc xbAxD12*DD且,两平面的法方向交角不超越90度.当 不是光滑点是,在 的邻域内,当 充分小时,存在 ,使得:*max *,0isjI( )()TjTjLRzc xbAx由 内一切次梯度夹角不超越90度,有( *)LRz( )( *)(*) ()()()0TjijLRLRzzbAxbAxbA

21、x由上面的讨论可得次梯度优化算法如下:STEP1: 任选初始拉格朗日乘子 STEP2: 对 ,从 中任选一个次梯度 ,假设 那么停,否那么 反复STEP2.,1ttt()tgts0ts 1max,0, :1tttstt 注:1、 的选取:10:,0,(,1981):,01( )( ):|ttttUPLPtttatFisherbztztcs 2、停顿准那么::0(),|:( )( ):()tttLRUPLPttLRaTb szorsc ztztdz迭代次数上限或在一定步数内变化不超过某给定值7.4.2 拉格朗日启发式算法Step1: 拉格朗日次梯度法求IP下界Step2: 对所求解可行化例7.4

22、.1 假设集合覆盖问题SC经过前面的松弛得到一个解 ,当其不可行时即存在i使得12(,)nxx xx10nijjja x一个可行化方法是求k,满足1min|1kji jj ncca 反复以上步骤,直到一切行都被覆盖.集合覆盖问题的拉格朗日松弛算法:Step1: 初始化0,0tStep2: 计算()tLRzStep3: 假设一切行被覆盖,stop; or 记 表示第i行没有被覆盖,在没有被覆盖的行中任选一行k,计算1is min|1,1,kjkjkdas其中1mtjjljldcaStep4 : 11,2tkktitiikttstepik 返回例7.4.2 对集合覆盖问题12341314234mi

23、n23451. .110,1,1,2,3,4jxxxxxxstxxxxxxj假设:(1.5,1.6,2.3)T1234( )min 1.10.80.31.25.3LRzxxxx( )LRz最优解为:(1,0,0,0,),( )4.2LRxz第三行没有被覆盖,在可覆盖第三行中选费用最小的列min0.8,0.3,1.20.3代替1231.501.602.20.3124( )min 1.10.50.9 5.64.5LRzxxxLR1324最优解为:x =x =1,x =x =07.5 案例运用 才干约束单机排序问题111mod:min,1,2,1max ,11,0.0,1,2;1,2,0iniiiT

24、ititniitiittiiitititelZTxd ina xsYc tT inifxstYotherintx(1)(2)(3):iiitiiTdxtidiati:完成 所需要的时段;: 时段产品的产量;产品的需求;:产品i的单位产品所占用的生产能力;c :t时段可提供的生产能力;s: i产品的生产准备所占用的能力。约束条件(1): 产品需求两约束约束条件(2): 个时段产能约束约束条件(3): 预备时间,ititixY T为自由变量,为因变量下算法的根本思想是将 中较大权数所对应的产品尽能够早地消费,1iin Step1: 当 时, ,依时段t才干 约束(2),将 尽能够往前安排直到 全部

25、 消费,能够出现以下几种情况: (a)假设 的全部需求没有全部消费,且时段t的才干足以满足 的消费预备,那么以时段t的最大余才干消费 ,剩余未能消费的分到 时段, 前往step1; (b) 假设的全部需求已消费,那么当 时停顿,否那么 前往step1; (c)假设 没有全部产出,且无法在该时段消费, 那么 ,前往step1;Step0: ,从第一时段 开场;,1,2SUn1t U*max|iiiU*i* id*i*i*i1t 1tt *i *SSi1,SnUUS *UUiStep2: 假设 那么 前往step2.,1,USn1,1,ttUnS 算法才干约束排序问题的拉格朗日松弛算法0111mod

温馨提示

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

评论

0/150

提交评论