电力系统优化模型与方法的讲义.doc

建模与优化方法在电力系统的应用Modeling and Optimization Methods for Power SystemSchool of Electrical Engineering, Shandong University, Jinan 250061, PR China* Corresponding author, E-mail address: Abstract: This course is for all the eager young talents. The vast power system is the most complicated man-made system and the greatest engineering innovation in the 20th century. To design, operate and control such a system must use the methods of modeling and optimization. Thus for the future engineers and managers in the power industry, its significant to learn the knowledge and methodologies that will help to make the reasonable decisions in the future career. The course is structured with two categories of contents which are the basic knowledge and the application. The knowledge is introduced as different optimization models such as the linear planning and the dynamic planning. While the application is based on a power system case analysis and project design. With more models being introduced, the project will be developed from a quite simple one to fairly challengeable at last.Keywords: 线性规划; 整数规划; 动态规划；多目标规划；Possibly the Game Theory 1. 第一次课，绪论 The first class, Introduction博弈论（Game Theory），亦名“对策论”、“赛局理论”，属应用数学的一个分支, 目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。 博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。定义：根据信息分析及能力判断，研究多决策主体之间行为相互作用及其相互平衡，以使收益或效用最大化的一种对策理论。博弈要素：1.决策人：在博弈中率先作出决策的一方，这一方往往依据自身的感受、经验和表面状态优先采取一种有方向性的行动。（博弈圣经） 2.对抗者：在博弈二人对局中行动滞后的那个人，与决策人要作出基本反面的决定，并且他的动作是滞后的、默认的、被动的，但最终占优。他的策略可能依赖于决策人劣势的策略选择，占去空间特性，因此对抗是唯一占优的方式，实为领导人的阶段性终结行为。（博弈圣经）意义：博弈论的研究方法和其他许多利用数学工具研究社会经济现象的学科一样，都是从复杂的现象中抽象出基本的元素，对这些元素构成的数学模型进行分析，而后逐步引入对其形势产影响的其他因素，从而分析其结果。 应用举例：1.经典的囚徒困境：警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择： 若一人认罪并作证检控对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监10年。 若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。 若二人都互相检举（相关术语称互相“背叛”），则二人同样判监8年。 用表格概述如下： 甲沉默甲认罪乙沉默二人同服刑1年乙服刑10年，甲即时获释乙认罪甲服刑10年，乙即时获释二人同服刑8年解说如同博弈论的其他例证，囚徒困境假定每个参与者（即“囚徒”）都是利己的，即都寻求最大自身利益，而不关心另一参与者的利益。参与者某一策略所得利益，如果在任何情况下都比其他策略要低的话，此策略称为“严格劣势”，理性的参与者绝不会选择。另外，没有任何其他力量干预个人决策，参与者可完全按照自己意愿选择策略。 囚徒到底应该选择哪一项策略，才能将自己个人的刑期缩至最短？两名囚徒由于隔绝监禁，并不知道对方选择；而即使他们能交谈，还是未必能够尽信对方不会反口。就个人的理性选择而言，检举背叛对方所得刑期，总比沉默要来得低。试设想困境中两名理性囚徒会如何作出选择： 若对方沉默、背叛会让我获释，所以会选择背叛。 若对方背叛指控我，我也要指控对方才能得到较低的刑期，所以也是会选择背叛。 二人面对的情况一样，所以二人的理性思考都会得出相同的结论选择背叛。背叛是两种策略之中的支配性策略。因此，这场博弈中唯一可能达到的纳什均衡，就是双方参与者都背叛对方，结果二人同样服刑2年。 这场博弈的纳什均衡，显然不是顾及团体利益的帕累托最优解决方案。以全体利益而言，如果两个参与者都合作保持沉默，两人都只会被判刑半年，总体利益更高，结果也比两人背叛对方、判刑2年的情况较佳。但根据以上假设，二人均为理性的个人，且只追求自己个人利益。均衡状况会是两个囚徒都选择背叛，结果二人判决均比合作为高，总体利益较合作为低。这就是“困境”所在。2.重复博弈：有一个好人，一个坏人，两人手中都拿有一把枪，两人相对而行，先开枪者可以保存性命，请问谁先开枪？分析：若好人因善良，不先开枪，那坏人由于其坏的本质，肯定会开枪；若好人想到坏人会开枪，造成好人去世坏人遗祸，好人会先坏人一步开枪；若坏人想到好人想到坏人会开枪，造成好人去世坏人遗祸，好人会先坏人一步开枪，那坏人会在好人之前开枪；最后得出的结论是两人均尽可能早地开枪。以上为典型的重复博弈，顾名思义，重复博弈是指同样结构的博弈重复许多次，其中的每次博弈称为“阶段博弈”（stage games）。重复博弈是动态博弈中的重要内容，它可以是完全信息的重复博弈，也可以是不完全信息的重复博弈。 重复博弈是指同样结构的博弈重复许多次。当博弈只进行一次时，每个参与人都只关心一次性的支付；如果博弈是重复多次的，参与人可能会为了长远利益而牺牲眼前的利益，从而选择不同的均衡策略。因此，重复博弈的次数会影响到博弈均衡的结果。2. 第二次课，关于电力系统优化的线性规划问题研讨教材推荐管理运筹学韩伯棠 高等教育出版社 工具推荐Matlab优化工具箱同学们可以参照阅读线性规划问题的模型组成： MinZ=CX St.TX=B TX =B转化为标准型： TX+TX=B X为松弛变量插入项目原题问题：I 概率计算II负荷中断 故障Pg=Pload PgPloadFploss=C(Pload-P6) =C（要求负荷-）决策变量 Pi= Pi(1-Z) 课堂问题：容量成本：单千瓦造价5000元/KW 30年收回燃料成本：290g/kw.h求每度电的成本。解析：成本=固定成本+变动成本在本题中应先解决固定成本的问题，及计算单位固定成本。令一年发5000h的电， 则单千瓦时固定成本=0.03元 即 单位成本=单位千瓦时固定成本+单位千瓦时耗煤成本而电价= 单位固定成本+单位燃料成本+*利润 成本 B A Q变动 注：A代表固定成本 B代表变动成本 Qi关于该线性规划问题的总结：关键字：建模方法 总结问题：分配发电机组发电功率（在满足负荷要求的前提下）使发电成本和负荷中断的损失最少。MinZ=Cost6 +Costploss (负荷中断损失) =煤耗率煤价+单位造价（单位电量的固定成本）+CplossPload- 价值系数约束条件：PiminPiPimax上述模型存在不足，请同学们思考并建立自己更好的模型建模和求解是解决优化的两个基本问题求解参照 单纯型法，计算机辅助求解3. 线性规划 Linear Planning在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。3.1 线性规划的实例与定义例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产台甲机床和乙机床时总利润最大，则应满足（目标函数） (1)s.t.（约束条件） （2）这里变量称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。3.2 线性规划的Matlab标准形式线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab中规定线性规划的标准形式为其中和为维列向量，为维列向量，为矩阵。例如线性规划的Matlab标准型为 3.3 线性规划问题的解的概念一般线性规划问题的标准型为 (3) (4)可行解 满足约束条件（4）的解，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。可行域 所有可行解构成的集合称为问题的可行域，记为。3.4 线性规划的图解法图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。如上图所示，阴影区域即为LP问题的可行域R。对于每一固定的值，使目标函数值等于的点构成的直线称为目标函数等位线，当变动时，我们得到一族平行直线。让等位线沿目标函数值减小的方向移动，直到等位线与可行域有交点的最后位置，此时的交点（一个或多个）即为LP的最优解。对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为，最优目标值。从上面的图解过程可以看出并不难证明以下断言：（1）可行域可能会出现多种情况。可能是空集也可能是非空集合，当非空时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。既可能是有界区域，也可能是无界区域。（2）在非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。（3）R非空且LP有有限最优解时，最优解可以唯一或有无穷多个。（4）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域的“顶点”。上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的维空间中，满足一线性等式的点集被称为一个超平面，而满足一线性不等式（或）的点集被称为一个半空间（其中为一维行向量，为一实数）。有限个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集也被视为多胞形）。在一般维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。定义1 称维空间中的区域为一凸集，若及，有。定义2 设为维空间中的一个凸集，中的点被称为的一个极点，若不存在及，使得。定义1 说明凸集中任意两点的连线必在此凸集中；而定义2 说明，若是凸集的一个极点，则不能位于中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域的顶点均为的极点（也没有其它的极点）。3.5 求解线性规划的Matlab解法*单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab解法。Matlab5.3中线性规划的标准型为 基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。 例2 求解下列线性规划问题 解 （i）编写M文件c=2;3;-5;a=-2,5,-1; b=-10;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c*x（ii）将M文件存盘，并命名为example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。求解线性规划问题 解 编写Matlab程序如下：c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-b,zeros(3,1)1.6 可以转化为线性规划的问题很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如：问题为其中，和为相应维数的矩阵和向量。要把上面的问题变换成线性规划问题，只要注意到事实：对任意的，存在满足 ，事实上，我们只要取，就可以满足上面的条件。这样，记，从而我们可以把上面的问题变成 4. Exercise4.1 通过下列问题联系建立简单线性规划问题模型的方法以及模型的形式1. 某厂生产三种产品I，II，III。每种产品要经过两道工序加工。设该厂有两种规格的设备能完成工序，它们以表示；有三种规格的设备能完成工序，它们以表示。产品I可在任何一种规格设备上加工。产品II可在任何规格的设备上加工，但完成工序时，只能在设备上加工；产品III只能在与设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润最大。设备产 品设备有效台时满负荷时的设备费用(元)IIIIII5764710981211600010000400070004000300321250783200原料费(元/件)单 价(元/件)52.000.502.802. 有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表： 工作工人甲乙丙丁15192619182317212122162324181917 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？3. 某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米，带轻型炸弹时每升汽油可飞行3千米。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4千米）外，起飞和降落每次各消耗100升。有关数据如表所示。要害部位离机场距离（千米）摧毁可能性每枚重型弹每枚轻型弹123445048054060050.250.00为了使摧毁敌方军事目标的可能性最大，应如何确定飞机轰炸的方案，要求建立这个问题的线性规划模型。4.2 电力系统的经济调度问题模型电力系统的概念：由发电、变电、输电、配电和用电等环节组成的电能生产、传输、分配和消费的系统。电力系统的目标：1、满足用电需求。（可靠性）2、满足经济实用。（经济性）例：供电厂给居民区和工厂供电，居民区需电量为500MW，工厂需电量为1000MW，选择合适的配置发电机组的方法在最大程度上满足电力系统的目标。 条件（供电机） 容量MW 煤耗g/kwh 单机故障率 1000 290 1% 600 310 5% 300 320 7% 200 350 10%煤价：1000元/吨 投资：5000元/千瓦 Pg：50%100%方法：数学建模5. 对偶理论与灵敏度分析5.1 原始问题和对偶问题考虑下列一对线性规划模型： s.t. (P)和 s.t. (D)称（P）为原始问题，（D）为它的对偶问题。不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：原始问题约束条件中的第列系数与其对偶问题约束条件中的第行的系数相同；原始目标函数的系数行与其对偶问题右侧的常数列相同；原始问题右侧的常数列与其对偶目标函数的系数行相同；在这一对问题中，除非负约束外的约束不等式方向和优化方向相反。考虑线性规划：把其中的等式约束变成不等式约束，可得 它的对偶问题是其中和分别表示对应于约束和的对偶变量组。令，则上式又可写成原问题和对偶的对偶问题约束之间的关系： 5.2 对偶问题的基本性质1o 对称性：对偶问题的对偶是原问题。2o 弱对偶性：若是原问题的可行解，是对偶问题的可行解。则恒有：。3o 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4o 可行解是最优解时的性质：设是原问题的可行解，是对偶问题的可行解，当时，是最优解。5o 对偶定理：若原问题有有限最优解，那么对偶问题也有最优解；且目标函数值相同。6o 互补松弛性：若分别是原问题和对偶问题的最优解，则 由上述性质可知，对任一LP问题(P)，若它的对偶问题(D)可能的话，我们总可以通过求解（D）来讨论原问题（P）：若(D)无界，则(P)无可行解；若(D)有有限最优解，最优值，则利用互补松弛性可求得(P)的所有最优解，且(P)的最优值为。例如对只有两个行约束的LP，其对偶问题只有两个变量，总可用图解法来求解。例9 已知线性规划问题 已知其对偶问题的最优解为，最优值为。试用对偶理论找出原问题的最优解。解 先写出它的对偶问题 s.t. 将的值代入约束条件，得，为严格不等式；设原问题的最优解为，由互补松弛性得。因 ；原问题的两个约束条件应取等式，故有求解后得到；故原问题的最优解为 ；最优值为。 5.3 灵敏度分析灵敏度分析是指对系统或周围事物因周围条件变化显示出来的敏感程度的分析。在以前讨论线性规划问题时，假定都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，值就会变化；往往是因工艺条件的改变而改变；是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这些参数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者