《第8章松弛算法.ppt》由会员分享,可在线阅读,更多相关《第8章松弛算法.ppt(48页珍藏版)》请在三一文库上搜索。
1、Chapter 8:拉格朗日松弛算法,8.1 基于规划论的松弛方法 8.2 拉格朗日松弛理论 8.3 拉格朗日松弛的进一步讨论 8.4 拉格朗日松弛算法 8.5 应用案例:能力约束单机排序问题,主要内容:,目标值,最优值,基于数学规划: 分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。,现代优化算法:禁忌搜索法、模拟退火法、遗传算法、蚁群算法等的目标值。,其它算法:分解法、组合算法等的目标值。,下界算法:线性规划松弛、拉格朗日松弛等的目标值。,例子1: 线性规划松弛: 在7.1.1中,将整数约束松弛为实数, 称其为7.1.1的线性规划松弛:,注:,定理7.1.1: 此类算法适合
2、于整数规划问题中,决策变量为较大整数的情形. 此类算法分两阶段: 第一阶段为求松弛后线性规划问题的最优解; 第二阶段为将解整数化,并考虑可行性.,例2: 对偶规划松弛方法: 7.1.2的对偶形式为:,其中Y为决策变量.,注:,由对偶理论知,7.1.2和7.1.3有相同的最优值,至于采用其中的哪个模型求解7.1.1的下界,需比较哪个计算简单.,例3. 代理松弛法:,当(7.1.1)中的约束太多时,代理松弛一个约束,代替(7.1.1)中的K个约束,极端情况可以用一个代替全部,注: 代理松弛法保证目标函数,整数规划约束不变, 显然,由代理松弛法求得的解不一定可行,例4. 拉格朗日松弛方法,基本原理:
3、 将目标函数中造成问题难的约束吸 收到目标函数中,并保持目标函数的线性,使问题容易求解.,Q:为什么对此类方法感兴趣?,A: (1). 在一些组合优化中,若在原问题中减少一些约束,则使得问题求解难度大大降低.(我们把这类约束称为难约束). (2). 实际的计算表明此种方法所得到的结果相当不错.,7.1 基于规划论的松弛方法,松弛的定义(7.1.1): 问题,整数规划模型:,满足下列性质时,称为7.1.1的一个松弛(relaxation). 可行解区域兼容: 目标函数兼容:,其中, 为7.1.1的可行域.,例7.1.1 set covering problem,问题描述: 设 ,所有 ,且每一列
4、对应一个费用 , 表示第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)的极点为 ,极方向为 则
5、:,由LD问题有限,则有:,上述问题等价于:,整理得:,其对偶问题为:,即有:,推论7.2.1: 对于任给c,整数规划问题IP和拉 格 朗日对偶问题LD的目标值相等的充要条件为:,证: 显然有,从而有:,再由定理7.2.2:,若对任何c有 ,则问题得证.,例7.2.1 假设整数规划问题IP,第一个约束为复杂约束,其拉格朗日松弛后的模型LR为:,4,3,2,1,1,2,3,4,l2,l1,l4,l3,E,D,C,B,A,7.2.3图解示意,单位化下降方向:,最优值只能在(4,0)和(3,4)两点得到,过这两点的直线方程:y+x4=16.其垂直方向为:,综合有:,例7.2.2(继7.2.1) 例7
6、.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存
7、在可行解,则,注:此定理说明,拉格朗日松弛对偶后的目标值 是IP 问题的一个下界,且不比 差.,定理7.2.3 的充要条件是存在 和 使得:,证明:、充分性:,、必要性:,记 为问题的最优解, 为问题的最优解,则:,例7.2.3 (继例7.2.1) 时, 为问题的一个可行解,此时:,一般情况下,可大致估计:,7.3. 拉格朗日松弛的进一步讨论,目的: 对非标准的拉格朗日形式讨论.,一、等号约束的松弛,二、LR最优解和LP最优解的关系,具体例见例7.3.1。,定理7.3.1 的充要条件为:,三、拉格朗日松弛的整数性,定义7.3.1 若LR的最优解与其整数约束无关,则称该问题具有整数性,即:,定理
8、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
9、.4 设LR的可行解集合Q由有限个整数点组成,其极点为 有:,证明:,注: 若 不是最大值点,则相交的两个同目标值的平面 满足,且,两平面的法方向交角不超过90度.,当 不是光滑点是,在 的邻域内,当 充分小时,存在 ,使得:,由 内所有次梯度夹角不超过90度,有,由上面的讨论可得次梯度优化算法如下:,STEP1: 任选初始拉格朗日乘子,STEP2: 对 ,从 中任选一个次梯度 ,若 则停,否则 重复STEP2.,注:,1、 的选取:,2、停止准则:,7.4.2 拉格朗日启发式算法,Step1: 拉格朗日次梯度法求IP下界,Step2: 对所求解可行化,例7.4.1 假设集合覆盖问题SC通过前
10、面的松弛得到一个解 ,当其不可行时即存在i使得,一个可行化方法是求k,满足,重复以上步骤,直到所有行都被覆盖.,集合覆盖问题的拉格朗日松弛算法:,Step1: 初始化,Step2: 计算,Step3: 若所有行被覆盖,stop; or 记 表示第i行没有被覆盖,在没有被覆盖的行中任选一行k,计算,Step4 :,例7.4.2 对集合覆盖问题,假设:,最优解为:,第三行没有被覆盖,在可覆盖第三行中选费用最小的列,7.5 案例应用 能力约束单机排序问题,约束条件(1): 产品需求两约束 约束条件(2): 个时段产能约束 约束条件(3): 准备时间,下算法的基本思想是将 中较大权数所对应的产品尽可能
11、早地生产,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:,
链接地址:https://www.31doc.com/p-2967969.html