第二章 線性規(guī)劃在電力系統(tǒng)中應用 [2011]

1、Dr. TANG Y2022-3-7Southeast University1本章框架1. 線性優(yōu)化概念2. 單純形法3. Matlab工具箱應用4. 電力系統(tǒng)中的應用2022-3-7Southeast University21939年蘇聯(lián)數(shù)學家L.V.坎托羅維奇;從40年代到50年代中期，美國由于軍事和生產的需要迅速地發(fā)展了這一分支;1947年美國空軍數(shù)學顧問G.B.丹齊克首次提出線性規(guī)劃的概念，并且提出求解線性規(guī)劃的單純形法；2022-3-7Southeast University32.1 什么是線性規(guī)劃2.1.1 線性規(guī)劃的初步認識在生產和管理經營活動中，經常遇到這樣的兩類問題：（1）如

2、何合理地使用有限的勞動力、設備、資金等資源，以得到最大的效益（如生產經營利潤）；（2）為了達到一定的目標（生產指標或其他指標），應如何組織生產，或合理安排工藝流程，或調整產品的成分，以使消耗資源（人力、設備臺數(shù)、資金、原材料等）為最少。2022-3-7Southeast University4(1)配載問題配載問題：某種交通工具（車、船、飛機等）的容積和載重量一定，運輸幾種物資，這些物資有不同的體積和重量，如何裝載可以使這種運輸工具所裝運的物資最多？(2)下料問題下料問題：某廠使用某種圓鋼下料，制造直徑相同而長度不等的三種機軸，采用什么樣的下料方案可以使余料為最少？(3)物資調運物資調運：某種

3、產品有幾個產地和銷地，物資部門應太如何合理組織調運，從而既滿足銷地需要，又不使某個產地物資過分積壓，同時還使運輸費用最??？(4)營養(yǎng)問題營養(yǎng)問題：各種食品所含營養(yǎng)成分各不相同，價格也不相等，食堂應該如何安排伙食才能既滿足人體對各種營養(yǎng)成分得需要，同時又使消費者得經濟負擔最少？此外，在地質勘探、環(huán)境保護等方面也都有與上述情況類似的問題。2022-3-7Southeast University5例2.1.1 生產安排問題某制藥廠生產甲、乙兩種藥品，生產這兩種藥品要消耗某種維生素。生產每噸藥品所需要的維生素量分別為30Kg，20Kg，所占設備時間分別為5臺班，1臺班，該廠每周所能得到的維生素量為16

4、0kg，每周設備最多能開15個臺班。且根據(jù)市場需求，甲種產品每周產量不應超過4t。已知該廠生產每噸甲、乙兩種產品的利潤分別為5萬元及2萬元。問該廠應如何安排兩種產品的產量才能使每周獲得的利潤最大？每噸產品的消耗每周資源總量甲乙維生素 /kg3020160設備/臺班51152022-3-7Southeast University6解：設該廠每周安排生產甲、乙兩種藥品的產量分別為x1,x2噸，則有：004155162325max211212121xxxxxxxxxz2022-3-7Southeast University7例2.1.2 喜糖問題設市場上有甲級糖和乙級糖，單價分別為20元/斤，10元

5、/斤?，F(xiàn)在要籌辦一樁婚事，籌備小組計劃怎樣花費不超過200元，使糖的總斤數(shù)不少于10斤，甲級糖不少于5斤。問如何確定采購方案，使糖的總斤數(shù)最大。2022-3-7Southeast University8解：設采購甲、乙兩種糖各x1,x2斤:00502001020max211212121xxxxxxxxxz2022-3-7Southeast University92.1.2 線性規(guī)劃問題的數(shù)學模型（1）每一個問題都有一組變量稱為決策變量，一般記為 x1， x2 ， xn 。對決策變量的每一組值： 代表了一種決策方案。通常要求決策變量取值非負，即 。（2）每個問題中都有決策變量需滿足的一組約束條件

6、線性的等式或不等式。（3）都有一個關于決策變量的線性函數(shù)稱為目標函數(shù)。要求這個目標函數(shù)在滿足約束條件下實現(xiàn)最大化或最小化。 001Txxx02n，012,jxjn ，,2022-3-7Southeast University10將約束條件及目標函數(shù)都是決策變量的線性函數(shù)的規(guī)劃問題稱為線性規(guī)劃線性規(guī)劃。線性規(guī)劃的一般數(shù)學模型為：1 122max minnnzc xc xc x11 11221121 1222221 12212,.;,0.nnnnmmmnnmna xaxa xba xa xa xbsta xaxaxbx xx2022-3-7Southeast University112.1.3 兩

7、個變量問題的圖解法對于只有兩個決策變量的線性規(guī)劃問題，可以用圖解法來求解。應用圖解法求解線性規(guī)劃問題可能出現(xiàn)的結果：(1) 有唯一最優(yōu)解；(2) 有無窮多個最優(yōu)解；(3) 無最優(yōu)解；(4) 無可行解。2022-3-7Southeast University122.1.4 線性規(guī)劃數(shù)學模型的標準形式一般線性規(guī)劃問題可寫成下列標準形式：2022-3-7Southeast University1311min. .,1,0,1,njjjnijjijjc xstxb imxjn2022-3-7Southeast University14min. .,0cxstAxbxA是m*n矩陣，c是n維行向量，b是

8、m維列向量2.1.4 將非標準形式化為標準形式如何從實際問題得到的線性規(guī)劃非標準形式的數(shù)學模型轉化為標準形式的數(shù)學模型：1）目標函數(shù)為求最大化；2）約束條件是小于等于型；3）約束條件是大與等于型；4）有個約束方程右端項 ；5）決策變量無非負要求。0ib 2022-3-7Southeast University15例： 將下列線性規(guī)劃模型化為標準形式：32132minxxxz., 0, 523, 2, 7.321321321321無約束xxxxxxxxxxxxts2022-3-7Southeast University16標準形式：7654210032maxxxxxxxz. 0, 5223, 2

9、, 7.76542154217542165421xxxxxxxxxxxxxxxxxxxxts2022-3-7Southeast University17線性優(yōu)化法簡而言之，目標函數(shù)和約束條件均為線性的，即為線性優(yōu)化。線性優(yōu)化可簡單分為兩類：單純形法與內點法。兩類方法均可解決數(shù)千變量和約束的線性優(yōu)化問題。單純形法雖然計算效率很高，但是隨著問題規(guī)模的擴大其迭代次數(shù)會呈指數(shù)型增長，而內點法在這一點上具有優(yōu)勢，因此電力系統(tǒng)中很多線性優(yōu)化問題都采用內點法。2022-3-7Southeast University182.2單純形法2.2.1 單純形迭代原理求解線性規(guī)劃問題的通用方法。單純形是美國數(shù)學家G.

10、B.丹齊克于1947年首先提出來的。理論根據(jù)是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是，則再轉換,按此重復進行。因基本可行解的個數(shù)有限，故經有限次轉換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。2022-3-7Southeast University19單純形法的一般解題步驟可歸納如下：把線性規(guī)劃問題的約束方程組表達成標準型方程組，找出基本可行解作為初始基

11、本可行解。若基本可行解不存在，即約束條件有矛盾，則問題無解。若基本可行解存在，從初始基本可行解作為起點，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數(shù)值更優(yōu)的另一基本可行解。按步驟3進行迭代,直到對應檢驗數(shù)滿足最優(yōu)性條件（這時目標函數(shù)值不能再改善），即得到問題的最優(yōu)解。若迭代過程中發(fā)現(xiàn)問題的目標函數(shù)值無界，則終止迭代。2022-3-7Southeast University20例1.2.1 求解下列線性規(guī)劃問題的最優(yōu)解004155160203025max211212121xxxxxxxxxz2022-3-7Southeast University21解：化為標準形式041

12、55160203000025max515142132154321xxxxxxxxxxxxxxz2022-3-7Southeast University22第一步：確定一個初始基本可行解；基本可行解就是滿足非負條件的基本解，因此要在約束矩陣A中找出一個可逆的基矩陣。10001010150012030A這里m=3，3階可逆方陣，可以看出x3,x4,x5的系數(shù)列向量是線性獨立的，這些向量構成一個基2022-3-7Southeast University23),(100010001543)0(pppB對應的基變量為x3,x4,x5，x1,x2為非基變量。將基變量用非基變量表示x3=160-30 x1-

13、20 x2x4=15-5x1-x2 （3）x5=4-x12022-3-7Southeast University24將(3)代入目標函數(shù)得Z=5x1+2x2+0令非基變量x1=x2=0,代入x3=160-30 x1-20 x2x4=15-5x1-x2 （3）x5=4-x1得到一個基可行解X(0)X(0)=(0,0,160,15,4)第二步：從當前基可行解轉換為更好的基可行解從數(shù)學角度看，x1,x2的增加將會增加目標函數(shù)值，從目標函數(shù)值中x1,x2前的系數(shù)看，x1前的系數(shù)大于x2前的系數(shù)，所以讓x1從非基變量轉為基變量，稱為進基變量進基變量，怎樣確定離基變量離基變量：2022-3-7Southe

14、ast University25因為x2仍為非基變量，故x2=0則(3)式變?yōu)閤3=160-30 x1160/30=16/3x4=15-5x115/5=3x5=4-x14/1=4min=3，所以當x1=3時，x4第一個減少到0，所以x4出基則X(1)=(3,0,70,0,1)Z(1)=152022-3-7Southeast University26此時非基變量為x2,x4,用非基變量表示基變量，代入(3)x3=70-14x2+6x4x1=3-1/5x2-1/5x4x5=1+1/5x2+1/5x4將(4)代入目標函數(shù)得Z=15+x2-x42022-3-7Southeast University2

15、7第三步：繼續(xù)迭代x2進基，x4仍為非基變量，令x4=0，則(4)式表示為x3=70-14x270/145x1=3-1/5x23/(1/5)15x5=1+1/5x2min=5，所以當x2=5時，x3首先減少到0，所以x3出基則X(2)=(2,5,0,0,2)Z(2)=202022-3-7Southeast University28此時非基變量為x3,x4,用非基變量表示基變量，代入(4) x2=5-1/14x3+3/7x4x1=2+1/70 x3-2/7x4x5=2-1/70 x3+2/7x4 將(5)代入目標函數(shù)得Z=20-1/14x3-4/7x4 此時若非基變量x3,x4的值增加，只能使Z

16、值下降 所以X(2)為最優(yōu)解，Z*=20, X*=(2,5, 0,0,2)2022-3-7Southeast University29單純形法的基本步驟：第一步：構造一個初始基本可行解。第一步：構造一個初始基本可行解。對已經標準化的線性模型，設法在約束矩陣 中構造出一個m階單位陣作為初始可行基，相應就有一個初始可行基，相應就有一個初始基本可行解。2022-3-7Southeast University30第第2步：判斷當前基本可行解是否為最優(yōu)解。步：判斷當前基本可行解是否為最優(yōu)解。求出用非基變量表示基變量及目標函數(shù)的表達式，稱之為線性規(guī)劃問題的典式（或稱為規(guī)范式）。在目標函數(shù)的典式中，若至少有

17、一個非基變量前的系數(shù)為正數(shù)，則當前解就不是最優(yōu)解；若所有的非基變量前的系數(shù)均為非正數(shù)，則當前解就是最優(yōu)解（指最大化問題）。將目標函數(shù)的典式中非基變量前的系數(shù)稱為檢驗數(shù)檢驗數(shù)。故對最大化問題，當所有的檢驗數(shù) 0時，當前解即為最優(yōu)解。2022-3-7Southeast University31第3步：若當前解不是最優(yōu)解，則要進行基變換迭代到下一個基本可行解。首先從當前解的非基變量中選一個作進基變量。選擇的原則一般是：目標函數(shù)的典式中，最大的正檢驗數(shù)所屬的非基變量作進基變量。再從當前解的基變量中選一個作離基變量。選擇的方法是：在用非基變量表示基變量的典式中，除了可進基變量外，讓其余非基變量取值為零，

18、再按最小比值準則確定離基變量。這樣就得到了一組新的基變量和非基變量，即已從上一個基本可行解迭代到下一個基本可行解。然后求出關于新基矩陣的線性規(guī)劃問題的典式，這就完成了基變換的全過程。在新的典式中可求出新基本可行解的取值及目標函數(shù)的取值。2022-3-7Southeast University32再回到第2步判斷當前新基本可行解是否已達到最優(yōu)。若已達到最優(yōu)，停止迭代。若沒有達到最優(yōu)，再進行第3步作新的基變換，再次進行迭代。如此往復，直到求得最優(yōu)解或判斷無（有界）最優(yōu)解時停止。2022-3-7Southeast University332.2 修正單純形法算法原理在單純形算法中，每步都需要計算矩陣

19、B的逆。修正單純形法通過對舊的矩陣B的逆做行變換，來得到新的矩陣B的逆，從而只需要在迭代的初始需要計算矩陣B的逆，縮短了求解時間。2022-3-7Southeast University342.3 大M法算法原理大M法的求解線性規(guī)劃的過程和單純形法一樣，不同的是對線性規(guī)劃的一般形式的處理方法，大M法將線性規(guī)劃:2022-3-7Southeast University35min. .0fcxAxbstxmin. .,0TfcxMe yAxybstx y轉化為2.4 對偶理論隨著線性規(guī)劃應用的逐步深入，人們發(fā)現(xiàn)一個線性規(guī)劃問題往往伴隨著與之配對的、兩者有密切聯(lián)系的另一個線性規(guī)劃問題。將其中一個稱為

20、原問題，另一個稱為對偶問題。2022-3-7Southeast University362.4.2 三種形式的對偶關系原問題與其對偶問題之間通常有3種不同的關系形式。以下將原問題記作LP問題，對偶問題記作DP問題。1 對稱形式的對偶關系2 非對稱形式的對偶關系3 混合形式的對偶關系2022-3-7Southeast University37表2.1 對偶關系相互對照表2022-3-7Southeast University381 對稱形式的對偶關系2 非對稱形式的對偶關系3 混合形式的對偶關系2022-3-7Southeast University392.4.3 對偶解（影子價格）的經濟解釋如

21、果把原問題的約束條件看成是廣義資源約束，則右端項的值表示每種資源的可用量。對偶解的經濟含義就是資源的單位改變量引起目標函數(shù)值的增加量。在經濟學中，通常用價值量來衡量目標函數(shù)值。因此對偶解也具有了價值內涵，通常稱對偶解為影子價格影子價格。影子價格是對偶解的一個十分形象的名稱，它既表明了對偶解是對系統(tǒng)內部資源的一種客觀估價，又表明它是一種虛擬的價格，而不是真實的價格。2022-3-7Southeast University402.4.4 靈敏度分析以上討論線性規(guī)劃時，把 等均看成是常數(shù)。但實際上這些數(shù)據(jù)有的是統(tǒng)計數(shù)據(jù)，有的是測量值，有的是專家評估得到的數(shù)據(jù)，并非是絕對精確的，且也不是絕對不變的。因

22、此有必要來分析一下當這些數(shù)據(jù)發(fā)生波動時，對目前的最優(yōu)解與最優(yōu)值會產生什么樣的影響？這就是所謂的靈敏度分析。靈敏度分析通常有兩類問題：一是當 中某一部分數(shù)據(jù)發(fā)生給定的變化時，討論最優(yōu)解與最優(yōu)值怎么變？二是研究 中數(shù)據(jù)在多大范圍內波動時，使原有最優(yōu)解仍為最優(yōu)解，同時討論此時最優(yōu)值如何變動？iijjbac,bAc,bAc,2022-3-7Southeast University412.4用MATLAB 解決線性規(guī)劃中的優(yōu)化問題2.4.1 軟件包解決線性規(guī)劃問題1951 年, 國際水平只能求解約束條件為10 個方程的線性規(guī)劃問題；1963 年, 能求解100010000 個方程的線性規(guī)劃問題；1984

23、 年, 美國貝爾實驗室的數(shù)學家卡瑪卡把射影幾何原理用于大規(guī)模線性規(guī)劃問題的求解；MATLAB是一個通用數(shù)學軟件包, 除了可以用其中的優(yōu)化工具箱來求解線性規(guī)劃外, 還有許多其他的強大功能。2022-3-7Southeast University422.4.2 MATLAB求解步驟線性規(guī)劃的算法主要是迭代算法, 它從初始的基本可行解開始, 通過多次迭代過程選出最優(yōu)解，它的迭代過程一般可描述為：2022-3-7Southeast University43求線性規(guī)劃問題數(shù)學模型如下：A不等式約束的系數(shù)矩陣Aeq等式約束的系數(shù)矩陣b不等式約束的常向量beq等式約束的常向量lb,ub自變量的上下范圍線性規(guī)

24、劃問題又分大型問題與中型問題, 解決方法有些不同, 大型問題的算法的第一步需對涉及到的約束條件進行預處理。2022-3-7Southeast University44min,. .TA xbf xstAeq xbeqlbxub函數(shù)linprog的用法(1)：x=linprog(f,A,b): 線性規(guī)劃只存在不等式約束； x=linprog(f,A,b,Aeq,beq): 線性規(guī)劃存在不等式和等式約束； x=linprog(f,A,b,Aeq,beq,lb,ub): 一般格式的線性規(guī)劃； x=linprog(f,A,b,Aeq,beq,lb,ub,x0): 設定初始值x0，這個初始值只適應于中型

25、問題； x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options): 通過options選項指定優(yōu)化參數(shù)；x=linprog(problem): 線性規(guī)劃問題通過構造problem來指定。2022-3-7Southeast University45problem結構字段含義字段字段含義含義字段字段含義含義f目標函數(shù)lb變量下界Aineq不等式約束中的系數(shù)矩陣ub變量上界bineq不等式約束中的常向量x0初始優(yōu)化點Aeq等式約束中的系數(shù)矩陣solver求解器，為“l(fā)inprog”beq等式約束中的常向量options優(yōu)化選項2022-3-7Southeast Univer

26、sity46函數(shù)linprog的用法(2)：x,fval=linprog():不但求出最優(yōu)解，而且返回目標函數(shù)的最優(yōu)值；x,fval,exitflag=linprog(): exitflag參數(shù)表示求解的結果;x,fval,exitflag,output=linprog(): output參數(shù)包含優(yōu)化過程中的各種輸出信息； x,fval,exitflag,output,lambda=linprog(): lambda參數(shù)是一個結構體，包含最優(yōu)解處的拉格朗日乘子。2022-3-7Southeast University47具體求解時, 首先是給矩陣f , A , b ，Aeq，beq，lb，ub賦值。MATLAB 給矩陣賦值是逐行進行的, 行之間用分號“；”隔開, 每行元素之間可以用“ ,”號，也可用空格隔開,并且用符號“ ,”置于矩陣右上角表示作矩陣的轉置運算。賦值完畢, 在命令窗口中調用優(yōu)化程序lp