机组组合基于Benders分解与割平面的方法及约束优化SQP算法研究

摘要

火电是我国的主力电源，中国电力企业联合会所公布的电力工业运行简况表明:截止到2015年8月底，我国以燃煤为主的火电机组占整个6000千瓦及以上电厂装机容量的68.6％。在大力提倡节能减排发展低碳经济的世界共识下，机组的优化运行即合理启停一些运行成本相对较高的机组具有重要的理论和实际意义。
　　电力系统机组组合问题是指在满足系统负荷需求与旋转备用等约束条件下，优化发电机组的启停状态和机组出力，使得计划期内发电总费用最小。在数学模型方面，常用一个复杂的混合整数非线性规划模型来表示机组组合问题，该模型中含有大量表示机组启停状态的0-1整数变量和表示机组出力的连续变量，是电力系统中最难求解的优化问题之一。机组组合问题可看作是两个相互联系的优化问题:机组调度计划问题与经济调度问题，其中机组调度计划问题是一个0-1组合优化问题，而经济调度问题是一个非线性约束优化问题。这两个优化问题的快速有效求解将直接影响机组组合问题的求解效率。本文一方面基于能有效求解复杂问题的Benders分解法以及割平面研究快速有效求解机组组合问题的方法;另一方面对求解非线性约束优化问题的快速有效算法之一——序列二次规划即SQP算法开展一定的研究工作，以期从数学方法的角度为电力系统机组组合问题提供可选取的数值方法。
　　本文首先基于Benders分解法与割平面提出能有效求解机组组合问题的改进的松弛型Benders分解法和加速广义Benders分解法。其次，基于求解混合整数规划问题的分支定界与割平面技术，并结合启发式方法提出能有效求解机组组合问题的割平面分支法。最后，本着探索计算量少且在较弱假设条件下仍具有相应收敛性的快速算法，提出一个新的求解不等式约束优化问题全局收敛模松弛SQP算法。全文共分为七章:第1章为绪论，主要阐述本课题研究的理论与实践意义，回顾和总结机组组合问题及其求解方法，介绍SQP算法基本思想与研究现状;第2章主要介绍本文所涉及的基本问题和相关理论基础，为后续章节内容提供理论分析和算法支撑;第3章至第6章为本文主要研究工作;第7章为结论与展望。本文主要研究成果如下:
　　1)基于Benders分解与覆盖不等式提出求解机组组合问题改进的松弛型Benders分解法。首先借助于透视割平面及线性化技术建立经典的纯火电机组组合问题一个近似混合整数线性规划模型，然后结合覆盖不等式提出求解仅含0-1整数变量混合整数规划问题改进的松弛型Benders分解法，最后将改进的松弛型Benders分解法用于求解经典机组组合问题。10～1000台机组24时段等多个系统的数值结果表明，改进的松弛型Benders分解法的计算时间相比于经典的Benders分解法大大减少。与其他方法的比较结果进一步说明所提方法能有效求解机组组合问题。
　　2)基于整数割平面和加速技术提出求解计及二氧化碳排放机组组合问题的加速广义Benders分解法。首先借助于线性化技术建立所讨论机组组合问题一个近似混合整数二次规划模型，然后通过求解辅助线性规划问题得到一类形式简单但对于求解机组组合问题非常有效的整数割平面，最后结合整数割平面及加速技术提出求解机组组合问题的加速广义Benders分解法。10～100台机组24时段等6个系统的数值结果表明，该方法具有良好的稳定性，能有效求解机组组合问题。
　　3)基于割平面与分支定界搜索以及启发式技术提出求解计及可入网电动汽车机组组合问题的割平面分支法。所提方法中用到两类有效割平面，即整数割平面与广义流覆盖不等式及其互补类，这些割平面能使相应机组组合的连续松弛问题有一个比较紧的表达式。此外，利用加入两类割平面后连续松弛问题的最优解以及启发式技术可得到原机组组合问题一个比较好的初始可行解。基于这两点，所提割平面分支法能大大减少分支定界树搜索的节点数。另一方面，著名商业软件CPLEX在结合本章所用的两类割平面后，其求解机组组合问题的计算效率得以加强。不计可入网电动汽车情形下10～100台机组24时段等6个系统以及计及可入网电动汽车情形下10台机组24时段50000辆电动汽车系统的数值结果表明，所提方法具有良好的收敛性，理论上可找到全局最优解。
　　4)提出求解非线性不等式约束优化问题一个新的全局收敛模松弛SQP算法。为减少计算量，每次迭代中算法所需要的可行下降方向是通过求解一个模松弛类二次规划子问题得到，并且算法采用l∞罚函数作为效益函数进行线搜索。此外，本章所提算法还在线搜索中考虑了约束最大违反度函数。正是因为算法中利用了新的罚参数修正公式以及线搜索技术，所提模松弛SQP算法在无任何迭代点列有界以及线性无关等较弱假设条件下仍具有全局收敛性。

目录

声明

摘要

第1章 绪论

1．1 引言

1．2 机组组合问题及相关算法回顾

1．2．1 机组组合问题概述与研究现状

1．2．2 机组组合问题的算法回顾

1．3 非线性约束优化问题的SQP算法

1．3．1 非线性约束优化问题快速算法简介

1．3．2 SQP算法的研究意义与研究现状

1．4 本文主要工作

1．4．1 尚需解决的问题

1．4．2 主要工作与内容安排

第2章 机组组合问题模型与相关理论基础简介

2．1 机组组合问题模型简介

2．2 Benders分解法简介

2．2．1 求解混合整数线性规划问题的BDM

2．2．2 求解混合整数非线性规划问题的GBDM

2．3 几类特殊有效割平面

2．3．1 基于0-1背包约束的覆盖不等式

2．3．2 基于固定费用网络流约束的广义流覆盖不等式及其互补类

2．3．3 透视割平面

2．4 求解混合整数非线性规划问题的割平面分支法

2．5 优化算法的一些基础知识以及SQP算法基本步骤

2．6 小结

第3章 机组组合问题改进的松弛型Benders分解法

3．1 引言

3．2 经典UC问题的数学模型

3．2．1 UC问题的基本描述

3．2．2 UC问题的近似混合整数线性规划模型

3．3 求解UC问题改进的松弛型Benders分解法

3．3．1 改进的松弛型Benders分解法

3．3．2 改进的松弛型BDM求解UC问题

3．4 仿真结果及分析

3．4．1 改进的松弛型BDM与传统BDM的测试结果比较

3．4．2 改进的松弛型BDM与其他方法的测试结果比较

3．5 小结

第4章 计及CO2排放机组组合问题的加速广义Benders分解法

4．1 引言

4．2 计及CO2排放UC问题的近似混合整数二次规划模型

4．3 计及CO2排放UC问题的加速广义Benders分解法

4．3．1 整数割平面

4．3．2 求解计及CO2排放UC问题的加速广义Benders分解法

4．4 仿真结果及分析

4．4．1 不计CO2排放的UC问题情形

4．4．2 计及CO2排放UC问题情形

4．5 小结

第5章 计及可入网电动汽车机组组合问题的割平面分支法

5．1 引言

5．2 计及可入网电动汽车UC问题的数学模型

5．3 计及可入网电动汽车UC问题的两类重要割平面

5．3．1 整数割平面

5．3．2 爬坡约束所对应的广义流覆盖不等式及其互补类

5．4 求解计及可入网电动汽车UC问题的割平面分支法

5．5 仿真结果及分析

5．5．1 不计可入网电动汽车UC问题情形

5．5．2 计及可入网电动汽车UC问题情形

5．6 小结

第6章 约束优化问题一个全局收敛的模松弛SQP算法

6．1 引言

6．2 算法及性质

6．3 算法的全局收敛性

6．4 小结

第7章 结论与展望

7．1 结论

7．2 展望

参考文献

附录

附录B 攻读博士学位期间发表的学术论文

附录C 攻读博士学位期间主持及参与的科研项目情况

致谢