清华大学电机系，100084 北京
1 引言
电力系统经济运行问题是一个复杂的大规模、非线性优化问题。求解该问题一般采用大系统分解协调方法［1,2］，将原问题分解成水电系统优化问题和火电系统优化问题，然后分别求解、协调。其中，水电系统优化问题中各变量之间既有时间上的联系，又有空间上的联系，它是解水火电经济调度问题的难点所在。
既约梯度网络流法是求解水电系统优化问题的常用方法［3,4］。其基本思路是，在用既约梯度法求解原问题过程中，利用网络流问题基矩阵的逆等于其道路矩阵转置这一特点简化矩阵求逆运算，加快问题的求解速度。但在实际应用中，经常出现“基变量达界后，找不到新的入基变量”的情况，使算法无法进行下去。本文针对这一问题进行了研究，提出了一种新的非线性最小费用循环流算法来求解水电系统优化问题。
2 水电系统优化问题网络流模型
水电系统优化问题约束可分为两类，一类是每时段每水库的流量平衡约束，另一类是变量的上下界约束。
每时段每水库的流量平衡约束为
(1)
式中 Ωi表示与水电厂i直接相连的上游水电厂;rit表示水电厂i在时段t的耗水量;sit表示水电厂i在时段t的水库库容;yit表示水电厂i在时段t的天然来水量。其中，耗水量rit又可表示为水电厂i在时段t的发电用水量dit与弃水量zit之和，即
rit＝dit＋zit
i，t(2)
如果用x表示所有的决策变量，b表示各水电厂各时段天然来水，则式(1)可写为
Ax＝b(3)
式中 A为节支关联矩阵。
由于要考虑灌溉、航运、防汛等各种因素，因此变量取值还存在下列的上下界约束：
以上各式可统一地记为
(8)
水电厂i在时段t的出力Hit可由下式求得
Hit＝f(sit，rit)＝Ki［φi(sit)－θi(rit)］diti，t(9)
式中 φi(sit)为上游水位与库容函数；θi(rit)为下游水位与耗水量函数。φi(sit)和θi(rit)可由相应的多项式表达。
这样，时段t中水电厂总的出力Ht为
(10)
设时段t中系统边际成本为λ*t，则该时段水电厂总的出力Ht所带来的效益Jt为
Jt＝λ*tHt(11)
式中 λ*t可由对非水电部分（包括火电、联络线等）预先进行优化求得。
在给定系统边际成本λ*t下，水电系统优化问题目标函数为
(12)
可简记为
J＝minf(x)(13)
由式(3)(8)(13)知，水电系统优化问题可由如下的非线性网络流模型表达：
minf(x)
s.t.Ax＝b(14)
3 用既约梯度网络流方法求解水电系统优化问题时可能出现的问题
既约梯度网流法基本思想如下。
对问题(14)，将A和x进行分解，为不失一般性，可令
A＝［B，S，N］,x＝［xB，xS，xN］T
式中 B是m×m可逆矩阵，xB、xS、xN分别称为基、超基、非基。xN中每个变量的值都在界上。
作上述分解后，基变量可被表达为超基变量和非基变量的函数。即
xB＝B－1b－B－1SxS－B－1NxN＝y(xS，xN)
因此问题(14)的目标函数可写为
F(xS，xN)＝f(y(xS，xN),xS，xN)
暂时忽略xB的上下界约束并固定xN，则问题(14)可用如下既约问题代替
min F(xS，xN)
s.t xS≤xS≤
S(15)
式中 xS、S分别为x、中相应于xS的子变量。
设dkS是既约问题(15)的可行下降方向。令dk＝［－B－1 S I 0］T dkS，若要使dks成为问题(14)的可行下降方向，则还需考虑在既约问题中被忽略的xB的上下界约束条件。即式(16)必须成立。
xB≤xB＋αdkB≤B,α>0(16)
式中 dkB为dk中相应于xB的子变量。
显然，当
xB<xB<B(17)
时，总存在α>0，使条件(16)成立，此时，dk也就是问题(14)的可行下降方向。
因此，在既约梯度网流法中，要求xB满足条件(17)，即应选择未达界的变量作为基变量。但在实际应用中，这一条件不一定总能满足。
典型的反例是，对下列非线性最小费用流问题：
min f(x)
s.t. Ax＝00≤x≤(18)
显然，x＝0是问题(18)的可行解，但此时所有变量都位于下界，找不到可供入基的变量，计算无法进行下去。
上例为一极端的例子。在实际应用中，更为常见的情况是，某基变量达界后应被换出，但找不到可被换入的未达界变量，使计算无法进行下去，即所谓“基变量达界后，找不到新的入基变量”。
出现上述困难的原因是，问题(15)是问题(14)忽略了xB的上下界约束并固定xN后的简化问题，其可行下降方向不一定总能成为原问题(14)的可行下降方向。
下文给出了一种新的算法，该算法能直接给出原问题的可行下降方向，从而避免出现上述情况。
4 新的非线性最小费用循环流算法
对网络G(V，A，s,t)，其非线性最小费用流模型可用式(14)表达。
设网络G的流值为v(f)。引入一条从收点t至发点s的人工弧，并令弧上流量为v(f)，弧流量下界为零，上界为正无穷大，弧费用为零。此时，网络G中所有节点都满足节点流量平衡条件
则称新问题为非线性最小费用循环流问题。
非线性最小费用循环流问题可用数学模型表示为
min f(x)
s.t. Ax＝0(19)
显然，通过引入人工弧可将水电系统优化问题转化为非线性最小费用循环流问题。
求解非线性最小费用循环流问题的算法计算步骤为：
①设已知初始可行点x(1)，置k＝1;
②求解线性最小费用循环流问题
min 
f(x(k))T.x
s.t. Ax＝0
‖x－x(k)‖∞≤ε (20)
式中 ε为任意给定的小正数。
③设问题(20)的最优解为x*。若f(x(k))T.(x*－x(k))＝0，则停止计算，x*为K－T点。否则，x*－x(k)就是问题的可行下降方向，转④;
④令
式中 i、xi、x*i和x(k)i分别为、x、x*和x(k)的第i个元素。
再令
λmax＝min｛δi，i＝1，2，…，n｝
⑤在［0，λmax］上作一维搜索
min f［x(k)＋λ(x*－x(k))］
s.t. 0≤λ≤λmax
得到最优解λk，令
x(k＋1)＝x(k)＋λk.(x*－x(k))
⑥置k为k＋1，返回②。
算法的关键在于快速求解线性最小费用循环流问题(20)。求解线性最小费用循环流问题的算法最早由Fulkerson和Minty［6］于1962年提出。文［7］提出了另一种算法，该算法是Fulkerson和Minty提出的Out of Kilter算法的扩展，可用来处理可分的非线性最小费用循环流问题。该算法也可用来求解线性最小费用循环流问题，与Out of Kilter算法相比，它更为快捷。
本文提出的算法可用来处理一般的非线性最小费用循环流问题，而且有着速度快、收敛性好的特点。算法的最优性证明和收敛性证明请参见文［5］。
5 应用实例
应用本文提出的模型和算法，对文［1］中2个火电厂、4个水电厂的例题进行了试算。计算在AMD K6-233机器上进行，计算时间为7 s。计算结果列于表1和表2。表1为每个水电厂每时段的用水量，表2为每个火电厂每时段的发电量。计算结果与文献［1］所给结果接近，说明本文提出的模型和算法是正确的。
表1 各水电厂每时段最优用水量
t 1 2 3 4 5 6 7 8 9 10 11 12 Q1 5.3 6.5 7.1 8.0 8.7 9.9 9.1 8.0 7.0 7.3 5.0 5.0 Q2 6.4 7.3 8.3 8.9 10.3 11.6 11.2 11.1 11.7 6.9 6.8 ——此文章转载于互联网，文中观点与本网站无关，如有侵权请联系删除
