数学规划的解题方法

1.线性规划

线性规划（Linear Programming，简称LP）方法是一种研究较早、方法成熟的运筹学重要分支，其目的是为合理利用有限的资源做出最优决策而提供科学的依据。该方法不依赖于初始可行解，具有全局收敛性，并具备了完善的敏感性分析对偶理论，同时，该方法易于编程实现，且已形成了很多通用的计算工具及程序[20-23]，便于大规模优化问题的建模求解，是水电站群优化调度领域最早广泛应用的优化算法之一[24]。比如Mannos[25]早在1955年就采用LP方法求解水库优化调度问题，推求最优运行策略；Dorfman[26]在其著作中介绍了3种不同复杂度的LP求解模型，并阐述了各模型求解水库调度问题的应用条件。Windsor和James[27]采用递推线LP求解水电站群防洪优化调度策略，但是，该方法假定预报信息是准确的，具有一定的局限性。Hiew等[28]根据北科罗拉多州大汤普森河8库水电站群系统的30年径流资料，利用LP方法求解多组水电站群优化调度策略的样本点，再通过线性回归方法得到最优调度曲线。Crawley和Dandy[29]采用线性目标规划方法，在考虑满足系统供水保证率要求前提下，求解水电站群最优调度策略，指导水电站群调度。由于线性规划方法的应用需要满足约束条件和目标函数线性化的要求，在处理具有非线性特点的水电站群优化调度问题时，需要对调度模型计算条件（比如水位-库容曲线、尾水位-泄流曲线、发电耗水率曲线等）作一定的假设或简化，通过合理的方式对计算条件进行近似线性化处理，优化解精度具有一定的限制。因此，可通过LP方法获得一个初始解或者近似优化解，再采用其他优化技术得到精度更高的优化解。

2.非线性规划

与LP相比，非线性规划（Nolinear Programming，简称NLP）方法求解的优化问题中常常包含非线性约束条件或阶段不可分目标函数，其求解思路通常是线性化NLP问题的非线性约束使其转化为LP问题，或者采用惩罚函数或者障碍函数处理约束条件，并纳入目标函数中构造成新的无约束优化目标函数进行求解。该方法始于20世纪50年代初，经过多年的发展，形成了很多有效的求解方法，并在水电站群优化调度领域广泛应用，主要包括连续线性规划（SLP）[30-32]、连续二次规划（SQP）[33-36]、广义既约梯度法（GRG）[37-39]等。Grygier和Stedinger[40]提出，SLP采用泰勒展开公式前2项，在初始解或可行解附近对非线性约束或目标进行线性化处理，通过不断迭代收敛到最优解。与其他非线性规划方法相比，SLP具有最好的求解效率，而且与LP-DP等方法在最优性、实现难易程度以及计算时间上进行了对比，但是，Bazarra等[41]指出SLP方法的收敛性无法得到保证。SQP通过拉格朗日函数处理目标函数，但是该方法随着计算时段的增长呈指数增长，难以应用于隐随机优化问题。因此，Arnold等[33]根据水电站群优化问题的特殊结构，对问题进行一定的简化，提出了一种计算时间与时段呈线性增长关系的SQP求解方法。GRG是根据单纯形法推广到非线性等式约束中而产生的一种梯度下降搜索方法，该方法应用于水电站群优化调度问题时，需将决策变量简化为相互独立，并通过带约束的梯度下降方法进行求解。总体而言，与LP相比，NLP方法更加符合水电站群优化调度问题的非线性特点，但是，NLP难以考虑随机性因素，且针对不同的优化问题所采用的求解方法不同，没有通用的求解工具和方法。另外，计算时间较长、求解效率较低也对该方法的广泛应用造成一定的影响。

3.混合整数规划混合整数规划（Mixed Integer Programming，简称MIP）方法是数学规划方法的重要分支，多用于涉及离散变量的数学规划问题，且优化问题的变量通常包含整数取值和非整数取值。该方法常常与线性规划和非线性规划相结合，可分为线性混合整数规划和非线性混合整数规划，常用的求解方法包括分支定界法、割平面法等，在处理水电站群优化调度问题中的机组开停机状态、运行时间等约束具有较好的效果。比如，Trezos等[42]以发电量最大为目标，构建了线性混合整数规划模型求解Big Creek流域水电站群长期发电优化调度策略。贾江涛等[43]考虑到水头对水电站群优化调度的影响，以水头作为离散化变量，将各水库机组在不同时段的开关机处理为多维的0～1约束，建立了线性混合整数规划模型求解水电站群短期发电调度问题，并采用计算工具CPLEX在3库12台机组的水电系统中验证了方法的有效性。吴宏宇等[44]将水火电联合调度系统中的非线性约束线性化处理，并把安全约束机组组合问题转换为线性混合整数规划问题进行求解，获得了满意的调度方案。Goganis和Sarimveis[45]通过二次混合整数规划方法（属于非线性混合整数规划）求解水火联合调度的最小花费问题。但是，对于规模较大、离散变量较多的优化问题，采用混合整数规划方法求解将非常困难且计算时间过长，难以广泛应用。

4.动态规划

动态规划（Dynamic Programming，简称DP）方法是水电站群优化调度领域最经典且应用最为广泛的优化搜索技术[16]。该方法是一种多阶段决策最优化数学方法，能够将多阶段决策过程转化为多个单阶段决策过程，利用各单阶段之间的相互关系递推求解各单阶段最优决策，能收敛到全局最优解。DP基本思想是最优化原理[46]，即最优策略的一个子策略对于它的初态和终态而言也必是最优的；同时，DP问题必须满足无后效性，即当前阶段状态不受之后阶段的状态所影响。DP方法对目标函数和约束条件的表现形式没有特殊的要求，可以处理优化问题中存在的非凸、非线性、连续性等因素，也易于随机因素的显性描述[47]，是求解水电站群优化调度问题非常有效的方法[48-54]。1965年Dahlin和Shen[55]为了获得包含水电和凝气机组的电力系统最优调度策略，采用动态规划方法求解以调度费用最小为目标的水电站群优化调度问题。Harley和Chidley[56]在1978年利用确定性动态规划方法制定水电站长期优化调度策略，探讨了数据序列长度和系统规模对方法的影响，并与仿真方法进行了比较。由于动态规划方法是通过变量离散实现最优决策的递推求解，随着水电系统规模的加大，计算机占用的内存以及计算耗时呈指数增长，造成维数灾问题。因此，学者们一直非常重视对动态规划方法的改进，尤其是如何降低动态规划方法维数。目前，通过学者们多年的研究，产生了很多改进的降维动态规划方法，主要以增量动态规划、离散微分动态规划、动态规划逐次逼近以及逐步优化算法等应用较为常见。

（1）增量动态规划。在动态规划方法中引入状态增量的求解思想，最早由Larson[57]在1968年提出，之后Hall等[58]在1969年提出了同样考虑状态增量的不同版本，并将这种方法命名为增量动态规划（Incremental Dynamic Programming，简称IDP）方法。该方法是一种迭代优化搜索技术，求解思路为根据给定增量在初始可行解附近设置搜索范围，快速地在有限的搜索空间内获得优化解，并且将获得的优化解作为下一次迭代的初始解，反复迭代直至计算收敛。

（2）离散微分动态规划。Hiedari等[59]在IDP的基础上，引入了离散化的思想，提出了能体现IDP概化形式的离散微分动态规划（Discrete Differential Dynamic Programming，简称DDDP）方法，并应用于一个4库水电系统求解长期最优调度策略。两者的区别在于前者的时段间隔在优化过程中是作为变量，而后者是作为固定值。因此，DDDP方法属于一种特殊的IDP方法，且状态增量在DDDP方法中被称为“廊道”。1975年，Chow等[60]在文献中分析了DP和DDDP的计算过程，列出了两者在处理水电站群优化调度问题时面临的空间复杂度和时间复杂度计算公式，并通过实例说明了DDDP方法的计算效率明显优于DP方法。Nopmongcol和Askew[61]在1976年采用多层IDP（MIDP）方法与文献[61]进行对比，结果显示MIDP比IDP具有更高的求解效率，而且更加适合求解高维问题。纪昌明和冯尚友[62]在1984年采用DDDP方法求解目标函数中嵌入惩罚函数的水电站群长期优化调度问题，并在汉江流域3库混联式水电系统验证了方法的收敛性及有效性。谢柳青和易淑珍[63]将马斯京根洪水演进与DDDP相结合，建立了水电站群多目标DDDP防洪优化调度模型，并采用大系统分解协调方法进行求解。

（3）动态规划逐次逼近。动态规划逐次逼近（Dynamic Programming Successive Approximations，简称DPSA）方法的降维性主要体现在能够将一个多维优化问题分解为一系列只含1个状态变量的一维问题，且每次迭代只优化1个状态变量，其他状态变量保持固定状态。Yeh和Trott[64]采用DPSA方法求解美国中央峡谷工程库群优化调度策略。程春田等[65]在制定乌江流域梯级水电站群优化调度图时，以初始调度图中各条基本调度线的控制点为状态变量，利用DPSA方法进行优化模拟，优化调度图的模拟结果优于初始调度图。李克飞等[66]建立了水库发电优化调度模型，并采用动态规划逐次逼近法（DPSA）与动态规划（DP）嵌套模型进行求解。另外，Opan等[67]和韩冰等[68]采用DPSA方法研究库群优化调度问题，并取得了不错的效果。

（4）逐步优化算法。逐步优化算法（Progressive Optimality Algorithm，简称POA）的求解特点是将一个多阶段优化问题分解为多个连续的两阶段子优化问题，并逐一迭代优化，经过多轮迭代直至满足收敛条件，得到优化解。该方法最早在1975年由加拿大学者Howson和Sancho[69]提出，在水电站群优化调度领域应用较为广泛[70-74]。梁虹和颜竹丘[75]提出了梯级水电站群保证出力最大及其子电站出力分配模型，并采用POA求解。费良军等[76]对1个多调度任务的水资源系统建立了多目标联合调度模型，通过POA与混合试探法结合对模型求解，结果表明该方法计算效率高，能获得满意的优化解。Cheng等[77]将时段变尺度思想与POA方法相结合，提出了变尺度逐步优化方法求解水电站群短期优化调度差异化目标模型，并与单一目标的优化解作比较，证明获得的优化解更优。李基栋等[78]提出并采用了二重POA计算方法对雅砻江下游梯级水库联合运行水位控制方式开展研究，得到了不同来水频率条件下的优化水库水位控制方式。另外，周建中等[79]、纪昌明等[80]采用POA方法分别对水电系统调峰问题和梯级水库调度图优化问题进行了研究，优化效果显著。

虽然上述改进方法有效地缓解了动态规划维数灾问题，但是对于大规模水电系统求解依然无法从本质上避免维数灾，且都存在明显的缺陷。比如，IDP、DDDP、DPSA以及POA对初始解非常敏感，很多学者就这些方法对初始解的敏感性做了大量的研究工作[81-84]，证明不是所有的初始解都可以收敛获得最优解；IDP、DDDP和POA是局部搜索方法，而DPSA方法只有在凸函数问题中可收敛至全局最优解，对于非凸函数问题，甚至局部最优解也无法保证能够获得。因此，学者们仍然致力于探索DP方法降维改进的新思路[85-89]。

5.多目标规划(www.xing528.com)

多目标规划（Multi-Objective Programming，简称MOP）是数学规划的一个分支，基本思想是在给定的搜索空间内求解多个目标函数的最优化，也被称为多目标最优化。该方法的基本求解思路通常有三种。一是通过常用的线性加权法等将多个目标函数转化为更易求解的单目标或双目标函数，但是，优化解对权重集具有很强的依赖性，不同的权重集可能会得到不同的优化解。二是采用分层序列法、层次分析法等，先对高层次的目标优化，在获得的当前最优解集内对下一层次的目标函数进行优化，直至求得所有目标函数的共同优化解。三是通过ε-约束方法建立优化问题的非劣解集，再采用其他数学方法从解集中获得最优解。由于水电站在实际调度中常需满足多个调度任务，因此，多目标规划方法更加符合水电站群优化调度领域实际情况，应用较为广泛[90-97]。在2000年Mousavi和Ramamurthy[98]通过ε-约束方法处理不同量级的费用最小目标和供水缺水量最小两个目标，采用最优控制理论和惩罚连续线性规划方法求解水电站群供水策略。彭杨等[99]建立了溪洛渡-向家坝梯级水电站考虑防洪、发电、通航、排沙的多目标决策模型，通过ε-约束方法处理多目标，采用鲶鱼效应粒子群算法生成非劣解集，再根据加权理想点法进行评价。黄草等[100，101]建立了长江上游水库群多目标优化调度模型，提出了水库群调度规则及蓄放次序。此外，很多学者如王本德等[102]、谢新民等[103]、邹进和张勇传[104]采用模糊优化方法求解多目标决策问题。

6.网络流规划

网络流规划（Network Flow Programming，简称NFP）方法属于一种图论理论和方法，能够求解具有网络结构特点的一类优化问题，是一种特殊的线性或非线性规划方法。考虑到水电站群优化调度问题的约束条件多呈现线性集合的特点，NFP方法将水电站群系统的内在联系描述为具有一系列网络节点和网络弧的网络结构[105]，网络节点表示水电站或水库，网络弧则表示水电站发电、泄量、蒸发等相关属性，约束条件上下限则表示为弧容量[106，107]，其基本求解思想为从初始可行流逐步逼近最优可行流，且求解过程中要求所有中途点流入量和流出量保持平衡[108]。刘广一[109]等在1987年建立了具有混联水电站群的水火电联合调度网络流模型，运用连续线性规划方法处理非线性的火电运行总费用最小目标函数，采用原始网络流和对偶网络流相结合进行求解。罗强等[110]建立了非线性网络流模型，结合连续线性规划和逆境法，求解3库梯级水电系统的多目标优化问题。NFP方法具有模型表现清晰直观、计算速度快、占用内存少、对复杂约束适应性强等优点，但是，对于网络模型表现困难的优化问题，NFP方法难以求解，使其应用受到了一定的限制。

7.拉格朗日松弛法

拉格朗日松弛（Lagrangian Relaxation，简称LR）是一种用于处理复杂约束的数学理论方法。其基本原理为将优化问题中不易处理且造成目标求解困难的约束条件纳入目标函数中构造成拉格朗日项，并保持目标函数的线性特点，通过拉格朗日乘子的不断更新计算得到原问题的下界，简化求解难度。由于LR方法具有简单易实现、计算效率高等优点，因此，在水电站群优化调度领域常用于求解存在系统关联约束的优化问题或组合优化问题[111-114]，而且适合与其他优化技术相结合，提高求解效率。

8.大系统分解协调

大系统分解协调（Decomposition-Coordination，简称DC）方法是大规模系统优化问题的高效求解方法[115-117]。DC方法的求解原理是将一个给定的大规模系统分解为多个更小规模且相互联系的子系统，然后采用适合的优化技术计算各个子系统的优化解[118]，再根据各子系统之间的关联关系，寻找上层协调器和下层子系统的耦合关系，调整各子系统的输入和输出，实现整个系统总目标的最优化[119]。DC方法可以有效降低大规模水电系统优化调度问题的维数，减小计算规模以及提高求解效率。高仕春等[120]采用DC求解三峡-清江梯级水电站群联合优化调度问题，将原问题分解为三峡梯级和清江梯级两个子系统，考虑到子系统之间的电力联系，采用DDDP方法分别求解。李安强等[121]根据各防洪区域对溪洛渡、向家坝预留防洪库容的需求，利用DC方法求解确定了两库的防洪库容分配方案，在此基础上进一步研究了配合三峡水库对长江中下游的联合防洪调度。贾本有等[122]以淮河中游防洪系统为研究实例，建立了以水库群系统安全度最大、行蓄洪区系统损失最小的防洪调度模型，并基于大系统分解协调法建立协调层和基于粒子群算法求解底层子系统优化问题，形成三级递阶分解协调结构和相应求解方法。此外，李爱玲[123]、解建仓等[124]也成功地应用DC方法解决了水电站群联合优化调度问题，并得到了满意的优化结果。

9.随机优化

随机优化（Stochastic Optimization，简称SO）方法的基本原理是在构建的数学模型中充分考虑随机因素的影响，采用适合的优化技术进行求解，使优化结果更加符合实际。入库流量是水电站群优化调度领域常见的随机因素，根据模型对入库流量随机性体现方式的不同[125]，主要分为隐随机优化和显随机优化。

隐随机优化（Implicit Stochastic Optimization，简称ISO）方法也称为Monte Carlo优化，其求解思路是依据已有的历史径流长时间序列或者通过径流模拟随机生成多组径流序列，采用确定性优化技术生成一系列优化调度样本，构成包含水库运行状态和水库调度决策的调度结果样本集，然后运用多元线性回归[126-128]、人工神经网络[129-131]方法统计分析隐藏在结果样本集中的运行规律，制定水电站（群）的调度函数及相应的调度规则，指导水电站（群）实际调度运行。万俊等[132]采用ISO方法，根据已有的27年历史径流资料，以旬为时段，采用POA方法求解综合利用水电站群优化调度最优轨迹，并以多元线性回归方法得到各旬的调度函数，通过模拟调度与常规调度结果作比较，验证了方法的有效性。胡铁松等[133]先利用DC方法和DDDP方法优化3库并联供水水电站群，获得优化调度策略集合，并以此作为人工神经网络的训练样本求得水电站群优化调度函数。ISO方法虽然能够在得到的调度函数或调度规则中体现径流的随机性，但是，由于径流资料是确定性的，优化调度策略具有唯一性，而且在采用数学统计分析方法确定调度函数的过程中，难以考虑径流相关性等因素，导致优化结果的应用具有局限性。因此，很多学者[134-136]仍然致力于研究鲁棒性更强、应用性更好的隐随机方法。

与隐随机优化相比，显随机优化（Explicit Stochastic Optimization，简称ESO）方法直接采用概率描述径流随机性[16]。ESO方法替代了确定性径流过程求解优化问题，径流过程不需要假设为确定已知的。ESO模型主要有两种[137]：一种是根据问题实际情况或者简化计算，随机径流作为相互独立的参数描述在目标函数中；另一种则需要考虑随机径流的相关关系（比如马尔科夫链），这种方式求解较为复杂，常用于单库优化。目前，ESO方法已成功与其他优化技术（如LP、DP等）相结合[138-141]，其中，随机动态规划（Stochastic Dynamic Programming，简称SDP）方法应用最为广泛，且取得非常多的研究成果[142-148]。随着众多学者对SDP方法深入研究，衍生了多种不同的SDP求解方法，包括抽样随机动态规划（Sampling Stochastic Dynamic Programming，简称SSDP）[149-151]、机会约束动态规划（Chance-constrained Dynamic Programming，简称CCDP）[152-155]、随机双重动态规划（Stochastic Dual Dynamic Programming，简称SDDP）[156-159]等。这些方法的区别在于选取随机径流的方式不同或者对约束条件的处理方式不同，比如，SSDP方法通过随机抽样获得径流序列的出现概率，CCDP方法则适用于处理具有机会约束的优化调度模型。但是，这些SDP方法都存在求解效率低下的缺点，尤其是求解大规模优化问题时，遭受“维数灾”问题的影响比确定性DP方法更为严重。