文档介绍：第8章松弛算法
目标值
最优值
基于数学规划: 分支定界法、割平面法、线性规划松弛再对目标函数可行化等的目标值。
现代优化算法：禁忌搜索法、模拟退火法、遗传算法、蚁群算法等的目标值。
其它算法：分解法、组合算法等的目标值。
差.
的充要条件是存在 和 使得:
证明：１、充分性：
２、必要性：
记 为ＩＰ问题的最优解， 为ＬＤ问题的最优解，则：
() 时, 为问题的一个可行解,此时:
一般情况下,可大致估计:
. 拉格朗日松弛的进一步讨论
目的: 对非标准的拉格朗日形式讨论.
一、等号约束的松弛
二、LR最优解和LP最优解的关系
。
的充要条件为：
三、拉格朗日松弛的整数性
若LR的最优解与其整数约束无关，则称该问题具有整数性，即：
若LR具有整数性，则
四、 拉格朗日分解
拉格朗日松弛算法
次梯度算法（subgradient optimization）
定义：（凹函数） 函数 满足以下条件称为凹函数
若LR的可行解集合Q为有限个实数点集，则以下函数为凹函数
函数为凹函数的充要条件为：
证明 必要性：设 为凹函数，则
H为凸集, 为边界点,所以存在过 和法方向 的支撑超平面 满足:
充分性:
A
B
C
若 为凹函数,在 向量满足:
则称 为 在 的一个次梯度,所有的次梯度集合记为:
若 为凹函数, 为 的充要条件为
设LR的可行解集合Q由有限个整数点组成,其极点为 有:
证明:
注: 若 不是最大值点,则相交的两个同目标值的平面 满足
且,两平面的法方向交角不超过90度.
当 不是光滑点是,在 的邻域内,当 充分小时,存在 ,使得:
由 内所有次梯度夹角不超过90度,有
由上面的讨论可得次梯度优化算法如下:
STEP1: 任选初始拉格朗日乘子
STEP2: 对 ,从 中任选一个次梯度 ,若 则停,否则 重复STEP2.
注:
1、 的选取:
2、停止准则：
拉格朗日启发式算法
Step1: 拉格朗日次梯度法求IP下界
Step2: 对所求解可行化
假设集合覆盖问题SC通过前面的松弛得到一个解 ,当其不可行时即存在i使得
一个可行化方法是求k,满足
重复以上步骤,直到所有行都被覆盖.
集合覆盖问题的拉格朗日松弛算法:
Step1: 初始化
Step2: 计算
Step3: 若所有行被覆盖,stop; or 记 表示第i行没有被覆盖,在没有被覆盖的行中任选一行k,计算
Step4 :
对集合覆盖问题
假设:
最优解为:
第三行没有被覆盖,在可覆盖第三行中选费用最小的列
案例应用 能力约束单机排序问题
约束条件(1): 产品需求两约束
约束条件(2): 个时段产能约束
约束条件(3): 准备时间
下算法Ａ的基本思想是将 中较大权数所对应的产品尽可能早地生产．
Step1: 当 时, ,依时段t能力 约束(2),将 尽可能往前安排直到 全部 生产,可能出现以下几种情况: