下载文档原格式
组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。
在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。
这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。
求解这类组合最优化问题方法分为精确算法和近似算法两类。
常用的精确算法有动态规划、分支定界和枚举等。
精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。
当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确算法并不可行。
利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。
近似算法是指在合理的计算时间内找到一个近似的最优解。
近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。
近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。
1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。
拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。
首先对于NP难的优化问题，其数学模型须具有可分离性。
通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。
利用乘子的迭代更新来实现子问题解的协调。
列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。
与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。
电力系统机组组合问题的研究1. 本文概述电力系统机组组合问题是电力系统运行和规划中的一个重要议题。
在这篇文章中，我们将深入探讨如何通过优化算法和决策支持系统来提高电力系统的经济性、可靠性和可持续性。
本文首先介绍了电力系统机组组合问题的研究背景和意义，阐述了在当前能源转型和电力市场改革的大背景下，如何通过科学合理的机组组合来实现电力系统的高效运行。
接着，文章将回顾相关领域的研究进展，包括传统的优化方法和近年来兴起的智能优化算法，以及它们在电力系统机组组合问题中的应用情况。
本文还将讨论电力系统机组组合问题面临的挑战和未来的研究方向，特别是在考虑环境保护和可再生能源融入的情况下，如何实现电力系统的绿色、低碳转型。
文章将介绍本文的研究方法和主要内容安排，为读者提供一个清晰的研究框架和阅读指南。
通过本文的研究，我们期望能够为电力系统的运行和规划提供有价值的参考和指导，为实现能源的可持续发展贡献力量。
2. 电力系统机组组合问题的理论基础电力系统机组组合问题（Unit Commitment Problem, UCP）是电力系统运行中的一个核心优化问题，旨在确定在未来某个时间段内，哪些发电机组应该开启或关闭，以及它们的出力水平应该是多少，从而满足预期的电力需求，同时优化运行成本和其他相关指标。
UCP是一个复杂的组合优化问题，涉及到大量的决策变量和约束条件，其理论基础涉及多个学科领域的知识。
UCP的理论基础包括电力系统的基本运行原理。
电力系统由多个发电机组、输电网和配电网组成，这些组成部分之间的相互作用和相互影响构成了电力系统运行的基础。
发电机组的出力、电网的传输容量以及负荷的变化等因素都会影响到电力系统的稳定运行。
在解决UCP时，必须充分考虑这些因素，确保电力系统的安全、稳定和经济运行。
UCP的理论基础还包括优化理论和算法。
由于UCP是一个复杂的组合优化问题，传统的数学方法往往难以直接求解。
需要借助优化理论和算法来寻找问题的最优解。
电力调度中的机组组合优化随着电力市场的逐渐完善和电力系统的日益复杂，电力调度越来越需要高效、精准的机组组合优化方法来保障电力稳定供应和市场效益。
机组组合优化是根据具体条件和需求，选取最优的机组组合，来实现最佳的电力调度和经济效益。
本文将介绍机组组合优化的相关内容，包括机组特性、机组组合的优化、机组调度中的负荷预测和风电光伏的接入等方面，旨在为读者提供一些关于电力调度的基本知识，以及行业内优化机组组合的最新技术和应用。
一、机组特性在进行机组组合优化前，我们需要了解机组的特性，包括发电能力、启停时间、最短运行时间、运行成本等因素。
在电力系统中，不同类型的机组有不同的特性，如火电机组、水电机组、风电机组、光伏机组等，它们的发电能力、启停时间、最短运行时间、运行成本等指标都不相同。
例如，火电机组的启动时间较长，而风电和光伏机组的启动时间较短，但其发电能力较不稳定。
这些特性对于机组组合优化非常重要，在实际应用中需要根据机组的类型和特性进行灵活选择，以达到最佳的机组组合效果。
二、机组组合的优化机组组合的优化是通过数学模型和计算方法，选取最佳的机组组合方案，来实现最佳的电力调度和经济效益。
在机组组合优化中，需要考虑诸多因素，如电力市场需求、机组特性、调峰能力等因素。
其中，调峰能力是机组组合优化的重要考虑因素之一。
调峰能力是指机组在发生负荷波动时，及时调整发电量来维持系统功率平衡，保障电力稳定供应。
对于不同类型的机组，要考虑它们的调峰能力和灵活度，以选择最佳的机组组合方案。
三、机组调度中的负荷预测负荷预测是电力调度中非常重要的环节，能够有效帮助我们了解未来的负荷状况，从而制定科学合理的机组组合方案。
负荷预测的精确度直接影响到机组组合方案的可靠性和经济效益。
现在，随着技术的不断进步和数据分析的集成应用，负荷预测已经具备了更高的精确度和实时性。
通过对历史数据的模拟分析，以及借助人工智能等技术手段，能够更好地把握未来负荷状况，优化机组组合方案，降低调度成本，提高市场竞争力。
机组组合问题的优化方法综述一、引言机组组合问题是一个经典的优化问题，广泛应用于电力系统、制造业、物流运输等领域。
该问题主要关注如何在满足一定约束条件下，合理选择一组设备或机组，以实现某种特定的目标，如总成本最低、总产量最大等。
随着科技的发展和实际需求的不断变化，机组组合问题的规模和复杂性也在不断增加，因此，研究和发展新的优化方法以解决这类问题具有重要的理论和实践意义。
二、机组组合问题的定义和特性机组组合问题是指在给定一组设备或机组，每个设备或机组都有各自的运行成本、运行时间、可用性等属性，如何在这些设备或机组中选择一部分，使得满足某种特定目标（如总成本最低、总产量最大等）的同时，满足一系列约束条件（如设备数量限制、总运行时间限制等）。
这类问题具有以下特性：组合性：问题的解是一组设备的组合，而非单一设备或机组。
约束性：问题的解必须满足一系列的约束条件。
复杂性：问题的规模和复杂性往往随着设备或机组的数量的增加而增加。
动态性：设备的状态和环境可能会随时间变化，需要动态调整机组组合。
三、经典优化方法线性规划：线性规划是一种常用的数学优化方法，可以通过构建和解决线性方程组来找到最优解。
在机组组合问题中，可以通过构建成本、产量等与设备选择和运行时间之间的线性方程组，求解最优解。
动态规划：动态规划是一种通过将问题分解为子问题，并逐一求解子问题的最优解以得到原问题的最优解的方法。
在机组组合问题中，可以通过构建状态转移方程，求解每个状态下的最优解。
遗传算法：遗传算法是一种模拟生物进化过程的优化方法，通过选择、交叉、变异等操作来产生新的解，并逐步逼近最优解。
在机组组合问题中，可以通过编码设备选择和运行时间的组合作为染色体，进行选择、交叉、变异等操作，以找到最优解。
模拟退火：模拟退火是一种以一定概率接受非最优解的优化方法，通过模拟金属退火的过程来寻找最优解。
在机组组合问题中，可以通过对每个解进行评估，并以一定概率接受非最优解，以避免陷入局部最优解。
机组组合问题的优化方法综述陈皓勇 王锡凡(西安交通大学电力工程系 710049 西安)摘 要 机组组合问题是编制短期发电计划首先要解决的问题,合理的开停机方案将带来很大的经济效益,由于问题十分复杂,很难找出理论上的最优解,文中介绍了机组组合问题的数学模型,分类综述了从60年代起该问题的主要解法,比较了各种方法的优缺点,并提出了尚待研究的问题。
关键词 发电计划 机组组合 优化方法分类号 TM 7321998205215收稿。
国家教委博士点基金资助项目。
0 引言电力系统经济调度的目的是在满足系统安全约束、电能质量要求的条件下尽可能提高运行的经济性。
经济调度的效益很大,根据国外资料和华北、东北等电网的实际测算,节省能源可达总耗量的015%～115%[1]。
经济调度是一个十分复杂的系统优化问题,从总体上解决,难度非常大,常分解为一系列的子问题分别处理。
从短期发电计划来看,可分为机组组合、火电计划、水电计划、交换计划、燃料计划等子问题。
其中机组的优化组合是编制短期发电计划首先要解决的问题,它的经济效益一般大于负荷经济分配的效益。
文献[2,3]中介绍了电力系统经济调度和机组组合问题的数学模型和基本方法。
机组组合问题是一个高维数、非凸的、离散的、非线性的优化问题,很难找出理论上的最优解,但由于它能够带来显著的经济效益,人们一直在积极研究,提出各种方法来解决这个问题,如启发式方法、优先顺序法、动态规划法、整数规划和混合整数规划法、分支定界法、拉格朗日松弛法、专家系统法、人工神经网络法、模拟退火算法、遗传算法等,文献[4,5]介绍了历年来机组组合问题的各种解法和相关参考文献。
本文对机组组合问题的主要解法进行了更深入的探讨,并加以分类综述,比较了各种方法的优缺点,提出了尚待研究的问题。
1 机组组合问题的数学模型根据实际系统不同的要求,对于机组组合问题可以建立不同的模型。
在一般情况下,应以系统各发电机组的开停机状态和出力为控制变量,在满足系统负荷和备用要求、线路潮流限制及机组爬坡速率(ram p rate ,即功率变化速率)、最小开停机时间、燃料总量等约束条件下,使开停机费用和运行费用之和最小。
机组组合问题的优化方法综述陈皓勇 王锡凡(西安交通大学电力工程系 710049 西安)1998205215收稿。
国家教委博士点基金资助项目。
(上接本刊1999年第4期第56页)5 拉格朗日松弛法电力系统是一个非常典型的大系统,是大系统优化和控制理论的一个重要应用领域[42]。
大系统的分解协调思想最早见于D an tzig 和W o lfe 对于线性规划问题的分解[43],而用于机组组合问题的主要是拉格朗日松弛(L agrangian relaxati on )法[44～47],该方法产生于70年代,是解决复杂整数和组合优化问题的一类优化算法,它建立在下述思想的基础上:许多困难的整数规划问题可看成是由一些边界约束条件联系在一起的一系列相对容易的子问题组成,利用这个特点,把约束条件被破坏的量和它们各自的对偶变量的乘积加在目标函数上作为惩罚项,形成拉格朗日问题。
拉格朗日问题相对容易解决,对于最大(小)化问题,它的优化值是原问题优化值的上(下)界,因此在分支定界法中,它能够取代线性规划法以提供下界。
下面以最大化问题为例来说明这种方法:Z =m ax X{c TX AX ≤b ,D X ≤e ,X ≥0且是整数向量}其中 X 是n 维向量;b ,c ,e 分别为m 维、n 维、k 维向量;A ,D 分别为m ×n ,k ×n 的矩阵。
假设问题的约束条件可以分为两组,即AX ≤b 和D X ≤e ,并且如果去掉约束AX ≤b ,问题会变得相对容易解决。
因此可以构造拉格朗日问题:Z D (u )=m ax X{c T X +u T(b -AX ) D X ≤e ,X ≥0且是整数向量} 对偶变量u 的值应该通过解对偶问题Z D =m in u{Z D (u ) u ≥0}来得到。
由于Z D (u )对u 是不可微的,通常用次梯度法来求解,从初始点u 0开始,应用公式u k +1=m ax{0,u k -t k (b -AX k )}迭代求解。
机组组合问题的优化方法综述陈皓勇 王锡凡(西安交通大学电力工程系 710049 西安)1998205215收稿。
国家教委博士点基金资助项目。
(上接本刊1999年第4期第56页)5 拉格朗日松弛法电力系统是一个非常典型的大系统,是大系统优化和控制理论的一个重要应用领域[42]。
大系统的分解协调思想最早见于D an tzig 和W o lfe 对于线性规划问题的分解[43],而用于机组组合问题的主要是拉格朗日松弛(L agrangian relaxati on )法[44～47],该方法产生于70年代,是解决复杂整数和组合优化问题的一类优化算法,它建立在下述思想的基础上:许多困难的整数规划问题可看成是由一些边界约束条件联系在一起的一系列相对容易的子问题组成,利用这个特点,把约束条件被破坏的量和它们各自的对偶变量的乘积加在目标函数上作为惩罚项,形成拉格朗日问题。
拉格朗日问题相对容易解决,对于最大(小)化问题,它的优化值是原问题优化值的上(下)界,因此在分支定界法中,它能够取代线性规划法以提供下界。
下面以最大化问题为例来说明这种方法:Z =m ax X{c TX AX ≤b ,D X ≤e ,X ≥0且是整数向量}其中 X 是n 维向量;b ,c ,e 分别为m 维、n 维、k 维向量;A ,D 分别为m ×n ,k ×n 的矩阵。
假设问题的约束条件可以分为两组,即AX ≤b 和D X ≤e ,并且如果去掉约束AX ≤b ,问题会变得相对容易解决。
因此可以构造拉格朗日问题:Z D (u )=m ax X{c T X +u T(b -AX ) D X ≤e ,X ≥0且是整数向量} 对偶变量u 的值应该通过解对偶问题Z D =m in u{Z D (u ) u ≥0}来得到。
由于Z D (u )对u 是不可微的,通常用次梯度法来求解,从初始点u 0开始,应用公式u k +1=m ax{0,u k -t k (b -AX k )}迭代求解。
其中t k 是标量步长,X k 是第k 步拉格朗日问题的优化解。
拉格朗日松弛法在机组组合问题中应用时,把所有的约束分成两类,一类是全系统的约束,即文章第1部分模型中的P (X ),一类是可以按单台机组分解的约束,如模型中的R (X ,Z ),M (X ,Z ),U (Z ),P (X )可以写成惩罚项的形式,加入目标函数,形成拉格朗日函数,拉格朗日函数可按单台机组分解成一系列的子问题,子问题一般用动态规划法求解,对偶问题一般用次梯度法[48]求解。
拉格朗日松弛法在机组组合问题中的应用研究始于70年代,80年代逐渐推广,90年代成为主流,有大量的理论和应用成果。
早期的应用多结合分支定界法,但在后来的应用中发现分支定界的框架是可以完全抛弃的,直接解对偶问题并结合一些启发式的调整策略即能得出原问题的最优解或次优解。
在后来的研究中发现,为解决由于线性费用函数造成的解的振荡问题,需要在目标函数中加入二次惩罚项,采用辅助问题原理(aux iliary p rob lem p rinci p le )和增广拉格朗日法(augm en tedL agrangian )来解决[49～51]。
文献[52,53]以分支定界法为框架,应用对偶方法求分支定界树各节点的下界,使用近似罚函数法,不但能解对偶问题,而且能为构造原问题的近似优化解提供有用的信息。
文献[53]论证了对偶间隙(duality gap ,即原问题的优化值和对偶问题优化值之间的差值)相对值随着机组数增加而减少。
由于对偶法提供了主问题紧的下界和构造优化可行解的有用信息,只需检查一个节点,甚至可以完全放弃分支定界框架。
随着机组数增加,计算量线性增长。
文献[54]直接应用拉格朗日松弛法求解机组组合和水火电负荷经济分配的问题,用次梯度法优化拉格朗日乘子,用动态规划法求解单台热力机组的开停机问题,用罚函数法求解凸水电优化控制问题,用文献[52,53]的方法从对偶问题的解构造原问题的可行解。
文献[55]提出的方法,不用分支定界的框架,而是直接从对偶问题的解构造原问题的解。
该方法利用了电力系统的如下特点:若所有投入运行的机组能满足系统的旋转备用要求,则系统的功率一定能够平衡。
因此使用特殊的算法来选择拉格朗日乘子,保证在迭代的过程中旋转备用能够满足要求。
文献[56]使用拉格朗日松弛法进行分解,用连续逼近151999年3月 电 力 系 统 自 动 化A utom ati on of E lectric Pow er System s 第23卷 第5期法和次梯度法求解拉格朗日乘子,并考虑了燃料约束。
文献[57]考虑了燃料限制和抽水蓄能电厂,并用可变量度法(variab le m etric m ethod )代替次梯度法优化乘子,改善了对偶问题的收敛性。
文献[58]把算法分成3个阶段:第一阶段用标准的次梯度法优化拉格朗日乘子;第二阶段使用系统化的并可通用的过程寻找满足旋转备用要求的对偶解;第三阶段进行负荷经济分配计算,得到原问题的优化解。
文献[59]在对偶问题迭代计算的每一步,都做了大量的努力来寻找原问题的可行解,并通过计算表明,考虑机组爬坡速率将使计算量大大增加。
文献[60]考虑了燃料限制,并用线性规划法进行负荷经济分配计算。
文献[61]解决长期机组组合问题,考虑了燃料限制和抽水蓄能电厂,使用可变量度法优化拉格朗日乘子,并用最小平方法寻找原问题的可行解。
文献[62]着重给出拉格朗日松弛法在实际应用中需考虑的细节问题。
文献[63]使用可变量度法优化乘子,分3个阶段来解决问题:第一阶段解对偶问题;第二阶段寻找近似优化可行解;第三阶段用线性规划法进行负荷经济分配计算,解线性规划时采用了D an tzig 2W o lfe 分解法。
文献[64]考虑的模型比较复杂,包括机组爬坡速率、线路传输容量限制、网损、燃料限制等。
机组爬坡速率在子问题中用对偶法考虑。
文献[65]解决的是多区域水火电联合电网的资源计划问题,其方法来自于机组组合问题,模型比较复杂,根据PG &E 系统的实际特点,考虑了8种资源模型、区域功率平衡限制、燃料总量限制等,对偶问题用次梯度法求解,而对于不同的子问题用不同的算法,文献[65]提出了一个扩展的过程以得到原问题的优化可行解。
文献[66～73]是研究机组组合、发电计划问题的系列文献。
文献[66]使用拉格朗日松弛法,用自适应步长的次梯度算法优化乘子,所提出方法的优点在于不必把发电机输出功率离散化,用系统化的方法处理机组爬坡速率和初始化过程。
文献[67]把文献[66]的方法推广应用到水火电联合电网的调度问题中,通过拉格朗日乘子进行水火电的协调,用优先顺序法求解水电子问题。
文献[68]的方法中进一步包括了抽水蓄能电厂,水库水位约束采用拉格朗日乘子松弛,分解为单个小时的优化问题,再用单变量线性或二次函数优化的方法解决。
文献[69]考虑了抽水蓄能电厂的动态特性,在解决单个小时的优化问题后,再用动态规划法考虑整个调度期间内的优化问题。
文献[70]采用增广拉格朗日法解决电力购买和热力机组调度问题,当全系统的负荷和备用约束被松弛后,整个问题被分解为电力购买子问题和火电子问题,前一子问题先确定每个购买时段内的优化购买功率,再使用动态规划法解决。
使用增广拉格朗日法克服线性费用函数造成的振荡问题并加快了算法的收敛性。
为克服拉格朗日松弛法中线性费用函数造成的振荡和奇异问题,文献[71]使用非线性函数(二次函数)来近似代替某些线性费用函数,而不是使用增广拉格朗日松弛法,显著地改进了算法的效果。
文献[72]用模糊关系来表示系统备用和目标函数,使问题转化成确定性的,用拉格朗日松弛法将问题分解为一系列的单机组子问题和一个成员(m em bersh i p )子问题,这种方法能在降低燃料费用和满足备用要求之间达到一个平衡。
文献[73]建立了比文献[70]更复杂的交易模型,从卖方公司的角度考虑了赢利的约束,即卖方必须获利,电力买卖才有可能进行,当单个时段内的优化电力销售功率被确定后,整个调度期间内的优化销售方案用动态规划法解决。
文献[74]考虑了火电厂和水电厂的机组组合问题,分解成火电厂和水电厂子问题,火电厂用常规的拉格朗日松弛法求解,水电子问题分为流域,流域再分为水库,流域级用网络流规划法,水库级的水力机组组合问题用前述D P —SC 法求解,使用连续逼近法优化水电子问题的拉格朗日乘子。
文献[75]考虑了系统的线路传输容量约束和环境约束,并用网络流法计算负荷经济分配,用增广拉格朗日法避免由线性费用函数造成的振荡。
文献[76]用增广拉格朗日法解决资源计划问题,算法分成两个阶段,即机组开停阶段和约束经济调度(负荷经济分配)阶段,在开停机阶段考虑优化潮流(op ti m al pow er flow )约束,因此用更严格的方法优化拉格朗日乘子。
文献[77]考虑了传输线功率极限,在拉格朗日函数中加入有关的惩罚项,首先解对偶问题,产生一些可能构造原问题优化可行解的可选方案,在解原问题的过程中评价这些方案,最后找出燃料费用最小的一个。
文献[78]提出了一种新的大系统机组组合的随机分解方法,随机扰动被建模为“情况树”(scenari o tree ),优化目标是减小平均发电费用,使用增广拉格朗日松弛法,与经典的确定性优化方法比较,新方法显著地节省费用。
文献[79]优化多运行模式机组的开停问题,随运行模式的不同,机组的运行参数有很大的区别,用常规的拉格朗日法可解决这个问题。
文献[80,81]都着重机组爬坡速率的处理,不同于文献[66],文献[80]将机组爬坡速率约束作为惩罚项加入目标函数,经验表明这种处理方法对每次迭代的时间影响很小,在实用中得到了比较好的结果;文献[81]将爬坡速率作为机组疲劳损耗的折旧费用加入目标函数中,用该方法可以灵活地选择爬坡速率。
文献[82]建立了一个通用的机组组合模型,可以包25 括最小开停机时间约束、潮流约束、线路潮流限制、电压限制、旋转备用约束、爬坡速率、总燃料和能量限制等,并用拉格朗日松弛法和辅助问题原理来解这个模型,对一个小的算例系统进行了计算。
综上所述,拉格朗日松弛法是一类有着成熟理论基础的整数(组合)优化算法,适合于解决大系统的优化问题。
由于电力系统的机组组合问题具有该算法所要求的特点,使该算法得到了十分广泛的应用。
该算法有以下优点:随着机组数的增加,计算量近似线性增长,克服了维数障碍,且机组数目越多,算法效果越好;方法十分灵活,不但可以成功地解决机组组合问题,也可以推广到水火电联合经济调度问题和电力交易的问题;算法的一些因子具有实际的物理(经济)意义,如与系统负荷约束相关的拉格朗日乘子即等于系统边际发电成本。
