拉格朗日松弛算法

《拉格朗日松弛算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章拉格朗日松弛算法当一个组合优化问题被判定为NP完全或NP难时，解决这个问题的常用方法是构造启发式算法，求尽量接近最优解的可行解。这些算法包括第二章至第六章的局部搜索算法、禁忌搜索、模拟退火、遗传算法、蚁群优化算法和人工神经网络等等。以极小优化目标函数为例，这些算法给出最优值的上界，第一章的1.4节给出这些算法的目标值同最优目标值关系的示意图如下：一步法的目标值目改进法的目标值标基于数学规划：分支定界启发式，割平面启发式，线性值规划松弛再对解可行化，拉格朗日松弛可行化等的目标值，现代优化算法：禁忌搜索，模拟退火，遗传算法，蚁群优化算法，人工神经网络

2、等的目标值其它：如限制解空间，分解法，组合算法等的目标值最优值下界算法：线性规划松弛，拉格朗日松弛等的目标值评价算法好坏的一个标准是考察它所计算的目标值同最优目标值的差别。由于组合优化问题的难度，求解最优值有时是非常困难的。解决这个难点的一个有效方法是通过计算下界，用上界和下界的差来评价算法。拉格朗日(Lagrange)松弛算法就是求解下界的一种方法。由于拉格朗日松弛算法的实现比较简单和有比较好的性质，它不仅可以用来评价算法的效果，同时可以用在其他算法中，以提高算法的效率。拉格朗日松弛算法包含两部分内容：一方面是提供下界，另一方面则演变为拉格朗日松弛启

3、发式算法。本章7.1节介绍一些数学规划松弛的方法，7.2节给出拉格朗日松弛的理论，7.3节进一步讨论拉格朗日松弛的适用模型和更一般的结论，7.4节讨论拉格朗日松弛算法，7.5节给出一个应用案例——能力约束单机排序问题。7.1基于规划论的松弛方法在此仅以整数规划为基础讨论，可在混合整数规划问题中作相应的讨论。整数规划的数学模型为Tzc=minx1st..Ax≥b(7.1.1)nxZ∈,+其中，决策变量x为n维列向量，c为n维列向量，A为m×n矩阵，b为m维列向量；系n数c，A和b取整数，Z表示非负整数集合。+1．线性规划松弛在(7.1.1)中将整数变量约

4、束松弛为实数，就可以得到172第七章拉格朗日松弛算法Tzc=minxLPst..Ax≥b(7.1.2)nxR∈.+称(7.1.2)为(7.1.1)的线性规划松弛。线性规划松弛扩大了整数规划的可行解区域。若记nnSx=∈{}Z+

5、Ax≥b，Sx'=∈{R+

6、Ax≥b}，则有S⊆S'，于是得到结论：定理7.1.1zz≤。LP1定理7.1.1说明线性规划松弛得到整数规划的一个下界。可以通过单纯形算法或多项式[1]时间的内点算法，求得(7.1.2)的线性规划的最优解。T当S中的一个解x0满足cx0=zLP时，推出x0为(7.1.1)的最优解。作为求解整数规划问

7、题启发式算法的一部分，线性规划松弛适用于整数规划问题中决策变量是比较大的整数。对这样的问题，启发式算法的两阶段为：第一阶段将整数规划问题松弛为线性规划问题，求解线性规划问题的最优解；第二阶段将线性规划的最优解按四舍五入或类似的原则整数化，同时考虑解的可行。2．对偶规划松弛方法线性规划(7.1.2)的对偶形式为Tzy=maxbDPTst..Ay≤c(7.1.3)nyR∈,+其中，决策y是一个m维列向量。(7.1.2)和(7.1.3)都为线性规划问题，它们的计算方法相同，且由对偶理论得到zz=≤z。至于采用(7.1.2)或(7.1.3)中哪一个求(7.1.

8、1)的下界，需比较哪一个计算简单。DPLP1无论如何，单纯形算法和内点算法在实际应用中都可能因为耗时过大而不能满足要求。如在一个循环计算的算法中，每一次循环需要求解一个线性规划问题，当循环的步数较大时，这样无论用单纯形算法还是内点算法都会感到计算时间过多，可能无法满足计算时间的要求。3．代理(surrogate)松弛法当(7.1.1)的约束过多时，代理松弛法是通过一个约束nKK⎛⎞∑∑⎜∑axijkk⎟j≥bij=1⎝k==11⎠k替代(7.1.1)中的K个约束n∑aikjxj≥bik,k=1,2,L,K。j=1极端的情况可以用一个约束nmm⎛⎞∑∑⎜

9、∑axij⎟j≥bij=1⎝i==11⎠i松弛约束Ax≥b。代理松弛法保证目标函数、整数变量约束不变，且因约束的减少造成计算量的减少。4．拉格朗日松弛方法拉格朗日松弛方法的基本原理是：将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性性，使得问题容易求解。产生对它的研究兴趣主要基于下面的原因：第一，一些组合优化问题是NP难，除非P=NP，否则在现有的约束条件下不存在求最优解的多项式时间算法。但在原有的问题中减少一些约束后，求解问题的难度就大大的减少，7.1基于规划论的松弛算法173使得减少一些约束后的问题在多项式时间内求得最优解。由此，将这些

10、减少的约束称为难约束。对于线性整数规划问题，将难约束吸收到目标函数后，问题又变的容易求解。这时