随机约束

随机约束（精选4篇）

随机约束 篇1

在制造业中, 制造商追求低成本高效益, 随着制造商掌握越来越多的生产销售信息, 制造商已经开始设计和改进生产运输计划。在这种环境下, 研究有效的生产运输方法得到了学者们的广泛重视。

运输计划通常和选址问题结合起来, 确定工厂和仓库的位置, 使到客户的费用最小化。在选址问题中, 假设货物由工厂运送到仓库, 生产产品的总量和运输的总量是相等的, 用0-1变量表示仓库是否开放, 建立0-1混合整数规划模型。选址问题可以用分支定界法和拉格朗日松弛法解决。

本文研究在生产和仓储过程中的生产运输问题。假设存在多个产销中心, 即生产地同时也是销售地。如果产销中心的需求大于生产能力时, 每个产销中心可以接受来自其它产销中心的产品。通过调节产销中心的产量和运输量, 使得生产和运输中的费用最小化, 制定最优的生产运输方案。

1 问题描述和模型

假设每个产销中心周围存在对产品的需求;产销中心生产每种产品的能力、费用, 及对该种产品确定的需求;在两个产销中心之间有着固定的运输费用;运输所有产品的费用是相同的, 卡车的平均运输能力为M。

整数规划模型如下

$\min {\displaystyle \sum _{k=1}^n{\displaystyle \sum _{i=1}^{m}c}}{}_{ki}x{}_{ki}+{\displaystyle \sum _{i=1}^m{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^m{\rm M}}}d{}_{ij}u{}_{ij}.(1)$

模型参数为:i, j=1, …m为第i、j个产销中心;k=1, …, n为第k种产品;M为运输能力;ski为产销中心i对产品k的需求量;pki为产销中心i对产品k的生产能力;cki为产销中心i生产单位数量产品k所需要的费用;dij为产销中心i运输到产销中心j单位数量产品所需的运输费用。

决策变量定义为:xki为产品k在产销中心i的产量;ykij为从产销中心i运输到产销中心j产品k的数量;uij为从产销中心i运输到产销中心j卡车的数量。

约束条件为

$\begin{array}{l}\{\begin{array}{l}x{}_{ki}\le p{}_{ki},k=1,\cdots ,n,i=1,\cdots ,m,\\ x{}_{ki}\ge {\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^{m}y}{}_{kij},k=1,\cdots ,n,i,j=1,\cdots ,m,\\ {\displaystyle \sum _{k=1}^{n}y}{}_{kij}\le {\rm M}u{}_{ij},i,j=1,\cdots ,m,(2)\\ x{}_{ki}-{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^{m}y}{}_{kij}+{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^{m}y}{}_{kji}\ge s{}_{ki},k=1,\cdots ,n,\\ i,j=1,\cdots ,m,\end{array}\\ \{\begin{array}{l}{\rm M}(u{}_{ij}-1)+1\le {\displaystyle \sum _{k=1}^{n}y}{}_{kij},i,j=1,\cdots ,m,\\ x{}_{ki}\in \mathbf{{\rm Z}}{}^{+},y{}_{kij}\in \mathbf{{\rm Z}}{}^{+},k=1,\cdots ,n,i,j=1,\cdots ,m,\\ u{}_{ij}\in \mathbf{{\rm Z}}{}^{+},i,j=1,\cdots ,m.\end{array}\end{array}$

在实际生产过程中, 由于不确定的因素影响, 参数都在一定的区间内变化。假设产销中心i对产品k生产能力为pki, 实际的生产能力由于生产条件和其他客观因素的限制是达不到pki, 实际的生产能力可能是估计生产能力的100 (1-p) %;每个产销中心的需求量也不确定, 它会随着时间的不同及经济形势的变化而围绕着一个值上下波动, 假设产品在每一个产销点的需求量存在一个±s的波动 (100s%) 。鉴于此, 本文将在建立整数规划的同时, 考虑这些不确定因素, 建立一个随机规划模型。

2 随机规划模型的建立

在随机规划模型中引入两个随机参数εpki、εski, 分别代表i产销中心对产品k的实际生产能力和实际需求量, 在一个置信度α的情况下使总费用最小[5,6]。

生产能力和市场需求的约束条件如下:

目标函数为

$\begin{array}{l}z={\displaystyle \sum _{k=1}^n{\displaystyle \sum _{k=1}^{m}c}}{}_{ki}x{}_{ki}+{\displaystyle \sum _{i=1}^m{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne i\end{array}}^m{\rm M}}}d{}_{ij}u{}_{ij},(3)\\ x{}_{ki}\le \epsilon {}_{p{}_{ki}},k=1,\cdots ,n,i,j=1,\cdots ,m,(4)\\ x{}_{ki}-{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^{m}y}{}_{kij}+{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne i\end{array}}^{m}y}{}_{kji}\ge \epsilon {}_{s{}_{ki}},k=1,\cdots ,n,i,j=1,\cdots ,m.(5)\end{array}$

模型如下:

$\{\begin{array}{l}\min \overline{z}\\ {\rm P}{}_r\{\omega \in \text{Ω}|z={\displaystyle \sum _{k=1}^n{\displaystyle \sum _{i=1}^{m}c}}{}_{ki}x{}_{ki}+{\displaystyle \sum _{i=1}^m{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^m{\rm M}}}d{}_{ij}u{}_{ij}\le \overline{z}\}\ge \alpha ,\\ {\rm P}{}_r\{x{}_{ki}\le \epsilon {}_{p{}_{ki}}\}\ge \beta {}_1,k=1,\cdots ,n,i,j=1,\cdots ,m,\\ x{}_{ki}\ge {\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne 1\end{array}}^{m}y}{}_{kij},k=1,\cdots ,n,i,j=1,\cdots ,m,\\ {\displaystyle \sum _{k=1}^{n}y}{}_{kij}\le {\rm M}u{}_{ij},i,j=1,\cdots ,m,(6)\\ {\rm P}{}_r\{x{}_{ki}-{\displaystyle \sum _{\begin{array}{l}k=1\\ j\ne 1\end{array}}^{m}y}{}_{kji}\ge \epsilon {}_{S{}_{ki}}\}\ge \beta {}_2,k=1,\cdots ,n,i,j=1,\cdots ,m,\\ {\rm M}(u{}_{ij}-1)+1\le {\displaystyle \sum _{k=1}^{n}y}{}_{kij},i,j=1,\cdots ,m,\\ x{}_{ki}\in \mathbf{{\rm Z}}{}^{+},y{}_{kij}\in \mathbf{{\rm Z}}{}^{+},k=1,\cdots ,n,i,j=1,\cdots ,m,\\ u{}_{ij}\in \mathbf{{\rm Z}}{}^{+},i,j=1,\cdots ,m.\end{array}$

其中:α、β1、β2为决策者预先给定的置信水平, min$\overline{z}$是α的乐观费用。

3 应用算例

5个生产销售中心生产3种不同类型产品a1、a2、a3, 假设运输过程中3种产品可以同时用卡车运输。案例中的生产商拥有5个区域产销中心:Hiroshima、Osaka、Nagoya、Tokyo、Sendai。[7]产品在这5个区域进行运输, 每种产品可以按照形状、颜色、材质分为10到30个类型。本文是为了在它们之间找出生产运输中的最优或满意解。不能取得客户的账单, 因此处理的问题只有5个产销中心和3种产品, 但是这些限制并不影响对问题的研究。每个地方的生产费用、生产能力及需求见表1。

把表1中的参数与随机规划相结合, 假设每个地方市场需求存在20%的上下波动, 每个产销中心的生产能力可能在预计能力的80%, 即s=0.2、p=0.2, εpki, εski 的分布函数为εpki～U (pki, 80%pki) , εski～N (ski, 0.04s${}_{ki}^2$) ) , 置信度α=0.90, β1=β2=0.95。模型的结果见表2、表3。

4 结束语

本文在多个产销中心的前提下研究生产运输规划, 首先运用整数规划建立模型, 然后考虑不确定因素, 并结合算例和随机规划对问题建立随机混合整数规划模型。考虑到参数的随机估计, 最后把模型和生产商的实例相结合, 进行计算机编程求解, 对模型进行测试, 获得满意解。

摘要：从决策者的利益出发对生产销售中心的生产费用和生产销售中心之间的运输费用进行研究使得客户的成本最小化。依据生产销售中心实际生产能力和市场需求, 制定生产销售中心的实际产量和运输量计划, 以达到生产运输成本最小。在不确定环境下, 把随机机会约束和混合整数规划相结合, 计算出在一定置信水平下的最优解, 制定稳健的生产运输方案。

关键词：最优化,生产运输问题,不确定规划,随机机会约束

参考文献

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

[2]刘宝碇, 赵瑞清.随机规划与模糊规划[M].北京:清华大学出版社, 2003.

[3]赵玮, 王荫清.随机运筹学[M].北京:高等教育出版社, 1993.

[4]Liu B D, Iwamura K.Chance constrained programming withfuzzy parameters[J].Fuzzy Set and systems (S1000-1506) , 1998, 94 (2) :227-237.

[5]高雷阜.不确定规划模型及其算法研究[J].辽宁工程技术大学学报, 2003, 22 (3) :413-415.

[6]Masatoshi Sakawa, Ichiro Nishzaki, Yoshio Uemura.Fuzzy pro-gramming and profit and cost allocation for a production and transportation problem[J].EUROPEANJOURNAL OF OPER-ATIONAL RESEARCH, 2000.

随机约束 篇2

关键词：报童问题,服务水平约束,随机需求,模型

0 引言

需求不确定情况下的进货问题是多数企业经常面临的现实问题,如果企业满足顾客需求的概率已知,那么在商品销售期间,企业的最优进货量与频次可以采用报童模型来确定,可使企业的期望利润最高或者期望损失最小。

2 模型

2.1 模型描述与假设

企业经营中有这样一类产品,它们品种不同,类型各异,单价差别较大,但具有一些共同的特点:①具有明显的季节性;②产品在销售季节或保质期内的需求具有不确定性;③考虑到商品品种多样化的要求,为防止仅考虑本类产品的利润而造成可能的较低的服务水平,从而导致顾客满意度下降影响超市整体利润,产品的服务水平必须控制在一定的水平。要求根据以上情况,确定该类商品每次的进货量。现做如下符号说明与假设:

商品的服务水平指商品能够满足顾客需求的程度,本文用缺货率来描述:服务水平=1-缺货率,即服务水平越高,缺货率越低;反之服务水平越低,缺货率越高。k:商品在销售季节或保质期内的单位销售利润,假设为定值;h:商品在销售季节或保质期外单位损失,假设为定值;r:商品在销售季节或保质期内的销量,为随机离散变量,假定为正整数;P(r):商品在销售季节或保质期内的销量为r时的概率,;β:商品缺货率上限;Q:商品的进货量,假定为正整数;C(Q):产品进货量为Q时的期望损失;L(Q):产品进货量为Q时的缺货率;假定销售期内只能进货一次。

2.2 模型建立

根据上述描述,建立以缺货率为约束、期望损失最小为目标的规划模型,如式(1):

其中:

含义为:期望损失由两部分组成,表示当进货量大于实际销量时,由于产品过季滞销造成的损失;表示当进货量小于实际销量时的机会损失。

2.3 模型求解

模型求解分为两个步骤:

(1)先不考虑约束条件,直接求目标函数对应的订购量Q*,并计算相对应的缺货率L(Q*);由于进货量Q为离散的整数,可知若要C(Q)最小,需满足式(4):

根据式(2),(4)有:

因此Q*可由式(5)确定。

(2)比较L(Q*)和β,若有L(Q*)燮β,则Q*即为模型的最优解;否则最优进货量Q可由式(6)确定:

分析:L(Q*)>β说明不考虑服务水平约束得到的缺货率大于要求的缺货率上限,为降低缺货率,必须增加进货量,即最优进货量Q>Q*,显然Q越大缺货率越小,但期望损失越大。为使目标函数最小,只要能证明C(Q)在Q>Q*为增函数,然后按式(6)确定的Q即为模型的最优解。

即C(Q)在Q>Q*时为增函数,因此可知,当L(Q*)>β时,为减少缺货率,可增加进货量Q,直到满足缺货率的最小Q,即为期望损失最小的进货量,即满足式(6)的Q为模型最优解。

3 算例

某超市每天销售一种蔬菜,每售出一个单位可获利润300元,该种蔬菜保质期为一天,当天不能售完则每一个单位损失130元。根据以往的统计资料,该种蔬菜每天的需求量概率见表1,为维持一定的服务水平,超市规定该类蔬菜缺货率不能高于于12%,试确定合适的进货量使期望损失最小。

期望利润的比较:

可以看到,考虑缺货率限制后,超市中该种商品的期望损失增加,即期望利润减少,但由于降低了缺货率,可以增加顾客的满意度,即加强了服务水平,必须采取其它销售手段增加超市的利润来弥补这部分损失,可以从整体上带来持续的盈利。

4 结论

本文研究了一类具有随机需求并受服务水平约束的商品进货量问题,建立了最优进货量数学模型,得出了最优进货量的计算方法,为蔬菜、水果、生肉、月饼等类商品进货量决策提供了理论依据。

参考文献

[1]Khouja M.The Single2Period(Newsvendor)Problem:Literature Review and Suggestions for Future Research[J].Omega,1999,27:5372553.

[2]Das B,Maiti M.An Application of Bilevel Newsboy Problem in Two Substitutable Items under Capital cost[J].A p pl ied Mathematics and Computation,2007,190:4102422.

[3]周艳菊,邱菀华等.不同约束下多产品报童问题解的比较研究[J].系统工程与电子技术,2008,30(1):97-103.

随机约束 篇3

随着全球能源和环境问题的日益突出,风能等可再生能源发电技术得到迅速发展,风电并网的规模也越来越大[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台常规机组的燃料耗量,

,其中,Pi,t为第i台常规机组在时段t的发电功率,Ai,2,Ai,1,Ai,0为第i台常规机组的耗量特性系数,对于水电机组,有Ai,2=Ai,1=Ai,0=0;E{·}为期望函数;Πt为xt的可行域。

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模型的求解速度。以某一实际省级电网为算例,通过与场景法和鲁棒优化调度方法的比较验证了所提出模型和求解方法的正确有效性。

随机约束 篇4

传统的运输问题可以转化为一个标准的线性规划,通过表上作业法、单纯形法或lingo软件等求解。在实际的运 输过程中,常受到许 多因素的 限制,如运输时间、选择的路径、费用、运输的安全可靠性等。在传统运输问题的基础上发展形成了多 目标运输问题,对于确定性的多目标运输问题有了较成熟的解决方案。虽然多目标运输问题对解决现实问题提供了有效的解决手段,但在一些具有随机性的现实问题中还是不能精确 地描述。李珍萍等对带时间窗约束的运输问题进行探讨,但只是限于经典模式下的运输问题,没有涉及到随机条件下的此类问题。

已有许多文章对运输问题进行研究和探索,但在实际运输问题过程中,是一个复杂的受多种不确定因素影响的优化问题,为此,在传统经典运输问题的基础上,增加了运输过程中运输线路能力的约束,运输过程中的时间约束由于一些意外原因,如可供应量、需求量、线路能力、时间等都 具有随机 性,提出一种基于时间约束的随机机会规划运输问题模型,并利用混合遗传算法求解,进行算例验证。

1运输问题模型

1.1传统运输问题

设某物资有m个产地Ai(i= 1,2,…,m),其产量分别为ai(i=1,2,…,m);有n个销地Bj(j= 1,2,…,n);从Ai到Bj运输物资 的单位运 价为cij(i=1,2,…,m;j=1,2,…,n);

在产销平衡的条件下,即的数学模型为

但在一般情况下,产销并不能总保持平衡,当产销不平衡时,问题可转化为产销平衡的运输问题模型。

1.2带有时间约束的随机机会约束规划运输问题模型

在实际中通常要考虑其可靠性(或风险),即利于(或不利于)事件发生的概率,为此决策者可根据自己的喜好或一定的目的选择建立运输问题的随 机机会约束规划模型。机会约束规划理论最早是Charnes和Cooper提出的,其特征是随机约束条件参数至少以一定的置信水平收敛。

Liu在机会约束规划提出之后,给出在随机环境条件下,若决策者希望极大化目标值函数的乐观值,建立如下的机会约束规划模型

其中约束条件中第 一个是目 标约束,第二个是联合机会约 束,a和β是决策预 先给定的 置信水平。

在现实生活的运输过程中,产地、销地、选择的线路能力、运输时间都存在随机性,但这些约束条件在一定的置信水平成立,虽然已经有一些人对此做了研究,如在需求随机条件下运输问题的机会约束规划模型研 究,对运输问 题进行了 综合实际 考虑,但仍缺少时间约束,因此可建立目标函数为最小费用的 带有时间 窗约束的 机会约束 规划模型, 则有

式中:ulr,vlr为权系数;σl为目标函数的置信水平;αi,βj,ηk为给定的供应量、销量以及线路能力的约束置信水平;tijk为运输过程中需要的时间;Tk为运输过程中最晚到达时间;Tk为软约束;γk为时间约束的置信水平。

2模型求解并验证

在处理机会约束规划模型时,传统的方法是将他们转化为各自的等价形式,但这种情况只在极少数条件下才能成立,而对于一些较复杂的问题难以处理。因此将神经元网络与遗传算法结合起来,设计了混合遗传算法来求解一般的随机机会约束规划模型。

算法步骤

1)用随机模拟技术为上述不确定性模型函数生成培训输入输出的数据;

2)根据得到的输入输出数据进行训练,训练一个神经网络近似不确定函数生成的训练数据;

3)初始化pop_size个染色体,其可行性可由经过训练的神经元网络检查;

4)通过交叉变异操作得到新的染色体,子代染色体的可行性可由经过训练的神经元网络检验;

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

6)根据每个染色体目标值计算其适应度;

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

8)重复第4~第7步骤,直到完成给定的循环次数;

9)找出其中最好的染色体作为最优解。

将随机模拟 技术作为 不确定函 数,则有U ∶ x(U1(x),U2(x),U3(x),U4(x),U5(x)),产生输入输出数据,其中

训练一个神经元网络(3个输入神经元,15个隐层神经元,3个输出神经元),不断地逼近不确定性模型函数U。然后将已训练好的神经元网络与遗传算法相结合,得到混合遗传算法。

史峰在MATLAB智能算法的30个案例分析中,对遗传算法与神经网络相结合的混合智能算法给出了分析案例,结合书中的分析,通过MATLAB实现设计的混合智能算法。

为验证混合遗传算法对在求解随机机会约束 规划模型 时的有效 性,给出具体 的实例,利用MATLAB编制混合遗传算法程序求解,下面给出在求解随机运输问题时的参数:

1)种群规模为50;

2)交叉概率为0.7;

3)变异概率为0.1;

4)评价函数参数为0.05;

5)迭代次数为200;

6)训练次数为3 000;

7)模拟次数为5 000。

实例:给出有两个供应店,两个销售点,两种运输方式的示例。假定目标费用最小,费用、时间、线路能力等约束条件服从某种分布的随机变量,相关参数数据如表1~表3所示。

在表1中:u(a,b)表示该参 数服从区 间为 [a,b]均匀分布的随机变量;N(μ,σ2)表示该参数服从期望为μ,方差为σ2的正态分布的随机变量; T(a,b,m)为参数服从三角分布的随机变量。

利用MATLAB软件,通过混合遗传算法进行求解,得出最优解为

从以上结果可以看出带有时间窗的随机机会约束规划模型的求解结果比较理想。

3结束语

从不确定角度对随机参数建立运输问题模型, 并在经典的运输问题基础上增加了时间窗约束和线路能力约束,因此模型从经典的运输问题线性规划转变为非线性规划,增加了求解的难度,很难找到最优解,但是本文利用混合遗传算法求解此类非线性规划模型案例,并对解进行优化,可以找到最优解。

摘要：对传统经典的运输问题从不确定性随机规划角度进行探讨分析,针对随机环境条件下的此类优化问题提出一种随机机会约束规划模型,并考虑在运输过程中的线路能力和时间窗限制,对其利用随机机会约束规划的思想进行处理,建立随机机会约束规划运输问题的数学模型。此外,由于模型涉及大量具有复杂性和随机性的随机变量,设计一种混合智能算法,即基于随机模拟的神经网络遗传算法来求解模型的近似最优解。最后利用数值算例来验证算法的有效性和可行性。