线性规划求解算法研究（精选8篇）
线性规划求解算法研究 篇1
0 引言
在经济管理、交通运输、工农业生产等经济活动中, 提高经济效果是人们不可缺少的要求, 而提高经济效果一般通过两种途径:一是技术方面的改进, 例如改善生产工艺, 使用新设备和新型原材料.二是生产组织与计划的改进, 即合理安排人力物力资源。线性规划所研究的是:在一定条件下, 合理安排人力物力等资源, 使经济效果达到最好。一般地, 求线性目标函数在线性约束条件下的最大值或最小值的问题, 统称为线性规划问题。满足线性约束条件的解叫做可行解, 由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的3要素。线性规划是运筹学的一个重要分支, 自1947年 乔治·伯纳德·丹兹格 (G.B.Dantzig, 1914—2005) 提出了一般线性规划问题求解的方法——单纯形法之后, 线性规划在理论上趋向成熟, 在实用中日益广泛和深入。
1 线性规划——数学模型
要对实际规划问题作定量分析, 必须先加以抽象, 建立数学模型。在建立线性规划模型时, 需要有关的专业知识, 并要有一定的经验和技巧。建立线性规划模型包括:①明确问题的目标和划定决策实施的范围 (包括时间界限) , 并将目标表达成决策变量的线性函数, 称为目标函数;②选定决策变量和参数。决策变量就是待决定的问题的未知量, 一组决策变量的取值即构成一个规划方案。决策变量的选定往往需要对问题进行仔细的分析;③建立约束条件。问题的各种限制条件称为约束条件。每一个约束条件均表达成决策变量的线性函数应满足的等式或不等式。约束条件往往不止一个, 通常表达成一组线性等式或不等式。线性规划问题就是在决策变量满足一组约束条件的情况下使目标函数达到极大值或极小值。 一般线性规划模型的形式为:
max (或min)
undefined
s.t.
undefined
式中max表示求极大值;min表示求极小值;s.t.表示受约束于或约束条件是;Z为目标函数;xj为决策变量;aij, bi和cj分别为消耗系数、需求系数和收益系数, 在具体的线性规划问题中具有不同的经济学意义, 一般都是已知实数。在线性规划中满足约束条件的一组数 (x1, x2, …, xn) 称为问题的一个可行解, 全体可行解构成的集合称为问题的可行域。在可行域上使目标函数取得极大值 (或极小值) 的可行解称为问题的最优解, 对应的目标函数值称为最优值。
2 线性规划——应用问题
在工业、农业、商业、行政、军事、公用事业等各个领域, 存在着大量的线性规划问题。有些规划问题本身是非线性的, 但往往可以通过改变标度或采用分段线性化等方法, 转化为线性规划模型。
用线性规划求解的典型问题有运输问题、生产计划问题、配套生产问题、下料和配料问题等。
(1) 运输问题。
某产品有n个产地, m个销地。已知各产地的产量和各销地的销量, 以及各产地到各销地的单位运价, 问如何安排各产地到各销地的运量, 使总的运费为最少?
(2) 生产计划问题。
用m种资源生产m种产品。已知各种产品每生产一单位可得的利润和所需的各种资源的数量, 以及各种资源的限额。问如何计划各种产品的生产量, 使总的利润为最大?
(3) 配套生产问题。
用若干台机床加工某种产品的各种零件。已知各机床加工不同零件的效率。问如何分配各机床的任务, 在零件配套的前提下使一个生产周期内的产量最高?
(4) 下料问题。
将一批固定规格的条材或板材裁剪成具有规定尺寸的若干种毛坯, 并已设计出若干种下料方式。问采用哪种下料方式, 能使各种毛坯满足所需数量, 又使总的用料最省?
(5) 混合配料问题。
用n种原料配制某些含有m种成分的产品。已知各种成分在各种原料中的单位含量, 以及各种原料的单价和限额。问怎样混合调配, 在满足产量要求和产品所含各种成分的要求下使成本为最低?
3 单纯性算法基本步骤
(1) 把线性规划模型变成它的标准形式。
(2) 确定初始基可行解, 建立初始单纯形表。
(3) 检查对应于非基变量的检验数λj, (j∈N) ;若所有这些λj均小于零, 则已得到最优解, 停止计算, 否则转入下一步。
(4) 在所有的λj>0中, 若有一个λk在单纯形表上对应的列向量的全部元素yik≤0 (i=1, 2, …, m) , 则此问题无解, 停止计算;否则转入下一步。
(5) 根据max{λj>0|j∈N}=λk, 即确定λk对应的非基变量λk为进基变量;再根据
undefined
确定基变量xr为离基变量。
(6) 基可行解的转换运算, 即实施行变换, 将单纯形表上xk对应的列向量变换为单位向量, 其中包括将λk变换为0, 而原yrk变换为1, 称元素yrk为变换轴心。
4 单纯形法的进一步讨论
现在已有单纯形法的标准软件, 可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度, 又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题, 也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解, 但实用价值不大。以下一个例子通过图解法求解, 可以理解线性规划的更多概念。
例如, 某工厂生产A, B两种产品, 已知生产A1kg, 耗煤9t, 耗电4kw, 用劳力3个工;生产B1kg, 耗煤4t, 耗电5kw, 用劳力10个工。已知生产1kg A的利润是500元, 生产1kg B的利润是900元。现根据工厂条件, 只能提供煤360t, 电力200kw, 劳力300个工。问如何安排两种产品的生产量, 才能使总的利润最大。
设A, B 的产量分别为x1, x2 (千克) , 则上述问题的线性规划模型是:
max Z=5x1+9x2
s.t. 9x1+4x2≤360
4x1+5x2≤200
3x1+10x2≤300
x1≥0, x2≥0
此问题的可行域为图中的多边形区域, 即阴影部分。目标函数的等值线为平行于直线 l的平行直线族。将直线l向右上方平行移动, 对应的目标函数值逐渐增大, 在即将脱离可行域之际, 它与可行域的交点便对应于问题的最优解。由此可知, 在可行域的顶点B 处, 目标函数达到最大值。因此, 问题的最优解为:x1=20千克, x2=24千克, 最大总利润为3.16万元。
摘要：线性规划 (Linear programming, 简记为LP) 模型是运筹学中的一个重要内容, 其基本解法——单纯形方法 (Simplex method) 则是处理运筹学模型的一种主要方法, 用于如何对有限的资源做出最佳方式的调配和最有利的使用, 以便最充分地发挥资源的效能去获取最佳经济效益。就一般线性规划问题求解方法——单纯形法作了详尽的综述。对线性规划进行了概述, 具体从线性规划发展简史、线性规划问题的数学模型和线性规划常见的一些应用3个方面进行了较详尽的综述;进行了单纯形法的概述, 这一部分主要涉及了单纯形法解题的基本步骤以及对单纯性算法作了进一步的讨论。
关键词：运筹学,线性规划,单纯性法
参考文献
[1]G.Dantzig, Linear Programming and Extensions Princeton Univer-sity Press, Princeton, NewJersey, 1963.
[2]S.Gass, Linear Programming, 4thed, McGraw-Hill, NewYork, 1975.
[3]L.S.Srinath, LinearProgramming:PrinciplesandApplications, Mac-millanPress, NewYork, 1983.
[4]胡清淮, 魏一鸣.线性规划及其应用[M].北京:科学出版社, 2004.
[5]《运筹学》教材编写组.运筹学 (第3版) .[M].北京:清华大学出版社, 2005.
线性规划求解算法研究 篇2
基于PSO求解随机相关机会规划的有效算法
随机相关机会规划是一类有着广泛应用背景的.随机规划问题,通过采用随机仿真产生样本训练BP网络以逼近机会函数,然后应用微粒群算法并以逼近机会函数的神经网络作为适应值估计,从而提出了一种求解随机相关机会规划的混合智能算法.最后通过实例仿真说明了算法的正确性和有效性.
作 者：肖宁 Xiao Ning 作者单位：陕西职业技术学院计算机科学系,西安,710100刊 名：计算机与数字工程 ISTIC英文刊名：COMPUTER AND DIGITAL ENGINEERING年，卷(期)：37(6)分类号：O221.5 TP183关键词：随机相关机会规划 微粒群算法 神经网络 随机仿真
线性规划求解算法研究 篇3
关键词：分布估计算法,非线性整数规划,概率模型,解空间
1 引 言
整数规划是数学规划中较复杂的一大类问题。Murty[1]证明了非线性规划问题为NP-hard问题,作为其子集的非线性整数规划也必为NP-hard问题,求解该问题精确解的算法具有指数复杂度。整数规划广泛应用于许多工程领域,如资源管理、生产调度、可靠性优化、目标分配、超大规模集成电路设计等。对于变量规模较小的整数规划,传统的求解方法有分支定界法、割平面法和隐枚举法等。但对于较大规模的问题,传统的方法比较耗时,近年来随着进化计算的发展,许多学者运用遗传算法(GA)、模拟退火算法(SA)、微粒群算法(PSO)、蚁群算法(AA)等方法来求解整数规划问题[2,3,4,5,6]。遗传算法吸取了生物进化和遗传变异论的研究成果,是一种群体性全局寻优方法,但算法执行到一定阶段后向最优解收敛速度缓慢,且遗传算法的性能依赖于遗传因子(选择概率、交叉概率、变异概率、种群规模、染色体长度等)的取值,并且会出现早熟收敛情况。模拟退火算法模拟物质材料的冷却与结晶过程,通过退火温度控制搜索过程,但当问题规模较大时,系统进入热平衡状态(对应于最优解)的时间较长。粒子群算法和蚁群算法性能也依赖于设定参数(如强度的衰减系数等),参数设定的优劣直接影响算法的运算效果。分布估计算法提出一种全新的进化模式,通过统计学习的手段建立解空间内个体分布的概率模型,然后对概率模型随机采样产生新的群体,如此反复进行,实现群体的进化。本文将分布估计算法推广应用到整数规划的解空间中,提出一种求解整数规划的新算法。
2 分布估计算法
分布估计算法(Estimation of Distribution Algorithms,EDAs)[7,8,9]是在进化计算领域兴起了一类新型的优化算法,是一种全新的进化模式。EDAs是在1996年由Mundefinedhlenbein 和Paaβ提出的一种广义型求解法。相对于传统的GA,在EDAs生成后代种群的过程中不需要交叉、变异操作,取而代之的是从一个概率分布中采样新的个体生成新的种群,而此概率模型是根据包含有从前代种群中挑选出来的个体的数据集估计而来。分布估计算法通过一个概率模型描述候选解在空间的分布,采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型,然后对概率模型随机采样产生新的种群,如此反复进行,实现种群的进化,直到满足停止准则。
根据概率模型的复杂程度以及不同的采样方法,分布估计算法发展很多不同的具体实现方法,但是都可以归纳为下面的基本步骤:首先随机生成M个个体,并有这些个体决定初始群体D0,并且对所有的个体进行评估。然后执行第一步,挑选N(N≤M)个个体(通称他们都拥有最好的目标函数值)。然后生成一个能最好的反映出n个变量相互依赖关系的n维概率模型。在根据上一步所得的概率分布获得M个新的个体组成新的种群。然后循环这3步,直到满足停止准则。
其伪代码形式如下:
3 非线性整数规划问题
有约束的整数规划模数学模型为:
undefined
上式中:Z为整数空间;变量xi的下、上限li,ui为整数,w=ui-li+1为xi的可能取的个数。对很多类实际应用组合优化问题,xi的可行域可以枚举。
可行解空间如图1所示,xi有ai个节点,每个变量取一个值就构成空间一个解。如xi取第mi个节点,则对应的解为(x1,x2,…,xn)=(l1+m1-1,l2+m2-1,…,ln+mn-1)。
对于有约束的整数规划可以把原约束方程作为罚函数项加入到原目标中,变成无约束的优化问题。基于此,本文主要研究无约束整数规划问题的求解方法。
4 整数规划的分布估计算法
4.1 解空间的概率模型
在讨论的非线性整数规划问题中,描述解空间的概率模型用简单的概率向量p=(p1,p2,…,pn)表示,p表示群体的概率分布。
4.2 初始化群体
初始群体D0在解空间按照均匀分布随机抽样产生。即概率向量undefined,其中undefined;j=1,2,…,ui-li+1。群体规模为2s,通过适应值函数f(x)计算各个个体的适应值。
4.3 新解产生
在此选择截断方法作为选择策略,选择种群的一半,即选择适应值较高的s个个体,Dundefined。因此Dundefined表示第l代选择后的优势群体。概率向量p通过表达式undefined更新。根据这个概率向量p通过随机采样的方法产生新一代群体,至此分布估计算法完成了一个周期。可见在不断重复产生新解的过程中,适应值高的个体的出现概率越来越大。按照这个步骤改变个体在解空间的概率分布,使适应值高的个体分布概率变大,适应值低的个体分布概率变小,如此反复进化,最终将产生问题的最优解。
4.4 停止准则
由于概率向量p的作用,当迭代次数足够多时,概率向量p会逐渐增大到1,这时产生问题的最优解。即停止准则为p=1。
4.5 算法步骤
算法步骤为:
(1) 随机产生2s个个体(即初始群体)D0;
(2) 通过适应值函数f(x)计算各个个体的适应值;
(3) 以截断方法作为选择策略,选择种群的一半,即选择适应值较高的s个个体,Dundefined;
(4) 估计选择的s个个体中每个个体的概率分布pl(x)=p(x|Dundefined),并通过这个表达式更新概率向量p;
(5) 根据概率向量p通过随机采样的方法产生新一代群体Dundefined;
(6) 如果没有满足停止准则,返回第(2)步。
5 算 例
为了验证上述分布估计算法求解非线性整数规划的有效性,用EDAs解下列算例[10]:
算例F1: min F1=|x1|+|x2|+…+|x10|
St.-10≤xi≤10,xi∈Z(i=1,2,…,10)
算例F2: min F2=xundefined+xundefined+…+xundefined
St.-10≤xi≤10,xi∈Z(i=1,2,…,10)
算例F3: min F3=(x1-10x2)2+5(x3-x4)2+(x2-2x3)4+10(x1-10x4)4
St.-10≤xi≤10,xi∈Z(i=1,2,…,4)
采用本文所提出的算法,利用Java语言编程求解算例。随机产生100个个体组成初始种群D0(s=50),计算适应值之后以截断方法作为选择策略,选取适应值较高的50个个体,估计这50个个体的概率分布更新向量p,在根据p通过随机采样的方法产生100个个体的新一代群体。反复执行直到满足停止准则,求得全局最优解,最优解取值如表1所示。
6 结 语
分布估计算法是进化计算领域内一个崭新的分支,他通过对整个群体建立数学模型,直接描述整个群体的进化趋势,是对生物进化“宏观”层面上的数学建模。分布估计算法通过概率模型可以描述变量之间的相互关系,对于解决非线性整数问题更加有效。通过算例,说明本文给出的算法有效。
参考文献
[1]Katta G Murty.Some NP-complete Problemin Quadraticand Nonlinear Programming[J].Mathematical Program-ming.1987(39):117-129.
[2]Rudolph G.An Evolutionary Algorithm for Integer Pro-gramming.Parallel Problem Solving from Natures—PPSNⅢ[M].Lecture Notes in Computer Science,Springer,Ber-lin.1994.
[3]丰建荣,刘志河,刘正和.混合整数规划问题遗传算法的研究及仿真实现[J].系统仿真学报,2004,16(4):845-848.
[4]谢云.用模拟退火算法并行求解整数规划问题[J].高技术通讯,1991,1(10):21-26.
[5]谭瑛,高慧敏,曾建潮.求解整数规划问题的微粒群算法[J].系统工程理论与实践,2004,24(5):126-129.
[6]黄樟灿,吴方才,胡晓林.基于信息素的整数规划的演化求解[J].计算机应用研究,2001,18(7):27-29.
[7]Bengoetxea E,Larraˇnaga P,Bloch I,et al.Solving graphMatching with EDAs Using a Permutation-based Repre-sentation.Esti mation of Distribution Algorithms.A NewTool for Evolutionary Computation.Kluwer Academic Pub-lishers,2002.
[8]Zhang Qingfu,Sun Jianyong,Edward Tsang,et al.Esti ma-tion of Distribution Algorithm with′2-opt Local Search forthe Quadratic Assignment Problem.StudFuzz,2006:281-292.
[9]Jiri Oceanasek.Entropy-based Convergence Measurementin Discrete Esti mation of Distribution Algorithms.Stud-Fuzz,2006:39-50.
线性规划求解算法研究 篇4
敏捷卫星是近年来出现的新一代对地观测卫星,由于保密的原因,国内外公开的相关敏捷卫星任务规划问题的文献资料不是很多。典型的主要有法国Lemaitre等人针对新一代敏捷卫星Pleiades的任务规划问题研究,提出了约束规划模型,比较了约束规划、贪婪、动态规划以及局部搜索等四种算法,并指出了各自的适用范围[1]。Panwadee针对敏捷卫星任务规划问题建立了多目标优化模型,提出了遗传算法的求解策略[2]。在国内研究中针对敏捷卫星的常规任务规划问题,陈宇宁,等分析了灵巧卫星调度问题的约束条件,构建约束满足模型,提出了基于蚁群算法的调度求解策略[3]。李玉庆构建了任务规划调度的数学模型,并采用了模拟退火算法和遗传算法相结合的混合遗传算法求解策略[4]。对于非敏捷卫星任务规划,美国的Wolfe等学者采用了三种算法求解对地观测卫星任务规划问题,研究表明遗传算法求解效率优于优先级调度算法和具有前看功能的求解算法[5]。由此可见,在解决卫星任务规划非线性NP-hard问题时,智能优化算法在求解敏捷卫星任务规划问题时具有很多优势。
在深入分析敏捷卫星任务规划特点的基础上,首先对敏捷卫星任务规划问题进行了抽象描述;然后构建了基于多目标的敏捷卫星任务规划模型;最后提出了蚁群算法和免疫遗传算法相结合的混合遗传求解方法。
1 问题描述及模型构建
1.1 敏捷卫星观测方式
敏捷卫星观测视角可以围绕翻滚、俯仰和偏航三个轴变化,具有三维观测自由度,它可以进行完成滚动、俯仰、偏航的星上动作,因此其具有很强的姿态机动能力。敏捷卫星有可能在能力允许的范围内沿任意走向对目标进行观测,因此敏捷卫星的灵活性和观测效率由于姿态敏捷的控制而得到了很大的提高,如图1所示[6,7]。敏捷卫星切换速度快,在俯仰轴14秒内可达到45度,平均速度可达到了3.2度每秒[8]。敏捷卫星能够进行俯仰,其可视时间窗口也相对比较宽泛,其可以在可见时间窗口内较自由地选择可见时间窗对观测目标进行观测。而非敏捷卫星不能做出俯仰的姿态,因此其只有在经过地面目标上空时才可见观测目标[9,10]。它们的观测方式对比如图2所示。正是由于敏捷卫星观测方式的复杂性,导致其任务规划求解对比于传统的非敏捷卫星任务规划问题更为复杂。
1.2 敏捷卫星对地观测组织实施
敏捷卫星对地实施过程是将包含有任务类型、任务目标优先级以及任务图像分辨率等要求的多用户任务需求,经过智能辅助分析后形成规范化的任务集;以敏捷卫星和地面站部署的现有资源集为基础,充分考虑敏捷卫星携带传感器类型、存储容量、俯仰角以及侧视角范围等一系列约束条件,在一定的规划时间范围内统一规划有限的敏捷卫星资源,将待观测任务集合理地安排到各个敏捷卫星上执行完成观测任务;然后将任务规划方案提交给地面测控中心进行操控实施调度,通过地面测控与观测目标的数据接收处理、评估后将用户所需的数据发送给敏捷卫星需求用户。卫星任务规划可以大大提高敏捷卫星的对地观测效率,可以满足更多的敏捷卫星用户需求。如图3所示敏捷卫星对地观测组织实施流程。
1.3 模型假设
敏捷卫星任务规划问题是一个极为复杂的问题,涉及到的决策对象繁多,还需要考虑对象间的关系错综复杂,而在解决问题时不可能考虑到所有的约束条件;为了更贴近实际,解决关键问题,需要对任务规划问题简化并适当做出一些假设,而这些假设都是与卫星任务规划调度实际紧密结合的,假设也是合理的[11]。
(1)每个敏捷卫星只携带一个星载传感器。
(2)同一颗敏捷卫星同一时刻只能执行一个元任务,而且只要开始执行一个元任务,则不能中断。
(3)敏捷卫星可靠性高,工作时故障发生的可能性很低;同时也不考虑天气、云层等有关气象条件对目标观测的影响。
(4)除周期性任务外,每个元任务在敏捷卫星规划的一个周期内只执行一次。
1.4 模型构建
1.4.1 目标函数
敏捷卫星任务规划的目标是在某一确定的时间段内,在满足卫星约束的前提条件下以尽量少的资源消耗完成尽可能多的任务、获得最大的综合收益,同时也希望各个敏捷卫星间负载更加均衡,达到尽量好的卫星成像效果。因此其敏捷卫星任务规划问题是一个多目标优化问题。任务规划目标函数数学表述如下。
目标1:任务收益率最大,即
目标2:任务完成率最大,即:
目标3:资源使用均衡度最大,即尽可能满足各可用载荷上负载均衡,工作时长均匀一些。即:
资源使用均衡度公式如下:
其中,max SWT=mjax(SWTj)。wi为观测任务ti的收益,PRI(ti)为观测任务ti的优先级,N为观测任务集中的任务总数。Tetij代表观测任务ti的结束时间,Tstij代表观测任务ti的开始时间。对于上述三个目标可以利用加权法实现。
maxf1=αM1+βM2+γM3,其中α,β,γ为影响因子,α+β+γ=1。
1.4.2 主要约束条件及数学描述
(1)可见时间约束
式(1)和式(2)要求观测任务起始时间必须在卫星与观测目标的可见时间窗内执行,其可见时间长度必须要大于任务的执行时长。其中,ETik为观测任务ti的可见时间窗的结束时间,Tstij为可见时间窗ti的开始时间。DuraT(ti)为观测任务的持续时间。
(2)俯仰角和侧摆角约束
式(3)和式(4)是侧摆角与俯仰角的约束条件,要求在任务转换时敏捷卫星在有限的时间内能够达到下次观测任务时所需要满足俯仰角和侧摆角的约束条件。其中,FAgij和BAgij分别为敏捷卫星j中观测任务ti在STjik时刻的俯仰角和侧摆角;ajf和ajb分别为敏捷卫星j进行姿态调整俯仰和侧摆两个姿态时的角加速度。
(3)太阳高度角约束
式(5)是太阳高度角约束,要求卫星执行任务时刻应该满足最小太阳高度角要求。其中,Ai(Ai∈(0,90])是任务ti在STjik时刻的太阳高度角。SEAmin是满足成像要求的最小太阳高度角。
(4)能量约束
式(6)是能量约束,卫星侧摆俯仰以及照相时所消耗的能量敏捷卫星应该能满足,其应该小于卫星最大能量。其中,ηi为敏捷卫星j观测单位时间内所消耗的能量;ρi表示敏捷卫星j在姿态调整时单位角度内所消耗的能量;πj卫星j在阳照区单位时间内的充电量;SNLij表示执行观测任务ti前敏捷卫星j可用的能量;SNLi表示敏捷卫星j最大的可用能量。
(5)存储容量约束
存储容量约束式(7)要求敏捷卫星在一个轨道圈次内执行观测任务ti时星上可用的存储容量满足成像要求。其中,SSRjt代表敏捷卫星j在t时刻的存储容量;imageSSR(tj)表示为执行观测任务ti所需要的存储容量;MaxSSRj代表敏捷卫星j的最大存储容量。
2 免疫遗传蚁群混合求解算法
从敏捷卫星任务规划模型中可以得出其目标函数具有非可导性、非连续;任务规划中的一些先验信息较少或者不存在;因此其为求解带来了一定的难度。遗传算法对于解决多数组合优化和调度问题,处理复杂约束问题和非线性问题具有众多优势。
同时针对蚁群算法具有初始解好,易陷入局部最优,收敛速度慢,求解精度不高等特点,并结合遗传算法的优点[12]。本文提出了将蚁群算法与免疫遗传算法相结合的求解算法,其能够克服每个算法的缺点,充分发挥各自的优势。
2.1 混合求解算法流程
设计的求解算法基本思想是将蚁群算法每次迭代中所产生的全部解的集合作为初始种群,对初始种群进行免疫遗传算法的多次进化迭代操作,尝试寻找相对于当前全局最优解更优秀的解,如图4所示求解算法流程图。
2.2 状态转移规则及信息素的更新
针对敏捷卫星任务规划的特点,借鉴蚂蚁系统的思想,本文在蚁群算法中的状态转移规则如下:一只处于节点r的蚂蚁应用式(8)选择将要移动到的下一个j节点[13]。
式(8)中,q为[0,1]均匀分布的随机变量,q0(0≤q0≤1)是一个参数;ηij是距离tij的倒数,tij是任务执行间隔时间的影响;Y的选择主要依据式(9)中的概率分布函数。
式(9)中,alldk(Ti)为蚂蚁k下一步可执行任务的集合;τij是信息素分布,PRI(ti)为观测任务的优先级影响。α,β,γ分别为各个影响因素作用强度的权重。
信息素局部更新策略:当蚂蚁从任务T(t0)出发,依照状态转移寻优策略选择下一个任务节点,若找不到,则返回;若找到,则构造可执行任务序列TSequ,将其目标值与当前全局最优任务执行序列TSequB的目标进行比较,若小于,则TSequ所有边上的信息素挥发,τNij=(1-ρ)τijOld,ρ为信息素挥发率;若大于,则更新全局最优解TSequB=TSequ。为加快收敛速度,每次依据式(10)只对最优任务序列上的信息素浓度进行更新。
式(10)中,,R为设定的参数。
2.3 混合求解算法基本操作
2.3.1 染色体编码结构
编码是遗传算法的关键,编码结构的选择会对求解空间产生直接的影响。编码方案是确定染色体串与问题的搜索空间中的点之间的映射关系。本文采用二进制编码方式构造染色体。敏捷卫星成像目标任务只有完成或不能完成两种状态,长度为N的等长0—1二进制编码构造染色体被选择采用。每一个二进制序列被称之为一个染色体段,因此整个二进制序列所代表的敏捷卫星成像任务的集合即为任务规划的结果。染色体串的每一位取值代表了该观测目标是否被选取,每个基因位对应着一个敏捷卫星观测元任务。
其中,将X={x1x2…xi…xN}。
为种群中的一个染色体,其染色体编码结构如图5所示。
2.3.2 遗传操作
选择:选择基于适应度比例的选择策略,即常用的轮盘赌法,个体i被选中的概率为,其中fi为个体i的适应度值;N为种群个体数目。
交叉:采用多点交叉的方法来进行,如图6所示。多点交叉比单点交叉具有更好的鲁棒性,具有更好的重组能力,不但可以解决过早收敛的问题,而且可以加快算法对整个解空间的搜索速度。
变异:每个个体的变异概率采用公式(11)来计算:
式(11)中,fmin和favg分别表示当前种群中个体适应度值的最小值和平均值,fi代表第i个个体的适应度值,P[i]代表第i个体变异概率。
3 实例分析
实例为10颗星,600个元任务的仿真场景,应用STK软件及Matlab2011a软件,卫星轨道数据来源于AGI公司于2010年6月发布的全球卫星轨道数据库,任务分布主要集中在重点热点地区,任务生成方法采用文献[14]的方法。为表述更加清晰,选择在实际应用中最广泛的点目标观测需求为例展开研究。仿真中的参数设置为:免疫遗传操作最大代数MAXGEN=1 300,交叉概率pc=0.95,变异概率pm=0.08,疫苗接种概率pv=0.5;蚂蚁数AntCount=40。所设计的算法与遗传算法和免疫遗传算法进行了对比,在内存为4 G,Intel-i5双核心CPU的环境下将每个算法运行15次,取平均值,对任务收益率、负载均衡度以及综合收益率几个方面进行了比较分析。运行结果统计处理后如表1、图7、图8所示。
从表1中可以看出在达到约98%最佳解性能时,遗传算法所用时间最多,免疫遗传算法次之,IA-COGA算法所用的时间最少,与GA相比节省了约373 s,可见其求解效率很高。
为运算结果对比更加清晰,加入了求解敏捷卫星任务规划的规则算法,主要有先来先服务(FIFS)和优先级规则算法(Priority),由于规则方法执行时间极短,因此本文将其画成直线与其它算法形成直观的对比,便于分析。从图7中可以得出IACOGA算法综合指标最高,其任务收益率高于其它算法;其次是IGA算法得到的结果,较接近IACOGA算法求得的值;GA算法、IGA算法以及IACOGA算法最终都超过了FIFS算法和Priority算法,相比较而言GA得到的理想解是最不理想的。从图8中可以得出IACOGA算法的任务均衡度也是最高的,优于其它两种算法。
综合来看,在算法初期,IGA算法曲线起点较高,但随着时间的推移,曲线上升幅度很小,很平缓。GA算法曲线初始起点较低,一段时间内上升幅度较大,但到最后曲线很是平缓,其方差波动也较大。IACOGA算法曲线起点较高,曲线上升也较快,其方差波动也较小,因此所设计的混合遗传算法具有较佳性能。
4 结束语
线性规划求解算法研究 篇5
关键词：双层规划,自适应粒子群优化算法,分层迭代
1 引言
双层规划研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者,并不直接干涉下层的决策;而下层决策者只需要把上层的决策作为参数,他可以在自己的可能范围内自由决策。这种决策机制使得上层决策者在选择策略以优化自己的目标达成时,必须考虑到下层决策者可能采取的策略对自己的不利影响。因此,双层规划是一种NP hard问题,具有一定的复杂性与现实意义。
目前对于双层规划模型通常采用数值仿真计算,以期在合理的时间内获得模型的近似最优解。但是,当前国内外一些学者提出的求解算法或求解方法,都是针对特定的双层规划模型提出的,并且算法的运行效率和收敛精度都不高。本文在分析和借鉴现有的一些较优秀的算法思想的基础上,提出采用自适应粒子群优化算法求解双层规划模型。实验研究表明,本文提出的算法不仅能有效求解双层规划模型,可以获得高质量的全局最优解,而且该算法具有通用性和普遍性,不依赖于具体的双层规划模型。
2 双层规划模型
双层规划模型的基本思想可以用下面的数学模型来描述:
设上层决策者控制的变量为
下层决策者控制的变量为
上层规划的数学模型为:
其中y=y(x)由下层规划求解。
下层规划数学的模型为:
双层规划模型是由以上两个相互关联的子模型(U)和(L)组成,F是上层规划所确定的目标函数,x为上层规划的决策变量,G是对变量的约束;f为下层规划所确定的目标函数,y为下层规划的决策变量,g是对变量y的约束。上层决策者通过设置x的值影响下层决策者,因此限制了下层决策者的可行约束集,而下层决策者的行为反过来又会通过y影响上层的决策,所以下层决策变量y是上层决策变量x的函数,即y=y(x),这个函数一般称为反应函数。
一般来说,求解线性双层规划问题是非常困难的,Jeroslow指出线性双层规划是一个NP-hard问题,Ben-Ayed及Bard对此结论给出了简短的证明;Hallsen对性双层规划是强NP-hard问题给出了严格的证明。后来,Vicente指出,寻找线性双层规划的局部最优解也是NP-hard问题,不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的,它也可能是一个非凸问题,并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。
3 粒子群优化算法模型
3.1 基本粒子群优化算法
粒子群优化算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法,在PSO中,每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值,每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解,在每一次叠代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体极值pBest,另一个极值是整个种群目前找到的最优解,这个极值是全局极值gBest。粒子在找到上述两个极值后,就根据下面两个公式来更新自己的速度与位置:
其中,Vk为迭代第k步粒子的速度,Xk为第k步粒子的位置,pBestk为第k步粒子本身所找到的最优解的位置,gBestk为第k步整个粒子群当前找到的最优解的位置;rand是[0,1]之间的随机数,c1和c2被称作学习因子,通常,c1=c2=2,w是加权系数,一般取值在0.1-0.9之间。
3.2 自适应粒子群优化算法
为了平衡PSO算法的全局搜索能力和局部改善能力,采用非线性的动态惯性权重系数,公式如下:
其中wmax、wmin分别表示w的最大值和最小值,f表示粒子当前的目标函数值,favg和fmin分别表示当前所有粒子的平均目标值和最小目标值。在上式中,惯性权重随着粒子的目标函数值而自动改变,因此称为自适应权重。
当各粒子的目标值趋于一致或者趋于局部最优时,惯性权重将增加,而各粒子的目标值比较分散时,惯性权重将减小,同时对于目标函数优于平均目标值的粒子,其对于的惯性权重因子较小,从而保护了改粒子,反之对于目标函数值差于平均目标值的粒子,其对于的惯性权重因子较大,使得该粒子向较好的搜索区域靠拢。
3.3 双层规划模型求解方法
双层规划问题是一个多目标优化难题,对于一个非线性双层规划问题,对其求解会更加复杂。粒子群优化算法结构简单,控制参数更少,本文将利用分层迭代的思想,采用改进的粒子群算法求解双层规划问题。算法的基本流程如下:
步骤1(初始化)初始化自适应粒子群算法中的参数;随机产生下层模型的初始解(需满足约束条件)。
步骤2 (求解上层规划)将下层模型的解代入上层模型,利用算法求解上层模型,获得上层模型的最优解。
步骤3(求解下层规划)将上层模型的解代入下层模型,利用传统优化方法求解下层模型,获得下层模型的最优解。
步骤4(判断)若满足算法终止条件(误差足够好或者达到最大迭代条件),则停止,否则转步骤2。
4 算例研究
下面通过几个双层规划模型的数值例子,来验证本文给出的自适应粒子群算法求解双层规划模型的可行性与有效性,并与参考文献中的结果做比较。
例1
例2
在上例中,取离子数为40,学习因子都取2,最大惯性权重为0.9,最小惯性权重为0.6,迭代步数取100,最后得到的结果和文献比较如表1所示。
从上述的例子结果可以看出,本文算法的计算结果和文献基本相符合,充分可以得出本文算法的有效性,另外,由于粒子群算法的简单与智能化,参数设定比较少,因此,在解决类似问题具有一定的优势。
5 结论
采用自适应粒子群算法求解双层规划模型是一项崭新的尝试,通过对算例的数值计算,表明本文提出的算法是非常有效的。自适应粒子群算法不仅能够有效的求解双层规划模型,而且具有一定的通用性和普遍性。本研究期望能为以合理的代价用智能算法求解大型复杂模型指明一条新的路径。
参考文献
[1]Kennedy J.Eberhart R.Particle swarm optimization[C].IEEE International Conference on Neural Networks(Perth,Austra1ia),IEEE Service Center,Piscataway,N J,1995,IV:1942-1948.
[2]Shi Y.Eberhart R.A modified particle swarm optimizer[C].IEEE International Conference on Evolutionary Computation,Anchorage,Alaska,May4-9,1998.
[3]孙会君,高自友.供应链分销系统双层优化模型[J].管理科学学报,2003,6(3):66-70.
[4]吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.
[5]江燕,胡铁松等.基于粒子群算法的非线性二层规划问题的求解算法[J].运筹与管理,2006,15(2).
[6]刘佳,秦四平.不确定性决策在配送中心选址y元素中的应用研究[J].物流技术.2006.(12):52—54.
[7]龚纯,王正林.精通MATLAB最优化设计[M].北京:电子工业出版社,2009.271-290.
求解非线性方程组的人工鱼群算法 篇6
人们在研究科学技术及生产实践中,常常会遇见对于非线性方程及方程组的求解问题。对于非线性方程及方程组的求解,传统的方法中是比较难求解且难以求到精确解。数值方法如牛顿法、延拓法与二分法等方法,都要用到目标函数的导数信息和初始点信息。初始点的选择往往非常关键,求解结果的收敛性在很大程度上依赖于初始点位置的选择,而要选择一个好的初始点,求解出非线性方程组的解,往往又非常困难。数值方法求解非线性方程组还存在收敛的局部性,对于一些较复杂的非线性方程组,数值解法容易导致求解失败、算法的有效性较低。
人工鱼群算法(Artificial Fish Swarm Algorithm,AF-SA)是我国学者李晓磊博士等人通过模仿鱼类行为方式提出的一种基于动物自治体的优化方法,是群体智能思想的一个具体应用。在一片水域中,一般情况是:鱼生存数目最多的地方是该水域中含营养物质丰富的地方。AF-SA作为一种新的智能优化算法,主要模仿了鱼的觅食、聚群和追尾行为,通过鱼群中各个体的局部寻优协作,从而达到群体的全局寻优目的。
本文是利用人工鱼群算法求解非线性方程及方程组,通过将非线性方程及方程组的求解问题转化为函数的优化问题,应用人工鱼群算法进行优化求解。相比传统数值方法求解非线性方程组,本文方法不需要使用初始点信息,也无需知道目标函数导数信息,并且在求解精度、收敛性方面也更好,能够以较快的速度求解出非线性方程及方程组的满意解。
1 人工鱼群算法
由文献[2]可知,人工鱼群算法是通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,从而实现算法的寻优功能。AFSA具有诸多优点:如可有效地克服陷入局部极值、求解时仅使用目标函数的值、在搜索空间具有一定的自适应能力、对初值与参数选择不敏感、收敛速度快和适用范围广等。
人工鱼中个体的状态可以表示为向量X=(x1,x,…,xn),其中xi(i=1,2,…,n)表示要寻优求解的变量。当前所在位置的食物浓度表示为Y=f(x),其中Y为目标函数值。人工鱼个体之间的距离表示为di,j=‖Xi-Xj‖。Visiual表示人工鱼的感知范围,Step表示人工鱼最大移动的步长,δ表示拥挤度因子,try_number表示人工鱼每次觅食时最大的试探次数。AFSA首先初始化一群人工鱼,这群人工鱼是通过迭代更新搜寻问题的最优解,在每次迭代过程中,是通过觅食、聚群及追尾等行为来更新自己。
1.1 觅食行为(prey)
设人工鱼当前状态为Xi,探索其视野范围领域内,即di,j≤Visiual,随机选择一个状态Xj,如果在求极小问题中Yj
其中rand(step)表示[0,step]间的随机数。
1.2 聚群行为(swarm)
设人工鱼当前状态为Xi,探索其视野范围领域内,即di,j≤Visiual,计算出伙伴数目nf及中心位置Xc,若nf≠0,可按公式(2)计算中心位置:
如果Yc/nf<δYi,则表明伙伴中心有较多食物且不太拥挤,就朝伙伴的中心位置方向前进一步,即执行公式(3);否则执行觅食行为。
若nf=0,执行觅食行为。
1.3 追尾行为(follow)
设人工鱼当前状态为Xi,探索其视野范围领域内,即di,j≤Visiual,计算出伙伴数目nf,若nf≠0,则Yj为最优的伙伴Xmax,如果Yj/nf<δYi,则表明伙伴Xmax的状态为具有较高食物浓度且其周围不太拥挤,就朝伙伴Xmax的方向前进一步,执行公式(4),否则执行觅食行为。
1.4 随机行为
人工鱼在视野范围领域内,即di,j
1.5 行为选择
在人工鱼群算法中,行为选择是根据具体解决问题的性质,对人工鱼当前运行环境状态进行评价,为下次运行选择一种合适的行为。通常根据实验情况,行为选择一般是按进步最快的原则或进步即可的原则进行。
1.6 公告板
人工鱼群算法公告板的设立是为了记录最优人工鱼的状态,方便运行结束输出最优解。在人工鱼寻优过程中,每条人工鱼在一次行动之后,都将自身的当前状态与公告板的状态进行比较,如果当前自身状态优于公告板的历史状态,则将当前自身状态取代公告板的历史状态,使得公告板每次都记录下历史的最优结果。
2 求解非线性方程组的人工鱼群算法
2.1 非线性方程组转化成函数优化
设非线性方程及方程组的数学模型可表示为:
其中,f(X)=[f1(X),f2(X),…,fm(X)]T可看作成变量X的m维向量函数。因此,可以将方程组写成分量的形式:
在非线性方程及方程组的定义域内x*为其根,那么对于非线性方程及方程组的求根x*可等价为:
的优化问题。
2.2 AFSA求解非线性方程及方程组的流程
(1)初始化设置人工鱼群算法的各参数。群体规模N,可视域Visual,步长Step,拥挤因子δ,最大试探次数try_number。
(2)根据非线性方程组及方程转化过来的目标函数,计算初始鱼群中各个体当前位置的食物浓度,比较大小,并将最优值写入公告板。
(3)各人工鱼分别执行追尾行为与聚群行为。选择Y值较大的行为实际执行,缺省行为方式为觅食行为。
(4)在人工鱼群中,各人工鱼每行动一次后,比较自身当前信息与公告板信息,将最优信息写入公告板中。
(5)人工鱼群算法终止判断。若公告板记录信息已达到预置的最低食物浓度要求,则输出计算结果,否则转入(3)。
(6)判断解非线性方程及方程组终止条件。若求解得到满意解,则终止执行。否则,转入(2)。
3 实验结果及分析
将人工鱼群算法应用于非线性方程及方程组的求解,其中参数可根据经验取值设置为:群体规模N=100,可视域Visiual=2.5,步长step=0.3,拥挤因子=0.618,最大试探次数try_number=10。计算中设置最小阈值为1e-06。
算例1:Leonardo方程
算例2:非线性方程
算例3:非线性方程组
为了验证算法的有效性,应用人工鱼群算法对每个算例,独立运行50次,将这50次的运行的最终结果统计如表1所示。
从表1可以看出,应用人工鱼群算法求解以上3个算例,每次都收敛,运算速度快、算法编程实现简单,并且都求得满意精度的解。
4 结束语
本文是将人工鱼群算法应用于非线性方程及方程组的求解。传统数值方法在求解非线性方程及方程组时存在初始值难选、收敛性较差等不足;应用人工鱼群算法求解不需要使用初始点信息,并且也无需知道目标函数的导数信息,所以可有效地避免传统数值方法求解的这些不足。
通过几个典型的非线性方程及方程组的求解实验可知,应用人工鱼群算法求解非线性方程及方程组表现出:求解效果较好、通用性强、实现简单。当然,人工鱼群算法作为一种较新的群体智能算法,还有许多待研究的方面。下一步的研究目标是扩大实验范围,进一步拓展人工鱼群算法的应用领域。
参考文献
[1]李庆扬,莫孜中,祁力群.非线性方程组的数值解法[M].北京:科学出版社,1999.
[2]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002(11).
[3]李晓磊,钱积新.基于分解协调的人工鱼群优化算法研究[J].电路与系统学报,2003(1).
[4][美]施依德(scheid,f.).数值分析[M].罗亮生,包雪松,王国英,译.北京:科学出版社,2002.
[5]臧明磊,杨士俊.用遗传算法解一元非线性方程[J].济宁师专学报,1998(6).
求解非线性方程组的三种算法 篇7
关键词：非线性方程组,牛顿型算法,信赖域算法,遗传算法
一、引言
非线性科学在工业、农业、科学研究领域占有重要地位，绝大多数问题最终都能转化为非线性方程(组)的求解问题，传统的解决方法有:牛顿法、割线法、延拓法、搜索法、梯度法、信赖域法、共轭方向法、变尺度法等．本文着重介绍信赖域算法、牛顿型算法、遗传算法三种方法．
非线性方程组为
其中
解非线性方程组一般分为两类方法:一类属于线性化方法，即把非线性方程组转化为一种近似的非线性方程组，构造出迭代格式，然后逐次接近准确解，达到满足精度要求就终止计算;一类属于求函数极值方法，即由非线性函数构造出一个目标函数，把方程组的求解问题转化为求目标函数的极值点问题．构造目标函数:
这样，在区域内求解非线性方程组问题(1)就转化为了函数优化问题:
显然，满足F(x1*,x2*，…，xn*)=0的非线性方程组的解X*(x1*,x2*，…，xn*)就是函数优化问题(2)的最优解．
二、牛顿型算法
求解非线性方程组的线性化方法为:
若取则得到求解非线性方程组的牛顿型迭代算法．
1. 牛顿法
牛顿法算法程序构造过程实际上是对非线性方程组(1)左端的非线性函数逐步线性化的过程．假定F:D∈Rn→Rn在开凸集内二次G-可导，且F″(x)在D内连续．设x*∈D是(1)式的解，x0∈D是x*的初始近似值．牛顿法虽然有收敛速度快和自校正等优点，但应用到实际计算中仍存在不少问题:迭代初始值x0要求与解x*很接近;每次迭代计算Jacobi矩阵F'(xk)和求解一个线性方程F'(xk)Δx=-F(xk)，工作量较大;当F'(xk)奇异或是病态时，计算将无法进行下去．为了解决这些问题，牛顿法有了如下几种变形．
2. 修正牛顿法
修正牛顿法主要是针对牛顿法计算量较大进行简化和改进，将牛顿法收敛快和简化牛顿法工作量省的优点结合起来，得到如下迭代程序:
从xk计算到xk+1中间做m次简化，只需计算一次Jacobi矩阵F'(xk)和求一次逆矩阵[F'(xk)]-1，这种修正牛顿法具有m+1阶收敛速度．
3. 参数牛顿法
参数牛顿法是为了保证每一步迭代中的F'(xk)非奇异或非病态，而引入所谓的阻尼因子λk使F'(xk)+λkI(这里I为n阶单位矩阵)非病态，此时得到迭代程序为:
当λk选得足够大，可以使矩阵F'(xk)+λkI对角占优，从而消除F'(xk)的奇异性，并具有局部收敛性．
4. 下降牛顿法
为了克服牛顿法的局部收敛，初始点x0选取要很靠近解x*，引入迭代参数，采用下降法思想具有大范围收敛的牛顿下降法，其迭代程序为:
其中0<ωk≤1是迭代参数，可以证明迭代式具有大范围收敛性，但实际应用中选择ωk仍比较困难．
牛顿法及其改进形式是最基础、应用广泛的求解非线性方程组方法，但由于牛顿法需要每步计算函数的导数，若导数不能直接表示出来，则很难求解，且在实际应用中往往受到很多条件的限制，它的收敛性和性能特征在很大程度上依赖于初始点的选择;另外，牛顿型算法在处理某些形式比较复杂的非线性方程组时效果不好．因此，牛顿法的各种变型都是针对牛顿法的某一缺陷而考虑的，实际应用时只能根据要解决主要问题采取相应的策略．
三、信赖域方法
信赖域方法首先定义一个在当前点与目标函数近似的二次模型，利用目标函数在一定的区域内与二次模型的充分近似，取二次模型的最优值作为信赖域方法的下一个迭代点．其出发点是利用目标函数的二次模型的近似程度来调节信赖域的大小:若新的迭代点不能使目标函数值有充分的下降，说明二次模型与目标函数的近似程度不够好，需要缩小信赖域半径;否则就扩大信赖域半径．
对非线性方程组F(x)=0的求解可转化为如下无约束优化问题:
相应的二次信赖域优化模型:
其中，在xk点Jacobi矩阵．
对于(7)，在xk点的下降方向dk有下述信赖域子问题产生．
四、遗传算法
求解非线性方程组对于传统算法的选择、构造与所要解决问题的特性有很大关系．遗传算法不采用确定性规则，而采用概率的变迁规则来指导它的搜索方向，是一种灵活的自适应算法，无需过多考虑问题的具体形式．由于非线性方程组改造成的函数多数是多峰值函数，遗传算法在其求解应用中具有较大优势，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效，近几年利用遗传算法求解非线性方程组的数值问题也有相关的研究成果．
刘灿文等“基于求解非线性方程组的并行遗传算法的设计”提出了将非线性方程组的数值求解问题(1)转化为线性约束最优化问题:
差度量函数．将遗传算法改进为自适应并行遗传算法求解该最优化问题，从另一角度为求解非线性方程组提供了一条比较有效的途径．
曾毅“改进的遗传算法在非线性方程组求解中的应用”提出利用改进的遗传算法求非线性方程组的解，数值模拟结果表明改进后的遗传算法不仅可以求得高精度的解，而且大大提高了遗传算法的局部寻优能力．曾毅“浮点遗传算法在非线性方程组求解中的应用”提出利用浮点遗传算法适应值的分布和实数编码的特点，通过缩小、移动搜索空间的方法，将整体和局部寻优能力有机结合，数值模拟结果表明该算法求精确解的有效性．吴国辉等“一种新的求解非线性方程组的混合遗传算法”提出利用浮点遗传算法全局群体搜索能力及起始搜索速度快的特点，快速得到接近精确解的较优解，之后将其作为拟牛顿法迭代的初始值，利用其局部寻优能力非常强的特点快速迭代至精确解，该算法融合了遗传算法和拟牛顿法的优点，具有较好的收敛速度和相当精度的收敛解．杜娟等“一种新的非线性方程组的混合量子遗传算法”综合考虑了量子遗传算法和拟牛顿法的各自优点，结合两者提出一种求解非线性方程组的有效算法，充分发挥量子遗传算法的群体搜索和全局收敛性，同时采用拟牛顿法作为一个强局部搜索算子，把量子遗传算法的寻优结果作为拟牛顿算法的初值，有效地解决了拟牛顿法对初始值的敏感问题，提高了算法的局部搜索能力，仿真实验表明此算法具有较高的求解精度与成功率．
线性规划求解算法研究 篇8
随着全球能源和环境问题的日益突出,风能等可再生能源发电技术得到迅速发展,风电并网的规模也越来越大[1,2]。由于风电出力具有很强的不确定性,含风电场的电网日前发电调度问题常描述成为一个含有随机变量的动态经济调度(DED)问题[3,4]。为了使获得的发电调度计划对于风电场出力不确定性具有适应性,通常采用场景法,通过对风电场出力随机变量进行抽样模拟,进而将随机模型转换为确定性DED模型[5,6,7,8,9,10]。由于随着抽样的场景数目的增多,场景法求解随机DED问题的模型维数将快速增大,直接求解非常费时,因而目前该方法主要应用于中小型系统的优化调度,应用于实际大型电网将面临模型维数太大、求解时间太长的问题。
另一方面,由于发电机组相邻时段出力的变化量存在爬坡率的限制,含风电场的电网日前发电调度问题是一个含有一天所有时段变量的联合优化模型,所有时段变量的同时求解是导致问题维数太大的另一个关键因素。动态规划(DP)法根据最优性原理,即Bellman方程可实现对于日前发电优化调度问题各个时段决策量的解耦求解[11,12]。然而,实际大电网机组众多,每个时段各个机组出力组成的状态维数非常之大,DP法应用于大电网发电调度问题将不可避免地面临着“维数灾”难题。
近似动态规划(ADP)理论通过近似描述值函数与状态量之间的关系来克服“维数灾”难题,文献[13,14]应用ADP理论求解大规模机组组合(UC)问题,不过没有考虑风电随机性对于电网UC的影响。文献[15,16]将ADP理论应用于含风电和储能装置的小型系统优化调度。文献[17]将含有单一风电场和抽水蓄能电站的电力系统随机DED问题描述为随机型存储模型,以抽水蓄能电站水库的储水电量作为系统的存储水平,并采用ADP算法克服随机规划问题中目标函数含有数学期望计算的难题。然而,所提方法只适用于必须含有抽水蓄能电站的电网调度问题;且建立的模型中并没有考虑网络安全约束,获得的调度计划无法满足工程应用需求;另外,目标函数采用机组出力的一次函数,能否适应于DED问题通常采用的二次目标函数还有待进一步验证。
由于目前国内大部分省级电网中不含有抽水蓄能电站,对于不含有抽蓄电站的大型电网,如何应用ADP算法求解其随机DED问题,同时考虑网络安全约束的影响,对于扩大ADP算法在求解随机优化调度问题方面的适用范围,无疑具有重要的实用意义。因而,本文以系统中多个风电场出力的日前预测曲线为基础场景,借助拉丁超立方抽样生成风电场出力误差场景。以当前时段的系统正旋转备用容量作为资源存储量,列写了相邻时段关系的系统状态转移方程,从而建立了不含抽水蓄能电站电网的随机DED问题的随机型虚拟存储器模型(VSM)。在考虑网络安全约束的条件下利用误差场景对随机DED问题各个时段的值函数进行训练,利用训练得到的值函数对预测场景下的VSM进行求解,得到考虑风电出力随机性影响的常规机组日前发电出力计划。
1 随机型VSM描述
存储模型通过设置一个表示系统资源存储量的变量作为系统的状态变量,很好地解决动态规划问题状态的“维数灾”。由文献[17]可知,对于含有抽水蓄能电站的电网,可以方便地以抽水蓄能电站水库的储水电量作为系统的资源存储量,但对不含抽水蓄能电站的电网,在系统中难以找到可直接表示系统资源存储量的变量,因此如何选取系统的资源存储量,成为此类系统存储模型构建的难点和应用ADP算法求解该类系统随机DED问题的关键。
由于在一般电力系统中,系统的旋转备用容量反映了系统的可调控发电能力,相当于存储在系统中可用于平衡风电场出力随机波动和负荷需求变化的容量,由于存储模型只设置一个表示资源存储量的变量,故本文选取系统的正旋转备用容量作为系统的资源存储量,并根据相邻时段的系统正旋转备用容量的变化关系,列写出系统的状态转移方程,从而建立适用于一般电力系统随机DED问题的VSM,并采用ADP算法求解。
1.1 目标函数
优化目标取常规机组总发电燃料耗量最小,由于风电出力的随机性,目标函数应表示为风电的各种可能出力下对应的常规机组总发电燃料耗量的期望值最小,如式(1)所示。
式中:T为调度周期总的时段数,本文取T=96;ΔT为每个时段的持续时间,即15min;St为t时段系统所处状态;xt为决策变量向量;Ct(St,xt)为时段t所有NgNg台常规机组的燃料耗量,
1.2 约束条件
1)基本约束
式中:Ploadj,t为负荷节点j在时段t的功率预测值;Nd为负荷节点数;Pwk,t为风电场k在时段t的出力值,为随机变量;Pi-和P-i分别为机组i的有功出力上、下限;rdi和rui分别为机组i的向下、上爬坡率。
其中,第1个式子为功率平衡方程,第2个式子为常规机组的有功出力上、下限约束,第3个式子为常规机组的爬坡约束。
2)网络安全约束
式中:Fl,t为时段t第l条支路的传输功率;Flmin和Flmax分别为第l条支路传输功率的下限和上限,一般Flmin直接取Flmax的负值;Fij,t为第i个安全断面中第j条支路在时段t的传输功率;Ωi为第i个断面包含的支路集合;FΩimin和FΩimax分别为第i个断面的安全下限和上限。
其中,第1个式子为输电线路安全约束,第2个式子为断面安全约束。支路传输功率Fl,t可由直流潮流模型近似表示为:
式中:Gl,i,Dl,j,Wl,k分别为第i台常规机组、第j个负荷和第k个风电场对支路l的功率转移分布因子,其值由网络结构和支路参数确定[18]。
由于实际大电网支路数众多,若在模型中加入所有的支路安全约束,优化模型的规模会大幅度增加,进而导致求解速度的快速下降。本文采用“求解→安全校验→添加越限支路约束再求解”循环的方法,直至所有支路功率都通过安全校验,这样可加快求解速度,并得到满足所有支路安全约束的最优解[19]。
3)旋转备用约束
为应对风电出力的不确定性和负荷预测误差,系统中应保留一定的旋转备用容量以保证系统安全可靠运行。系统及各常规机组备用约束如下:
式中:sui,t和sdi,t分别为机组i在时段t能够提供的正旋转备用容量和负旋转备用容量;T10为要求的机组旋转备用响应时间,取10min;Su,t和Sd,t分别为系统在时段t的正、负旋转备用容量;Lu和Ld分别为负荷对系统正、负旋转备用的需求系数,通常设定为2%~5%;wu和wd分别为风电场出力对系统正、负旋转备用的需求系数,根据目前国内风电功率预测系统的预测误差范围,可设定为10%~25%;P-wk为风电场k的额定出力。
4)状态转移方程约束
通过将系统正旋转备用容量Su,t设置为系统在时段t的资源存储量,取系统时段t的状态向量为St=(Su,t,Pw,t),则系统的状态转移方程如下:
式中:Ps,t为时段t系统正旋转备用容量相对上一时段的变化量;Pw,t为时段t所有风电场出力组成的向量。Ps,t既与时段t风电场出力随机变量Pw,t有关,又与时段t常规机组出力决策变量xt有关。该方程的物理意义是系统状态在随机变量和决策变量共同作用下的演化形式,体现了相邻两个时段系统正旋转备用容量之间的耦合关系。
5)系统旋转备用变化量约束
每一时段系统正旋转备用容量相对上一时段的变化量有一定的范围限制,这个范围可由风电出力变化量与负荷变化量确定。当风电出力增加大于负荷增长时,系统正旋转备用变化量应满足:
当风电出力增加小于负荷增长时,系统正旋转备用变化量应满足:
2 ADP思想与模型处理
2.1 DP的局限性
基于Bellman的最优性原理,求解多阶段决策问题时,严格意义上DP可以求得全局最优解[20]。对初值问题DP的求解决策过程如图1所示。图中:Jt为时段t的收益;St=fs(St-1,xt)为时段t-1到时段t的状态转移方程。令xt*为时段t的最优决策,求解时先从最后时段开始往前逐一时段递推,依次得到各时段最优决策和值函数与状态关系xT*(ST),VT(ST),x*T-1(ST-1),VT-1(ST-1),…,x1*(S1),V1(S1)的表达式,其中,Vt为时段t的值函数,即从时段t到末时段T内所有阶段收益总和的最优值,然后代入初始状态S0并结合状态转移方程,从前往后逐一求得各时段的最优决策和值函数。
由DP的求解过程可以看出,应用DP求解DED问题,当机组出力连续时,由于爬坡率约束的存在,相邻时段之间的决策变量具有耦合,机组出力可行域也是随不同时段变化的,难以用解析表达式描述决策、收益与状态之间的关系;当机组出力离散时,可以对所有的机组出力组合情况进行评估,但随着机组数、时段数、状态变量数的增加,组合情况呈指数式增长,将面临“维数灾”问题。
2.2 ADP思想
由DP的决策过程可知,DP在求解DED问题时虽然能够求得全局最优解,但对于实际大型电网来说其推导过程过于繁琐,求解的复杂程度难以接受。近年来,Powell等人将ADP方法运用到具有随机性可再生能源接入的电力系统调度中,很好地克服了DP求解DED问题的局限性。
由2.1节可知,DP在决策前需从后往前逐一推导每一状态St对应的值函数Vt(St)的表达式,这是DP求解的关键和难点。如果假定各时段值函数的表达式Vt(St)已知,则在求解当前时段t时,只需在St-1的基础上结合状态转移方程St=fs(St-1,xt)和当前时段值函数Vt(St),即可求得当前时段t的最优决策xt*。但各时段值函数的精确表达式Vt(St)事先无法预知,这为模型的解耦求解带来困难,ADP的思想就是通过采用近似值函数来逼近描述时段t的值函数与状态St的关系,从而实现模型的时段解耦求解,进而可依次求得各时段的近似最优决策xt。由此可以看出,ADP算法的关键就是近似值函数的合理表示。
2.3 模型处理
为了方便应用ADP对随机DED问题的VSM进行求解,需对模型进行一些必要的处理。为此将每个时段假想成两个阶段,分别对应决策前状态(Su,t,Pw,t)和决策后状态(Sxu,t,Pw,t)[21],并定义S^u,t(Pw,t)为时段t观察到随机变量的实现值后状态的变化量。其中,决策前状态(Su,t,Pw,t)表示仅考虑随机变量引起的状态变化量S^u,t(Pw,t)的作用,而未做出决策前的系统状态;决策后状态(Sxu,t,Pw,t)表示做出最优决策后系统的状态。因此系统状态转移方程转化为:
式(9)表示假定时段t观察到的风电变化量直接作用于系统正旋转备用容量,由Sxu,t-1增加演化为Su,t;式(10)表示做出决策得到常规机组出力值xt后,Su,t加上系统正旋转备用容量的实际变化量Ps,t(xt),并扣除没有实际作用效果的后,最终得到决策后系统正旋转备用容量Sxu,t。引入决策前状态和决策后状态后,可得时段t的决策前状态值函数Vt*(Su,t,Pw,t)和决策后状态值函数Vtx(Sxu,t,Pw,t)如下:
此处Πt为由式(2)至式(5)和式(7)、式(8)所确定的xt的可行域。
由式(9)可知,从时段t的决策后状态到时段t+1的决策前状态,仅考虑随机因素的作用,所以式(12)中含期望计算,这给求解带来不便。因此在应用ADP算法求解随机DED问题时,除了要解决近似值函数的合理描述问题,还要处理好系统中随机因素引起的期望计算。
根据文献[21]可知,对于资源分配问题,对于没有明显特性的值函数,可以通过查表与聚类、参数模型、非参数模型等一般工具获得近似值函数;而对于值函数相对资源存储量具有连续、线性或近似线性、非线性(凹性或凸性)性质的,可以采用接近其特性的函数对值函数进行近似。文献[22]给出了对于线性目标函数存储模型采用满足凸性的分段线性函数近似值函数的收敛证明,由于上述VSM的目标函数是二次函数,和线性函数一样具有凸函数特性,因而本文采用满足凸性的分段线性函数来逼近其决策后状态的值函数Vtx(Sxu,t,Pw,t)。因此,通过在决策后状态Sux,t的取值区间上取离散断点R=ρ,2ρ,…,mρ,令vt(Pw,t)=[vt(Pw,t,ρ),vt(Pw,t,2ρ),…,vt(Pw,t,mρ)]T为时段t值函数的斜率向量,其中,m为存储量的所有分段数,ρ为每段长度,则t时段决策后状态的近似值函数可表示如下:
式中:Vtb为时段t值函数的截距;ytr为第r段的存储量。
将式(13)代入式(11),则随机DED问题的VSM可转化为如下不含期望运算的确定性二次规划模型:
3 VSM的ADP求解
3.1 近似值函数的求取
应用ADP求解VSM时,近似值函数t(Sxu,t,Pw,t)对精确值函数Vtx(Sxu,t,Pw,t)的近似精度越高,则近似最优决策xt越接近xt*。为获得高质量的近似值函数,首先根据确定性优化模型求解结果对近似值函数的斜率向量和截距进行初始化,然后扫描误差场景,在每个场景下逐个时间段求解二次规划问题(式(14)),并根据求解结果采用逐次投影近似路径(SPAR)算法[16]修正每次迭代的近似斜率值vtn(Pw,t)和截距值Vntb,直到得到收敛的近似值函数tn(Sxu,t,Pw,t)。SPAR算法对近似值函数的求取过程如图2所示。图中,tn(Sxu,t,Pw,t)为第n次迭代所得近似值函数,Vtx(Sxu,t,Pw,t)为事先未知的精确值函数,和vtx分别为第n次迭代时段t值函数的斜率近似值和时段t值函数斜率的精确值。
斜率向量和截距初始化时,首先根据确定性优化模型的决策结果,获得各时段的资源存储水平Sux,,t0及相应时段的值函数值Vt0。斜率初值设定时以(Sux,,t0,Vt0)作为该时段值函数的极小值点,且其两边各段的斜率符号相反,与极小值点相邻的两段关键点的斜率初始值可根据优化目标的物理意义合理设定,本文主要根据常规机组的煤耗特性系数确定,其余段的斜率根据满足值函数凸性的斜率单调递增特性依次设定。在初始斜率向量给定后,初始截距V0tb根据式(15)确定。
式中:为时段t值函数的斜率初始值。
给定初始斜率向量和截距后,依次在每个场景下逐个时段求解二次规划模型(式(14)),再进行斜率和截距修正,斜率修正过程参见文献[17],得到第n个场景迭代的近似斜率分量和近似值函数值tn(·,Pnw,t)后,根据式(16)计算截距修正值Vntb为:
实际计算中,可只对图2所示关键区域的两段斜率进行修正,再结合截距修正,以节省值函数训练时间,提高计算速度。
3.2 ADP求解过程
ADP求解随机DED问题VSM的步骤如下。
步骤1:求解预测场景对应的确定性经济调度模型,得到各时段决策xt0、存储量和值函数值Vt0。
步骤2:初始化各时段的近似斜率向量,根据初始斜率值和来确定初始截距V0tb。
步骤3:借助拉丁超立方抽样生成基于预测场景P0w,1,P0w,2,…,P0w,T的误差场景样本,获得N个误差场景Pnw,1,Pnw,2,…,Pnw,T(n=1,2,…,N)[23];令n=1,t=1。
步骤4:若n>N则转步骤11,否则继续。
步骤5:若t>T则转步骤9;若t=1,则令的上限和下限设置为;否则计算决策前的资源存储量
步骤6:求解式(14)的二次规划模型,得到最优决策xtn,并计算得到决策后的资源存储量
步骤7:若t<T,则进行斜率和截距修正。
步骤8:t增加1,转步骤5。
步骤9:对场景n的求解结果进行网络安全校验,若存在支路越限,则将越限支路的安全约束加到式(14)所示模型,令t=1,转步骤5;若不存在支路越限,则转步骤10。
步骤10:n增加1,转步骤4。
步骤11:求解预测场景的VSM,获得调度计划。
4 算例分析
为验证本文所建立的随机DED问题的VSM和ADP求解算法的有效性,对某个不含抽水蓄能电站省级电网的发电调度进行建模和求解。以该省网2015年1月5号的数据为例,共有85台常规机组,其中火电机组46台,装机容量为14 560 MW;水电机组39台,装机容量为8 208 MW。风电场5座,额定容量分别为3 958.5,1 140,192,99,49.6 MW,其并网站点见附录A图A1,其中前两个风电场的出力预测曲线,以及系统日前负荷预测曲线和外送功率曲线见附录A图A2和图A3。系统共有线路498条,3个安全断面,各断面数据见附录A表A1。
假定风电出力预测误差服从正态分布,数学期望为各时刻的风电出力预测值,标准差为预测值的20%,借助拉丁超立方抽样方法分别生成20,50,100,200个误差场景进行求解。以20个场景的求解为例,训练过程中值函数变化如图3所示。可以看出,训练刚开始时误差场景的值函数与由确定性模型优化结果反推的值函数非常接近,随着训练的进行,后面误差场景求解得到的值函数慢慢趋向收敛,整个训练过程耗时198.39s。
本文构建的随机VSM和ADP算法求解结果与场景法求解结果的值函数对比见附录A图A4。采用本文模型和ADP算法求得的一天总发电燃料耗量为7.572 027万t,场景法求得的总发电燃料耗量为7.487 056万t,且由附录A图A4中各时段的值函数比较可以看出,ADP算法与场景法求得的燃料耗量结果十分接近。以上比较充分说明了本文建立的不含抽水蓄能电站的随机DED问题的VSM及ADP算法求解的正确有效性。
ADP算法求得的系统正旋转备用与场景法优化结果比较如图4所示。可以看出,两种方法得到的系统正旋转备用的整体变化趋势也基本一致,只是ADP算法得到的系统正旋转备用整体上比场景法略微大一些。
两种方法得到的机组出力计划比较如图5和图6所示。由图5可以看出,两种方法得到的火电机组的出力计划基本一致,部分机组在某些时段出力存在微小偏差。由图6可以看出,场景法得到的水电机组出力存在很大的跳跃,而ADP算法得到的水电机组出力则变化比较缓慢,这是由于水电机组功率调节速度快,每个时段可调节功率范围较大,因此场景法求解时在满足各种约束的条件下为了优化目标函数而使得机组出力会有较大的波动跳跃,这与水电机组自身的调节特性相吻合,而在采用VSM和ADP算法求解时由于式(6)至式(8)的约束,限制了系统正旋转备用的变化,使得备用响应容量较大的水电机组的出力变化也较为缓慢,这更符合实际电网运行调度中对机组出力的调控要求。
同时,由于模型中添加了断面安全约束,能够保证所获得调度方案下系统的安全运行。以20个误差场景的优化为例,与不含断面安全约束求解结果对应的安全断面2的输电功率对比如表1所示。可以看到,在未加断面约束时优化得到的总燃料耗量为75 706.61t,但断面2在某些时段存在功率越限;加入断面约束后,总燃料耗量为75 720.27t,比不加断面约束时增加了13.66t,但断面2功率都小于安全极限。因此,在模型中加入网络安全约束后,为了使系统的关键线路和断面的输送功率在限定范围内,机组的出力安排可能会使得系统总的燃料耗量有所增加,这在一定程度上使得系统的经济效益有所下降,但却避免了系统运行在不安全状态,对系统的安全可靠运行具有重要意义。
接下来分别将该算法与场景法在20,50,100,200个场景的情况下进行比较,验证该算法的计算性能。使用计算机为Intel(R)Core(TM)i7-4900MQ CPU 2.80GHz/32GB内存,计算结果如表2所示。由表2可见,场景法在场景数较少时具有较快的计算速度,但随着场景数的增加,计算所需内存和时间都大幅增长,这在很大程度上限制了场景法的应用,尤其是对于风电场数目多需要抽样很多个场景来准确模拟风电出力特性的大型电网调度问题,场景法求解将会受到计算机内存容量限制。而ADP算法由于实现了对各个场景和各个时段的解耦求解,将大规模优化问题分解成若干个小规模优化问题逐个求解,所以随着场景数的增加,所需内存无明显增长,求解时间也基本只增加了新增加场景进行值函数训练所增加的时间。对于100个场景求解时间只有16min左右,约为场景法的1/12;即使对于200个场景求解时间也只有33min左右,计算速度明显提高。
同时,将所提出算法与基于极限场景集的鲁棒优化调度(RS)方法比较[24]。为保证极限场景能覆盖95%的可能风电出力,取风电功率的变化范围为[μ-2σ,μ+2σ],其中,μ为期望值,σ为标准差值,由于系统中含有5个风电场,故共有25即32个极限场景,RS方法求解总耗时6 378.83s,优化结果的总燃料耗量为75 654.04t。
由此可以看出,虽然RS方法比场景法更能保证对风电出力大范围波动的适应性,但其目标函数值也更大,且在极限场景只有32个的情况下,其求解时间已经分别达到50个场景下场景法和ADP算法的3.3倍和12.9倍,当系统中风电场数目增大时,其求解时间将增加得更为明显。因此,ADP算法与RS方法比较同样能够大幅提高计算速度。
另外,由于极限场景的数目与风电场数目呈指数关系增长,随着风电场数目的增大,RS方法和场景法一样会面临由于问题规模过大超出计算机内存容量限制进而无法求解的问题。因此,ADP算法对于含多个风电场的大型电网随机优化调度问题具有更好的适应性,在求解速度上相对RS方法及场景法具有明显的优势,能够很好地满足应用于实际大型电网日前发电调度的要求。
5 结语
本文将ADP理论推广应用于不含抽水蓄能电站的电网随机DED问题,以正旋转备用容量为存储量,建立不含抽水蓄能电站的电网安全约束随机DED问题的VSM,并通过与场景法和鲁棒优化调度方法求解结果的比较分析验证了所建模型和求解算法的正确有效性,为ADP理论应用于快速求解一般大型电网的随机DED问题提供了新途径。ADP算法实现了对随机优化调度模型各个场景和各个时段的解耦求解,将一个大规模优化问题分解为一系列小规模优化问题,有效提高了对大电网随机优化调度模型的求解速度。采用ADP算法求解随机型VSM的优化结果中对应的水电机组出力变化比场景法更加合理,符合实际电网运行调度中对机组出力的调控要求。另外,对于含有抽水蓄能电站的电网调度问题,也可以采用本文提出的VSM建模方法并通过ADP算法快速求解;即便是对于含有多个抽水蓄能电站的电网调度问题,文献[17]的建模方法由于只适用于含单一抽水蓄能电站的电网,会存在建模困难,而本文的VSM建模方法同样能够适用。
本文研究中采用分段线性函数对值函数进行近似,所得调度方案对应的目标函数值比场景法的结果有所增大,如何提高值函数的近似精度,以获得更优的调度方案是本文下一步工作重点;同时,本文建立模型中未考虑不同时段机组启停状态的变化,如何应用ADP算法求解随机机组组合问题是本文的进一步研究方向。
附录见本刊网络版(http://www.aeps-info.com/aeps/ch/index.aspx)。
摘要：针对大电网安全约束随机动态经济调度(DED)问题的求解时间太长,提出了应用近似动态规划算法快速求解不含抽水蓄能电站电网的安全约束随机DED问题的方法。建立了随机DED问题的虚拟存储器模型,以系统的正旋转备用容量作为存储变量,构建系统相邻时段的状态转移方程,并考虑了各输电线路和断面的安全约束。以风电场日前功率预测曲线为基础,通过拉丁超立方抽样产生风电场出力的误差场景,并逐一场景递推求解每个时段的二次规划模型以对各个时段的值函数进行训练,形成收敛的值函数,再代入预测场景求解以获得最终的优化调度方案。该方法实现了对随机DED模型各个场景和各个时段的解耦求解,将一个大规模优化问题分解为一系列的小规模优化问题,有效提高了对大电网随机DED模型的求解速度。以某一实际省级电网为算例,通过与场景法和鲁棒优化调度方法的比较验证了所提出模型和求解方法的正确有效性。