拉格朗日松弛算法求解组合优化问题概要.ppt

定理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. 算法Ａ * * Chapter 7:拉格朗日松弛算法 7.1 基于规划论的松弛方法 7.2 拉格朗日松弛理论 7.3 拉格朗日松弛的进一步讨论 7.4 拉格朗日松弛算法 7.5 应用案例:能力约束单机排序问题 主要内容: 目标值 最优值 基于数学规划: 分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。 现代优化算法：禁忌有哪些信誉好的足球投注网站法、模拟退火法、遗传算法、蚁群算法等的目标值。 其它算法：分解法、组合算法等的目标值。 下界算法：线性规划松弛、拉格朗日松弛等的目标值。 例子1: 线性规划松弛: 在7.1.1中,将整数约束松弛为实数, 称其为7.1.1的线性规划松弛: 注: 定理7.1.1: 此类算法适合于整数规划问题中,决策变量为较大整数的情形.