電力系統(tǒng)優(yōu)化模型與方法的講義

1、建模與優(yōu)化方法在電力系統(tǒng)的應(yīng)用Modeling and Optimization Methods for Power SystemSchool of Electrical Engineering, Shandong University, Jinan 250061, PR China* Corresponding author, E-mail address: yudayangAbstract: This course is for all the eager young talents. The vast power system is the most complicated man-ma

2、de 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

3、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 applica

4、tion 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: 線性規(guī)劃; 整數(shù)規(guī)劃; 動態(tài)規(guī)劃；多目標規(guī)劃；Possibly the Game Theory 1. 第一次課，緒論 The first class, Introduction博弈論（Game Theory

5、），亦名“對策論”、“賽局理論”，屬應(yīng)用數(shù)學的一個分支, 目前在生物學、經(jīng)濟學、國際關(guān)系、計算機科學、政治學、軍事戰(zhàn)略和其他很多學科都有廣泛的應(yīng)用。博弈論主要研究公式化了的激勵結(jié)構(gòu)間的相互作用。是研究具有斗爭或競爭性質(zhì)現(xiàn)象的數(shù)學理論和方法。也是運籌學的一個重要學科。 博弈論考慮游戲中的個體的預(yù)測行為和實際行為，并研究它們的優(yōu)化策略。定義：根據(jù)信息分析及能力判斷，研究多決策主體之間行為相互作用及其相互平衡，以使收益或效用最大化的一種對策理論。博弈要素：1.決策人：在博弈中率先作出決策的一方，這一方往往依據(jù)自身的感受、經(jīng)驗和表面狀態(tài)優(yōu)先采取一種有方向性的行動。（博弈圣經(jīng)） 2.對抗者：在博弈二人對

6、局中行動滯后的那個人，與決策人要作出基本反面的決定，并且他的動作是滯后的、默認的、被動的，但最終占優(yōu)。他的策略可能依賴于決策人劣勢的策略選擇，占去空間特性，因此對抗是唯一占優(yōu)的方式，實為領(lǐng)導人的階段性終結(jié)行為。（博弈圣經(jīng)）意義：博弈論的研究方法和其他許多利用數(shù)學工具研究社會經(jīng)濟現(xiàn)象的學科一樣，都是從復(fù)雜的現(xiàn)象中抽象出基本的元素，對這些元素構(gòu)成的數(shù)學模型進行分析，而后逐步引入對其形勢產(chǎn)影響的其他因素，從而分析其結(jié)果。 應(yīng)用舉例：1.經(jīng)典的囚徒困境：警方逮捕甲、乙兩名嫌疑犯，但沒有足夠證據(jù)指控二人入罪。于是警方分開囚禁嫌疑犯，分別和二人見面，并向雙方提供以下相同的選擇： 若一人認罪并作證檢控對方（

7、相關(guān)術(shù)語稱“背叛”對方），而對方保持沉默，此人將即時獲釋，沉默者將判監(jiān)10年。 若二人都保持沉默（相關(guān)術(shù)語稱互相“合作”），則二人同樣判監(jiān)1年。 若二人都互相檢舉（相關(guān)術(shù)語稱互相“背叛”），則二人同樣判監(jiān)8年。 用表格概述如下： 甲沉默甲認罪乙沉默二人同服刑1年乙服刑10年，甲即時獲釋乙認罪甲服刑10年，乙即時獲釋二人同服刑8年解說如同博弈論的其他例證，囚徒困境假定每個參與者（即“囚徒”）都是利己的，即都尋求最大自身利益，而不關(guān)心另一參與者的利益。參與者某一策略所得利益，如果在任何情況下都比其他策略要低的話，此策略稱為“嚴格劣勢”，理性的參與者絕不會選擇。另外，沒有任何其他力量干預(yù)個人決策，參

8、與者可完全按照自己意愿選擇策略。 囚徒到底應(yīng)該選擇哪一項策略，才能將自己個人的刑期縮至最短？兩名囚徒由于隔絕監(jiān)禁，并不知道對方選擇；而即使他們能交談，還是未必能夠盡信對方不會反口。就個人的理性選擇而言，檢舉背叛對方所得刑期，總比沉默要來得低。試設(shè)想困境中兩名理性囚徒會如何作出選擇： 若對方沉默、背叛會讓我獲釋，所以會選擇背叛。 若對方背叛指控我，我也要指控對方才能得到較低的刑期，所以也是會選擇背叛。 二人面對的情況一樣，所以二人的理性思考都會得出相同的結(jié)論選擇背叛。背叛是兩種策略之中的支配性策略。因此，這場博弈中唯一可能達到的納什均衡，就是雙方參與者都背叛對方，結(jié)果二人同樣服刑2年。 這場博弈

9、的納什均衡，顯然不是顧及團體利益的帕累托最優(yōu)解決方案。以全體利益而言，如果兩個參與者都合作保持沉默，兩人都只會被判刑半年，總體利益更高，結(jié)果也比兩人背叛對方、判刑2年的情況較佳。但根據(jù)以上假設(shè)，二人均為理性的個人，且只追求自己個人利益。均衡狀況會是兩個囚徒都選擇背叛，結(jié)果二人判決均比合作為高，總體利益較合作為低。這就是“困境”所在。2.重復(fù)博弈：有一個好人，一個壞人，兩人手中都拿有一把槍，兩人相對而行，先開槍者可以保存性命，請問誰先開槍？分析：若好人因善良，不先開槍，那壞人由于其壞的本質(zhì)，肯定會開槍；若好人想到壞人會開槍，造成好人去世壞人遺禍，好人會先壞人一步開槍；若壞人想到好人想到壞人會開槍

10、，造成好人去世壞人遺禍，好人會先壞人一步開槍，那壞人會在好人之前開槍；最后得出的結(jié)論是兩人均盡可能早地開槍。以上為典型的重復(fù)博弈，顧名思義，重復(fù)博弈是指同樣結(jié)構(gòu)的博弈重復(fù)許多次，其中的每次博弈稱為“階段博弈”（stage games）。重復(fù)博弈是動態(tài)博弈中的重要內(nèi)容，它可以是完全信息的重復(fù)博弈，也可以是不完全信息的重復(fù)博弈。 重復(fù)博弈是指同樣結(jié)構(gòu)的博弈重復(fù)許多次。當博弈只進行一次時，每個參與人都只關(guān)心一次性的支付；如果博弈是重復(fù)多次的，參與人可能會為了長遠利益而犧牲眼前的利益，從而選擇不同的均衡策略。因此，重復(fù)博弈的次數(shù)會影響到博弈均衡的結(jié)果。2. 第二次課，關(guān)于電力系統(tǒng)優(yōu)化的線性規(guī)劃問題研討

11、教材推薦管理運籌學韓伯棠 高等教育出版社 工具推薦Matlab優(yōu)化工具箱同學們可以參照閱讀線性規(guī)劃問題的模型組成： MinZ=CX St.TX=B TX <=B轉(zhuǎn)化為標準型： TX+TX=B X為松弛變量插入項目原題問題：I 概率計算II負荷中斷 故障Pg=Pload Pg<PloadFploss=C(Pload-P6) =C（要求負荷-）決策變量 Pi= Pi(1-Z) 課堂問題：容量成本：單千瓦造價5000元/KW 30年收回燃料成本：290g/kw.h求每度電的成本。解析：成本=固定成本+變動成本在本題中應(yīng)先解決固定成本的問題，及計算單位固定成本。令一年發(fā)5000h的電， 則

12、單千瓦時固定成本=0.03元 即 單位成本=單位千瓦時固定成本+單位千瓦時耗煤成本而電價= 單位固定成本+單位燃料成本+*利潤 成本 B A Q變動 注：A代表固定成本 B代表變動成本 Qi關(guān)于該線性規(guī)劃問題的總結(jié)：關(guān)鍵字：建模方法 總結(jié)問題：分配發(fā)電機組發(fā)電功率（在滿足負荷要求的前提下）使發(fā)電成本和負荷中斷的損失最少。MinZ=Cost6 +Costploss (負荷中斷損失) =煤耗率×煤價+單位造價（單位電量的固定成本）+CplossPload- 價值系數(shù)約束條件：PiminPiPimax上述模型存在不足，請同學們思考并建立自己更好的模型建模和求解是解決優(yōu)化的兩個基本問題求解參

13、照 單純型法，計算機輔助求解3. 線性規(guī)劃 Linear Planning在人們的生產(chǎn)實踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟效益的問題。此類問題構(gòu)成了運籌學的一個重要分支數(shù)學規(guī)劃，而線性規(guī)劃(Linear Programming 簡記LP)則是數(shù)學規(guī)劃的一個重要分支。自從1947年G. B. Dantzig 提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實用中日益廣泛與深入。特別是在計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。3.1 線性規(guī)劃的實例與定義例1 某機床廠生產(chǎn)

14、甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用機器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機床需用三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為機器10小時、機器8小時和機器7小時，問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？上述問題的數(shù)學模型：設(shè)該廠生產(chǎn)臺甲機床和乙機床時總利潤最大，則應(yīng)滿足（目標函數(shù)） (1)s.t.（約束條件） （2）這里變量稱之為決策變量，（1）式被稱為問題的目標函數(shù)，（2）中的幾個不等式是問題的約束條件，記為s.t.(即subject to)。上述即為一規(guī)劃問題數(shù)學模型的三個要素。由于上面的目標函數(shù)及約束

15、條件均為線性函數(shù)，故被稱為線性規(guī)劃問題?？傊?，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標函數(shù)最大或最小的問題。在解決實際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當，直接影響到求解。而選取適當?shù)臎Q策變量，是我們建立有效模型的關(guān)鍵之一。3.2 線性規(guī)劃的Matlab標準形式線性規(guī)劃的目標函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，Matlab中規(guī)定線性規(guī)劃的標準形式為其中和為維列向量，為維列向量，為矩陣。例如線性規(guī)劃的Matlab標準型為 3.3 線性規(guī)劃問題的

16、解的概念一般線性規(guī)劃問題的標準型為 (3) (4)可行解 滿足約束條件（4）的解，稱為線性規(guī)劃問題的可行解，而使目標函數(shù)（3）達到最小值的可行解叫最優(yōu)解?？尚杏?所有可行解構(gòu)成的集合稱為問題的可行域，記為。3.4 線性規(guī)劃的圖解法圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理。我們先應(yīng)用圖解法來求解例1。如上圖所示，陰影區(qū)域即為LP問題的可行域R。對于每一固定的值，使目標函數(shù)值等于的點構(gòu)成的直線稱為目標函數(shù)等位線，當變動時，我們得到一族平行直線。讓等位線沿目標函數(shù)值減小的方向移動，直到等位線與可行域有交點的最后位置，此時的交點（一個或多個）即為LP的最優(yōu)解。對于例1，顯然等位線越趨于右上

17、方，其上的點具有越大的目標函數(shù)值。不難看出，本例的最優(yōu)解為，最優(yōu)目標值。從上面的圖解過程可以看出并不難證明以下斷言：（1）可行域可能會出現(xiàn)多種情況?？赡苁强占部赡苁欠强占?，當非空時，它必定是若干個半平面的交集（除非遇到空間維數(shù)的退化）。既可能是有界區(qū)域，也可能是無界區(qū)域。（2）在非空時，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)解（其目標函數(shù)值無界）。（3）R非空且LP有有限最優(yōu)解時，最優(yōu)解可以唯一或有無窮多個。（4）若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標函數(shù)值的可行域的“頂點”。上述論斷可以推廣到一般的線性規(guī)劃問題，區(qū)別只在于空間的維數(shù)。在一般的維空間中，滿足一線性等式

18、的點集被稱為一個超平面，而滿足一線性不等式（或）的點集被稱為一個半空間（其中為一維行向量，為一實數(shù)）。有限個半空間的交集被稱為多胞形，有界的多胞形又被稱為多面體。易見，線性規(guī)劃的可行域必為多胞形（為統(tǒng)一起見，空集也被視為多胞形）。在一般維空間中，要直接得出多胞形“頂點”概念還有一些困難。二維空間中的頂點可以看成為邊界直線的交點，但這一幾何概念的推廣在一般維空間中的幾何意義并不十分直觀。為此，我們將采用另一途徑來定義它。定義1 稱維空間中的區(qū)域為一凸集，若及，有。定義2 設(shè)為維空間中的一個凸集，中的點被稱為的一個極點，若不存在及，使得。定義1 說明凸集中任意兩點的連線必在此凸集中；而定義2 說明

19、，若是凸集的一個極點，則不能位于中任意兩點的連線上。不難證明，多胞形必為凸集。同樣也不難證明，二維空間中可行域的頂點均為的極點（也沒有其它的極點）。3.5 求解線性規(guī)劃的Matlab解法*單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。單純形法是首先由George Dantzig于1947年提出的，近60年來，雖有許多變形體已被開發(fā)，但卻保持著同樣的基本觀念。由于有如下結(jié)論：若線性規(guī)劃問題有有限最優(yōu)解，則一定有某個最優(yōu)解是可行區(qū)域的一個極點?；诖?，單純形法的基本思路是：先找出可行域的一個極點，據(jù)一定規(guī)則判斷其是否最優(yōu)；若否，則轉(zhuǎn)換到與之相鄰的另一極點，并使目標函數(shù)值更優(yōu)；如此下去，直到

20、找到某一最優(yōu)解為止。這里我們不再詳細介紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的Matlab解法。Matlab5.3中線性規(guī)劃的標準型為 基本函數(shù)形式為linprog(c,A,b)，它的返回值是向量的值。還有其它的一些函數(shù)調(diào)用形式（在 Matlab 指令窗運行 help linprog 可以看到所有的函數(shù)調(diào)用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標函數(shù)的值，Aeq和beq對應(yīng)等式約束，LB和UB分別是變量的下界和上界，是的初始值，OPTIONS是控制參數(shù)。 例2 求解下列線性規(guī)劃問

21、題 解 （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即可得所求結(jié)果。求解線性規(guī)劃問題 解 編寫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 可以轉(zhuǎn)化為線性規(guī)劃的問題很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃問題來解決。如：問題為其中

22、，和為相應(yīng)維數(shù)的矩陣和向量。要把上面的問題變換成線性規(guī)劃問題，只要注意到事實：對任意的，存在滿足 ，事實上，我們只要取，就可以滿足上面的條件。這樣，記，從而我們可以把上面的問題變成 4. Exercise4.1 通過下列問題聯(lián)系建立簡單線性規(guī)劃問題模型的方法以及模型的形式1. 某廠生產(chǎn)三種產(chǎn)品I，II，III。每種產(chǎn)品要經(jīng)過兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成工序，它們以表示；有三種規(guī)格的設(shè)備能完成工序，它們以表示。產(chǎn)品I可在任何一種規(guī)格設(shè)備上加工。產(chǎn)品II可在任何規(guī)格的設(shè)備上加工，但完成工序時，只能在設(shè)備上加工；產(chǎn)品III只能在與設(shè)備上加工。已知在各種機床設(shè)備的單件工時，原材料費，產(chǎn)品

23、銷售價格，各種設(shè)備有效臺時以及滿負荷操作時機床設(shè)備的費用如下表，要求安排最優(yōu)的生產(chǎn)計劃，使該廠利潤最大。設(shè)備產(chǎn) 品設(shè)備有效臺時滿負荷時的設(shè)備費用(元)IIIIII5764710981211600010000400070004000300321250783200原料費(元/件)單 價(元/件)0.251.250.352.000.502.802. 有四個工人，要指派他們分別完成4項工作，每人做各項工作所消耗的時間如下表： 工作工人甲乙丙丁15192619182317212122162324181917 問指派哪個人去完成哪項工作，可使總的消耗時間為最??？3. 某戰(zhàn)略轟炸機群奉命摧毀敵人軍事目標。已

24、知該目標有四個要害部位，只要摧毀其中之一即可達到目的。為完成此項任務(wù)的汽油消耗量限制為48000升、重型炸彈48枚、輕型炸彈32枚。飛機攜帶重型炸彈時每升汽油可飛行2千米，帶輕型炸彈時每升汽油可飛行3千米。又知每架飛機每次只能裝載一枚炸彈，每出發(fā)轟炸一次除來回路程汽油消耗（空載時每升汽油可飛行4千米）外，起飛和降落每次各消耗100升。有關(guān)數(shù)據(jù)如表所示。要害部位離機場距離（千米）摧毀可能性每枚重型彈每枚輕型彈12344504805406000.100.200.150.250.080.160.120.20為了使摧毀敵方軍事目標的可能性最大，應(yīng)如何確定飛機轟炸的方案，要求建立這個問題的線性規(guī)劃模型。

25、4.2 電力系統(tǒng)的經(jīng)濟調(diào)度問題模型電力系統(tǒng)的概念：由發(fā)電、變電、輸電、配電和用電等環(huán)節(jié)組成的電能生產(chǎn)、傳輸、分配和消費的系統(tǒng)。電力系統(tǒng)的目標：1、滿足用電需求。（可靠性）2、滿足經(jīng)濟實用。（經(jīng)濟性）例：供電廠給居民區(qū)和工廠供電，居民區(qū)需電量為500MW，工廠需電量為1000MW，選擇合適的配置發(fā)電機組的方法在最大程度上滿足電力系統(tǒng)的目標。 條件（供電機） 容量MW 煤耗g/kwh 單機故障率 1000 290 1% 600 310 5% 300 320 7% 200 350 10%煤價：1000元/噸 投資：5000元/千瓦 Pg：50%100%方法：數(shù)學建模5. 對偶理論與靈敏度分析5.1

26、原始問題和對偶問題考慮下列一對線性規(guī)劃模型： s.t. (P)和 s.t. (D)稱（P）為原始問題，（D）為它的對偶問題。不太嚴謹?shù)卣f，對偶問題可被看作是原始問題的“行列轉(zhuǎn)置”：原始問題約束條件中的第列系數(shù)與其對偶問題約束條件中的第行的系數(shù)相同；原始目標函數(shù)的系數(shù)行與其對偶問題右側(cè)的常數(shù)列相同；原始問題右側(cè)的常數(shù)列與其對偶目標函數(shù)的系數(shù)行相同；在這一對問題中，除非負約束外的約束不等式方向和優(yōu)化方向相反?？紤]線性規(guī)劃：把其中的等式約束變成不等式約束，可得 它的對偶問題是其中和分別表示對應(yīng)于約束和的對偶變量組。令，則上式又可寫成原問題和對偶的對偶問題約束之間的關(guān)系： 5.2 對偶問題的基本性質(zhì)1

27、o 對稱性：對偶問題的對偶是原問題。2o 弱對偶性：若是原問題的可行解，是對偶問題的可行解。則恒有：。3o 無界性：若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。4o 可行解是最優(yōu)解時的性質(zhì)：設(shè)是原問題的可行解，是對偶問題的可行解，當時，是最優(yōu)解。5o 對偶定理：若原問題有有限最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標函數(shù)值相同。6o 互補松弛性：若分別是原問題和對偶問題的最優(yōu)解，則 由上述性質(zhì)可知，對任一LP問題(P)，若它的對偶問題(D)可能的話，我們總可以通過求解（D）來討論原問題（P）：若(D)無界，則(P)無可行解；若(D)有有限最優(yōu)解，最優(yōu)值，則利用互補松弛性可求得(P

28、)的所有最優(yōu)解，且(P)的最優(yōu)值為。例如對只有兩個行約束的LP，其對偶問題只有兩個變量，總可用圖解法來求解。例9 已知線性規(guī)劃問題 已知其對偶問題的最優(yōu)解為，最優(yōu)值為。試用對偶理論找出原問題的最優(yōu)解。解 先寫出它的對偶問題 s.t. 將的值代入約束條件，得，為嚴格不等式；設(shè)原問題的最優(yōu)解為，由互補松弛性得。因 ；原問題的兩個約束條件應(yīng)取等式，故有求解后得到；故原問題的最優(yōu)解為 ；最優(yōu)值為。 5.3 靈敏度分析靈敏度分析是指對系統(tǒng)或周圍事物因周圍條件變化顯示出來的敏感程度的分析。在以前討論線性規(guī)劃問題時，假定都是常數(shù)。但實際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件一變，值就會變化；往往是因工藝條件的改變而改變；是根據(jù)資源投入后的經(jīng)濟效果決定的一種決策選擇。因此提出這樣兩個問題：當這些參數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化；或者這