动态最优范文

动态最优范文（精选8篇）

动态最优 第1篇

广告作用于消费者, 促成其购买行为, 大多数情况下并不是一次、一时或一种信息和媒体作用的结果, 而是广告信息的多次重复的累积效果的体现。在尚未发生购买行动之前, 都是广告效果的累积时期, 通过连续、多次的广告, 强化影响, 使得量的积累转化为质的飞跃, 促成消费者购买。实际中, 企业也很少有只发布一次或几次广告的。这也使得很难评估某一次广告的单一效果。张伯伦 (Chamberlin, 1933) [1]可能是最早对广告进行研究的经济学家, 通过建立模型, 他认为广告投入与销售收入的比例 (广告投入规模) 等于广告的价格弹性时企业达到最大利润。1954年, R.Dorfman和Peter O.Steiner (1954) 通过建立多夫曼斯坦纳模型, 在假设边际收益递减规律的前提下说明了最优的广告销售比率取决于广告量和企业产品的需求价格弹性, 由此表明了价格决定和非价格决定之间的相互依赖关系。研究结果表明如果一个企业能控制其某项产品的价格、质量和广告支出, 那么, 当利润达到最大化时, 需求价格弹性的绝对值、边际广告收益 (销售反应) 、产品质量弹性的绝对值这三者完全相等[2]。鲍莫尔 (W.Baumol, 1967) [3]提出了以销售收入最大化为目标的静态模型, 并为霍金斯 (C.J.Hawkins, 1970) [4]、凯夫格里斯和布什内尔 (M.Kafoglis&R.Bushnell, 1970) [5]发展。该模型认为企业的最佳广告投入取得必须达到边际成本>边际收入, 此时总收入最大, 但利润不是最大。Nerlove和Arrow则在Dorfman和Steiner的模型中加入商誉 (goodwill) 积累和衰减因素, 提出了Nerlove-Arrow模型 (Nerlove&Arrow, 1962) [6]。任方旭 (2001) 等人运用需求函数、价格需求弹性理论, 分析广告投入不变时的最优产品价格策略, 运用广告需求弹性理论, 分析产品价格、广告水平同时变化时的最优策略[7]。梁云 (2005) 等人研究了在广告与价格联合模型中, 分析在位企业与进入企业对广告与价格两种竞争手段的组合运用[8]。

以上模型大多从静态的角度来分析, 实际上, 广告具有时间性, 是一个动态的过程, 从动态的角度, 制造商应如何决策广告投入?这是本文所要研究的内容。

一、问题分析与模型建立

事实上, 制造商做广告的目的就是为在消费者中形成良好的商誉。假设在第菖期做的广告, 对该期之后的产品销售也有一定的影响, 即所谓的商誉存量。当期广告对未来需求的效应无疑要小于当期广告对当期需求的效应。但当期广告对未来需求的效应并不为零。m表示制造商的广告投入。一般情况下, 商誉与广告投入成正比例, 在此处用M来表示商誉。

动态广告投资策略问题是最优控制问题, 其实质上就是找到一种能使经营企业的目标泛函达到极大值的广告投资策略。而制造商的投资不可能无穷大, 设制造商的广告投资为m, 且, 仍用M表示商誉积累。由于考虑到商誉积累, 因此当期的市场需求只与当期的商誉积累有关。

根据文献[6]设制造商的需求函数可表示为商誉积累的关系式:

则其利润函数为:

事实上广告的作用虽然能扩大商品的销路, 但是随着时间的推移, 如果没有做任何关于产品的广告, 那么人们对该商品将逐渐忘却。因此, 广告商誉也会减少。那么此时制造商就必须进行广告投资, 一部分是弥补过去商誉的折损, 一部分是增加未来的产品商誉。设δ为商誉折旧, 则商誉的增加与广告投资满足如下关系式:

假设在初期即t=0时, M (0) =m0。

根据以上分析, 制造商的利润极大化问题可以表示为:

二、模型分析

命题1:当足够大, 式 (2) 有最优解:

证明:根据变分法原理, 得到Euler方程为:

因此得到:, 因此该商誉存量的调整不具有动态特征。但由于受到广告投资的约束, 会出现最快到达的问题。

当M0

随着时间推移, M (t) 沿着路径, 一直到达Ms, 然后沿着Ms移动。

而当时, 解得:。

考察ts, 假设足够大。如果不是足够大, 那么M (t) 沿着路径不能到达Ms, 而是会沿这条路径一直增长。如果足够大, 使得沿路径可以到达Ms, 因此, 有和, 从而能保证ts>0。

因此最优解为:

命题2:存在一个起始的区间, 在这个区间上, 广告的支出为一常数。

证明:通过可以得到随着时间推移, 当t>ts时, 由式 (1) 、式 (2) 得到, 其变化 (如图1所示) :

从以上模型可以看出, 该模型反映了产品的生命周期中不同阶段投入广告的策略。例如在产品生命周期之初, 应投放开拓型广告, 主要为推广新的产品、观念或者服务而发布广告, 其目的是为吸引消费者的注意, 进而了解和购买。随着产品逐步被消费者购买使用, 产品进入成长期与成熟期, 就会有更多的企业加入市场。那么, 在初期、成长期、成熟期广告费用都会逐渐增加, 最后在产品衰退期广告费用维持一个固定的值, 一般此时广告宣传侧重用商标、企业形象来提醒消费者, 使他们继续购买。

结束语

本文从连续的角度, 运用最优控制理论, 得出了广告投入在不同时期的最佳广告投入水平, 为企业提供了广告投入的决策凭据。实际上, 从连续的角度, 本文假定了产品价格是给定的, 只是单方面考虑了广告投入, 分析价格与广告投入同时变化时的最优决策将进一步研究。

摘要：广告的作用是多次重复的累积效果的体现, 其目的就是为在消费者中形成良好的商誉。从连续的角度, 运用最优控制理论, 得出广告投入在不同时间的投入水平。

关键词：广告,动态,连续

参考文献

[1][英]张伯仑.垄断竞争理论[M].北京:华夏出版社, 2009.

[2]Dorfman, Robert and Steiner, Peter O.Optimal advertising and optimal quality[J].American Economic Reviezu.1954, (44) :826-836.

[3]Baumol, William J.Business Behavior, Value, and Growth[M].New York:Harcourt, Brace&World, 1967.

[4]C.J.Hawkins.On the Sales Revenue Maximization Hypothesis[J].Journal of Industrial.Economics, 1970, (13) :223-234.

[5]Kafoglis M, Bushnell R.The revenue maximization oligopoly model:comment[J].Am Eco Rev 1970, (3) :427-428.

[6]Nerlove, Marc.Arrow, Kenneth J.Optimal advertising policy under dynamic conditions[J].Economical, 1962, (29) :129-142.

[7]任方旭, 邵云飞, 唐小我.用需求弹性确定广告、产品价格竞争策略的研究[J].郑州航空工业管理学院学报, 200l, (4) :35-40.

动态最优 第2篇

关键词:CVaR模型自融资策略动态组合最优

一、引言

Matkowitz投资组合理论是现代金融的开端,均值-方差模型形成了金融风险管理的框架。从理论的观点来看,均值-方差模型存在两个亟须改进的问题:

1、风险测度。方差作为风险测度最大的缺点就是把高于均值的部分纳入了风险,显然:这一部分真是我们所需要的。在此基础上,很多学者提出了下偏风险理论。VaR就是基于下偏风险提出来的,同时还是近些年来提出的也是最重要的风险测度。但是VaR存在一些缺点,尤其体现在资产分布存在尖峰厚尾性上,同时VaR还不满足次可加性,次可加性是一致性风险的重要性质。本文针对VaR的这两个缺点,提出了CVaR(Conditional Value at Risk),也被成为尾部VaR,平均超值损失和平均不足量。

2、时间模型。传统的投资组合策略选择采用单期模型,很明显这与现实存在很大差异,然而,动态的均值-方差模型存在很多的困难,直到2000年,动态的均值-方差模型最优策略才被研究出来。

本文采用连续时间的动态模型,在期权定价的背景下,假定股票价格服从带有漂移项的几何布朗运动,用CVaR做为风险测度研究投资计划期[0, T]下的最优投资策略。

二、市场模型

考虑这样的资产市场,有n种风险资产和1种无风险资产。

表示第i种风险资产在时刻t的价格,,

,表示无风险资产在时刻t的价格。由模型得出的资产价格的微分方程为:

这里,r表示无风险利率,表示一个标准的n维的布朗运动,表示风险资产的期望收益率向量, 表示风险资产的波动率矩阵,

表示σ的第i行向量。并假定波动率矩阵满足非退化(non-degeneracy)条件

其中为给定常数,I为n×n单位矩阵。

由于风险和收益相匹配原理,我们可以一般性的假设:

。

在这篇文章里,我们全部使用自融资的投资策略,即:除了初始资本投资外,不会追加资本投资,而且保持投资比例不变。也就是说:

= ,。为一个不变的投资组合,其中表示投资于风险资产i上的财富比例。用 表示当投资者采取允许投资组合时的财富过程,那么它遵循如下微分方程

其中1n表示分量全为1的n维列向量,x表示投资者的初始资本。

应用Wick-Ito积分,解微分方程(1)得到:.

同时也可以得到: (3)

对给定的置信度,我们用表示标准正态分布对应置信度α的分位数。因为我们主要关注下偏风险,所以我们限定 ,这样有。

命題1 对应置信水平α财富过程的分位数 的表达式为

证明:设=

易得: ~

的对应置信水平α的分位数为:

由于是一个严格单调函数,所以有:

所以:

命题2

的含义是“条件在险价值”,是指损失超出的条件均值,也称平均超值损失。

三、最优策略

本文定义的最优投资策略是根据Matkowitz的均值-方差模型,指在以给定的风险值下,对期望终端财富最大化模型,用数学模型表示为:

四、有效前沿

通过上述最优策略的研究得知,满足最优策略的条件有两个:

这个方程所对应的图像就是均值- 的有效前沿边界。

五、结论

本文使用了 作为风险测度,代替了 ,体现出了 的优点,本文的研究结果似乎也很令人高兴,然而现实中资产分布并没有完全像几何布朗运动刻画的那样,很多研究表明:除了尖峰厚尾性的分布外,股票价格还具有自相似性和长相依性,所以,本文需要完善的地方还有很多,现在已有分式几何布朗运动作为模型的改进,同时风险测度的方法也有很多,我认为研究的空间还是很大的。

参考文献:

[1]王春峰 金融市场风险管理[M].天津:天津大学出版社. 2001

[2]Merton, R.C.: Optimum consumption and portfolio rules in a continuous-time model. J. Econ. Theory3, 373-413 (1971)

[3]Artzner, P., Delbaen, F., Eber J.-M., Heath, D.: Coherent Measures of Risk.Mathematical Finance. 9, 203-228 (1999)

[4]Jorion, P.: Value at Risk: The New Benchmark for Controlling Market Risk. McGraw-Hill, New York(1997)

[5]Li, D., Ng,W.L.: Optimal dynamic portfolio selection: multiperiod mean-variance formulation. Math.Finance 10, 387-406 (2000)

[6]Emmer S, Klüppelberg C, Korn R. Optimal portfolio with bounded capital at risk[J]. Mathematical Finance, 2001, 11: 365-384.

动态规划法之最优性原理教学 第3篇

并非所有问题都适用动态规划法。只有满足最优性原理的问题才适应该方法，称最优化问题。这类问题往往在满足约束条件的前提下，通过目标函数的评价寻找最优解。最少硬币数付款问题、矩阵连乘问题、最优三角剖分问题等都是常见的经典最优化问题。0/1背包问题也在对物品价值取值离散化之后也能适用动态规划法[3]。动态规划法是传统算法手段中最有价值的一种，也是教学难度最大的一种。动态规划法是算法课程的重点。而最优性原理则是动态规划法的教学难点，是该算法教学成败的关键。

1 正确理解最优性原理

最优性原理又称最优子结构性质。具有该性质的问题的特征是：原问题最优解中包含其子问题的最优解。这是适用动态规划法的必要条件。理解这一条件时容易出现偏差。原问题所含的全部子问题的最优解是否都包含于原问题的解之中呢?初学者常常认为原问题的任意分解方式得到的所有子问题的最优解都包含在原问题的解中。这样的解其实不存在。学习的关键在于正确识别原问题最优解所导出的子问题，只有这些子问题的最优解才包含在原问题最优解之中。以下用矩阵连乘问题[4]为例分析。

x行y列的矩阵与y行z列矩阵相乘，需进行x*y*z次乘法运算。给定n个矩阵M1 M2Mn，其中相邻矩阵可乘。矩阵乘法满足结合律，所以n个矩阵连乘有多种运算次序，希望找到一种最佳次序，使总计算量最小。设有四个矩阵A,B,C,D连乘。

错误的理解方式为：原问题是ABCD，其子问题有九个，分别是A、B、C、D、AB、BC、CD、ABC、BCD、ABCD。

其实特定运算次序只包含部分子问题，而不是包含所有潜在的子问题。初学者按照错误的方式去分析将不能识别最优化问题。正确的理解方式为：由原问题最优解导出若干子问题，只有这些子问题的最优解包含在原问题的最优解之中。原问题为ABCD，运算次序不同则该问题包含的子问题不同。用括弧确定运算次序。如A((BC)D)表示先由BC相乘，结果再与D相乘，最后由A与之相乘。这一过程仅有六个子问题，它们是A、B、C、BC、BCD、ABCD。若这一运算次序是原问题的最优解，那么其中BCD的最优解为(BC)D，而不是B(CD)。

学生常陷入错误理解。既然连最优性原理都不能理解，就更谈不上其证明，所以会感到动态规划法特别难。即使通过模仿掌握少量特定问题的动态规划法求解过程，也难举一反三。需要经过很长时间才能学会动态规划法。教学中教师应注意及时引导学生采取正确的理解方式，从而提高学习效率，也能帮助学生减少畏难情绪。

2 最优性原理的证明

矩阵连乘问题有着大量不同的运算次序，穷举检验各次序所包含的子问题是否取得最优解是不现实的。而证明某问题符合最优性原理是运用动态规划法的关键。其证明常用反证法[5]。先假设由问题的最优解导出的子问题的解不是最优的，然后设法说明此时可以构造比原问题最优解更好的解，从而矛盾。

将矩阵连乘积Mi Mi+1Mk简记为M[i:k]，ik。设M[i:k]的最优计算次序在j处断开，ij

证明：用反证法。假设原问题最优解所包含的(M1M2Mj)和(Mj+1Mj+2Mk)的计算次序并非它们的最优次序。那么必有更优的M[i:j]或M[j+1:k]。以二者合并可得M[i:k]，使得新解优于所谓的原问题最优解。矛盾。原理得证。

3 自底向上的递推求解

最优性原理保证了能够通过合并子小问题最优解得到更大问题的最优解。因此可以用自底向上的方式求解。先求解最小的各种子问题的最优解，再逐步将小问题合并为更大的问题，直到求解出待解问题为止。为了能实现解的合并，常需建立递推式。矩阵连乘例子中设Ai有Wi-1行Wi列。计算A[i:k](1ikn)所需要的最少数乘次数c[i,k]，则原问题的最优值为c[1,n]。i=k时，A[i:k]=Aj,c[i,i]=0,i

最优化问题常常是从子问题的组合中选优作为更大规模问题的解，这就是所谓的合并过程。但是也特殊情况下，合并过程无需选优。例如自底向上求解斐波那契数列F(n)。F(n)=F(n-1)+F(n-2)。教学时应向学生解释这些合并方式的特点。并举出多个例子来强化，斐波那契数列、还有三角剖分、TSP等问题都是鲜明的例子。

设有4个矩阵其维数分别为A1=4*2,A2=2*3,A3=3*5,A4=5*1。利用表格记录各子问题的最优解，避免重复计算。该问题的的最优解为A1(A2(A3A4))，共需29次乘法运算。

4 教学效果分析

教学中注重发现学生对最优性原理的错误认识，及时引导其正确思考，加快了学生对动态规划法的掌握，在有限时间内能学习更多的例子，掌握的程度也比改进教学之前大为提高。

参考文献

[1]秦裕瑗.Bellman最优性原理[J].应用数学,1994(7).

[2]王红梅.算法设计与分析[M].北京:清华大学出版社,2006.

[3]孙红丽.背包问题的算法设计与分析研究[J].电脑知识与技术,2008(9).

[4]王晓东.算法设计与分析[M].3版.北京:清华大学出版社,2010.

动态最优 第4篇

关键词：发电企业,竞价策略,最优动态,环境分析,模型构建

2002年我国电力行业打破了原来的垄断模式,进行了“厂网分开,竞价上网”的改革,将竞争引入发电环节,上网竞价成为了发电企业竞争的重要因素。由于电力商品的特殊性和电力生产的复杂性,电力市场条件的不稳定和信息的不对称,加大了发电企业竞价的难度。因此,结合电力市场实际现状,对发电企业的竞价策略研究成为现阶段电力市场的重点工程。

一、发电企业竞价环境分析

电力市场是电力的买方和卖方相互作用以决定其电量和电价的过程。更具体的来讲,电力市场是采用法律、经济等手段,本着公平竞争、自愿互利的原则,对电力系统中发电、输电、供电、用户等各成员组织、协调运行的管理机制和执行系统的总和。电力市场的基本特征是开放性、竞争性、网络性和协调性。电力市场是指电力生产、输送、配用和销售关系的总和。其中包括市场主体、市场客体、市场载体、市场价格、市场运行规则和市场监管等要素。这些要素相辅相成,缺一不可。

(一)市场信息和交易规则

发电企业上网竞价主要针对剩余未平衡或政府扶持行业的电量竞价,并不影响合同电量的交易方式。发电企业以机组为单位,电量为机组所能达到的最小出力点进行竞价,国家电网通过对发电企业的报价进行网损修正,最终以市场购电费用最低为目标进行的竞价交易。

整个电力市场的竞价运行过程分四步走,见表1。

表1竞价运行过程

(二)山西省电力市场竞价现况分析

2014年山西省组织了第一次电力市场竞价。主要针对第三季度的剩余电量,总电量为12个亿。最终只成交了5亿,剩余电量由双边撮合达成交易。2015年2月10日国家电网山西地区组织了山西省第二次电力交易,本次交易主要针对大用户进行交易,参与的用户是电解铝行业,其中四个电解铝企业总申报电量为58个亿。参与的发电企业限定为30万千瓦时以上的火力发电企业,大约30个发电企业。,2月10日上午开展了竞价指导会议,于当日14时至16时开放交易平台,整个报价和竞价过程在电力交易平台上实施,17时电力交易平台自动生成交易结果。主要采取竞价撮合的竞价方式。

每个发电企业只允许一台机组参与(即30万或60万机组),核算电量按照一台机组的发电量上限作为核算依据;对发电企业有最高限价,最高限价为0.3772元/千瓦时;用户有最低限价,其价格为0.3022元/千瓦时;买方价格按照由高到低排列,卖方价格按照由低到高排列,最终买价不低于卖价,交易方能成交,最终成交价格为买方报价和卖方报价的平均值。若卖方报价相同时,按照发电量大的发电企业优先;发电量一致时按照南区优先,除此之外,可按照联合交易的优先或环保平均分高的优先等原则;卖方不支持阶梯报价,支持成交后两个买方,最终交易结算分别按照各自成交价格进行结算。

现阶段山西省电力市场竞价仍处于起步阶段,第二次的58亿电量全部交易成功。根据竞价结果分析可得:

1.竞价规则中对用户(买方)限制最低报价,其价格为0.3022元/千瓦时(即302.2元/MWH),最终交易价格为买方价格和卖方价格的算术平均值,由最终交易价格可得出最高的成交价格为238元/MWH,最低的成交价格为194.8元/MWH,假定用户(买方)均报最低价,则可得到中标的发电企业(卖方)的报价中最高的价格为173.8元/MWH,最低价格为87.4元/MWH。发电企业为了得到中标电量,而采取盲目的报低价,很有可能导致利润的负增长。

2.整个竞价过程参与竞价的发电企业至少有30多个,然而竞价成功的发电企业主要集中于华能和漳电。其中漳电的各个电厂报价均很低,甚至只是发电企业的基本发电成本,对于发电企业而言,增发的电量对利润影响不大。如果在竞价体制中存在着这样的合谋报价的现象,会导致不公平竞争,长此以往下去,不利于市场的正常发展。

3.本次竞价主要针对的电解铝产业,其最终成交价格均低于合同电量的合同价格和大用户的协商价格,为电解铝产业用户在电价方面得到了很大的经济让利,但是这样的行业保护行为,并不利于整个市场的发展。

综上所述,我国在政策上逐步推行电力市场的竞价上网,发电企业竞价现状并不成熟,如何竞价成为电力行业的焦点问题。

二、最优反应动态机制模型构建

通过博弈各方对信息的了解情况和博弈各方的行动顺序不同两个角度,对博弈进行分类。其中只要有一方对其他博弈方的信息不完全了解均属于不完全博弈,只有对信息全部知情才属于完全信息博弈。静态博弈通常指决策者同时行动或者彼此间并不知情行动的先后顺序,动态博弈通常指决策者的行动有先后顺序,且后决策者可通过观测先决策者的行为结果制定相应的行动。

(一)最优反应动态机制原理

最优反应动态属于进化博弈理论中较为典型的动态机制,主要适用于少数有限理性博弈方之间的重复博弈,且博弈方具有快速学习的能力和策略进化。在此理论机制下,一次博弈结束之后,博弈方会对本期博弈的结果进行分析和总结,对自身的策略进行相应调整。经过博弈方多次不断地调整策略的过程,最终根据“进化稳定策略”(Evolutionary Stable Strategy,ESS)给出博弈的均衡解。在这种理论机制中,最终并不能得到博弈各方的最优策略,而是体现出博弈各方策略调整的趋势。

(二)主观判断因素的引入

由上述理论可知ESS的定义如下:假设x是博弈U的一个竞价策略组合,如果存在任意的ε,则对于任意的y≠x和ε∈(0,1),均满足:

则称x是一个进化稳定策略,其中u(策略1,策略2)表示博弈方在双方策略为(策略1,策略2)时的收益。ESS表示整个博弈各方抵抗其他因素侵袭的一种稳定状态。

本文的研究主要基于以下假定条件:

假定在电力市场中有n个火力发电企业,即说明有有限个发电企业,由于发电企业有着行业壁垒,发电企业的个数不会发生大幅度的变动。实际竞价过程中,发电企业主要通过报价和电量来进行竞争。

发电成本主要有固定成本和变动成本,与发电量有着密切关系,因此本文假定成本函数为二次函数,形式如下公式2.2.2所示。

发电企业的成本函数为:

其中,am、bm、cm为成本参数,Pm表示发电企业m的竞标电量(即最大供电量),假定电力市场电量的总需求为Q,各竞价的发电企业可以提供的最大供电量为Pm,max。

所有发电企业能够提供的最大供电量之和为。同时考虑整个电力市场的供需平衡和各个发电企业的最大供电量情况,各发电企业的中标电量符合以下条件:

电力市场开始竞价时,各个发电企业向电力交易中心提交各自的报价情况。Fm=Fm(Xm,Pm),其中Xm为报价曲线的参数。交易平台结合各个发电企业的报价和竞标电量,将报价按照由低到高的顺序进行排列,直到竞标电量总和满足电力市场的总需求为止,最终由交易平台公布各个发电企业的中标电量。

各个发电企业仅通过对自身的情况和预测的市场供需情况进行报价,假定不存在各个发电企业之间的联合报价。竞价的发电企业的收益函数为:

发电企业竞价时不仅考虑其发电的成本、竞价收益,在做出竞价决策时,个人的主观判断往往也会对最终竞价策略有很大的影响。其中,本文参考期望效用理论和累积前景理论,结合现实中发电企业的主观判断的影响因素对原有的最优反应动态理论模型进行改进。

收益效用函数为:

式中:r和δ分别表示收益部分和损失部分价值函数的敏感程度,本文为了简化研究,假定r=-δ,则收益效用函数为:

其中,Wm为收益的参考点,假定参考收益等于发电企业m的中标电量Qm与发电企业以往成交电量的电价平均价格Ft,即Wm=FtQm。

假设每个发电企业只有两种策略选择:高价策略和低价策略,假设发电企业采取高价策略且竞价成功的概率为y,采取低价策略且竞价成功的概率为z,市场中采取高价策略的发电企业个数为d,则可得知采取低价策略的企业个数为n-d。整个电力市场中全部电量中采取高价策略的发电量为,采取低价策略的那部分发电量为。

下面分别对电力市场不同的供需情况进行讨论。

1.电力供不应求或供求平衡时,即pmax≤Q,则发电企业采取高价策略一定可以成功。此时y=1,所有的发电企业将采取报高价的策略。当Q>pmax时,发电企业所报高价会不断趋近于市场最高限价。

2. 当电力市场中电力供过于求,且当0≤PL≤Q,可得到z=1时,发电企业采取低价策略一定竞价成功,即z=1,市场中除了采取低价策略的发电企业的发电总量外,剩余的发电电量(Q-PL)将留给了采取高价策略的发电企业。

3.当电力市场中发电量供过于求,且当时Q≤PL≤pmax,即时,发电企业采取高价策略一定失败,即y=0。此时采取低价策略的发电企业将竞争市场所需电量Q,此时

综上所述,当市场竞价电量为Q,参与竞价的全部可发电量pmax和采取高价策略的发电商的个数d三个因素共同作用下,发电企业采取高价或低价策略竞价成功的概率函数如下:

发电企业采取高价策略是可以成功竞价得到的发电量为pm,H=ypm,max,采取低价策略竞价得到的发电量为pm,L=zpm,max。

由于收益效用为,πm=Vm+r骔E(Vm)-Wm」=(1+r)Vm-r FtQm则分别讨论采取高价和采取低价策略的收益效用函数:

采取高价策略的收益效用函数为:

采取低价策略的收益效用函数为:

在每一个离散的时刻t=1,2…,每个发电商选择高价或者低价策略中的将作为本次竞价的策略,根据最优反应动态的定义,最优反应动态方程:

发电企业采取高价策略的收益小于采取低价策略的收益时,下一次竞价时,各个发电企业不会再采取高价策略;当采取低价策略时,收益低于高价策略时,发电企业继续调整报价策略,通过这样不断结合收益情况来改变报价策略,最终达到一个相对稳定的均衡状态。即达到最优状态。在公式2.2.5带入公式2.2.6和2.2.7,在代入公式2.2.8和2.2.9再次得到各个发电企业的竞价均衡点,博弈各方通过对均衡点进行分析,得出下一次竞价的策略。

三、案例分析

(一)假定条件

本文假定有5家发电企业参与竞争,发电企业A的竞争对手分别为B、C、D和E。每个发电企业均有一台燃煤火电机组,并以最大的可供电量参与电力市场的竞价。且这些发电企业有着相同的成本函数和机组容量。发电企业竞价容量段为[300MW,600MW],发电企业成本函数为C(Pi)=0.158Pi2+116.7Pi+19770,其中C(Pi)表示发电企业的成本函数,单位为CNY/(KWh);Pi表示发电企业的实际出力,单位为MW。

假设某一时段的市场电量总需求Q为2000MW·H,且在短时期内保持不变。假定电力市场的最高报价为Fmax=377.2元MW·h,最低报价为Fmix=150.8元/MW·h。用户的最低报价为302.2元/千瓦时,假定各个发电企业能够提供的最大出力即最大发电量为pm,max=600MW·h。

(二)风险厌恶因子的确定

累积前景理论可知,决策者在面对收益时表现为风险厌恶,而面对损失时表现为风险偏好;文中r即为决策者面对收益时表现出的风险厌恶的程度,本文用风险厌恶因子来描述发电商面对收益时敏感的程度。

风险厌恶表示在收益情况未知时,个人或组织对承受风险情况的偏好程度。即用来测量人们为降低所面临的风险而进行支付的意愿。在同样的风险收益情况下,每个竞价者表现出的风险厌恶程度不同。厌恶风险程度高的人往往在做出决策时,为逃避风险而选择利益回报率低一点的策略。对于发电企业的竞价过程而言,竞价者参与竞价会产生一定的风险,中标或不中标的概率都不测,中标与否直接关系着发电企业的收益情况。风险厌恶因子r,其中0<r<1。厌恶因子r越大,竞价者想获得竞标成功的的欲望越强,所以竞价者会尽量降低竞标价格,来提高竞价成功的概率。因此风险厌恶因子的确定,直接影响着竞价者参与竞价时的报价。

影响发电企业对风险厌恶程度的因素很多,通过对兴能发电企业的深度调查,并结合相关文献的梳理,将影响厌恶因子的关键因素概括,如表2所示。

表2 影响风险厌恶因子的关键

由于这些因素不能进行很好的量化,而且面对不同的企业有着不同的预估,因而对这些因素进行评估具有很大的模糊性,本文将通过建立模糊综合评价模型对这些因素的影响进行权重分析,通过量化风险厌恶程度来确定出风险厌恶因子的大小。

首先,确定影响厌恶因子的关键因素。确定影响因素的指标权重系数有很多种方法,如专家打分法(Delphi)、层次分析法(AHP)、主成分分析法、最大熵法、Delphi-AHP法。本文采用专家打分法来确定权重。

设因素集U={ui|i=1,2,…n},模糊集M∈F(U)。由于各影响因素的重要性有差异,在对厌恶因子进行分析时必须判断影响因素的权重。利用二元对比排序方法来得到关键因素的权重,设模糊集M为各影响因素在厌恶因子确定中的相对重要性,权重即为该影响因素在模糊集M的隶属度。

令专家组成评判组,对各个影响因素进行二元对比评估得到模糊优先关系矩阵A([aij]n*n),令aij满足以下条件:

上述条件表明:

(1)ui和uj相比较而言,重要程度上没有什么优越性,则记作aij=0。

(2)ui和uj相比较而言,重要程度不好确认,两者的优越成分加在一起等于1,也即aij+aji=1;

(3)ui和uj相比较而言,重要程度不相上下,则认为aij=aji=0.5。

其次,本文采用平均法来得到模糊集M的隶属函数:

最后,对M中的各个影响因素的隶属度进行归一化处理,进而得到各个影响因素的权重。

假设本文确定的影响因素为四个,因此可以建立因素集U={u1,u2,u3,u4}={成本的高低、企业的综合情况、电力市场的大环境、其他竞价企业的行为},对于各个影响因素进行专家打分,结合李克特的五度量表,根据对各个影响因素的评分进行分析,设打分集B={b1,b2,b3,b4,b5},其中b1表示低,b2表示较低,b3表示中等,b4表示显著,b5表示高。通过各个专家对影响因素进行评判,得到模糊子集D,其D={di1,di2,di3,di4,di5},i=1,2,3,4。

得到评判矩阵为:

通过模糊变换得到,E=DB。

对E进行归一化处理得到F,其中F={f1,f2,f3,f4}。

则厌恶因子r可以表示为:r=φ1f1+φ2f2+φ3f3+φ4f4。

决策者面对收益时,对风险的厌恶程度不尽相同,影响其厌恶程度的因素和各因素的影响程度存在着很大的差异。发电企业必须根据自身的实际情况,提出合理的影响因素,并对其进行真实的评判,才能得到较为正确的厌恶因子。本文通过模糊综合评价法得到的厌恶因子,客观地给企业提供了一个衡量指标。与此同时,企业通过对自身企业的不断完善,增强企业的综合竞争力,来影响其面对收益时的风险厌恶程度。

(三)报价分析

此模型中假定发电企业上网报价最多允许报1段,中标的发电企业按照其报价价格和买方价格的算术平均数进行结算。本文假定用户的最低报价为302.2元/千瓦时。5个发电企业风险厌恶因子对应的策略系数,见表3(见下页)。

发电商在首次竞价时没有可以参考的报价信息,假设各发电商认为各个竞价策略系数下中标电量均匀分布,结算价格即为发电企业报价和用户报价的算术平均值。根据最优反应动态机制的竞价策略的不断调整过程。假定从第13轮开始,这五个发电企业经过短暂的竞价调整后,迅速达到稳定状态,找到各自的最优报价策略系数,并对竞价策略系数不再进行大幅度改变。

整个竞价过程,假定每个发电企业在竞价结束后,结合自身中标电量和结算价格对自身报价策略系数进行调整,体现了发电企业是参照其他竞价的发电企业竞价策略不断选择的过程,这种调整的行为过程即为决策者相互学习的过程,属于最优反应动态机制的研究范围。

表3 发电企业竞价策略系数

(四)结果分析

由于每个发电企业的成本情况、发电能力等方面的不同,各个发电企业对于不同的竞价结果会采取不同的竞价策略系数。同时发电企业面对风险的程度也不同,进行选择不同的竞价策略系数。当发电企业的成本水平较低,在竞价过程中易获得收益,通常在面对风险时用体现出风险厌恶,发电企业会通过报低价来争取强的更多的竞标电量,进而提高自身的利润。而当发电企业与其他发电企业比较自身发电成本水平较高时,竞价策略选择会尽可能的避开低报价,往往会选择高报价来以求得更高的结算价格,进而获得更高的收益。

四、发电企业竞价策略建议

(一)发电成本进行控制和科学评估

1. 有效控制自身发电成本。对于发电企业而言,发电量、单位发电成本和成交价格均决定着发电企业的利润。市场竞争中,价格是市场竞争的核心因素。自身发电成本偏低,就有着很大的浮动余地,增加竞价成功的概率。

2. 对成本进行科学评估。有效分析自身发电的成本情况,分析发电的固定成本与可变成本,科学评估发电成本的最高估价和最低股价,其估价的差值也直接影响着决策者的最终估价。

3. 充分了解同行的电量成本。由于发电机组的类型主要是30万和60万机组,与容量小的机组相比,容量大的机组有着较强的成本优势。因此在竞价过程中,根据自身机组的电量成本,判断别的发电企业的发电机组类型,进而估算其他发电企业的电量成本,在竞价过程中一定要充分考虑自身和同行业的电量成本。

4. 以往成交电量电价的平均价格与最终报价成正比,因此要对以往成交电价的科学评估。

(二)科学调整发电计划

1. 保证机组的稳定运行。电力市场竞价的初期,每个发电企业对竞价机制和竞价环境不熟悉,导致缺乏一个较为完善的报价体系。有些发电企业不考虑自身机组运行现状,盲目抬高报价,以至于不能够充分利用发电容量,频繁地启动和暂停机组不仅会对设备造成不良的影响,而且会带来一系列的经济问题。因此要结合自身机组的状况,充分考虑机组的负荷和维修计划等因素,合理安排报价,以免带来不必要的损失。

2. 考虑年度电量目标。对于火力发电企业而言,首先要满足合同电量,保证拿到合同电量带来的基本利润;其次,在尽可能的通过协议撮合或大用户交易来争取更多的电量;最后再通过竞价得到增发电量的机会。每个发电企业都有各自的年度电量目标,尽可能在不亏本的前提下,以求得更多的电量,进而完成年度电量目标。中标电量的增加直接影响着发电企业的利润,与此同时,发电量的增加同时降低了单位发电成本,间接影响着发电企业的利润。

3.积极调整计划,捕捉获利商机。电能不同于别的商品,不可以被大量储存。由于一些发电企业会存在机组维修或者报停等特殊情况,而电力市场的需求是刚性的,此时对于发电企业而言,需要及时掌握市场动态,迅速调整现有调度运行规则,积极争取增发更多的电量来求得利润最大化。

(三)科学地调控风险承受能力

影响发电企业对风险厌恶程度的因素很多,通过分析可得知,发电成本的高低、电力市场的大环境、机组的运行状况等因素,直接影响着决策者面对竞价时的风险厌恶程度。除此之外,还与决策者自身的心理作用和个人习惯因素有很大的关系。过于风险厌恶和风险偏好都将影响竞价的成败,因此需对决策者的风险偏好程度进行科学的调控。

(四)建立科学的报价体系

通过建立科学的报价体系,有助于发电企业不断总结报价经验,调整自身的最终报价,争取最大化的上网电量和最优利润。发电企业还应奖励有效的竞价辅助决策系统,结合电力市场的变化做出准确的预测,提高竞价上网的几率,达到利润最大化。

动态最优 第5篇

目前多数公交查询系统的换乘方案都是采用最短路径的算法, 本文对公交线路数据采用动态分段技术进行组织与处理, 结合邻接矩阵的路径查询算法, 实现了可获得基于最短路径、最小换乘数或是最少费用等各种最优换乘方案, 提高了公交换乘方案的适用性。

动态分段技术在GIS的网络分析模型中, 线性特征构成了地理网络的基础框架。早期的GIS系统多数采用弧段结点模型来描述线性特征, 该模型由一组弧段组成, 而弧段由构成网络线的一组有序坐标对组成, 其中弧段的两个端点称为结点。与线性特征相关的属性信息储存在与弧段相关联的属性表中[1]。

动态分段是在弧段-结点数据模型的基础上根据不同的属性按照某种度量标准对线性要素进行动态相对定位的一种技术[2]。其基本思想是在拓扑图形的基础上建立线路系统, 在对线性地物的空间信息进行查询和显示的过程中, 系统根据所选择的属性数据以及所要满足的某种特定条件, 动态地建立空间实体与其属性数据之间的关联与逻辑分段, 从而达到在不增加系统数据库实际容量的前提下实现系统数据信息的按需分配[3]。

2、数据的动态分段组织

在本文中, 利用动态分段技术对公交数据进行处理, 各要素类和事件表的设计如下: (1) 街道要素类。城市街道空间数据是本系统公交网络的基础数据, 公交线路网络在此基础上创建。 (2) 公交线路要素类。在街道数据基础上通过动态分段方式建立。 (3) 公交站点要素类。存储公交站点数据, 由站点编号和站点名称组成。 (4) 站点事件表。它是动态分段点事件表, 由公交站点数据与公交线路数据生成, 站点与线路通过RID进行关联。站点的度量值可确定站点在公交线路中的顺序、两站点方向、站点之间的距离等。 (5) 街道事件表。它是动态分段线事件表, 由街道数据与公交线路数据生成, 街道路段与公交线路通过RID进行关联。街道路段的起止度量值可确定某路公交经过该街道长度, RID与Street Name关联, 可获得街道经过的公交。

3、系统实现

3.1 算法分析

在获得用户出行的起始站点及目的站点后, 能否从一个站到另一个站, 须不断判断站点之间是否有联系, 本算法中用邻接矩阵的存储了站点间的通达关系, 两个站点可直达则值为1, 不可直达则值为0, 相同站点对值也为0。

在给定了起始站点、目的站点及搜索树层数N后, 对邻接矩阵进行按行优先 (广度优先搜索的思路) 搜索, 建立一个以起始点作为根结点的双亲表示法搜索树。双亲表示法搜索树结点数据结构包含两个数据域, 第一项为结点值, 第二项为父结点索引值。根结点的无父结点, 规定父结点索引值为-1。

当搜索树层数达到指定层数N时, 对邻接矩阵停止搜索, 搜索树建立完毕。然后从搜索树中包含目的站的叶子结点出发, 找到父亲结点, 一直回溯到根结点为止, 除叶子结点和根结点外所经过的结点, 即为换车的中间站点, 记录经过结点并加入方案组。当搜索层数过大或公交数据组织不合理时, 所得到的方案并非完全正确。对于这些错误方案应给予排除, 得到最终正确的方案组。

3.2 最优方案获得

基于动态分段的公交线路数组织, 在公交线路数据中有着票价和公交线路长度属性值, 只需计算起始站点间公交线路长度之或票价之和, 即可得到最短路径或是最少费用的公交换乘方案。在本文的公交换乘算法中, 由于使用了邻接矩阵来存储站点的连通性关系, 在查询时对搜索树的搜索层数就为换乘的次数, 最后对此方法进行了实现。

在公交换乘方案的查询中, 最短路径分析只需选择路径长度为搜索的限制条件, 点击查询按钮后可得到两点之间的乘车方案列表, 方案按路径长度排序;最少换乘分析选择换乘次数为搜索的限制条件, 点击查询按钮后可得到两点之间的乘车方案列表, 方案按换乘次数排序;最少费用分析选择乘车费用为搜索的限制条件, 点击查询按钮后可得到两点之间的乘车方案列表, 方案按乘车费用排序。

实验表明, 基于动态分段的公交换乘方案查询, 可以方便的设置不同的限制条件, 如换乘次数、路径长度、乘车费用等, 满足各种要求的乘车方案。

4、结语

动态分段技术较好的解决了城市公交查询系统在处理线性特征的数据时存在着重复数字化、数据冗余量大、多属性数据综合查询不易和数据难以维护等问题。本文在动态分段技术下实现了最优公交乘车方案的查询实现, 但也存在一些问题, 如对公交网络的抽象只限于完全的双向线路, 情况较为特殊, 在后续研究工作中可考虑更多情况。在方案查询时考虑更多因素, 如行驶时间、乘车频率等因素, 使之更加接近真实情况。

参考文献

[1]高勇, 刘瑜, 邬伦.GIS网络分析的动态分段方法与实现.地理与地理信息科学, 2003, 19 (4) :41-44.

[2]吴木旺, 任丽梅, 查良松.基于动态分段技术的城市公交系统数据库的建立.地理信息世界, 2006, 4 (003) :61-65.

动态最优 第6篇

中国风电装机规模增长迅速,截至2014年底,全国全口径风电累计并网容量已达95.8GW,同比增长25.6%[1]。根据国务院签发的《能源发展战略行动计划(2014—2020年)》,十三五期间中国将继续大力发展风电,重点规划建设甘肃酒泉、新疆哈密等9个大型现代风电基地[2],中西部风电向东部负荷中心远距离、大规模外送的客观需求将更为迫切。而高压直流输电技术是大规模、远距离、高效率传输电能的重要手段,为国内风电基地、水电基地等新能源大规模跨区消纳提供了有力的物理平台。目前,中国跨区直流输送容量已超过50GW[3],交直流互联电网的基本格局已初步形成。

随着风电远距离外送规模的不断扩大和交直流互联电网的快速发展,对于送端电网而言,大规模风电场和直流换流站的接入对系统无功潮流分布造成极大影响,传统基于直流潮流的有功发、输电计划模式将难以满足电网调度计划工作的实际需求。因而,含风电接入的交直流互联电网日前发电计划在传统发电计划基础上应具有以下新的内涵:(1)风电机组有功、无功功率及电压特性的精确建模;(2)交直流互联电网的交流潮流约束及校核;(3)直流输电系统建模及控制运行参数的动态优化;(4)火电、风电、直流换流站及无功补偿设备的有功、无功动态协调优化;(5)该复杂非线性问题的高效求解。

国内外在此领域的研究成果主要是在最优潮流、动态无功优化、机组组合等问题中分别考虑风电场接入[4,5,6,7,8,9]和交直流互联电网[10,11,12,13,14,15],研究成果总结如下。(1)文献[4,5]建立了恒速恒频风电机组的稳态模型,在此基础上提出了含风电场的系统潮流计算迭代算法;文献[6]推导了异步风力发电机的无功功率—电压特性方程,在此基础上研究了含大型风电场的多时段动态无功优化问题;文献[7]则将该特性方程应用于交流网络约束最优潮流问题当中;文献[8]建立了变速恒频风电机组的稳态模型,并深入研究了其无功功率极限的计算方法;文献[9]将变速恒频风电机组引入动态最优潮流模型中,并采用现代内点法求解。(2)文献[10,11,12]提出了考虑交直流互联电网的最优潮流模型及算法;文献[13,14]分别研究了交直流系统的动态无功优化和考虑直流功率日调节次数约束的无功优化实用化方法;文献[15]则在安全约束机组组合模型中考虑了交直流电网运行控制约束。上述文献均仅研究了风电或者直流接入对潮流优化计算的影响,并未深入研究风、火、直流线路有功和无功协调优化问题。

文献[16,17]在动态最优潮流中对直流线路接入电网的风电场建模,采用场景分析法根据风速概率密度函数描述风电出力随机性,考虑了双馈感应风力发电机(W-DFIG)的有功、无功出力上下限及直流输电系统稳态运行方程、交流潮流方程;然而模型中未考虑W-DFIG的有功、无功耦合特性约束及直流输电电量等多时段动态耦合特性约束,求解算法方面仅通过调用CONOPT软件包求解,难以满足该复杂非线性问题的计算效率要求。

综上,风、火协调的交直流互联电网发电计划本质上是涵盖火电机组有功和无功发电计划、直流输电计划、风电运行状态优化,以及无功补偿设备投切计划等多维协同优化问题,目前尚无有效的解决方案。针对当前西部风电汇集地区对交直流互联电网日前发电计划的实际迫切需求,本文在上述研究成果的基础上,提出了考虑风电接入的交直流互联电网动态最优潮流(wind power integrated dynamic optimal power flow with AC/DC system,AC-DC-WDOPF)建模、求解框架、数学模型和求解算法,并通过对比算例验证了本文所述模型、方法的有效性。

1 AC-DC-WDOPF建模求解思路

1.1 AC-DC-WDOPF原问题描述

原问题可以通过以下统一模型描述:

AC-DC-WDOPF原问题在确定常规发电机组启停方式、风电机组有功出力预测值的基础上,目标函数f(x,α)以交直流互联电网发电成本最低、电容电抗器投切次数最少为优化目标。

AC-DC-WDOPF原问题的决策变量由连续变量x和离散变量α两类构成:x包括节点电压、节点相角、常规机组无功出力、风电机组无功出力、直流输电系统控制参数;α则表征风电场、直流换流站并联电容和电抗器的投切状态。W-DFIG已逐步成为当前风电场采用的主力机型,占比近70%[18],本文后续模型中的风电均针对W-DFIG建模。

AC-DC-WDOPF原问题的约束条件可划分为两类:一类是描述系统空间维耦合和多时段时间维耦合的约束条件gdr(x,α)和hdr(x,α),主要包括系统电力平衡,常规火电机组电量、爬坡约束,电容、电抗器日内投切次数限制约束,直流输电电量计划等时段间耦合等约束;另一类是交直流系统各类元件的稳态运行控制约束条件gad(x,α)和had(x,α),主要包括交流潮流方程、直流输电系统稳态运行、直流换流站内控制系统、直流传输功率上下限、爬坡速率、风电运行特性、无功补偿设备运行特性等约束。

1.2 AC-DC-WDOPF建模求解框架

AC-DC-WDOPF原问题的数学模型是一个复杂非线性混合整数规划(MINLP)模型,难以直接求解。为此,本文针对AC-DC-WDOPF模型特点,基于Benders分解法[15,19]提出了时空协调、主子迭代的建模思路与求解框架,如图1所示。

上述建模求解框架,将AC-DC-WDOPF问题转化为考虑电容、电抗器投切次数等时段间耦合约束的全时段动态安全约束经济调度(SCED)主问题和各时段含W-DFIG的交直流互联电网最优潮流(OPF)子问题求解。其中,主问题为混合整数线性规划(MILP),用于解决考虑各类时段间耦合约束的时间维协调优化问题;子问题为非线性规划(NLP)模型,用于校核各时段交直流互联电网内各有功、无功设备在空间维协调优化的可行性。具体内涵如下。

1)主问题:基于直流潮流建立动态SCED模型,重点考虑时段间耦合约束,包括火电机组爬坡速率、常规机组日计划电量、直流日计划传输电量,以及并联电容、电抗器日投切次数限制约束,兼顾系统有功平衡和线路有功潮流约束;风电场仅考虑风功率预测的有功结果。主问题实现发电机组有功出力、直流输电计划、并联电容和电抗器日投切计划的协调优化,所得的最优解不一定满足原问题中的交流潮流约束条件、直流输电系统稳态运行约束及风电运行特性约束,因此,需要构建可行性子问题校验主问题最优解的可行性。

2)子问题:各可行性子问题均为单时段最优潮流模型,该模型引入松弛变量衡量主问题最优解在子问题中的不可行性程度,以松弛变量之和最小为优化目标;基于交流潮流建模,精细化地考虑W-DFIG、并联电容、电抗器及直流输电系统的稳态控制运行约束。若主问题最优解通过所有子问题可行性校核,则该最优解即为原问题的最优解;否则未通过可行性校验的子问题向主问题反馈用于修正主问题可行域的约束条件。

上述建模思路与求解框架具有如下特点。

1)物理意义明确:由于系统运行的经济性仅与火电机组的有功出力有关,因此主问题主要关注系统运行经济性和时段间耦合等系统性约束,而将各系统元件的复杂非线性约束以可行性校验的方式放在子问题中考虑,在降低问题复杂性的同时,使得主、子问题分解具有明确的物理意义。

2)数学理论严谨:基于Benders分解的求解框架在不损失迭代最优性的前提下,将复杂MINLP分解为主、子问题,主、子问题间通过构造连接约束和反馈Benders可行性约束,确保算法的收敛性和迭代过程的最优性。

3)优化求解高效:将该复杂MINLP问题化整为零,将整数问题、时段间耦合约束在主问题中构成MILP模型求解;将复杂非线性约束在时间维度上解耦为多个单时段NLP模型在子问题中求解,极大地降低了问题求解难度,并利用并行计算技术提升求解效率。

2 AC-DC-WDOPF的数学模型

根据上述建模思路,本节基于Benders分解法建立AC-DC-WDOPF主、子问题的数学模型。

2.1 主问题优化模型

2.1.1 优化目标

式中:PGi,t为发电机组i在时段t的有功出力;CGi为发电机组i的发电成本函数;T为优化总时段数;NG为发电机组总数;αCu,t和αLv,t分别为电容和电抗器组u,v在时段t的投入标识变量,为0-1整数变量,其取值由式(3)决定;NC和NL分别为并联电容、电抗器总组数;ξ为数量级远小于发电成本的罚因子,用于尽量减少并联电容、电抗器日内的投切次数;δt≥0为时段t的网损松弛变量。

式中:SCu,t和SLv,t分别为并联电容和电抗器组u,v在时段t的状态标识变量,为0-1整数变量,取0值表示该电容/电抗器组未投入,反之则代表投入。式(3)用于描述电容、电抗器组投入标识变量与状态标识变量的关联数量关系,仅当状态变量由0变为1时,投入标识变量才为1,计入投入次数。

主问题基于直流潮流,未考虑系统网损;而子问题基于交流潮流,所得机组有功出力中包含网损,为保证子问题反馈至主问题的机组有功出力修正条件有效,需在系统电力平衡约束中考虑网损松弛,并在主问题中引入较大罚值M用于限制各时段网损量。

2.1.2 约束条件

1)并联电容、电抗器日投切次数约束,这里仅需限制投入次数即可。

式中:ZC和ZL分别为并联电容器、电抗器日投入次数限值。

2)子问题反馈的Benders割约束。该约束中包含了对机组有功出力、直流功率、电容、电抗器投切次数的反馈修正要求,详见下节子问题优化模型。

系统电力平衡方程、线路有功潮流、机组出力和直流功率爬坡、机组发电量、直流传输电量、机组出力和直流功率上下限等约束可参见文献[20]。

2.2 子问题优化模型

子问题均针对单时段建模,下述公式中均省略时标t。

2.2.1 优化目标

式中:ε+iG和ε-iG为主、子问题间发电机组出力的偏差松弛变量;ε+dk和ε-dk为主、子问题间直流线路k传输功率的偏差松弛变量;NK为直流线路条数;ε+mC和ε-mC为主、子问题间节点m上投入并联电容器的偏差松弛变量;B为系统节点数;ε+nL和ε-nL为主、子问题间节点n上投入并联电抗器的偏差松弛变量。各种松弛变量的具体起作用方式详见后续主子问题连接约束式。该优化目标ω量度了主问题的优化结果在子问题中的不可行程度,当ω=0即满足主、子问题收敛性条件,即表明主问题所得最优结果完全满足子问题约束,约束条件不需要松弛。具体应用时可根据最优性和效率的需求设定ω的限值[19]。

2.2.2 约束条件

1)含W-DFIG接入的交直流互联电网潮流约束

式中:PmG和QmG分别为节点m上发电机组注入的有功和无功出力,,i∈m表示与节点m相连的机组i;PmD和QmD分别为节点m上的有功负荷和无功负荷,和QmL分别为节点i上并联电容、电抗器的无功注入/输出;Vm和Vn分别为节点m和n的节点电压幅值;θmn为节点m与节点n的相角差;Gmn和Bmn分别为连接节点m和节点n线路的电导和电纳;PmW和QmW分别为节点m上风电场的有功和无功出力;Vdk,Idk,φk分别为接入节点m直流线路k的换流变压器交流侧母线电压、电流及功率因数角。若节点m与直流线路整流侧相连,则Vdk=Vkd1,Idk=Ikd1,Vkd1和Ikd1分别为直流线路k整流侧母线电压和电流;若节点m与直流线路逆变侧相连,则Vdk=Vkd2,Idk=Ikd2,Vkd2和Ikd2分别为直流线路k逆变侧母线电压和电流。模型中其余直流系统相应变量同理,不再赘述。

PmW和QmW可由下式确定:

式中:PeW和QeW分别为节点i上风电场内第e台风电机组的有功和无功出力;NmW为节点m上风电场接入的并联风电机组台数。PeW可依据风功率预测结果确定,QeW上、下限则主要受变流器转子侧电流限制[8]。

风电机组有功功率Pe一般由风功率预测确定,无功功率Qe主要由节点电压Us和功率因数角φw决定[8],传统运行中通常采用定电压或定功率因数控制方法。本文动态最优潮流的目的是通过优化各类变量使得系统中各元件协调运行在最佳运行点,因而Us和tanφw在本文中均为优化变量,从而可以根据系统需要充分发挥W-DFIG的无功调节能力,支撑系统电压、降低系统损耗。

2)主、子问题连接约束。其中式(9)为主、子问题的直流传输功率偏差控制约束;式(10)为主、子问题的发电机组有功出力偏差控制约束;式(11)为主、子问题的并联电容、电抗器无功注入/输出偏差控制约束。

式中:P*dk为主问题求得最优解对应的直流线路传输功率;P*iG为主问题求得最优解对应的节点i上所有发电机组有功出力之和;SuC*和SvL*为主问题最优解;xuC和xvL分别为并联电容、电抗器单组容量;u∈m和v∈n分别表示并联在节点m和n上的电容、电抗器。

直流线路稳态运行、潮流限值约束见文献[20]。

3 AC-DC-WDOPF的求解方法

3.1 算法求解流程

根据第2节构建的AC-DC-WDOPF主、子问题优化模型,主问题为MILP问题,子问题为NLP问题。本文以确保问题求解最优性为原则,提出了基于Benders分解法的主、子问题迭代流程,如图2所示。

算法流程中各模块的具体功能如下。

步骤1:准备主、子问题优化所需的各项基础数据,包括负荷及风功率预测数据、网络拓扑、发电机组技术经济参数、无功补偿设备参数、风电场技术经济参数、直流换流站设备参数等,迭代次数g初始化为1。

步骤2:求解主问题。主问题为考虑无功补偿设备的交直流互联电网动态SCED模型,本质为MILP,可直接求解。

步骤3:获得第g次迭代的最优解x(g)*,构建优化子问题。

步骤4:并行求解各时段可行性子问题。

步骤5:判断各子问题是否满足收敛条件,若是则当前最优解x(g)*为AC-DC-WDOPF原问题的最优解;否则各不可行子问题向主问题反馈Benders可行性约束,迭代次数g=g+1,返回步骤2。

步骤6:输出原问题最优解,包括发电机组有功、无功出力,风电机组无功出力,各无功补偿设备投切计划,直流输电系统运行控制计划。

3.2 Benders割建模

根据3.1节提出的求解算法流程,采用Benders分解法高效求解AC-DC-WDOPF问题的关键在于构造子问题反馈的可行性约束,即Benders割[19]。根据主、子问题连接约束(式(9)至式(11))形式,Benders可行性约束如下。

式(12)反映了为消除主问题最优解在子问题中的不可行量度ω,主问题优化变量PkD,PiG,SuC,SvL的调整需求。λdk,λiG,λmu,λmv为相应约束的拉格朗日乘子,该乘子若等于0,表明相应连接约束为松弛约束,主问题在该轮迭代中获得的最优解满足该连接约束;该乘子若不等于0,表明相应连接约束为起作用约束,主问题在该轮迭代中获得的最优解不满足该连接约束,相应乘子反映了主问题最优解增量对子问题最优解ω(即子问题不可行量度)的灵敏度,并通过Benders可行性约束将这一信息反馈给主问题,实现子问题对主问题优化空间的修正。

本文提出的上述求解方法将MINLP问题转化为MILP主问题和一系列NLP子问题并行求解,一方面利用Benders分解法的严格算法框架,在不损失迭代最优性的前提下将整数问题与非线性问题、单时段最优潮流与全时段动态优化问题剥离求解,方便使用成熟商业计算软件;另一方面利用并行计算技术将考虑双馈感应发电机(DFIG)、交直流电网的高度非线性模型在子问题中优化求解,有效提升AC-DC-WDOPF问题的计算效率。

4 算例分析

算例采用CEPRI-6机22节点系统[21],对比直流系统控制参数计算结果;电网基础数据、直流系统基本参数同文献[20]。MILP模型采用CPLEX12.3软件包求解,NLP问题采用IPOPT3.9.2软件[22]计算。

4.1 对比算例设计

本文针对日前发电计划的常见问题,设计了3种计划制定模式,以验证本文所述方法的有效性。

1)模式1(M_Ⅰ):基于直流潮流,仅考虑有功平衡的传统发电计划制定方式。

2)模式2(M_Ⅱ):基于交流潮流,直流传输功率固定,风电机组考虑固定功率因数,不考虑无功补偿设备。

3)模式3(M_Ⅲ):本文所述AC-DC-WDOPF方法,基于交流潮流,灵活优化直流功率,精确考虑DFIG、无功补偿设备建模。

4.2 算例基础数据

1)系统日负荷曲线

本文基于北方某省实际日负荷曲线,将文献[21]算例中负荷作为当日最大负荷,其余时段负荷按比例调整作为系统日负荷曲线,曲线形状见附录A图A1。

2)风电基本数据

采用DFIG模型,相应模型参数见文献[9]。风电场位于节点11处,即直流整流侧所在节点。设置当日风电预测最大出力标幺值为1.242 2,相应风电标幺值预测曲线见附录A图A1。

3)无功补偿设备

直流整流运行需要消耗大量无功,在节点11设置电容器组,补偿系统感性无功。为便于示意,本文算例中仅设置了一组电容器,相应容抗标幺值设为0.5,则在1.05的电压上限水平下,其能够输出的感性无功功率为0.551 3。

4.3 安全性对比分析

在涉及直流及风电的日前计划制定中,若不考虑直流和风电机组的无功特性,可能导致系统实际运行中出现无功缺额,影响电压水平和直流送电功率,从而造成日前计划在实际运行中不可行。本文重点分析了节点11的无功平衡情况。

1)模式M_Ⅰ本质为基于直流潮流的传统SCED,由于未考虑无功功率,所得有功计划结果将造成系统交流潮流不收敛,部分节点存在无功缺额,造成系统存在低电压风险。如图3所示,M_Ⅰ的最优解持续存在无功功率缺额。尤其在高峰时段,随着系统无功需求增加和直流功率上升,节点11无功缺额进一步增大。

2)模式M_Ⅱ中风电机组功率因数固定,发电时发出感性无功功率。早、晚高峰时段,当直流输电功率上升,无功需求增加,而此时风电机组功率下降,发出无功功率减少,又未考虑无功补偿设备,造成高峰时段节点11存在无功缺额如图3所示。

3)模式M_Ⅲ为交直流电网动态最优潮流,不仅灵活优化了直流功率和系统发电资源,而且协调优化了W-DFIG、无功补偿设备,使得节点11不存在无功缺额。

4.4 经济性分析

为更好地对比经济性,在M_Ⅲ基础上将直流功率控制模式改为定功率模式,直流功率设置与M_Ⅱ一致,所得优化结果定义为M_Ⅳ;同时在M_Ⅱ中考虑无功补偿设备,确保M_Ⅱ有可行解。

1)运行总费用分析

各模式总体运行费用对比如表1所示。

由表1可见,对比M_Ⅱ和M_Ⅳ,在相同直流传输功率情况下,本文所述AC-DC-WDOPF方法由于充分考虑了W-DFIG的无功调节能力,从而有效减少了系统的无功流动,降低了系统网损,相应系统运行费用降低了0.11%。对比M_Ⅳ和M_Ⅲ,灵活优化直流传输功率后,可进一步扩大系统的寻优空间,运行费用进一步降低了0.08%。

2)网损分析

为进一步分析运行费用变化的机理,本文对比分析了M_Ⅱ和M_Ⅳ优化结果的网损,如图4所示。

相比模式M_Ⅱ,M_Ⅳ可以灵活地调整风电机组功率因数角tanφw,从而在更大范围内调整系统的无功分布,使得各时段系统网损均有所降低,在负荷高峰时段无功功率缺额较大时网损降低更为明显。

由于风电机组、直流及无功补偿装置均在节点11,节点11的无功波动最大,因此主要网损变化支路10-11上,相应各时段的网损对比如图5所示。可见M_Ⅳ模式在负荷高峰无功缺额时段,通过调整风电机组的功率因数增加其所发出的无功功率,可有效减少支路10-11上的无功流动,从而降低网损。

3)电容器投切次数分析

在模式M_Ⅱ中,随着负荷高峰时段直流传输容量加大,无功支撑不足,需要在早晚高峰时段投入电容器,而低谷时段由于无功过剩,需要将电容器切除,当日需要投切电容器2次,投入时段分别为时段7~11和15~18;而采用本文所述方法的模式M_Ⅳ,W-DFIG能够在高峰时段提供无功支撑,低谷时段吸收无功功率,避免了电容器投切。

4.5 Benders迭代收敛性分析

附录A图A2展示了24个整点时段主、子问题迭代过程中子问题不可行量度的收敛过程,各时段Benders主、子问题迭代均在12次之内收敛,并行计算总时长为77.13 s。可见,本文所述基于Benders分解的主、子问题迭代方法收敛性良好。

5 结语

随着风电及跨区直流输电的迅猛发展,直流送端风、火、直流线路的协调优化运行对于提高电网优化运行效益、确保直流近区电压水平具有重要意义。本文建立了综合考虑直流线路、W-DFIG及无功补偿装置运行特性的交直流电网动态最优潮流模型,实现了对直流送端风、火、直流线路协调优化问题的精确描述;提出了基于Benders分解法的求解模式和求解方法,将原问题转化为基于直流潮流的动态经济调度主问题和一系列精细考虑风电机组和直流系统的单时段交直流互联最优潮流子问题求解。

算例结果表明,本文所述模型能够优化含风电的交直流互联电网的运行方式,在确保潮流及电压不越限的前提下,获得发电成本更低、网损更小的系统运行点;所提出的主、子问题分解优化的求解方法收敛性能良好。本文所述模型及方法将为直流送端考虑风、火、直流线路协调运行发电计划的精益化编制及高效求解提供有益思路,今后可进一步在模型中考虑风功率的随机特性。

动态最优 第7篇

高等教育出版社影印版《INTRODUCTION TO ALGORITHMS》(第二版)中,基于动态规划法思想,建立最优二叉搜索树算法,选择子问题的划分,r值的循环范围过大。当二叉树结点较多时,算法的时间复杂度较大,造成程序运行时较多开支。

2经典最优二叉搜索树算法分析

原最优二叉搜索树算法时间复杂度为:

本文引用《INTRODUCTION TO ALGORITHMS》(第二版)第363页例题15.5-2作为实例分析:

原算法计算结果:

(e阵列为建立两个结点之间的二叉搜索树的时间期望值花费,w阵列为两个结点之间查找成功与否的概率和,root阵列为两个结点间最优二叉搜索树的最优化划分方法。)

e,w,root阵列各个计算顺序为:

经分析,原算法r值的范围可再次缩小,原r范围为从i~j,如实际情况i与j值较大,循环次数较多,算法时间复杂度较大。

3算法的改进及可靠性证明

3.1算法的改进

计算r时,root阵列记录e阵列的最优划分方法。例如e[1,7],e阵列公式e[i,j]=e[i,r-1]+e[r+1,j]+w[i,j],r循环范围1~7,计算以下式子:

7次,计算e[1,6]的式子为:

共6次。

e[1,6]是e[1,7]子问题。动态规划特点:若子问题最优,则主问题也最优。则root[1,6]=3就保证计算e[1,7]时,r循环1~3时,一定是r=3,e[1,7]最小。则计算e[1,7]时可从r=3开始计算。即计算e[1,7]时,原算法重复了(1)~(2)式的计算。

同理,e[2,7]是e[1,7]的子问题,root[2,7]=5就可保证一定是r=5时,e[1,7]最小。原算法重复(6)~(7)式的计算。整个算法中,这两种情况重复出现,使原算法运行时间开支较大。

经分析,r值范围改为root[i,j-1]~root[i+1,j]。

3.2 改进算法的可靠性证明

根据动态规划思想,若子问题划分最优,则主问题最优,而计算e[i,j]时,根据原算法,知root[i,j-1]已计算。即i~j-1结点最优化划分已选,计算e[i,j]时,只需r从root[i,j-1]值开始。

同理,root[i+1,j]也算出。即i+1~j结点最优化划分已选,计算e[i,j]时,r取值上限为root[i+1,j]值。其它循环同理。

3.3 改进算法的实现

改进算法,应注意root阵列初始值,root[1,1],,root[7,7]没对应取值范围,需要在计算前,先初始化root[i,i](i=1,2,,7)。

改进算法如下。

改进算法的6~19行时间复杂度:

改进算法的最坏时间复杂度为:

注意,原算法时间复杂度是确定的,而改进算法15行时间复杂度随着问题不同而不同,给出改进算法的时间复杂度T(n2)是最坏情况的时间复杂度。改进算法比原算法节省时间是因为15行语句。改进算法虽然有3个for语句循环,但经过计算,其时间复杂度为O(n2)。因为root阵列的值会相互影响,即若root[i,j-1]与root[i+1,j]值相差较大,则root[i+1,j]与root[i+2,j+1]值相差较小,所以此句循环次数远小于n,使改进整体算法的时间复杂度整体减小。

4两种算法的优越性比较

现在比较两种算法的优越性。

从表2、表3可以看出,理论上改进算法比原算法运行时间减少14%,实际例题中,改进算法比原算法节省时间36%。n值较大时,改进算法的效果将更加理想。

5总结

本文在最优二叉搜索树构造算法中,主要改进了子问题的划分时r值的循环范围,减小了算法的时间复杂度,由原来的O(n3)减小为O(n2),并讨论改进算法的优越性。

文中输出格式与教材中格式不相同,但不影响理解和阅读。改进算法虽然在表面上与原算法有较大改动,其实只是为了让改进算法适应更好的环境,例如考虑到root的初始值,增加的语句并不会增加程序的开支;相反,当n值越大时,改进算法节省的时间将更显著。

参考文献

[1]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.The Massachusetts Institute of Technology Press,2001.

[2]Knuth D E.Optimum binary search trees,Acta Informatica,1971,1:14-25.

[3]Hu T C,Tucker A C.Optimal computer search trees and variable-length alphabetic codes[J].SIAM Journal on Applied Mathematics,1971,21(4):514-532.

动态最优 第8篇

本文将使用动态规划算法来针对最优路径问题进行求解, 动态规划算法是一种被用来对无后效性的多阶段决策过程求解的算法, 该算法最初于2O世纪50年代由美国数学家Bellman等人提出。最优路径问题具有“从起始点为中心慢慢向外扩展, 直至扩展到终点”的特点。通常人们会使用Dijkstra算法进行求解, 但由于其需要遍历节点, 所以效率很低。经调查, 在实际应用中的很多问题若使用动态规划法进行求解来替代使用非线性规划或线性规划的算法进行求解, 可使得计算速度得到大幅提高, 可有效减少确定决策的时间成本。动态规划法较之其他算法的优势是可以将一个复杂的问题分解成一组类型相同且更加容易解决的子问题, 这使得使计算过程大幅简化, 且更加适用于计算机处理。若要使用动态规划算法来求解实际问题, 则应按照优先照顾整体的思想, 以逆序的方式找到每个可能状态的最优策略, 然后确定的整个序列的最优策略和最优解, 算法的使用者应除去所有中间非最佳的解决方案, 同时, 这也使得动态规划法对求解最优方案的计算复杂度比穷举法和Dijkstra算法大大减少。故而, 在实际求解最优路径运输问题中, 使用动态规划法具有稳定可靠, 简洁系统, 清晰明朗的优点, 值得大幅推广。

一、动态规划基本思想

1.1基本思想解释

作为一种新型的算法设计技术, 动态规划法常常被应用于求解组合最优化的问题当中。动态规划法的基本思想为:首先将全局问题转化成若干个局部问题, 为了实现整体最优化的目的, 则必须根据原始问题本身的特点来确定最优的局部决策, 即先将整个求解过程划分为若干个“看似不相关, 实则互相联系”的子阶段, 在确定上一阶段的决策以后才能转到下一阶段, 并且要在各个阶段都做出决策, 这样才能在各个阶段选取各个阶段的最优决策, 如此才能得出整个过程的总体决策。总结实际应用经验可以得出:动态规划算法的适用的问题通常都是多阶段的决策问题, 且该问题还需具有无后效性。总结其特征如下:

(1) 划分出的各个阶段都具有若干个“可能出现”的状态。

(2) 划分出的各个阶段的状态之间转换的成本相对明确, 并且在最优决策的确定时, 各个阶段的成本间具有明确的递推关系。

(3) 划分出的各个阶段都与最优决策序列之间的无必然的联系。

(4) 问题能被分成几个子阶段, 而求解问题的过程就是对各个子阶段的求解过程。

1.2动态规划基本步骤

(1) 描述最优解的特性, 进而描述其结构特征。

(2) 自底向上计算出划分出的各个阶段的最优值, 并做好相关记录。

(3) 递归定义出原始问题的最优值。

(4) 根据计算出的原始问题最优值, 构造出最优解 (最优路径) , 完成全部计算。

二、动态规划建模过程

(1) 分解原始问题并确定各个子阶段的最优决策。求解多级决策问题的过程是:首先将待求解问题依照问题的特点划分为若干个子阶段, 划分出的各个子阶段都需要为整体最优而解决局部问题, 且划分时需要严格按照决策实施的时间或者空间的分割顺序进行划分, 下文中用i来表示阶段变量。

(2) 确定状态并确定状态变量。在多级决策问题的求解过程中, 自然状态可以用来指示各个阶段具体的开始位置, 其中自然状态还包括了客观条件阶段性数目的状态, 是用来描述各个子阶段的必要信息, 描述状态变量还可以适用一组或一个具有无后效性的变量, 下文中用Hi来表示第i级的状态变量。

(3) 确定原问题解决方案的决策变量及其集合。在实际应用中, 决策是对阶段状态的选择, 也是决策者从当前阶段向下一阶段所做出的选择, 决策集合是决策变量的取值范围。下文中决策集合用Di (Hi) 表示, 决策变量用Ui表示。

(4) 写出状态转移方程。设定状态转换方程为Hi+1=Ti (Hi, Ui) 。其中, Ti (函数关系) 会随着问题的改变而改变, 如果第i个阶段的状态变量确定 (即Hi确定) , 那么第i+1阶段状态变量的值也随着第i个阶段的决策变量Ui的确定而确定。

(5) 列出指标函数。根据n和vi具有递推性和可分离性, 求出指标函数n和vi, 的关系, 并列出指标函数。

(6) 写出动态规划函数的基本方程。fn+1 (Un+1) =0 (边界条件) ;fi (Hi) =opt{vi+fi+1}, i=n, n-1, …, 1;用f (Hn+1) 来表示第i-n阶段的最优策略函数。

三、应用举例

将一个实际运输问题进行抽象, 并且使用网格图进行表示, 如图1。点A为起始地点, 点E为目标地点, 其余节点均为可能经过的节点, 节点间的连线为可能经过的路径, 节点间的连线上的数值表示两节点间的运输成本。根据动态规划算法的建模要求, 可以建立相应的算法模型, 以求出该运输过程的最优路径。

将动态规划的计算结果如图2所示:

由图2可以清晰地看出, 货运成本最低的路线为:AB2C1D1E或AB3C1D1E或AB3C2D2E。最低运费为110。

由本实例我们可以总结出动态优化具有以下优点: (1) 运算结果清晰明了。 (2) 易于找到全局最优解。 (3) 可以得到一组解, 这有利于下一步的分析。

四、结语

选用动态规划法求解最优路径问题, 其优点在于步骤稳定可靠, 过程简洁系统, 结果清晰明朗, 十分适用于实际使用。使用动态规划算法求解无后效性的多阶段决策问题不仅效率非常高, 而且易于实现。虽然使用动态规划算法使用起来仍具有一定的局限, 不过动态规划法具有很高的实用性, 而且人类已经运用动态规划算法成功地解决了诸多实际问题。虽然在本文中只考虑了货运路径选择的问题, 但我们可以改进或者结合启发式算法, 使其能在实际问题中更好地应用, 这有待于日后的继续研究。

摘要：动态规划法适用于解决多阶段决策问题, 其操作方法是首先分解问题为若干个子问题, 然后找到的各个子问题的解决方案, 最后从这些子问题的解决方案中得出原问题的最优解决方案。动态规划方法适用于解决阶段性明显的最优路径问题, 并能有效地提高工作效率。本文以动态规划法为指导思想, 描述了应用动态规划法来解决最优路径问题的基本原则, 并对各种实际状况的解决办法加以讨论。

关键词：动态规划,最优路径,数学模型,多阶段决策

参考文献

[1]钱颂迪.运筹学[M].北京:清华大学出版社, 2002.

[2]谬慧芬, 邵小兵.动态规划算法的原理及应用[J].中国科技信息, 2005 (21) :42.

[3]蒋琦玮, 陈治亚.物流配送最短径路的动态规划方法研究[J].系统工程, 2007, 25 (4) :27-29.