一种求解机组组合问题的改进拉格朗日松弛算法

一种求解机组组合问题的改进拉格朗日松弛算法0拉格朗日乘子优化由于两台机组的组合问题是一个大型、非线性和混合的优化问题，因此很难找到理论上的最佳解但由于其显著的经济效益，人们一直在积极研究，并提出了许多解决方法拉格朗日松弛法是一种分解协调算法，随着问题规模的增大，其计算量线性增长，非常适用于机组组合这种大规模的混合整数规划问题;其拉格朗日乘子也在一定意义上体现了其经济（物理）含义但是，也有一些缺点，由于其目标函数的非凸性，用对偶问题求解时，存在对偶间隙，需要根据对偶问题的优化解采取一定的措施构造原问题的优化可行解;拉格朗日松弛法求解机组组合问题，会受到机组对拉格朗日乘子的灵敏度的影响，因此，拉格朗日乘子初值的选取、所采用的乘子的修正策略，都会对算法的计算效率产生一定的影响;而算法的迭代过程中容易出现振荡现象，需要采取措施加快收敛针对上述问题，本文对传统的拉格朗日松弛法进行了改进，结合拉格朗日乘子的物理意义通过启发式排序法得到较优的初值;根据拉格朗日松弛法快速收敛到可行解，振荡收敛到最优解的特点，在构造可行解时直接采用自适应性次梯度法将对偶问题的解沿优化方向逐步修正为可行解;获得可行解后，为了缓解乘子迭代过程中的振荡现象，采用集结投影次梯度法，使得迭代过程中能够对历史信息加以利用，从而加快收敛速度1机组运行约束传统机组组合数学模型为1）目标函数2）系统约束条件3）机组运行约束发电机组输出功率上下限约束最小开停机时间约束开机费用约束其中:T为系统调度期间的时段数；N表示系统总机组数;P2拉格朗日松弛算法的改进

2.1拉格朗日松弛拉格朗日松弛法求解机组组合问题基于分解协调的思想，对于式1~6所描述的机组组合问题的数学模型，对系统约束

2、3进行松弛，得到原问题的拉格朗日松弛问题式中入拉格朗日松弛函数7可写成可以看出，前一部分只与每个机组自身有关，第二部分在拉格朗日乘子已知的情况下为定值因此拉格朗日松弛问题即转化成为单机问题的求解运用对偶理论，形成两层的优化问题底层问题用于求解单机优化问题上层问题优化拉格朗日乘子，即解对偶问题式中，L

2.2拉格朗日乘子优化拉格朗日乘子初值的质量具有比较重要的意义，好的初值能够使迭代尽早收敛，减少计算时间，不同的初值也可能会产生不同的优化结果由于拉格朗日乘子在一定程度上体现了电能量价格和备用价格的经济意义为了能获得一个质量较优的拉格朗日乘子的初始值，本文借鉴文献［12］方法，根据机组满负荷平均煤耗每个优化时段，优先选取FL利用求得的人而对于全系统的每个时刻式中，m为按上述

2.3方便的种类本文采用动态规划法求解单机子问题动态规划法在处理单机问题时，对于机组启停约束等处理是比较方便的单机问题求解过程中，若直接以式13目标函数作为动态规划中用于比较的累积费用，则所计算的开机费用为整体的开机费用，对于那些低运行费用高开机费用的机组，会因为动态规划的择优路径取决于这一个时刻的累计费用而很难被选中，因此本文在动态规划过程中以C

2.4乘子的修正策略运用拉格朗日松弛法求解机组组合问题时，由于目标函数的非凸性，用对偶问题求解时，存在对偶间隙，需要根据对偶问题的优化解采取一定的措施构造原问题的优化可行解本文直接通过一种自适应性次梯度法进行拉格朗日乘子的修正，将对偶问题的解拉入可行解的范畴，能够保证此可行解的优越性本文中所采用的自适应性次梯度法分别为各时刻功率平衡约束和系统备用约束的不平衡量，也是对偶问题在各相应拉格朗日乘子处的次梯度常参数a和B的取值分为以下三种情况1）若pdif2）若pdif3）若pdif当发电机组所供给的输出功率小于负荷和旋转备用的需求时，如1）,人上述拉格朗日乘子的修正策略对于各时段都是相同的，这样的修正方式对于各种不平衡程度不加以区别可能会产生计算振荡在迭代过程中，可判断是否有个别时刻的不平衡量的比例明显高于其他时刻，这时对其区别对待，适当加大它的修正幅度以缓解振荡现象如已知某一时刻rdif

2.5影次梯度法修正拉格朗日乘子传统的次梯度方法直接将次梯度作为搜索方向，在搜素过程中解的振荡现象严重本文在获得可行解之后，采用集结投影次梯度法对历史次梯度加以利用来修正拉格朗日乘子，迭代方向更加准确，文献［14］对此算法收敛性进行了理论证明集结投影次梯度法是指，对偶问题的求解过程中，可以得到J首先，计算次梯度g其次，定义权重，认为历史次梯度与当前所得次梯度方向越近，则其包含的信息越多，所赋予的权重也越大最后，更新拉格朗日乘子式中,

2.6对偶间隙的影响在拉格朗日松弛法求解机组组合问题时，对偶问题的最优解总是小于或等于相应的原优化问题的最优解，两者之间的差别被称作对偶间隙，对偶间隙的大小，直接反映了迭代求解过程中所获得的机组组合方案的优劣程度，因此可以作为算法是否结束的标准在上述每次迭代得到可行解后，求得相对对偶间隙当相对对偶间隙满足所要求的精度或迭代达到最大迭代次数时，算法结束本文提出的改进拉格朗日松弛算法计算流程如图1所示3测试结果仿真计算在Lenovo-PC机上进行，CPU为CeleronT.86GHz,采用Matlab

7.0计算编程以文献［12］的

10、

20、

40、

60、

80、100机的6个测试系统进行计算分析，并与文献［15］中的传统拉格朗日松弛法LR及遗传算法GA,文献［16］的进化算法EP,文献［17］的遗传算法与拉格朗日松弛法结合算法LRGA,文献［18］中的基于机组分类的遗传算法GAUC和文献［12］的基于动态规划的拉格朗日松弛法DPLR和自适应性拉格朗日松弛法ELR进行了对比其中系统负荷备用设为负荷总需求的10%,相对对偶间隙的收敛标准设为

0.01,最大迭代次数设为100次表1给出运用本文方法的10机系统24时段的优化结果本文所采用的改进拉格朗日松弛法ILR优化所得10机系统的发电成本与上述各文献优化算法进行了对比，如表2所示可以看出ILR算法的10机优化成本要小于上述各文献图

2、图

3、图4分别给出了采用自适应性次梯度法和集结投影次梯度法的单一策略，以及本文所述的两种方法的联合修正策略三者所对应的迭代过程中相对对偶间隙的变化情况采用单一策略时，由于直到迭代达到最大迭代次数100次时，相对对偶间隙仍没有达到精度要求，所以图2和图3是100次迭代过程中的相对对偶间隙变化图而采用联合策略时,经34次迭代相对对偶间隙就达到了精度要求，故图4显示的是34次迭代过程中的相对对偶间隙变化图两种单一策略在达到精度要求之前就开始出现振荡现象而联合策略中，迭代次数达到34次时，对偶间隙即达到精度要求因此这种交替迭代的思想更易跳出单一策略时的振荡现象，加速收敛同理对

20、

40、

60、

80、100机系统进行测试，表3对其优化的运行成本与其他几种算法进行了对比表4列出了本算法六个算例的CPU计算时间表

3、表4所示各种规模下，本文改进拉格朗日松弛法与其他五种方法的计算结果相比，本算法相对于文献［15］传统拉格朗日松弛法节省了发电运行成本，相对于其他全局寻优的算法，可以在较短的时间内得到一个质量较好的近似最优解本方法的计算速度较快，计算时间随系统规模线性增长通过算例对比，本算法的优化成本小于传统的拉格朗日松弛法，同时具有速度优势，能在很短的时间内得到比较满意的近似最优解，可用于大规模系统的机组组合的运算为了与上述算例进行统一对比，本文并未考虑爬坡约束，在今后的研究中，可以将爬坡约束加入到考虑范围4优化算法仿真本文提出一种改进拉格朗日松弛法算法，以求解机组组合问题通过自适应性次梯度法与集结次梯度法两种策略的交替使用来缓解计算中的振荡现象，加速收敛仿真结果表明，本算法总运行成本的优化结果优于传统的拉格朗日松弛法，且具有速度优势其计算时间随系统规模线性增长，可用于大规模电力系统本算法以后可以将爬坡和网络约束等纳入考虑范畴，运用到安全约束机组组合中，加以完善。