随机机会约束规划

2024-08-05

随机机会约束规划（精选7篇）

随机机会约束规划第1篇

对传统运输问题的描述是:A1,A2,…,Am为某种产品的产地,其产量分别为a1,a2,…,am;B1,B2,…, Bn为销售地,其销量分别为b1,b2,…,bn,Cij为单位产品由产地Ai运往销售地Bj的运输成本,其目标是使运输所有产品的总费用最小。

设xij为决策变量,表示从产地运往销地的产品数量,则目标函数可表示为

在传统运输问题中,供应和需求都是确定的, 但在实际运输过程中,存在许多不确定性,比如运输成本、生产地的供应量、销售地的需求量以及企业自身的财务状况和物资应急储备等,这些都使得决策者所要考虑的目标不再是简单而单一的,这些不确定参数和多个目标已形成了不确定性环境中的多目标运输模型。

对于上述的不确定性环境中的多目标运输模型,它的需求不总是确定的,而是一个随机变量,这就使得约束条件不再是线性约束,而变成了一种含有随机变量的约束。此时,传统运输问题的规划模型已经不适用于规划中含有变量的情况,我们需要运用随机规划模型的理论来求解。

1随机机会的约束规划描述

随机机会约束规划主要是针对约束条件中含有随机变量的情况,在这种情况下,当观测到随机变量实现以前,就必须做出决策,它的一般表示形式为

式中:x为决策变量;ξ为随机变量;pr为事件p发生的概率;α,β为置信水平;f为在置信水平至少为 α,β时,目标函数所取得的最大(最小)值。

2随机机会约束规划模型的建立

在传统的运输问题中,供应和需求都是确定的,但在实际中,由于运输过程的复杂性,需求往往是随机的,根据上述的随机机会约束规划模型,建立如下的需求随机运输问题机会约束规划模型

其中,对各变量的定义如下:

1)pr为目标r相对于目标r+1的重要性,即对所有的r,都有PrPr+1;

2)ulr为对应优先因子r第l个目标正偏差的权重因子;

3)vlr为对应优先因子r第l个目标负偏差的权重因子;

4)dl+为目标l偏离目标值的正偏差;dl为目标l偏离目标值的负偏差;

5)fl为目标约束中的函数,为运费、时间、利润等的函数;

6)ξ为单位产品由i地运往j地的系数矩阵;

7)cl为预先给定的目标值;

8)p为优先级的个数;L为目标约束的个数;m为供应地的个数;n为需求地的个数;

9)α1i,α2i,α3i为在各个条件约束,如资源、销售、运输能力等情况下的置信水平;

10)βl为给定目标函数的置信水平。

与运输问题的确定性规划不同的是,机会约束规划模型存在机会约束。一般情况下,将机会约束规划转化为与其等价的等式形式求解。但是对于一些较复杂的问题,就需要借助遗传算法来求解。

3随机机会约束的求解算法

对于那些复杂的机会约束规划模型,我们首先采用随机模拟的方法得到目标约束值,然后结合遗传算法和神经网络产生混合智能算法,来搜寻最优解和近似最优解。下面首先介绍几个相关定理和概念:

定理1:设随机向量ε退化为分布函数,为φ的随机变量ε ,函数g(x,ε)形如g(x,ε)=h(x)-ε 这样的形式,那么pr{g(x,ε)≤0}≥α,当且仅当h(x)≤ka,其中,ka=sup{K/K =φ-1(1-α)}。

命题:若约束条件以置信度 αj成立,即则运用定理1可转化为的形式。

定理2:设随机向量,ε = (a1,a2,a3,,…,b),g(x,ε)=a1x1+a2x2+ … +anxn-b,若随机变量ai和b相互独立,且都服从正态分布,则pr{g(x,ε)≤ 0}≥ α,当且仅当其中的φ是标准正态分布函数。

3.1目标约束的随机模拟

寻找d+和d-的最小非负值,使它满足目标约束pr{d-≥b-f(x,ξ)}≥β,pr{d+≥f(x,ξ)-b}≥ β,其中ξ为随机参数。

Step1:令N′为βN的整数部分,其中N′是αN的整数部分;

Step2:从随机变量的概率分布中随机抽取N个独立的随机向量ξi,i= 1,2,3,…,N ,得到一系列的数值 {f1(x,ξ1),f2(x,ξ2),…,fN(x,ξn)},作为样本值;

Step3:由step2可以得到fi=b-f(x,ξi)和fi+=f(x,ξi)-b,i=1,2,…,N ;

Step4:由大数定律可知,在序列 {fi}iN-1和 {fi+}iN-1中第N个最小数可分别作为负偏差d-和正偏差d+的估计值,并且d+>0,d->0;若d+<0, d-<0,则跳到step5;

Step5:若d+<0,d-<0,则置d+=0,d-=0。

3.2混合智能算法

Step1:随机模拟不确定函数并生成训练的输入和输出数据;其中不确定函数为

Step2:根据step1中生成的训练数据,训练一个神经网络去近似上述的不确定函数;

Step3:染色体数目初始化,并通过神经网络检测染色体的可行性;

Step4:运用交叉和变异来更新染色体,同时通过神经网络来检测子代染色体的可行性;

Step5:运用神经网络计算所有染色体的目标函数值;

Step6:根据目标值,使用基于序列的评价函数计算每个染色体的适应度;

Step7:通过轮盘赌选择染色体;

Step8:重复step3到step7,直至完成给定的循环次数;

Step9:输出最好的染色体作为目标函数的最优解。

4算例

下面给出有两个供应点,两个需求点,两种运输方式的算例。每个点之间不同运输方式的利润、费用、时间和约束矩阵如表1~表4所示。

在随机条件下,建立多目标运输问题的规划模型,用pijk表示通过第k种运输方式将产品从i地运往j地所获得的利润,cijk表示费用,tijk表示消耗的时间,其中i=1,2,…;j=1,2,…,pijk,cijk,tijk,都为随机变量,则得到利润矩阵p = (pijk)m×n×k,费用矩阵c= (cijk)m×n×k,时间矩阵T = (tijk)m×n×k,故得到总利润为费用为消耗的总时间

在机会约束规划模型中,各置信水平均取0.8, 各个目标的目标值以及优先结构如下所示:

优先级1:pr{-f1(x,p)+1 100≤d-1}≥0.8;

优先级2:pr{f2(x,c)-1 700≤d+2}≥0.8;

优先级3:pr{f3(x,T)-1 300≤d3+}≥0.8.

运用上述的混合智能算法对该模型进行求解, 参数设为:种群规模为30,变异概率为0.2,交叉概率为0.4,评价函数中的参数为0.05,经过100次迭代后,求得的最优解满足上述三个目标。

5结论

本文针对运输问题在随机条件下的不确定因素,运用随机机会约束规划的理论方法,建立了在需求随机条件下的机会约束规划模型,采用随机模拟对目标函数进行处理,然后把神经网络和遗传算法结合起来,设计了混合智能算法来求解,最后通过一个算例,显示了该模型更贴合实际。将本文所述的随机仿真、神经网络及遗传算法相结合的混合智能算法应用于随机期望值模型,随机相关机会规划其他两类随机规划中。

摘要：在传统运输问题的研究中,供应和需要都是确定的,然而在实际中,运输过程中的各个环节相当复杂,物资供应量和市场需要都具有不确定性。针对这种不确定因素,运用随机机会约束规划的理论方法,建立在随机环境中运输问题的机会约束规划模型,结合神经网络和遗传算法,设计适用于此条件的混合智能算法来求解。通过实例的计算和分析,显示该模型不论在计算随机运输问题的过程中,还是其结果的准确性上均具有较强的实践意义。

随机机会约束规划第2篇

关键词：水库调度,机会约束,随机多目标,不确定模拟,混合智能算法

0 引言

梯级水电站水库群一般是兼顾多个目标的大型水利枢纽系统,通常具有防洪、发电、航运、供水及灌溉等多种功能,上下游水库间往往具有复杂的水力、电力联系,同时梯级水电站水库群在调度的过程中,各部门在年内部分时段不同目标之间存在着一定程度的用水矛盾,如具有结合库容的水库在汛期防洪与发电争夺库容利用的矛盾、枯水期上游供水与发电的矛盾等等。因此水电站水库群联合调度是一个具有复杂约束条件的多目标优化调度决策问题。传统的水电站水库群调度往往仅考虑单一调度目标,忽略了流域梯级上下游电站群以及多个调度目标间的统筹协调关系,造成上下游电站调度运行不匹配、流域梯级水电枢纽综合效益难以充分发挥等问题。另外,水库在进行实际调度的过程当中,受到水文、水力等众多不确定性因素的影响[1],其中以入库径流的不确定性影响最大,目前的许多研究把入库径流当作确定性径流处理[2,3,4,5],忽略了不确定性给水库实际调度带来的风险,难以描述水库的实际运行情况,无法量化水库调度风险与效益之间的关系,给决策者进行调度决策带来一定的困难。机会约束规划主要是针对约束条件中含有随机变量,且须在观测到随机变量实现之前做出决策的问题。本文分析入库径流的不确定性给水库调度带来的影响,结合对入库径流的随机模拟,建立基于机会约束的梯级水库调度随机多目标决策模型。

在处理多目标问题时,目前已有多种优化方法应用到多目标模型求解中,如线性规划[6]、非线性规划[7]、网络流[8]、群体智能算法[9,10,11]等。利用线性规划法建立的优化模型难以反映水库调度过程中的强非线性因素;非线性规划法计算量相对较大,求解大规模优化问题时存在收敛特性不稳定的缺点;动态规划法易陷入“维数灾”。群体智能算法对优化模型无连续性、光滑性及其凸性要求,从理论上可全局收敛到优化问题的全局最优解,因此成为研究热点,并显示出其独特的优越性。本文针对所建模型的多目标性及约束条件的复杂性,给出了混合智能算法的求解方法,并以三峡和葛洲坝梯级水库为例,通过对模型的求解,获得梯级水库调度的最佳妥协解,为不确定环境下的水库多目标优化调度提供技术支持。

1 模型建立

机会约束规划是随机规划的一种,规划允许所作决策在一定程度上不满足约束条件,但该决策应使约束条件成立的概率不小于决策者事先给定的某一置信水平α[12],即违反约束条件的概率小于1-α。

梯级水电站水库群进行调度过程中,不同部门涉及到不同的用水目标,如防洪目标、发电目标、航运目标、供水目标等。本文主要研究水库的防洪、发电和航运等几类目标。水库在汛期,对于有防洪要求的水库,主要考虑大坝和下游的防洪安全,一般以水库坝前水位最低和下泄流量最小为目标。在调度的过程中,水库水位和下泄流量受到入库流量不确定性的影响,防洪目标以随机机会约束的方式进行处理;在整个调度期内,针对梯级水电站水库群发电优化调度,以可能实现的总的发电效益最大为目标,以平均年发电量最大来表征,模型中允许在一定置信水平的前提下存在风险;对于有航运要求的水库,以航运效益最大为目标,以通航保证率来表征,模型中允许在一定置信水平的前提下存在风险。综上分析,构建基于机会约束的水库调度随机多目标决策模型如下。

优化目标:

约束条件:

式中:为梯级电站水库群联合调度的目标利润,其中式(2)和式(3)分别为梯级电站水库群联合调度发电效益(发电量)的计算公式和航运效益(通航保证率)的计算公式;Ni,t为t时段电站i的出力;N为电站数;T为调度期总时段数;m为模拟计算的年数;△t为时段长度;Ki为电站i的出力系数;qi,t为t时段电站i的发电流量,Hi,t为t时段电站i的平均发电水头。St(zt,qt)为时段t的通航情况,是一个0-1变量,与水位和下泄流量有关,zt、qt分别为t时段的水位和下泄流量,时段满足通航要求取值为1,否则取值为0;式(4)和式(5)为目标的机会约束条件,其中α1、α2分别为发电和航运目标约束的置信水平。

式(6)为水库蓄水量的机会约束条件,将水库的蓄水量视为不确定变量,Vimin为电站i的死库容;Vimax为电站i正常蓄水位对应的库容,汛期时则是防洪限制水位所对应的库容;β1为水库蓄水量约束的置信水平;式(7)为水库下泄流量的机会约束条件,将水库的下泄流量视为不确定变量,式中qi,tmin,qi,tmax分别为t时段电站i的最小下泄流量和下游允许最大下泄流量,β2为水库下泄流量约束的置信水平;式(8)为水库水量平衡约束,Vi,t、Vi,t+1为t时段电站i初、末水库蓄水量;Qi,t、qi,t、qlossi,t为t时段电站i入库流量、出库流量及扣损流量(对应蒸发、渗漏等水量损失);式(9)为水电站预想出力约束,Ni,t、Nimin和Ni,预分别为t时段电站i的实际出力、最低出力限制及预想出力;式(10)为水库之间的水量平衡约束,Qi+1,t为t时段下游电站的入库流量,qi,t为t时段上游电站的下泄流量,Qini+1,t为t时段下游电站的区间入流。

2 模型求解

2.1 入库径流的随机模拟

梯级水电站水库群进行调度过程中,受到众多不确定因素的影响,尤以入库径流的不确定性影响最大。水电站的入库径流具有多变性与不确定性的特点,是一种连续随机过程。入库径流的不确定性分析对梯级电站水库群的多目标调度决策方案的确定具有重要意义。本文采用考虑相邻时段影响的正态分布对梯级电站水库群的入库径流量进行随机模拟,概率分布密度函数可表示为

式中:Qi,t为水库i在时段t的入库流量;t|t-1、t,t-1分别为计及前一时段入库流量Qi,t-1影响后Qi,t的条件期望值和方差。

由历史数据可得相关的分布参数,具体计算公式为

式中:t、t分别为入库流量Qi,t的期望值和方差;t-1、t-1分别为入库流量Qi,t-1的期望值和方差;t为入库流量Qi,t、Qi,t-1的相关系数;T为时段数。

2.2 对多目标问题的处理

对于许多实际多目标规划问题,有效解集可能很大,复杂程度随着目标数量的增加而大致呈指数上升趋势,从一大群有效解中选出最好的一个也较困难。妥协方法是一种基于偏好的方法,该方法寻找的是根据某种距离度量方式来确定的与理想点最近的解作为多目标问题的最佳妥协解。妥协方法不直接探讨怎样权衡最理想,而是描述如何选择最不后悔,它的数学描述是后悔函数。

采用LP范数的距离函数作为后悔评价函数,其中q为目标个数,模型中q=2,p为范数参数,p≥1,zj为第j个目标的取值,模型中目标值的表达式如式(2)和式(3),zj*为理想点的值,在用遗传算法对问题进行求解时,理想点的值取当前代中的最大值。多目标问题中不同目标函数的优化结果由于量纲、数量级之间的不同,需要先对各目标的后悔值进行归一化,使它们在区间[0,1]取值,归一化后的后悔函数表达式为

其中:zmax表示最大值;zmin表示最小值。妥协方法是根据后悔函数求解妥协解的方法,定义最佳妥协解为后悔函数最小的一个,即min r(z,p),其他约束条件不变。

2.3 混合智能算法求解

对于所建的基于机会约束的随机多目标决策模型,传统方法难以求解,因此本文设计了基于妥协方法、不确定模拟技术和遗传算法的混合智能算法进行求解。混合智能算法的具体求解步骤如下。

1)输入系统数据及遗传算法要求的种群规模、交叉概率、变异概率等。

2)遗传编码。遗传算法采用实数编码,以水库时段末水位值作为优化变量,即以各水库各时段末水位实数值为“基因”,以整个调度期各水库各时段末水位系列为“染色体”。

3)种群初始化。初始化N个染色体,并采用不确定模拟技术检验染色体是否满足机会约束(即对任一染色体,生成N个随机向量,若有n(0≤n≤N)个随机向量使得约束条件满足,且n/N大于等于给定的机会约束置信水平,则表示染色体满足机会约束),满足模型所有的约束条件,则接受其为可行染色体。

4)对染色体进行交叉和变异操作,并同样采用不确定模拟技术计算后代染色体的可行性。

5)采用不确定模拟技术计算所有染色体的目标值(对任一染色体,生成N个随机向量,针对每一个随机向量计算其目标值;然后将这N个目标值由小到大进行排序,得到序列{f1,f2,…,fN}。取N′为aiN(i(28)1,2)的整数部分。由大数定律,序列{f1,f2,…,fN}中第N’个最大的元素可以作为染色体目标值的估算)。

6)根据目标值使用基于后悔函数的评价函数式(17)计算各个染色体的适应度。

7)通过旋转赌轮的方法选择染色体。

8)重复步骤4)至步骤7)直到完成给定的循环次数,给出最好的染色体作为决策者的最佳妥协解。

3 实例研究

三峡和葛洲坝是长江中上游干流的两座大型水库。三峡工程是治理开发长江的关键性工程,规模巨大、举世瞩目,三峡大坝为千年一遇设计,万年一遇校核,工程承担防洪、发电、航运和枯水期向下游补水等综合利用任务,其综合利用效益显著。葛洲坝水库距上游的三峡水库38 km,是一座径流式水电站,是长江干流上修建的第一座大型水电工程,是三峡工程的反调节和航运梯级。三峡、葛洲坝在汛期共同承担下游地区的防洪任务,本文主要考虑大坝和下游的安全,在模型中以机会约束的形式控制库容和下泄流量;梯级发电要求以整个调度期内的发电量最大为目标;航运要求在枯水期尽量保持高库水位(采用坝前水位达到150 m的时间)。增加坝下游枯水期下泄流量,使枯水期航深提高(采用下泄流量不小于5 000 m3/s控制)。水库参数如表1所示。

假定各电站各时段入库流量都符合相邻时段相互影响的正态分布的随机变量。以日为计算时段长,假定三峡和葛洲坝水库各时段的入库流量预测方差为50。混合智能算法求解中,种群规模为50、交叉概率pc=0.8,变异概率pm=0.025,最大迭代次数2 000,后悔评价函数中p=1。

令梯级电站目标利润的置信水平α1,α2及库容和下泄流量约束的置信水平β1,β2变化,其他参数不变,采用混合智能算法进行求解,可以得到不同置信水平下的调度方案,如表2所示。

由表2可以看出,当β1,β2一定时,随着目标达到机会α1,α2的逐渐增大,发电和航运的两个目标值逐渐减小(方案1、2、3、4、8)。可见多目标问题的优化结果越好,实现该结果的机会就越低。对于决策者来说,可以从计算结果判断出发电计划和航运计划可能获得的效益和实现该计划的机会。实际上,置信水平反映了调度人员对梯级水库运行可靠性的重视程度,给定的置信水平越高,说明对系统的可靠性越重视,对运行风险越厌恶,但同时系统运行的经济性也就越差。因此,在给定置信水平时需要统筹考虑系统运行的可靠性和经济性。当发电和航运的目标约束固定在0.8时,随着β1,β2的减小(方案4、5、6、7),发电目标值逐渐增大,从变化过程可以看出,三峡梯级水库防洪与发电之间矛盾突出,而发电与航运之间并没有明显的矛盾。

在固定的置信水平下,令α1=α2=0.8,β1=β2=0.9。假定龙头水库入库径流的预测方差发生变化,得到入库径流预测方差变化条件下的计算结果,如表3所示。

由表3可以看出,在给定的置信水平下,随着入库径流预测精度的降低(预测入库径流的方差增大),发电和航运的两个目标值逐渐减小,目标值的变化反映了入库径流不确定性的影响,入库径流不确定性越强,对调度的影响越大。因此在对不确定性因素合理预测的基础上,本文所建模型能事先对梯级水电站的风险和效益进行比较分析,利于决策者进行权衡并做出较满意的调度决策。

4 结论

由于梯级水电站水库群联合调度是一个具有复杂约束条件的多目标优化调度决策问题,并且在调度过程当中受到众多不确定性因素的影响。本文主要针对不确定性条件下水电站水库群的调度优化决策进行探索研究,所建立的随机多目标模型受输入条件的不确定性和各目标间的复杂关系影响,一般优化算法难以求解,这里采用耦合不确定模拟技术、妥协算法及遗传算法的联合求解方法对模型进行求解得到了预期效果,与现有方法相比,所提出的模型能够根据系统所面临的不确定性因素的范围与影响程度,为调度人员做出调度决策提供必要的方案和信息。但由于所针对的研究对象不同和问题的复杂性,所建模型的适用范围和求解效率还有待进一步提高。

参考文献

[1]王丽萍,张验科,纪昌明,等.基于概率最优化方法的水库发电调度风险分析[J].电力系统保护与控制,2011,39(16):1-6,12.WANG Li-ping,ZHANG Yan-ke,JI Chang-ming,et al.Risk analysis of reservoir generation dispatching based on probability optimization method[J].Power System Protection and Control,2011,39(16):1-6,12.

[2]裴哲义,伍永刚,纪昌明,等.跨区域水电站群优化调度初步研究[J].电力系统自动化,2010,34(24):23-26.PEI Zhe-yi,WU Yong-gang,JI Chang-ming,et al.Preliminary study on optimal dispatch of cross-regional hydropower station group[J].Automation of Electric Power Systems,2010,34(24):23-26.

[3]曾勇红,姜铁兵,张勇传.三峡梯级水电站蓄能最大长期优化调度模型及分解算法[J].电网技术,2004,28(10):5-8.ZENG Yong-hong,JIANG Tie-bing,ZHANG Yong-chuan.A long-term scheduling model for stored energy maximization of three gorges cascade hydroelectric stations and its decomposition algorithm[J].Power System Technology,2004,28(10):5-8.

[4]陈立华,梅亚东,董雅洁,等.改进遗传算法及其在水库群优化调度中的应用[J].水利学报,2008,39(5):550-556.CHEN Li-hua,MEI Ya-dong,DONG Ya-jie,et al.Improved genetic algorithm and its application in optimal dispatch of cascade reservoirs[J].Journal of Hydraulic Engineering,2008,39(5):550-556.

[5]纪昌明,刘方,喻杉,等.基于鲶鱼效应粒子群算法的梯级水库群优化调度[J].电力系统保护与控制,2011,39(19):63-68.JI Chang-ming,LIU Fang,YU Shan,et al.The optimal operation of cascade reservoirs based on catfish effect particle swarm optimization algorithm[J].Power System Protection and Control,2011,39(19):63-68.

[6]Khodr H M,Gómez J F,Barnique L,et al.A linear programming methodology for the optimization of electric power generation schemes[J].IEEE Trans on Power Systems,2002,17(3):864-869.

[7]Wei H,Sasaki H,Kubokawa J,et al.Large scale hydrothermal optimal power flow problems based on interior point nonlinear Programming[J].IEEE Trans on Power Systems,2000,15(1):396-403.

[8]Oliveira G G,Soares S.A second-order network flow algorithm for hydrothermal scheduling[J].IEEE Trans on Power Systems,1995,10(3):1635-1641.

[9]喻洁,季晓明,夏安邦.基于节能环保的水火电多目标调度策略[J].电力系统保护与控制,2009,37(1):24-27.YU Jie,JI Xiao-ming,XIA An-bang.Multi-objective Hydro-thermal dispatch based on energy conservation and environmental protection[J].Power System Protection and Control,2009,37(1):24-27.

[10]芮钧,梁伟,陈守伦,等.基于变尺度混沌算法的混联水电站水库群优化调度[J].水力发电学报,2010,29(1):66-68.RUI Jun,LIANG Wei,CHEN Shou-lun,et al.Optimal operation for a large-scale hydropower station system based on mutative scale chaos optimization algorithm[J].Journal of Hydroelectric Engineering,2010,29(1):66-68.

[11]叶碎高,温进化,王士武.多目标免疫遗传算法在梯级水库优化调度中的应用研究[J].南水北调与水利科技,2011,9(1):64-67.YE Sui-gao,WEN Jin-hua,WANG Shi-wu.Application of the multi-objective immune genetic algorithm in the operation of cascade reservoirs[J].South-to-North Water Diversion and Water Science&Technology,2011,9(1):64-67.

随机机会约束规划第3篇

电力系统发生大停电之后, 通常根据系统在恢复过程中不同时期的特点, 将恢复过程分为3个阶段:黑启动阶段、网架重构阶段和负荷恢复阶段[1,2,3]。网架重构阶段的主要任务是选择合适的厂站与线路组合以及相应的投运顺序, 尽快为重要的厂站送电并逐步建立起一个稳定的网架结构, 为下一阶段全面恢复负荷打下坚实基础。

目前国内外学者在网架重构这一课题已进行了大量研究, 图论、复杂网络理论以及多种智能优化算法都得到了广泛的应用, 主要的工作集中在两方面:目标网架的确定以及恢复到目标网架的具体恢复路径序列的确定。文献[4-8]的重构目标是找到综合性能最优或次优的若干骨架网络, 即确定目标网架。文献[9-14]则主要侧重于送电路径操作顺序的优化。在此基础上, 文献[15-18]将两者统一考虑, 在优化恢复路径序列的同时确定目标网架, 一定程度上避免了确定目标网架和优化恢复路径序列这两个网络重构环节脱离的问题。之前的研究大多将线路的操作时间作为确定数来处理, 但由于网架重构阶段所涉及的元件及操作众多, 对线路投运来说, 其操作时间具有不确定性。有学者认识到了这一点而将操作时间作为随机数处理[13], 但随机分布规律建立在大量的统计数据之上, 历史数据很可能由于数据量不足而产生偏差, 从而导致结果不准确。而结合历史数据及相关运行经验, 往往较容易确定其最可能的取值以及可能分布的范围, 操作时间的这种不确定情况更适合用模糊变量表示, 且可以用隶属函数很好地表示其模糊特性。因此, 将操作时间作为模糊变量处理更贴近理论实际。同样, 线路投运时的恢复可靠性也具有不确定性, 不同线路组合造成目标网架整体的恢复可靠性也不同, 基于系统安全性考虑, 往往希望形成的目标网架具有高可靠性, 而之前对这方面的研究较少。因此, 综合考虑线路投运时其操作时间与恢复可靠性的不确定性, 建立更为合理、准确的网架重构模型很有必要。

在上述背景下, 本文将线路操作时间与恢复可靠性假设为三角模糊变量, 运用模糊机会约束规划理论, 建立了求解网架重构优化的模糊机会约束模型。模型中考虑了机组的启动时限, 并用机会约束条件确保机组节点成功获得启动电源的可能性在一定的置信水平上, 在此基础上, 定义整个网架的恢复可靠性指标并以此建立目标函数来评价重构方案的优劣, 优化得到在尽可能短的重构时间内达到恢复可靠性最高的网架。此外, 根据网架重构的特点及要求, 提出了适用于本模型的基于模糊模拟的交叉粒子群优化求解方法, 即采用模糊模拟来处理模型中的约束条件与目标函数, 并用交叉粒子群优化算法为目标节点的恢复顺序进行寻优, 同时结合Dijkstra算法确定目标节点的恢复路径。

1 网架重构的优化模型

1.1 模糊机会约束规划

模糊机会约束规划是针对约束条件中含有模糊变量, 并且模糊约束条件成立的可能性不小于决策者给定的置信水平的一种规划方法。其一般形式如下:

式中:x为决策变量;ξ为模糊变量;gj (x, ξ) ≤0为模糊约束条件;p为约束条件的个数;f (x, ξ) 为包含决策变量和模糊变量的目标函数;α和β分别为决策者给定的对约束条件和目标函数的置信水平;为在给定的置信水平β下能实现的最优目标值;Pos{·}表示{·}中事件的可能性。模糊机会约束模型也可用可信性测度或必要性测度来表示[19]。

1.2 网架重构的模糊机会约束模型

1.2.1 模糊参数的确定

本文以三角模糊变量来表示线路的操作时间, 结合运行经验, 对于某条可恢复的线路, 其操作时间介于乐观估计值t1与悲观估计值t3之间, 而t2是其最可能的恢复操作时间, 操作时间的这种模糊性可用三角模糊变量表示, 其隶属函数如式 (2) 所示。文中涉及的其他参数的模糊性都可用类似的方法来描述和处理。

1.2.2 目标网架的恢复可靠性指标

在系统网架重构阶段, 对于每个待恢复节点, 认为其恢复路径上经过的节点完全可靠, 其恢复可靠性主要取决于恢复路径上所含线路的恢复可靠性, 且认为路径上每条线路的恢复可靠性相对独立。因此, 可将节点的恢复可靠性等效为由恢复路径组成的串联系统的可靠性, 即对待恢复的目标节点i, 设其恢复路径上第j条线路的恢复可靠性为, 则节点i的恢复可靠性为:

式中:Ni为节点i恢复路径上的线路数。

进而对于整个目标网架来说, 定义评价其恢复可靠性的指标为在系统重构时间内网架中各目标节点恢复可靠性的均值。具体定义式如下:

式中:N1为待恢复目标节点的个数。

1.2.3 模糊机会约束模型

当系统中的机组多为火电机组时, 合理地利用机组的启动时限, 在尽可能短的时间内恢复尽可能多的机组是提高系统重构速度的关键。机组启动时限与机组停机前的状态与停电时间有关系, 机组热态启动与冷态启动的界定本身就是模糊的, 属模糊量的范畴, 且用模糊变量和对应隶属函数能较好地表示其模糊特性。本文主要针对的是机组的热启动时限。

另外, 系统安全性也是系统恢复过程中需要考虑的重要因素。因此, 在追求快速性的同时, 还应兼顾系统的安全性要求, 使建立的目标网架具有较高的可靠性。

考虑以上因素并结合机会约束的特点, 本文以机组在其启动时限内成功获得启动电源为约束, 以在尽可能短的重构时间内网架恢复可靠性达到最高为目标, 建立了如下网架重构优化的模糊机会约束模型, 以期得到满足一定置信水平的网架重构方案。

式中:优化目标为最大化目标函数的值, 且目标函数值是目标函数在置信水平至少是β时取的最大值;为整个网架重构的时间, 即从网架重构开始到所有目标节点得到启动电源的时间, 本文假设在网架重构阶段每一步仅投入一条线路, 所以即组成恢复网架的各线路的模糊操作时间之和, 亦为三角模糊数;α为机组得到恢复的时刻不超过其启动时限所达到的置信水平;为机组节点g的恢复路径上第k条线路的模糊操作时间;为机组g的模糊启动时限, 亦设定为三角模糊数;Ng为待恢复机组节点g恢复路径上的线路数;NE为恢复网架包含的线路条数。

此外, 本文对由算法优化得到的恢复方案进行潮流校验, 只有通过潮流校验或各调节量在允许范围内的方案才视为可行。重构方案需满足的潮流约束如下:

式中:Pi和Qi分别为节点的有功、无功注入功率;δij为节点i, j间的相角差;Gij和Bij分别为节点导纳矩阵元素rij的实部和虚部;Pg和Qg分别为机组节点g的有功、无功出力;Ui和Uj分别为节点i和节点j的电压;NG为待恢复目标机组节点个数;NV为恢复网架中包含的节点个数;Pl m为线路m上流过的有功功率;上标min和max分别表示相应变量的最小和最大值。

2 网架重构的优化算法

本文采用模糊模拟来处理模糊机会约束模型中的目标函数和约束条件。同时, 根据网架重构自身的特点, 在已知恢复目标的基础上, 需要得到各节点的恢复顺序及相应的恢复路径。因此, 本文通过基于模糊模拟的交叉粒子群优化算法为待恢复目标节点优化恢复顺序, 同时采用经典的Dijkstra算法为待恢复节点确定恢复路径。

2.1 最短路径算法

在利用交叉粒子群优化算法为目标节点生成不同的恢复顺序时, 还需要根据网络的恢复情况和节点位置确定具体的恢复路径。同时, 采用模糊模拟处理目标函数和约束条件时, 待恢复节点的恢复路径须已确定。因此, 本文采用基于网络拓扑和线路权值的最短路径算法———Dijkstra算法来对路径进行寻优。算法的主要过程如下:设D[a]为从起点s到某一点a的距离, 首先从网络中选取具有最小D[a]的点a, 并把点a放在集合V中, 则集合V就是已计算出具有最短路径的点的集合。对所有经过点a而与起点s相通的点b, 设L (a, b) 为点a到点b的距离, 如果存在D[b]>D[a]+L (a, b) , 则将原路径值D[b]调整为D[a]+L (a, b) , 重复此过程直到所有的点全部放入集合V中。

由于本文将线路操作时间作模糊数处理且已在目标函数和机会约束条件中加以体现, 所以仅将每条线路的充电无功功率作为线路权值。当系统存在多回线时, 则取充电无功功率最小的线路。搜索时, 将黑启动电源或初期黑启动小系统作为每次搜索的起点。特别地, 为加速算法搜索过程, 在为一个目标节点搜索到恢复路径后, 将处在恢复路径上的线路的权值置为0。这样处理后, 不会影响恢复路径的选取。

2.2 模糊模拟

2.2.1 检验模糊系统约束

由于本文的机会约束条件针对的是机组节点, 所以在采用Dijkstra算法为每个待恢复目标节点寻找到恢复路径后, 仅对待恢复的机组节点进行模糊模拟检验。具体做法如下。

步骤1:从模糊变量的α水平截集中均匀地产生出清晰变量tgk′和Tg′。

步骤2:将清晰变量代入式 (5) 的机会约束条件式中, 若满足则认为此恢复路径可行。

步骤3:若不满足, 则重复步骤1和步骤2共N次, 其中N为模糊模拟的次数。

步骤4:若在N次模拟之后仍不能满足约束, 则认为机组节点在由该恢复顺序得到的恢复路径下不能在其启动时限内有效恢复。

步骤5:对于不可行的情况, 将代表节点恢复顺序的粒子进行变异修改, 具体做法是将没有通过检验的机组节点在粒子中的位置由原位置换到第1位, 即优先恢复, 位于该节点之前的节点则依次后退一位。

步骤6:将进行变异后的粒子重新采用Dijkstra算法确定恢复路径, 并重复步骤1至步骤3。若此时经过N次模拟仍返回不可行, 则认为该机组不能在其启动时限内恢复。

步骤7:在对前述不满足要求的机组节点优先恢复后, 若出现其他机组不满足约束条件的情况, 则仍采用上述方法, 重复步骤5和步骤6。

步骤8:若多次换位后, 仍无法保证所有待恢复机组满足模糊约束, 则按照满足尽可能多机组启动时限的原则, 优化选择热启动阶段恢复的机组, 对于不能在启动时限内恢复的机组, 安排在冷启动阶段恢复。仅采用Dijkstra算法为其搜索最短路径作为恢复路径, 且不再考虑机组启动时限的约束, 即不再对其进行模糊模拟检验。

2.2.2 模糊目标函数的处理

在所有待恢复节点通过模糊约束检验之后, 对模糊目标函数进行处理, 具体做法如下。

步骤1:。

步骤2:从模糊变量的β水平截集上均匀产生清晰变量Rij′和tm′。

步骤3:将清晰变量代入式 (4) 、式 (5) 中, 求得目标函数值f, 若, 则置。

步骤4:重复步骤2和步骤3共N次。

步骤5:返回, 即为求得的目标函数的最大值。

2.3 交叉粒子群优化算法

本文采用交叉粒子群优化算法对待恢复目标节点的恢复顺序进行优化。粒子群优化算法是由Kennedy博士和Eberhart博士提出的一种智能优化算法[20]。该算法首先初始化一群随机粒子, 每个粒子代表问题的一种解, 在迭代过程中, 各个粒子通过与两个“极值”不断进行比较来更新自己的位置和速度:一个是本粒子在各次迭代中的最优解即个体极值pbest;另一个是目前整个种群得到的最优解即全局极值gbest。文献[21]在原有粒子群优化算法的基础上引入交叉操作, 提出了交叉粒子群优化算法, 将当前解分别与两个极值位置pxbest和gxbest进行交叉, 从而产生新解的位置。

算法采用整数编码, 粒子初始化为待恢复节点的不同恢复顺序。算法中指导粒子进行迭代更新的适应度函数为式 (5) 中的目标函数, 即

以图1所示的5节点网络为例, 进一步说明Dijkstra算法根据粒子进行节点恢复路径搜索及粒子交叉更新的过程, 各线路的权值已在图中标出。

假设节点1为黑启动电源, 待恢复的目标节点为[2 3 4 5], 粒子个数为2, 那么首先初始化得到2个粒子J1=[2 5 4 3]和J2=[3 2 4 5], 其中每个粒子代表一种节点恢复顺序。按照前述Dijkstra算法的原理, 对于粒子J1=[2 5 4 3], 采用Dijkstra算法确定最短恢复路径的过程如下。

首先, 对于最先恢复的节点2, 由Dijkstra算法搜索得到其最短恢复路径1-2;接着将线路1-2的权值置为0, 并继续搜索节点5的恢复路径, 得到2-5;依此类推, 进一步搜索得到节点4的恢复路径5-4, 节点3的恢复路径4-3。这样就得到了粒子J1的恢复路径, 即1-2-5-4-3。

针对粒子交叉更新, 本节将粒子Ji分别与全局极值位置gxbest和个体极值位置pxbest进行交叉操作, 得到新的粒子Ji′。仍以图1为例, 粒子的交叉方法如下。

假设当前进行第j次迭代, 对于待交叉更新的粒子J1 (j) =[2 5 3 4], 假设此时全局极值位置gxbest=[2 3 4 5], 个体极值位置pxbest=[5 2 3 4], 那么首先在gxbest=[2 3 4 5]中随机选取一个交叉区域C1=[4 5], 之后将交叉区域C1加到J1 (j) 前面, 并删除J1 (j) 中已在C1中出现的数字, 得到粒子J1″ (j) =[4 5 2 3];接着将粒子J1″ (j) 与个体极值位置pxbest=[5 2 3 4]交叉, 首先选取交叉区域C2=[34], 之后将交叉区域C2加到J1″ (j) 前面, 并删除J1″ (j) 中已在C1中出现的数字, 最后得到的新粒子为J1′ (j) =[3 4 5 2]。

2.4 算法流程

将前述各部分算法整合, 得到基于模糊机会约束的网架重构优化算法的流程图, 详见附录A图A1。

3 算例分析

3.1 算例1

以图2所示的IEEE 30节点系统为例, 对本文提出的方法进行有效性及合理性验证。该系统共包含6台发电机, 40条线路。其中, 机组节点1作为黑启动电源, 待恢复的机组节点为[2 13 22 23 27], 待恢复的负荷节点为[6 10 12 15 19 21 30];假设机组27的热启动时限为三角模糊数 (10, 15, 20) , 其余各机组的热启动时限均为 (25, 30, 35) ;各条线路的操作时间为三角模糊数 (2, 2.5, 3) , 各线路的恢复可靠性设定如下:其中线路3-4, 4-6, 8-28, 10-20, 10-17, 22-24的恢复可靠性为 (0.9, 0.95, 1) , 其余各线路的恢复可靠性均为 (0.7, 0.85, 1) 。

其他参数设置如下:粒子个数Np=10, 粒子群优化算法允许迭代的最大次数Nmax=60, 模糊模拟的次数N=1 000, 置信水平α和β均为0.95。潮流校验时, 被恢复机组的出力取最大出力的30%。

采用本文提出的方法对网架重构方案进行优化, 得到最优网架重构方案如图2所示。图中:实线为构成网架的线路, 实线连接的部分即最优的目标网架, 实心圆圈为待恢复节点。

表1所示为目标节点的恢复顺序与具体的恢复路径。

根据表1给出的网架重构过程, 可以看出以下几点。

1) 由于机组节点27的热启动时限比较短, 所以在机会约束的限制下, 由算法得到的结果优先对机组27进行了恢复, 且其他机组也均在其热启动时限内得到了启动电源, 实现了最大限度地恢复发电。最终获得的最优目标网架重构时间的模糊期望值为40min。

2) 最终得到的目标网架包含了事先设定的具有较高可靠性的部分线路4-6, 10-20和22-24, 对这些线路被纳入目标网架的原因, 以线路10-20为例简单进行分析。对于目标节点19, 从其所处的网络位置可以看出, 可由其临近的目标节点10或15通过路径10-20-19或15-18-19对其恢复。所以若节点10和15在节点19之前都得到恢复的话, 仅从最短路径来看, 由于路径15-18-19的权值较小, 该条路径较优。但是, 本文寻求的是具有高恢复可靠性的网架, 线路10-20具有较高的恢复可靠性, 所以由算法得到的结果优先对节点10进行了恢复, 并选择通过路径10-20-19对节点19进行恢复, 以期达到更高的恢复可靠性, 这与预期结果一致。分析其他高可靠性的线路没有被纳入网架的原因, 其一是由于线路本身权值较高, 基于Dijkstra算法搜索路径时不被采纳;其二是由于本模型将节点恢复可靠性等效为串联系统的恢复可靠性, 所以有时虽然某最短路径包含了恢复可靠性较高的线路, 但由于路径上线路较多导致目标节点恢复可靠性降低而被摒弃。

为增强说服力, 采用文献[10]的方法来对本文的待恢复目标节点确定最优目标网架, 并进行对比分析。其中机组节点27的启动时限设为15 min, 其余参数的设置与文献[10]一致, 得到的最优目标网架 (实线连接部分) 如图3所示。

对比图2与图3所示的两种最优目标网架可以看出, 两种方案都是由16条线路组成的, 且大部分组成路径相同, 仅在节点2, 6和23的恢复路径选择上略有差异, 主要是两种方法的模型与线路权值选择不同造成的。但两种方案均通过潮流校验, 均是可行的恢复方案。

通过对比分析, 进一步说明了本文将操作时间和恢复可靠性做模糊数处理合理且可行。所提出的方法可以有效地根据电网的恢复情况及拓扑结构, 合理地优化节点的恢复顺序和确定相应的恢复路径, 得到满足要求的最优目标网架。

3.2 算例2

为了进一步验证本文提出的方法在实际系统应用中的有效性, 以云南电网的部分区域 (云南昆明地区与曲靖地区220kV及以上系统的大部分区域, 包括51个厂站节点、7个发电厂和67条线路) 为例, 计算该区域在大停电之后的恢复路径。选择曲靖地区的鲁布革电厂作为黑启动电源, 待恢复的机组节点为昆明电厂、阳宗海电厂、滇东电厂、雨汪电厂、曲靖电厂和宣威电厂, 待恢复的其他节点为海埂、青山、花山、沾益、金钟、厂口、宝峰。

采用本文算法对其进行求解, 其中曲靖电厂与阳宗海电厂的启动时限设置得较小, 其他机组节点的启动时限设置得较大。最终得到的最优目标网架如图4所示。

4 结语

本文将线路投运时操作时间与恢复可靠性合理化为三角模糊变量, 在模糊机会约束的框架下, 建立了计及机组启动时限的网架重构优化模型, 并提出了适用于本模型的模糊模拟、交叉粒子群优化算法与Dijkstra算法相结合的求解方法。通过最后的实例分析, 本文提出的方法不仅可以有效地根据电网的恢复情况及拓扑结构, 合理地优化节点的恢复顺序, 为尽可能多的机组提供启动电源并满足一定的置信水平, 同时使优化得到的目标网架具有较高的恢复可靠性, 有利于网架重构阶段系统的安全运行。此外, 本文提出的理论框架具有一定的通用性, 可用来处理网架重构阶段所涉及的其他具有模糊性的不确定因素, 也可进一步考虑将这种思路延展应用到黑启动的其他阶段。

随机机会约束规划第4篇

1 应急情况下机型指派模型研究

1.1 确定情况下航班调度问题的机型指派模型

机型指派管理对航空公司收益管理有较大影响, 是整个航班计划管理的核心部分。以下是马苏德·巴扎尔甘提出的机型指派模型

式中:C为到达机场集合, 表示网络中所有结点或停场过夜机场;F为航班集合;Pi, j为由机型j飞航班i的成本;如果航班i用机型j执行, 则xi, j=1, 否则为0, M为网络中的机场 (结点) 数;J为机型集合。

1.2 应急情况下的航班调度机型指派问题相关机会约束模型

在应急情况下, 管理者期望在花费资金较少的情况下最大概率的实现预期的管理目标, 由于在航班应急情况下, 许多参量出现一定的随机型, 原来的一部分确定型变量转化成为随机变量, 传统的确定型数学规划模型无法很好地求解这类机型指派问题, 相关机会约束模型, 在根据具体条件情况要求下设定一定的优先等级, 允许在一定情况一定置信水平下满足约束条件, 其模型如下。

式中:ξ是个随机向量;x是个决策向量;α和β是管理者预先给定的置信水平。Pi, j+f (Si, ξj) =*Pi, j为航班实际的成本。其中ξj表示航班j的旅客量, 是一个随机变量;Si表示机型i的座位数;Gk, j为机型j在机场k过夜的飞机数量。Nj为机型j的可用飞机数量;当结点k的航班i是进港航班, Sj, k=+1, 当结点k的航班i是离港航班, Si, k=-1。

2 模型算法研究

2.1 机会函数的计算机仿真拟合计算

设gj (x, ξ) ≤0, j=1, 2, …, P是事件Aj在点x的诱导约束, 则机会函数式fj (x) 由下式给出:

相关机会约束目标函数变化为Max (f1 (x) , f2 (x) , …, fp (x) ) , 其中x为管理变量;ξ为随机变量, 其分布为φ (ξ) 。

我们允许采用蒙特卡罗随机拟合方法估计机会函数fj (x) 。具体思想是利用ξ为随机变量的分布φ (ξ) , 从中产生N个随机向量, 分别记为ξ1, ξ2, …, ξN;设N次试验中gj (x, ξk) ≤0 (k=1, 2, , …, N) 成立的次数为n, 即随机变量中符合约束条件的个数。由中心极限定理和大数定理得出, 机会函数允许用近似估计概率。

2.2 随机拟合仿真的改进遗传算法

由于相关机会模型问题的复杂性, 很难利用现有的理论方法求解, 采用蒙特卡罗随机仿真拟合的改进遗传算法极大地方便求解模型。基于蒙特卡罗随机拟合的改进遗传算法求解步骤如下。步骤1:确定变异概率Pm, 交叉概率Pc及种群数参数N;步骤2:编码优化问题, 形成有N个染色体的初始群体, 并借用随机拟合技术检验染色体的可行性;步骤3:借用随机拟合技术估算初始种群中每个染色体的适应值;若停止规则满足, 则算法停止, 否则转下一步;步骤4:估算概率步骤5:以概率Pi从初始种群中随机选部分染色体构建新的种群;步骤6:按照给定的变异概率Pm与交叉概率Pc, 对染色体实行变异与交叉操作, 并借用蒙特卡罗随机拟合技术检验后代的可行性;步骤7:重复步骤2至步骤6, 直到完成设定的循环次数;步骤8:给出方案结果最好的染色体作为最终最优解。

3 算例分析

A航空公司为应对由风暴等不确定因素引起的大面积航变, 提前制定应急预案。该公司有2种机型, 6架Ⅰ型飞机, 3架Ⅱ型飞机, Ⅰ、Ⅱ机型的座位数分别为185、200。设A航空公司甲、乙城市之间的航班旅客需求为ξ1 (去) 、ξ2 (返) 分别为正态分布ξ1~N (150, 352) 、ξ2~N (160, 472) , 首先来解2.1中的模型, 根据算例的数据, 得到F={1, 2, 3, 4, 5, 6}, J={1, 2}, M={1, 2, 3}, N1=6, N2=9, 由程序得到最优解确定性模型最小成本为115 608, 甲乙往返满足旅客量需求置信水平分别是80%、52%。现引入相关机会约束, 设定一定的优先等级, 设定满足甲去乙为第一优先级, 置信水平不低于90%, 乙返回甲地为第二优先级, 置信水平不低于80%, 满足在相关基础模型参数基础上, 求解的相关机会约束模型最小成本为121 956。并且误差不超过2%。结果显示, 成本虽然有所增加, 却能够以较高的置信度满足旅客需求, 模型具有鲁棒性, 往返置信水平分别提升到90%、80%以上, 有效提升航空公司形象及顾客满意度, 有利于长远发展。

4 结语

在前人成果基础上构建相关机会约束的机型指派模型, 并运用蒙特卡罗随机拟合与改进遗传算法等方法求解模型, 结果显示模型的可行性及鲁棒性, 一定程度上可为航空公司的应急机型调度提供相应参考。但模型仅考虑了不确定旅客需求的随机性, 实际情况较为复杂, 可以进一步研究同时包含模糊不确定性、随机不确定性的突发状况及应急调度。

摘要：为应对民航突发情况, 保障民航运行安全, 提出应急调度这一概念。本文阐述常规情况下航班调度的基本模型, 分析其在应急情况下的弊端。引入相关机会约束, 构建应对突发状况的应急调度模型。根据拟合数据, 利用基于随机拟合的改进遗传算法, 借用matlab软件求解模型。结果显示, 基于相关机会约束规划的机型指派模型在考虑随机因素的情况下, 比基本模型更符合实际动态环境要求。

关键词：相关机会约束,应急调度,机型指派,遗传算法

参考文献

[1]赵秀丽.航空公司不正常航班恢复模型及算法研究[D].南京:南京航空航天大学.2010.

[2][美]马苏德·巴扎尔甘.航空公司运营规划与管理[M].邵龙, 王美佳, 译.北京:中国民航出版社, 2006:39-56, 81-91.

[3]牟德一, 王志新, 夏群.基于机组延误概率的鲁棒性机组配对问题[J].系统管理学报, 2011, 20 (2) :207-212.

[4]刘宝碇, 赵瑞清, 王纲.不确定规划及应用[M].北京:清华大学出版社, 2003:84-91.

随机机会约束规划第5篇

再制造是指通过回收、拆卸、分拣、清洗、喷涂、翻修及再装配等环节, 修复或改造废旧产品, 恢复零部件或产品性能的技术和活动[1]。与传统制造过程相比, 再制造过程对象是报废的成形零件, 存在着尺寸超差、残余应力、内部裂纹和表面变形等一系列缺陷。因此, 再制造车间具有多重不确定性, 集中表现为[2]: (1) 再制造产生的原因及发生时间、地点、数量等难以准确预测; (2) 再制造产品的性能、质量及制造需求不确定; (3) 产品的再制造工艺路线、再制造周期及再制造成本不确定; (4) 再制造的目标具有多样性, 如减少资源消耗、保护环境、降低生产成本和提高服务质量等; (5) 再制造后产品的市场需求、价格等难以准确预计。

如何在不确定环境下对再制造车间生产调度进行优化设计, 保证再制造生产过程顺利运行, 已成为再制造企业提高生产管理水平的关键环节之一。再制造调度主要包括拆卸调度、再加工调度和再装配调度[2]。目前, 已有学者对再制造生产调度进行了研究。Li等[3]提出了一种混合遗传算法对再制造生产计划进行优化, 且运用优先随机批量机制对其进行仿真。Jac等[4]研究了分组作业调度问题, 建立了混合整数规划模型, 使用智能算法进行求解。目前再制造调度研究文献主要集中于再制造加工调度, 而对再制造拆卸和装配调度研究较少。再制造装配过程中, 零部件是由再利用件、再制造件和新品件组成, 文献[5-6]描述了再制造装配质量的复杂性, 得出零部件的装配质量的不确定性导致工位装配时间波动很大, 精确的装配时间难以获得的结论。由于再制造产业的特殊性, 对于这些不确定性信息, 很难估计它的概率分布规律, 只能凭借经验或历史数据给出大致的区间估计, 故采用模糊理论来描述不确定信息。模糊集合理论[7]自从提出以来, 在自动控制、模式识别等许多领域获得了广泛的应用。研究者就模糊调度问题开展了许多研究。孙燕等[8]提出一种基于微粒群算法的求解模糊机会约束规划的混合智能算法, 通过仿真实验验证了其可行性。胡恒等[9]针对加工时间和交货期都不确定的模糊调度问题, 提出一种基于多群体并行的遗传算法。

本文在借鉴现有研究成果的基础上, 采用模糊变量来描述再制造车间装配时间的不确定性, 构建了基于模糊机会约束规划的再制造装配车间的不确定性模型, 提出了一种求解该模型的混合智能算法, 并给出了求解方法及相应流程, 最后, 通过仿真实例验证了该混合智能算法对解决再制造装配车间调度问题的可行性。

1 再制造装配车间调度问题模型

1.1 模糊变量及其数学描述

不确定环境下的工位装配时间一般采用随机变量或模糊变量来描述, 其中描述随机变量的概率密度函数是以大量稳定的统计数据为基础的。对于再制造装配车间而言, 零部件质量受回收数量、拆卸数量和库存数量等因素的影响, 其不确定性往往导致工位装配时间范围波动很大, 因此本文采用基于可信性测度的模糊变量来描述再制造车间工位装配时间。

定义1[10]设θ是非空集合, P (θ) 是θ的幂集。如果Pos是可能性测度, 则三元组 (θ, P (θ) , Pos) 称为可能性空间。

定义2[10]设ξ为一从可能性空间 (θ, P (θ) , Pos) 到实直线R上的函数, 则称ξ是一个模糊变量。

定义3[11]假设 (θ, P (θ) , Pos) 是可能性空间, A是幂集P (θ) 中的一个元素, 则称为事件A的可信性测度。

在模糊理论中, 文献[12?13]定义了可能性测度Pos{}, 文献[11]定义了必要性测度Nec{}。

定义4[14]设ξ为模糊变量, 且α∈ (0, 1], 则称ξinf (α) =inf (r|Cr{ξ≤r}≥α) 为模糊变量ξ的α悲观值。

1.2 问题描述

再制造装配车间调度问题类似于流水车间调度问题。描述如下:假定一个再制造装配车间有n个产品要在m台机器上进行装配, 由于要组装n个产品的零部件质量等级不同, 导致工位装配时间和装配成本随零部件质量等级波动范围大, 是变化的不确定量;每个产品的装配工序都相同, 并且以相同的次序在各机器上装配;同时忽略装配工位的流转时间、准备时间、装配时间和卸载时间, 统称为装配时间;在满足工序顺序约束、机器约束和交货期约束等前提下以最小化预定置信水平下最大装配时间的悲观值为调度目标。该模型满足如下假设: (1) 所有产品在每台机器上装配次序相同; (2) 不同产品之间具有相同的优先级; (3) 同一台机器在某一时刻只能装配一个产品, 同一产品的同一道工序在同一时刻只能被一台机器装配; (4) 产品的每道工序一旦开始, 装配便不能中断; (5) 所有产品在零时刻都可以被装配。

再制造装配作业调度问题变量描述如下:J={J1, J2, …, Jn}表示n个产品的集, M={M1, M2, …, Mm}表示m台机器的集, 分别表示产品Ji的第j道工序的开始时间、完成时间和装配时间, 分别表示工件Ji的最后一道工序的开始时间、完成时间和装配时间, 工件Ji的交货期为Di。

1.3 调度建模

由于再制造装配时间为模糊变量, 因此开始时间、完工时间也都是模糊变量。在这样的模糊环境下, 再制造装配车间调度模型无法像经典约束条件那样, 给出一个精确的数学模型和确定的可行集。模糊机会约束规划是由Liu等[15]提出的一类模糊规划, 其显著特点是模糊约束条件至少以一定的置信水平成立, 允许所做决策在一定程度上不满足约束条件, 只要求该决策使约束条件成立的可信性不小于决策者预先给定的置信水平。它为不确定性决策问题提供了解决思路。

对于求极小化问题, 模糊机会约束规划模型通常表示为

式中, x为决策向量;ξ为模糊向量;f (x, ξ) 为目标函数;gi (x, ξ) 为约束函数;α、β分别为决策者预先给定的置信水平。

在装配时间为模糊变量的再制造装配车间中, 交货期约束可以描述为模糊机会约束, 即

现取预定置信水平下最小化最大装配时间悲观值作为优化目标, 其模糊机会约束模型描述为

式中, 为目标函数在置信水平β下的最小化最大装配时间的悲观值。

同时, 还要受到产品装配顺序约束和机器资源的约束, 即

综上所述, 装配时间为模糊变量的模糊机会约束规划模型可表示为

2 模型求解

2.1 混合智能算法介绍

求解模糊机会约束规划主要有两种方法。第一种方法是转化为确定性的等价规划, 但这种方法要求目标函数和约束条件的参数符合某种特征分布。由于再制造车间的不确定性, 导致相关参数呈现模糊性特性, 故无法转化为清晰等价形式。第二种方法是逼近法, 通过模拟仿真生成大量样本数据集来逼近机会约束函数, 结合智能算法来优化求解模型。第二种方法更符合再制造生产实际, 本文在参考文献[10, 16]基础上设计一种将模糊模拟技术、神经元网络和遗传算法相结合而成混合智能算法, 用来对模糊机会约束规划进行求解。在仿真平台上, 运用模糊模拟技术, 产生大量的输入输出样本数据;利用样本数据结合反向传播算法训练多层前向神经网络, 逼近不确定函数;将不确定函数嵌入到遗传算法中, 检验染色体的可行性和计算染色体的目标值, 优化再制造装配调度问题。

2.2 模糊模拟

模糊模拟是对模糊系统进行抽样试验的一项技术, 当模拟次数达到一定程度时, 模拟值就可以无限接近精确值。下面给出本文需要的模糊模拟计算方法。

利用模糊模拟计算事情的可信性:

算法步骤[8]如下:

(1) 设L=Cr{g (x, ξ) ≤0}。

(2) 分别从θ中均匀产生θk, 使得Pos{g (x, ξ (θk) ) }≥ε, 并定义vk=Pos{g (x, ξ (θk) ) }, k=1, 2, …, N, 其中ε是个充分小的数。

(3) 计算

(4) 若L≥α则将L作为样本数据。

当采用可信性测度时, 利用模糊模拟确定最小的, 使得成立的算法步骤[11]如下:

(1) 设。

(2) 分别从θ中均匀产生θk, 使得Pos{f (x, ξ (θk) ) }≥ε, 并定义vk=Pos{f (x, ξ (θk) ) }, k=1, 2, …, N, 其中ε是个充分小的数。

(3) 计算

找到满足L (r) ≥β的最小值r。

(4) 由L (r) 的单调性知, 可以采用二分法找到最小的r, 返回r。这个最小的r可以作为的估计值。

本文利用仿真软件Extend建立上述模糊模拟模型, 进行多次仿真试验, 检验模糊机会约束规划模型的约束条件, 并计算优化目标值, 为训练神经网络提供近似样本数据。

2.3 神经网络的函数逼近

2.3.1 多层前向神经元网络

人工神经网络是由许多神经元连接而成, 用以抽象简化和模拟人脑行为的一类适应系统。Minsky等[17]提出的多层前向神经元网络是目前使用较多的网络结构, 已经被广泛用于函数逼近、模式识别和网络优化等领域, 已经证明对于任何在闭区间的一个连续函数都可以用一个三层前向神经元网络来逼近。因此, 我们通过模糊模拟产生的大量样本数据, 训练神经网络来逼近p+1个不确定函数, 即

2.3.2 反向传播算法训练神经网络

反向传播算法是训练多层前向神经网络的基本方法, 它实际上是一种梯度下降的最小化方法。该过程是通过选择权重来极小化网络输出和实际输出之间的误差, 是一种无约束化的计算方法。

一般以网络输出的误差平方和

最小作为网络训练的理想结果。其中ω为权重向量、F (xi, ω) 为神经网络的输出映射函数, (xi, yi) 为训练数据。主要步骤[10]如下。

(1) 初始化权重向量ω, 并令μ=1, β=4/3, α=0.05, 学习速率η=0.01, 预先确定的精确度E0=0.05, 适应参数λ=1, k=0。

(2) k←k+1。

(3) 根据下列两式调整权值ω:

(4) 根据下式计算误差Ek:

式中, dk, i为期望输出;yk, i为实际输出;Φ (x) =ln (cos (βx) ) /β。

(5) 如果k<N, 返回步骤 (2) , 其中, N是学习样本数, k是学习样本的序号。

(7) 如果E>E0, 那么k=0, λ=exp (-μ/E2) 并返回步骤 (2) 。

(8) 结束。

2.4 利用遗传算法优化再制造装配调度问题

(1) 编码和解码。由于再制造产品装配顺序相同, 染色体采用自然数来表示工件的加工顺序。例如[4 2 1 5 3], 表示该批产品的加工顺序为J4、J2、J1、J5、J3, 一条染色体对应一个可行的调度方案。

(2) 初始化。初始化染色体种群, 设置种群大小、交叉概率、变异概率和算法迭代次数等, 用训练好的神经网络检测染色体的可行性, 判断是否满足交货期机会约束。

(3) 适应度函数。将训练后的神经网络嵌入到遗传算法中, 根据输出最大装配时间悲观值将染色体由好到坏排序, 采用基于序的评价函数eval (Chromoi) =a (1-a) i-1进行评价, 其中, a为评价参数, eval表示评价函数, Chromoi表示第i个染色体。

(4) 选择。从父代染色体种群中选择适应值最高的个体遗传到下一代种群中。本文采用最常用的轮盘赌选择法进行选择。

(5) 交叉。采用随机两点交叉, 其操作规则是, 首先随机选取两个基因作为交叉基因, 交叉后, 判断染色体中[1, n]区间内缺失的自然数, 然后将未参与交叉基因中重复的自然数替换成缺失的自然数。

(6) 变异。随机选取染色体中的部分基因进行互换, 以维护种群的多样性。

(7) 算法终止条件为预先设定的最大迭代次数或出现可接受解终止。

综上所述, 混合智能算法主要步骤如图1所示。

3 算例分析

以某再制造装配车间为例, 现准备装配7个产品, 装配工序由5台机器完成。根据对历史数据的统计分析, 总结出组装产品的再制造件在不同失效等级的概率及对应情况下的模糊加工时间 (用三角模糊数表示) 和交货期机会约束, 如表1所示。如组装产品J1的零部件失效等级为二级的概率约为0.56, 在机器M1上的工序装配时间为 (16, 17, 19) min, 即最乐观加工时间为16min, 最可能加工时间为17min, 最悲观加工时间为19min。产品J1在置信水平0.7下, 交货期为485min;在置信水平0.8下, 交货期为500min;在置信水平0.9下, 交货期为515min。

本次试验通过仿真软件Extend建立模糊模拟仿真模型, 样本容量为1000, 模糊模拟次数为1000, 以获得样本数据;基于这些样本数据, 利用反向传播算法 (初始化权重0.9) 训练神经元网络 (7个输入神经元, 15个隐层神经元, 8个输出神经元) 来逼近不确定函数;把训练好的神经元网络嵌入到遗传算法中, 种群规模50, 最大迭代次数1000, 交叉概率0.8, 变异概率0.1, 基于序的评价常数a=0.05, 优化目标为满足工序顺序约束、机器约束和交货期约束等前提下最小化预定置信水平下最大装配时间的悲观值。在CPU为CORE-2T5600, 主频为1.83GHz, 内存为2GB的硬件环境上应用MATLAB R2009编写仿真实验程序。依次改变置信水平, 通过运行混合智能算法得到的调度结果如表2所示。由表2可以看出, 不同的置信水平下, 调度方案是不完全相同的, 表中的调度结果不一定是最优解, 但是能够保证在满足相关约束和在一定置信水平前提下, 最大的装配时间悲观值最小。随着置信水平的增大, 系统的稳定性增强, 装配周期也随着增大, 表明再制造企业决策者要根据管理目标, 选择相应的置信水平, 折中选择相应的调度方案。由于篇幅所限, 只给出置信水平为0.8时, 算法最优结果的迭代过程图 (图2) 。从图2可以看出, 由于混合智能算法计算量较大, 仿真运行时间也较长, 在一定置信水平下, 该解是一种较理想的妥协解。

4 结论

(1) 针对不确定环境下的再制造装配车间调度问题, 采用基于可信性测度的模糊变量描述装配时间, 建立了约束条件以一定置信水平成立的模糊机会约束规划调度模型, 并研究了模型的求解方法。

(2) 提出了一种集模糊模拟、神经网络和遗传算法相结合的混合智能算法。应用模糊模拟技术在仿真软件平台上产生样本数据, 通过反向传播算法训练神经网络以逼近不确定函数, 并将训练好的神经网络和遗传算法相结合, 求解再制造装配调度问题。

(3) 通过实例对模型和算法的可行性进行了验证。该模型和算法为不确定性环境下再制造装配车间调度理论提供了新的思路和方法。

摘要：针对再制造零部件质量的不确定性导致工位装配时间波动范围大和调度模型难以准确描述的问题, 采用基于可信性测度的模糊变量表示再制造零部件的装配时间, 建立基于置信水平下的模糊机会约束规划调度模型, 并提出求解该模型的混合智能优化算法:应用模糊模拟技术产生样本数据;利用反向传播算法训练多层前向神经网络逼近不确定函数;将训练后的神经网络与遗传算法相结合, 以优化再制造装配车间调度问题。实例验证了该模型和算法的可行性。

随机机会约束规划第6篇

输电系统规划的任务是确定最佳的网络结构,满足电力输送的要求,并且投资最小。在规划中考虑不确定因素对于获得稳健的电网规划方案、降低系统运行风险至关重要[1]。

风电作为一种可再生能源,近年来在中国得到快速发展建设,多个装机容量超过100 MW的大型规划风电场直接接入220 kV电力系统中。风电本身所固有的随机性和间歇性,给电力系统的规划和运行增添了新的不确定因素[2,3]。因此,只考虑1个或几个典型运行方式的确定性输电网规划模型不适用于含有风电场的输电系统。迄今为止该问题尚未得到解决,在以前的文献中仅见对不同的含有风电场的规划方案进行可靠性评估的工作[4]。

本文提出了用机会约束规划[5,6,7]方法解决考虑负荷和风电场输出不确定性的输电网络规划问题。与传统的Monte Carlo方法计算有功潮流概率分布[6,7]不同,本文采用了Monte Carlo与解析法相结合的方法:用Monte Carlo模拟出风电场出力的概率密度函数,然后代入解析的直流概率潮流计算中。这种模拟与解析相结合的方法极大地降低了计算量,使风电模型与概率潮流和机会约束规划相结合成为可能。为了进一步降低计算量,在优化过程中设计了一种两步式遗传算法。

本文提出的机会约束规划方法的测试结果显示,与传统的确定性规划方法相比,该方法能提供更丰富的信息:不同的负荷分布会产生不同的最终规划方案;风电场出力特性发生变化,输电系统不过负荷的概率也不同。这些信息在确定性规划模型中都无法得到,说明了采用机会约束规划的必要性。

1 含风电场模型的直流概率潮流计算

如果电力系统中负荷和发电机出力的分布已经确定,通过直流概率潮流计算[8],线路有功潮流的概率分布以及每条线路过负荷的概率就可以确定。假设负荷服从正态分布,负荷需求、发电机的输出、不同风电场的风速是独立的。

1.1 风电场的概率输出模型

由于风速变化,风电场运行过程中的输出功率在0与额定功率之间波动。由于精确的风速很难预测,建立概率模型是较好的解决方案。风速分布用威布尔分布来模拟[9],尺度参数和形状参数由观测到的风速的期望和标准差来折算[10]。风机输出特性可用3个参数来近似描述:切入风速Vci、额定风速Vrate、切出风速Vco。设Prate为风机额定功率,风速V与风机有功出力P的关系可用下式描述[11]:

$Ρ = {\begin{cases} 0 0 \leq V < V_{c i} \\ Ρ_{r a t e} \frac{V - V_{c i}}{V_{r a t e} - V_{c i}} V_{c i} \leq V < V_{r a t e} \\ Ρ_{r a t e} V_{r a t e} \leq V \leq V_{c o} \\ 0 V_{c o} < V \end{cases} (1)$

如果风速分布和风机的特性已知,风电场的输出分布用Monte Carlo法模拟。设风机参数为:Vci=4 m/s,Vrate=10 m/s,Vco=22 m/s,风电场的风速期望值Ewind=5.4 m/s,标准差σwind=2.7 m/s。模拟104次得到的风电场出力概率密度分布示于图1,并可用下式的函数关系来描述:

$f (x) = {\begin{cases} F_{z e r o} δ (x) x = 0 \\ g (x) 0 < x < Ρ_{r a t e} \\ F_{r a t e} δ (x - Ρ_{r a t e}) x = Ρ_{r a t e} \\ 0 其他 \end{cases} (2)$

式中:f(x)为风电场有功输出的概率密度函数;x为风电场的有功输出;Fzero和Frate分别为风电场输出为0和额定值的概率;δ(x)为单位冲击函数;g(x)为描述0与Prate之间的连续概率密度分布的函数,可以用拟合的多项式曲线或离散点来表示。

1.2 概率直流潮流

输电线上的有功功率概率分布可以用概率潮流计算来确定。线路流动有功功率与节点注入有功功率之间的关系为[8]:

$Ρ_{L} = A Ρ_{Ν} (3)$

式中:PL为线路有功功率向量;PN为除平衡节点外的节点注入有功向量;A为系数矩阵。

假设pN1,pN2,…,pNn-1是PN的元素,因为节点注入有功等于发电机输出有功减去本地负荷消耗的有功,则节点注入有功的概率密度函数f1(x),f2(x),…,fn-1(x)就等于发电机有功输出的概率密度函数与负荷概率密度函数的卷积。设[at,1,at,2,…,at,n-1]是矩阵A的第t行,t=1,2,…,m;pij是PL的第t个元素,表示连接节点i和节点j的线路上的总流动功率,因此有:

$p_{i j} = a_{t, 1} p_{Ν 1} + a_{t, 2} p_{Ν 2} + \dots + a_{t, n - 1} p_{Ν n - 1} (4)$

由概率理论中的随机变量的函数理论[12],at,kpNk(k=1,2,…,n-1)的概率密度函数为:

$f_{t, k} ´ (x) = \frac{f_{k} (\frac{x}{a_{t, k}})}{a_{t, k}} (5)$

pij的概率密度函数为:

$f_{L, t} (x) = f_{t, 1} ´ (x) * f_{t, 2} ´ (x) * \dots * f_{t, n - 1} ´ (x) (6)$

式中:*表示卷积计算。

因此,根据式(3)中的节点输入与线路潮流的确定性关系,如果每一个PN中的元素的概率密度函数确定,PL中的每个元素的概率密度函数也就可以确定了。

独立正态分布随机变量的特性可以用来减小卷积的计算量[12]:如果2个随机变量服从正态分布,期望和方差分别是E1,E2和σ21 ,σ22,则这2个随机变量之和仍然服从正态分布,并且其期望为E=E1+E2,方差为σ2=σ21+σ22。因此,当计算fL,t(x)=ft,1′(x)*ft,2′(x)*…*ft,n-1′(x)时,正态分布的ft,·′(x)应该排在非正态分布的ft,·′(x)前面。由于式(2)中的风电场出力分布是非正态的,考虑的风电场越多,计算量越大。下文将叙述在网络优化过程中为降低计算量而采取的措施。

2 输电系统的机会约束规划方法

2.1 传统的确定性电网规划模型及其扩展

设输电网络中的并联线路型号相同,最基本的确定性电网规划模型如下[13,14]:

目标函数:

$\min \sum c_{i j} n_{i j} (7)$

约束条件:

$\begin{array}{l} S^{Τ} Ρ_{L} + g = d (8) \\ p_{i j} - γ_{i j} (n_{i j}^{0} + n_{i j}) (θ_{i} - θ_{j}) = 0 (9) \\ | p_{i j} | \leq (n_{i j}^{0} + n_{i j}) \bar{ϕ}_{i j} (10) \\ 0 \leq g \leq \bar{g} (11) \\ 0 \leq n_{i j} \leq \bar{n}_{i j} (12) \\ n_{i j} 为整数, (i, j) \in Ω (13) \end{array}$

式中:cij为节点i-j之间新建线路的费用;nij为加到i-j节点之间的线路的数量;S为节点—线路关联矩阵;g为发电机有功输出列向量;d为预测的节点负荷列向量;γij为节点i-j之间的电纳;n0ij 为节点i-j之间的已建成线路条数;θi为节点i的电压相角; $\bar{ϕ}$ ij为节点i-j之间每条线路的流动功率上限; $\bar{g}$ 为最大发电机功率输出容量; $\bar{n}$ ij为可以在节点i-j之间新建线路的最大条数;Ω为所有备选线路的集合。

式(7)的目标函数为找到最优的输电网结构,满足负荷需求,并且投资最小。最终的优化方案必须满足所有的约束条件:等式约束(8)表示节点的有功注入关系;等式约束(9)为线路潮流方程;式(8)和式(9)共同构成直流潮流计算;不等式约束(10)为线路运行不过负荷的限制。

式(7)可用遗传算法、模拟退火、蚂蚁算法、粒子群等启发式算法来求解。由于需满足式(10)的约束条件,即所有的备选方案中都不能有线路过负荷,造成备选方案的多样性不足,优化过程中易发生早熟。因此,在目标函数中增加因线路容量不足而导致的切负荷项,将存在线路过负荷的方案也引入备选方案集,目标函数(7)和约束条件(8)修正为[13,14]:

$\begin{array}{l} \min (\sum c_{i j} n_{i j} + α \sum r_{i}) (14) \\ S^{Τ} Ρ_{L} + g + r = d (15) \end{array}$

式中:r为负荷削减列向量,元素为ri;α为输电线路容量不足而导致的减负荷的罚因子。

需注意的是:该模型的目标仍然是要找到最经济的没有切负荷的方案。目标函数中存在表示切负荷的第2项的目的是作为一个惩罚项来改进启发式算法的结果。有了这一项,在优化过程中有无过负荷的方案都会出现在方案集中,扩大了备选方案的多样性。如α值适当,优化结束时α∑ri应等于0。

优化过程中产生的每一个有过负荷的备选方案都需要用线性规划计算α∑ri[15],这些重复的线性规划计算非常耗时。为了减轻计算量,本文提出了一个反映过负荷的替代模型:式(14)中的切负荷项用式(16)中的线路过负荷百分比的和来表示,约束式(15)变为式(17),式(16)的其他约束与式(9)~式(13)相同。

目标函数:

$\min (\sum c_{i j} n_{i j} + α_{e} \sum e_{i j}) (16)$

约束条件:

$S^{Τ} Ρ_{L} + g = d (17)$

式中:

$e_{i j} = {\begin{cases} 0 | p_{i j} | \leq \bar{p}_{i j} \\ \frac{| p_{i j} | - \bar{p}_{i j}}{\bar{p}_{i j}} | p_{i j} | > \bar{p}_{i j} \end{cases}$

$\bar{p}_{i j} = (n_{i j}^{0} + n_{i j}) \bar{ϕ}_{i j}$

式(16)避免了式(14)中用线性规划计算切负荷的过程,所以采用式(16)的输电网规划计算速度比用式(14)快得多。式(16)与式(14)本质上的含义是相同的:都是根据过负荷的程度惩罚有过负荷的方案。在不考虑发电机出力调整的输电系统规划算例[13]中,式(16)和式(14)可以分别被认为是粗略和精确反映过负荷程度,2个模型最终会得到相同的计算结果:一个没有过负荷并且费用最小的规划方案。

2.2 输电网机会约束规划模型

当在输电网规划中考虑负荷和风电场时,如果要保证所有的线路在任何情况下都不过负荷,电网投资会非常大。一个合理的选择是使系统运行在约束条件之内的概率达到一个可接受的值。出于这种考虑,提出了输电网规划的机会约束模型:把约束条件(10)转换到概率领域,输电网络不过负荷的概率应大于某个特定的概率β,即

$Ρ r {| Ρ_{L} | \leq \bar{Ρ}_{L}} \geq β (18)$

式中:Pr{·}表示概率事件; $\bar{Ρ}$ L为线路潮流上限列向量,其中元素为 $\bar{p}$ ij。

如果节点i-j之间的线路有功潮流概率分布满足Pr ${| p_{i j} | \leq \bar{p}_{i j}} \geq β$ ,也就是在线路容量限制之内的有功分布区域大于β,则该线路无过负荷;否则就是有过负荷,过负荷程度用εij表示:

$ε_{i j} = {\begin{cases} 0 Ρ r {| p_{i j} | \leq \bar{p}_{i j}} \geq β \\ β - Ρ r {| p_{i j} | \leq \bar{p}_{i j}} Ρ r {| p_{i j} | \leq \bar{p}_{i j}} < β \end{cases} (19)$

输电网机会约束规划模型可以为:

目标函数:

$\min (\sum c_{i j} n_{i j} + α_{ε} \sum ε_{i j}) (20)$

约束条件:

$\begin{array}{l} Ρ r {| Ρ_{L} | \leq \bar{Ρ}_{L}} \geq β - ε (21) \\ f_{L, t} (x) = f_{t, 1} ´ (x) * f_{t, 2} ´ (x) * \dots * f_{t, n - 1} ´ (x) \\ t = 1, 2, \dots, m (22) \\ 0 \leq g \leq \bar{g} (23) \\ 0 \leq n_{i j} \leq \bar{n}_{i j} (24) \\ n_{i j} 为整数, (i, j) \in Ω (25) \end{array}$

式中:αε为线路过负荷概率罚因子;ε为εij列向量。

式(20)的目标函数为考虑到负荷分布和风电场的概率分布,在满足规定的不过负荷概率β的前提下新建线路费用的最小化。反映所有备选方案的过负荷程度的惩罚项为所有线路的过负荷程度之和乘以罚因子。式(21)为式(18)与式(19)的结合,反映了备选方案的过负荷程度与β之间的关系。式(22)用于确定线路的有功概率密度分布函数。

2.3两步式遗传算法

采用遗传算法[14]来优化式(20),为了减轻计算量,优化过程分为以下2步:

1)遗传算法的前几代,风电场的分布用正态分布来表示。由于风电场有功分布必然在0与Prate之间,根据正态分布的特点:几乎所有(约99.7%)的正态分布点都位于E+3σ与E-3σ之间,用正态分布拟合风电场分布时,设E为Prate/2,σ为Prate/6。

2)用真实的风电场有功输出分布(式(2))进行遗传迭代。采用这种方法是因为在计算过程中发现在遗传算法产生的初始种群的适应度普遍较差,遗传迭代过程同时也是种群整体的进化过程。遗传计算的第1步和第2步可以被分别认为是粗略优化步骤和精细优化步骤。在两步式遗传算法中,经过第1步遗传迭代后,种群收敛到一个比较好的程度,然后采用真实的风电场有功输出分布进入第2步遗传优化求得最终解。只要这2步中的种群规模适度,从第1步到第2步的过程中就能够保留最优方案而不会丢失。

3 算例分析

算例采用Garver 6节点系统[16],总负荷需求为760 MW,假设风电连接到节点3。负荷的期望值设为确定值。进行了以下5项测试。

1)确定性规划模型(式(14))与本文提出的模型(式(16))的有效性比较

用式(14)和式(16)不考虑风电机组和负荷不确定性的确定性规划的结果是相同的:n2-6=4,n3-5=1,n4-6=2,投资为200×103美元。用式(14)的计算时间为22 s,而式(16)的计算时间仅1.7 s。说明式(14)与式(16)在规划计算中是等效的。

2)规定的β与规划方案及投资费用的关系

风速参数:Ewind=5.4 m/s,σwind=2.7 m/s;风电场参数:Vci=4 m/s,Vrate=10 m/s,Vco=22 m/s;负荷特性:σload/Eload=5%。表1的测试结果说明β越高,所需投资费用越大。

3)β已知,不同负荷分布时的规划方案

风速参数:Ewind=5.4 m/s,σwind=2.7 m/s;风电场参数:Vci=4 m/s,Vrate=10 m/s,Vco=22 m/s;规定β=1。表2的计算结果说明负荷的不确定性越大,为保证规定的不过负荷概率β,规划方案需要的投资越大。

4)系统风电场参数不同时的不过负荷概率β

风速参数:Ewind=5.4 m/s,σwind=2.7 m/s;负荷参数:σload/Eload=10%。表3的计算结果说明风电场参数影响规划方案的不过负荷概率β。

5)不同风力参数下系统的不过负荷概率β

风电场参数:Vci=4 m/s,Vrate=10 m/s,Vco=22 m/s;负荷参数σload/Eload=10%。表4的测试结果说明风电场风力情况也影响规划方案的不过负荷概率β。

从以上测试中可见,通过考虑各种不确定因素,可以控制最终得到的规划方案的风险。不过负荷概率β值高的方案风险小,但规划方案总投资费用增加,决策者应进行权衡。如果满足一个规定的β值,规划方案和建设费用与负荷的分布关系很大。这也意味着采用确定性的规划模型是不够的。β值不但与风电场容量有关,而且与风机参数有关。

4 结语

由于规划方案的性能受到很多不确定因素的影响,本文提出的机会约束规划方法与传统确定性方法相比,考虑了更多的信息,如风速分布、风力发电机的参数、负荷分布等。不但计算出最终规划方案,并且用不过负荷概率来量化风险。本文提出的模型可以被认为是传统的确定性输电规划模型向不确定领域的延伸,用该方法可以得到更稳健的输电系统规划方案。

不同于传统的Monte Carlo方法确定最终的线路功率概率分布,本文提出了Monte Carlo方法与解析法相结合的解决方案。风电场形状复杂的概率分布由Monte Carlo方法模拟得出,然后代入解析法的直流概率潮流计算中。这种模拟与解析相结合的方法极大地降低了计算开销,并且使机会约束规划模型中可以引入风模型和概率潮流计算。为了加快优化速度,采用了一种两步式遗传算法。算例证明了本文方法的有效性。

摘要：提出了一种考虑负荷和风电场输出功率不确定性、基于机会约束规划的输电系统规划方法。将Monte Carlo方法与解析的概率潮流计算方法相结合,得到含风电场电网输电线路的有功概率潮流分布。通过改进经典的输电系统规划模型,得到考虑负荷和风电场有功出力的概率分布、基于概率潮流计算的输电系统机会约束规划模型。为了有效求解该模型,设计了一种两步式遗传算法。该方法可以有效处理输电系统规划中的不确定性,并为规划人员提供比传统方法更丰富的信息。算例证明了该方法的有效性。

随机机会约束规划第7篇

存贮论中研究的主要问题可以概括为“何时订货”和“每次订多少货”两个问题。从这里可以看出,供应商供货能力充分,但是,当需求量特别大以至于一个供应商不可能满足供货要求时,就需要向多个供应商采购,所以存贮论还应研究“向谁订货”的问题。另外,在市场环境中,存在各种不确定性,例如顾客的需求是随机的、采购或需求的时期是随机的等,所以关于存贮模型就有确定型和不确定型两类,特别是近年来,随着随机和模糊理论的发展,许多学者致力于不确定存贮模型的研究。文献[1]给出了需求为确定的情况下向多个供应商采购的模型及其算法。文献[2]研究了需求为随机条件下向多个供应商采购的采购—存贮随机期望值模型及其算法。但是,在实际问题中,随机约束没有给出一个确定的可行解,而且含有随机变量的约束条件往往是以一定的置信水平α成立的,鉴于此,本文利用文献[2]中的随机期望值模型,加以改进,建立了更符合实践的需求随机条件下向多个供应商采购的随机机会规划模型,受Liu和Liu[3]的启发,设计了一种混合智能算法进行求解,最后给出了结论说明了算法的可行性。

1 问题描述与模型建立

1.1 采购库存问题

在经济全球化的影响下,企业与企业之间的竞争已不是单纯的依靠企业资源,而是供应链与供应链之间的竞争。供应链是指包括上下游企业之间进行经济活动发生的物流、业务流、工作流、信息流和商流组成的系统,供应链参与者通俗意义上包括生产商、供应商、零售商、顾客等。

产品采购库存问题是供应链管理当中的一个重要问题,是在需求确定或者不确定的情况下,向供应商采购原材料以便生产制造。供应商可以是一个也可以是多个,对于不同的供应商有不同的采购策略。当把原材料采购回来以后就存在库存管理的问题,如何使得原材料存放的多以及安全管理都是采购库存研究的问题。在采购库存管理的过程当中,要保证成本最低。

随着生产力水平的提高,供应链管理当中出现的采购库存问题变得越来越复杂,是一个具有多层次、随机需求、环境不确定、多个节点的系统网络。因此,为了更好地指导实践,采用不确定规划理论研究问题具有一定的实践指导价值。

1.2 基本知识

不确定规划理论就是在环境不确定的情况下,采用模糊数学、概率论等理论对研究对象建模分析的理论。

事件:在目标函数中,除决策变量外,还存在随机变量,这样的含有随机变量的目标函数就构成了事件。

不确定环境:在约束条件中,除决策变量外,还存在随机变量,这样的随机约束构成了不确定环境。

机会约束:随机约束以一定的置信水平α成立的约束条件构成了机会约束。

1.3 模型的建立

在某大型钢铁冶炼厂,某月月初铁矿石的库存量为vk吨,月末库存量为vk+1吨,冶炼厂对铁矿石的需求量为t吨/天,t为连续的随机变量,密度函数为f ,t ,,不允许缺货,库存费用为q元/吨·日,安全库存量为QS。有m个供应商可提供满足要求的铁矿石。已知第i 1,≤i≤m,个供应商每月最多能供货次数为Mi,每次最大供货能力为Yi,每次供货的费用为ci元,每吨单价为ai元,每月供货xi次,每次供货Qi。文献[2]给出的采购—存贮随机期望值模型为:

其中,Z= (X,Q,) X= (x1,x2,…,xm)T,Q= (Q1,Q2,…,Qm)

在模型中,目标函数表示的是采购和存贮过程中涉及的成本,包括三部分,分别是采购成本和平均存贮费用、安全库存费用和缺货损失。约束条件 (1) 表示采购的铁矿石与月末月初的库存差之和需要与炼铁厂的需要量相等,约束条件 (2)、约束条件 (3) 分别表示采购次数和每次的采购量都有一个上限。考虑到实际问题当中,会出现损耗等不确定情况,约束条件 (1)不一定是等式,可以将以上模型改进为如下的随机机会规划模型:

其中,Z= (X,Q,) X= (x1,x2,…,xm)T,Q= (Q1,Q2,…,Qm)

2 求解算法

对于上文给出的模型Ⅱ,可以将机会约束 (4) 转化成其确定的等价形式,然后对等价的确定模型进行求解。本文利用把神经元网络嵌入遗传算法的思想设计了混合智能算法进行求解,具体思想如下:

Step1用随机模拟技术为不确定函数产生输入输出数据;

Step2根据产生的输入输出数据训练一个神经元网络逼近不确定函数;

Step3初始化pop_size个染色体,并利用训练好的神经元网络检验染色体的可行性;

Step4通过选择、交叉和变异操作更新染色体,并利用训练好的神经元网络检验子代染色体的可行性;

Step5利用训练好的神经元网络计算所有染色体的目标值;

Step6根据目标值计算每个染色体的适应度;

Step7通过旋转赌轮选择染色体;

Step8重复步骤4到步骤7直到完成给定的循环次数;

Step9给出最好的染色体作为最优解。