具有混合動態(tài)約束的系統(tǒng)優(yōu)化調(diào)度

1、最優(yōu)控制課程Project報告PAGE 具有混合動態(tài)約束的系統(tǒng)優(yōu)化調(diào)度火電機(jī)組子問題求解第一小組成員： 楊勇 李培 李潔 張俊杰 目 錄第一章 引言問題分析實驗結(jié)果心得體會致謝具有混合動態(tài)約束的系統(tǒng)優(yōu)化調(diào)度火電機(jī)組子問題求解新方法引言優(yōu)化的問題由來已久。從人類勞動的歷史開始，優(yōu)化的問題就應(yīng)運而生了。如何在客觀條件一定的情況下，使一件事做的更好，就成為人類不懈追求的目標(biāo)。使一件事做的更好可能是花費時間最少，等量產(chǎn)出的情況下消耗最小等等，這就關(guān)系到如何安排一系列事件的順序等問題。隨著歷史的發(fā)展，優(yōu)化問題的研究也在不斷的進(jìn)步。如今一方面，系統(tǒng)優(yōu)化問題滲透到許多學(xué)科研究之中，另一方面，優(yōu)化也成為了一門

2、專門的學(xué)科并且有了堅實的理論基礎(chǔ)和一系列的經(jīng)典方法。 生產(chǎn)優(yōu)化調(diào)度的目的是合理安排有限的生產(chǎn)資源，達(dá)到成本最低、能源最省等目標(biāo)。對于電力、化工等一大類生產(chǎn)系統(tǒng)，通常包括多套不同型號的生產(chǎn)設(shè)備。優(yōu)化調(diào)度問題除要考慮生產(chǎn)量、原料限制、合同產(chǎn)量等系統(tǒng)約束外，每個單臺設(shè)備通常具有十分復(fù)雜的離散動態(tài)運行約束如不連續(xù)輸出區(qū)間、開關(guān)機(jī)約束，以及連續(xù)動態(tài)運行約束如生產(chǎn)能力、輸出變化限制等。本文的研究就是在這樣的背景之下進(jìn)行的。主要討論了火電機(jī)組的調(diào)度問題。為了在滿足各種系統(tǒng)約束（生產(chǎn)量，合同成本，開關(guān)機(jī)約束，爬升約束等等）的前提下是系統(tǒng)的費用最低，能源最省，如何調(diào)度不同機(jī)組的開關(guān)機(jī)時間，決定單個機(jī)組的開關(guān)機(jī)序

3、列和發(fā)電功率就是我們的目標(biāo)。問題分析1系統(tǒng)方法從數(shù)學(xué)規(guī)劃的角度來看，整個火電機(jī)組（24個機(jī)組）的調(diào)度問題屬于NP問題，即隨著系統(tǒng)規(guī)模的增大，計算量將呈現(xiàn)指數(shù)增長的趨勢。當(dāng)系統(tǒng)規(guī)模增長到一定程度時，直接求解這個問題是不可能的或者幾乎不可能的，例如有時候，以目前的計算機(jī)運行速度計算，將要需要幾十萬年甚至上百萬年數(shù)量級；即使是幾個月的時間也是不現(xiàn)實的，因為如果那樣的話將會失去實際意義。近年的研究表明拉格朗日松弛法是求解具有可分結(jié)構(gòu)問題的最有效算法之一，其主要思想是在對偶理論基礎(chǔ)上，利用拉氏乘子松弛系統(tǒng)約束，將原問題分解成若干子問題，形成二級優(yōu)化結(jié)構(gòu)。下級對子問題分別求解，上級更新拉氏乘子。對偶解收斂

4、后，再應(yīng)用啟發(fā)式方法或系統(tǒng)化方法將對偶解調(diào)整為可行解。拉格朗日松弛法的主要優(yōu)點包括：將大規(guī)模問題分解為若干子問題求解從而降低了復(fù)雜度；便于靈活處理多種約束；計算時間隨問題規(guī)模增大僅呈線性增長；計算中得到的對偶函數(shù)值可定量評價可行調(diào)度方案的優(yōu)劣；Lagrange乘子在實際中有重要的經(jīng)濟(jì)意義。整個火電機(jī)組的調(diào)度問題可以通過拉各朗日松弛法分解為多個子問題求解，即各個單個機(jī)組的開關(guān)機(jī)問題。單個機(jī)組的開關(guān)機(jī)問題是一個具有混合參數(shù)（連續(xù)參數(shù)，離散參數(shù)）的最優(yōu)控制問題。通過解耦的方法分別處理離散參數(shù)和連續(xù)參數(shù)，使兩方面的控制都達(dá)到最優(yōu)。首先應(yīng)用動態(tài)規(guī)劃法，在每個連續(xù)運行的時段內(nèi)，確定最優(yōu)的連續(xù)決策變量，然后

5、再利用動態(tài)規(guī)劃法，求解最優(yōu)的離散狀態(tài)和控制。鑒于整個火電機(jī)組生產(chǎn)調(diào)度問題復(fù)雜度和工組量的因素（各種約束可能達(dá)到上萬個），我們在這里只是嘗試解決單機(jī)組的優(yōu)化調(diào)度問題，即下層的子問題。那么這個子系統(tǒng)的輸入是拉各朗日乘子，輸出是這個機(jī)組的最小消耗成本。在這個子系統(tǒng)中要考慮發(fā)電量約束，最小開關(guān)機(jī)約束，功率的爬升約束，冷開機(jī)時間等多種約束。在這個子問題中，單機(jī)組的最優(yōu)開關(guān)機(jī)序列是一個重要的結(jié)果。是連接輸入?yún)?shù)和輸出參數(shù)的橋梁。2問題描述考慮有I套火電機(jī)組的系統(tǒng)，調(diào)度周期為T個時段，那么整個機(jī)組的混合優(yōu)化問題可以表示為： （1）這里和分別是機(jī)組在第時段內(nèi)的連續(xù)和離散狀態(tài)變量，為表示控制機(jī)組的離散控制變量。

6、通常對應(yīng)于機(jī)組在第時段內(nèi)的發(fā)電量，為機(jī)組在第時段內(nèi)的生產(chǎn)成本，為離散狀態(tài)轉(zhuǎn)換引起的費用，一般僅當(dāng)與異號時此費用非零，否則為零，它與機(jī)組目前的狀態(tài)和離散控制變量有關(guān)。問題的約束可分為系統(tǒng)約束與設(shè)備約束兩類，系統(tǒng)約束主要包括：(2)(3)其中為第時段的發(fā)電量要求， 表示電力系統(tǒng)調(diào)度中的系統(tǒng)備用，是設(shè)備在第時段內(nèi)發(fā)電量為時消耗的原料（不等號相反）, 是第時段的原料限制（或系統(tǒng)備用需求）。設(shè)備約束主要包括：連續(xù)狀態(tài)方程：，(4)其中為連續(xù)控制變量；離散狀態(tài)方程： (5)離散狀態(tài)方程通常表示設(shè)備開機(jī)時間（取正值）或關(guān)機(jī)時間（取負(fù)值）的演變，比如表示第時段內(nèi)設(shè)備處于開機(jī)狀態(tài)，且已連續(xù)開了3個時段；連續(xù)狀態(tài)

7、約束：，(6)通常表示機(jī)組的生產(chǎn)能力和最小輸出，其中、分別為設(shè)備的最小和最大輸出量，因為物理約束和效率的考慮，機(jī)組的輸出區(qū)間可能是不連續(xù)的，即一般不為0；連續(xù)控制變量約束：，(7)表示機(jī)組輸出變化能力，其中為機(jī)組輸出變化率上限；離散控制變量約束：(8)表示對機(jī)組開關(guān)機(jī)的限制，其中為最小開機(jī)時間，為最小關(guān)機(jī)時間；3拉格朗日松弛接下來我們在Lagrange松弛法框架下引入對偶函數(shù)如下： （9）這樣就可以松弛掉系統(tǒng)約束和產(chǎn)量約束，是對應(yīng)于系統(tǒng)約束的乘子向量，是對應(yīng)于產(chǎn)量約束的乘子向量。在此基礎(chǔ)上，連續(xù)控制變量（功率爬升約束）和離散控制變量（開機(jī)，關(guān)機(jī)時間）的對偶問題可描述為： （10）不難看出，(9

8、)可以分解為：其中： (11)稱為第i個子問題，它只與機(jī)組i有關(guān)，這樣通過解對偶問題（11）就可以間接獲得原問題的解。求解時的基本步驟如下：初始化乘子求解所有子問題修正乘子，判斷解是否收斂，若未收斂，轉(zhuǎn)b，否則停止。我們的工作就是求解子問題。4. 子問題解決方案a)離散狀態(tài)變量和離散控制約束的優(yōu)化通過拉格朗日松弛法，我們得到了火電機(jī)組解耦以后的子問題。在解對偶問題時，由于系統(tǒng)約束已被松弛，所以只需考慮單機(jī)組的約束(4)-(8)。當(dāng)連續(xù)控制變量約束(7)不存在（即）時，解子問題(12)可采用動態(tài)規(guī)劃法直接求解。每一個離散狀態(tài)所對應(yīng)的最優(yōu)連續(xù)狀態(tài)變量是唯一的，若第時段，則相應(yīng)的最優(yōu)連續(xù)狀態(tài)變量為：

9、 (13)由于連續(xù)控制變量約束（7）的存在，我們采用按離散控制變量的變化來劃分階段，得到如下的狀態(tài)轉(zhuǎn)移圖（為描述方便，假定設(shè)備初始時刻處于關(guān)機(jī)狀態(tài)且已關(guān)夠最小關(guān)機(jī)時間，其它情況下狀態(tài)轉(zhuǎn)移圖的建立過程完全類似）：說明：每個圓圈表示一個狀態(tài)，圈上的數(shù)字對應(yīng)一個時段編號。由于初始時設(shè)備處于關(guān)機(jī)狀態(tài)，所以第一階段的任務(wù)是決定何時開機(jī)，又因為設(shè)備已關(guān)夠最小關(guān)機(jī)時間，所以最早的可以開機(jī)的時段是第1時段。既然第1時段可以作為第1次開機(jī)時段，那么其它時段都可以作為第1次開機(jī)時段，另外，一種可能的決策是設(shè)備一直不開機(jī)，為容納這種決策，在圖中加入一個時段，編號為，因此第1階段的所有決策含義已明確（每個決策對應(yīng)一條

10、線段）。接下來是第2階段，第2階段的任務(wù)是決定第一次關(guān)機(jī)操作在哪個時段進(jìn)行。對于離散狀態(tài)變量和離散控制約束，我們可以用動態(tài)規(guī)劃的方法直接求解。動態(tài)規(guī)劃的基本思想：動態(tài)規(guī)劃是解決多段決策過程的極為有力的工具。有以下假定：目標(biāo)函數(shù)具有Markov性質(zhì)認(rèn)為現(xiàn)在和將來的決策不影響過去的狀態(tài)，決策和目標(biāo)。存在狀態(tài)反饋控制認(rèn)為u(k)=u(x(k),k)，即x(k)可以獲得，不論是直接測量或是重構(gòu)；根據(jù)x（k），立即作出決策u（k）。用從后往前的逆推方法，即如果某一時刻以后的控制是最優(yōu)的，那么它以后的任何時段的控制也都是最優(yōu)的，就可以得到每個時段的最優(yōu)控制u，這就是Bellman方程： 定義：Bellma

11、n方程：b)連續(xù)控制變量的優(yōu)化在計算開機(jī)區(qū)間決策費用時，動態(tài)規(guī)劃的方法是一種比較有效的方法，通過求得各時段的出發(fā)費用(Cost-to-go)函數(shù)來得到最優(yōu)的連續(xù)狀態(tài)和控制。已有文獻(xiàn)在解決此問題時基本思想是結(jié)構(gòu)動態(tài)規(guī)劃(6,10,14)，但由于未能充分利用問題(1)-(8)的特性，計算過程比較復(fù)雜。通過分析連續(xù)動態(tài)約束特性，在這里，我們使用了一種簡化結(jié)構(gòu)動態(tài)規(guī)劃新算法，它的基本思想是通過分段線性函數(shù)的平移和相加運算來求得各時段的出發(fā)費用。方法計算過程簡單且計算量非常小。假定，是兩個時段編號且，再假定對應(yīng)于圖2中一個開機(jī)區(qū)間，由(12)式知該決策的費用為離散狀態(tài)轉(zhuǎn)換費用(相應(yīng)于開機(jī)區(qū)間之后的關(guān)機(jī)操

12、作的費用，此項費用容易計算)與下述連續(xù)優(yōu)化問題的最優(yōu)值之和：(14)其中所受約束包括：(15)(16)(17) (14)-(17)是一個非線性規(guī)劃問題，且只含連續(xù)變量。在很多實際問題中，設(shè)備性能曲線通常都是以離散點方式給出，是連續(xù)分段線性函數(shù)。應(yīng)用簡化結(jié)構(gòu)動態(tài)規(guī)劃法對(14)-(17)求解。首先遞歸定義出發(fā)費用函數(shù)：(18)上式的極小化受(16)、(17)約束?？紤]到（15），記(19)于是(20)由此可得問題(14)-(17)的動態(tài)規(guī)劃遞推算法如下：1反向遞推：初始化，置。對，由(20)求得。2正向遞推：初始化，置：，其中受 (17)約束。對，依次計算：在(19)中置為，求得(19)的最優(yōu)解

13、為，置。根據(jù)動態(tài)規(guī)劃原理，上述算法中得到的、就是(14)-(17)的最優(yōu)解。在上述算法的第一步，要求得到出發(fā)費用函數(shù)的表達(dá)式，這是結(jié)構(gòu)動態(tài)規(guī)劃方法與一般動態(tài)動態(tài)規(guī)劃方法的最大區(qū)別。若，均為凸的分段線性函數(shù)，問題可以大大簡化。此時可證也是凸分段線性函數(shù)(6,10,12)，所以只需要確定轉(zhuǎn)折點，就可以確定的表達(dá)式?？紤]到(14)-(17)的特點，提出簡化結(jié)構(gòu)動態(tài)規(guī)劃法計算，使得第二步的計算非常簡單。以下是針對g凸函數(shù)的情況下所進(jìn)行的相應(yīng)的平移操作，具體證明從略。其中，情況一是g為單調(diào)增的情況，情況2是g為單調(diào)減的情況，情況3為先減后增的情況。圖3. 與的關(guān)系下面我們以求解開機(jī)區(qū)間23，24的出發(fā)費

14、用為例，說明上述算法及其物理意義。首先進(jìn)行反向遞推：給出24時刻所對應(yīng)的函數(shù)（，在不影響問題本質(zhì)的前提下，我們簡化了f的表達(dá)式，忽略了乘子u），并找出g的極小值點，圖中是x130。從最低點處，平移爬升約束個單位，如下圖所示：將其與23時刻的g函數(shù)相加： 得到23時刻的出發(fā)費用函數(shù)如下圖所示：類似的，如果開機(jī)區(qū)間為22，23，24，求22時刻的出發(fā)費用，則需將23時刻的出發(fā)費用函數(shù)進(jìn)行響應(yīng)平移，如下圖所示：然后再按照遞推公式，與22時刻的f函數(shù)相加，即可得到22時刻的出發(fā)費用。其他開機(jī)區(qū)段的出發(fā)費用函數(shù)類似。最后，根據(jù)正向遞推，求出最優(yōu)的連續(xù)狀態(tài)和控制。首先求出令出發(fā)費用最低的（即：求出出發(fā)費用

15、函數(shù)的最小值點）；根據(jù)下一時刻的出發(fā)費用函數(shù)，決定出下一個最優(yōu)狀態(tài)；由和的出；循環(huán)進(jìn)行b)、c),直到求出最后一個開機(jī)時段的最優(yōu)狀態(tài)。第三章 實驗結(jié)果1實驗（1）所用數(shù)據(jù)pmax=130; 最大功率pmin=20; 最小功率tminup=5; 最小開機(jī)時間tmindown=5; 最小關(guān)機(jī)十幾年tcoldup=9; 冷關(guān)機(jī)時間delta=40; 爬升約束hotstart=500; 熱啟動費用coldstart=2*hotstart; 冷啟動費用l=12,23,17,17,36,17.5,18,27,15,6,8,16,22,50,10,20,37,16,8,26,17,12,22,30; 乘子向

16、量step=(pmax-pmin)/22;point=pmin:step:pmax;costofpoint=0.002*point.*point+16.6*point+700; 費用函數(shù)2實驗所求得的最優(yōu)狀態(tài)及最小費用開機(jī)序列（0：關(guān)機(jī)態(tài) 1：開機(jī)態(tài)）a = Columns 1 through 12 0 0 0 1 1 1 1 1 0 0 0 0 Columns 13 through 24 0 1 1 1 1 1 0 0 0 0 0 1最優(yōu)狀態(tài)序列：e = Columns 1 through 12 0 0 0 100 130 130 130 130 0 0 0 0 Columns 13 thr

17、ough 24 0 130 90 130 130 90 0 0 0 0 0 130調(diào)度得到的最小值mincost = -3.6202e+003最優(yōu)狀態(tài)的圖形表示如下：3用遍歷法得到的結(jié)果為了與動態(tài)規(guī)劃的方法進(jìn)行比較，我們還采用了遍歷的方法用遍歷方法得到的結(jié)果：開機(jī)序列（0：關(guān)機(jī)態(tài) 1：開機(jī)態(tài)）a = Columns 1 through 12 0 0 0 1 1 1 1 1 0 0 0 0 Columns 13 through 24 0 1 1 1 1 1 0 0 0 0 0 1最優(yōu)狀態(tài)序列：e = Columns 1 through 12 0 0 0 100 130 130 130 130 0

18、 0 0 0 Columns 13 through 24 0 130 90 130 130 90 0 0 0 0 0 130調(diào)度得到的最小值mincost = -3.6202e+003開機(jī)序列（0：關(guān)機(jī)態(tài) 1：開機(jī)態(tài)）a = Columns 1 through 12 0 0 0 1 1 1 1 1 0 0 0 0 Columns 13 through 24 0 1 1 1 1 1 0 0 0 0 0 1最優(yōu)狀態(tài)序列：e = Columns 1 through 12 0 0 0 100 130 130 130 130 0 0 0 0 Columns 13 through 24 0 130 90

19、130 130 90 0 0 0 0 0 130調(diào)度得到的最小值mincost = -3.6202e+003遍歷結(jié)果的圖形輸出如下：1實驗（2）所用數(shù)據(jù)pmax=130; 最大功率pmin=20; 最小功率tminup=5; 最小開機(jī)時間tmindown=5; 最小關(guān)機(jī)十幾年tcoldup=9; 冷關(guān)機(jī)時間delta=40; 爬升約束hotstart=560; 熱啟動費用coldstart=2*hotstart; 冷啟動費用l=12,23,17,17,36,17.5,18,27,15,6,8,16,22,50,10,20,37,16,8,26,17,12,22,30; 乘子向量step=(pm

20、ax-pmin)/22;point=pmin:step:pmax;costofpoint=0.00211*point.*point+16.5*point+680; 費用函數(shù)2實驗所求得的最優(yōu)狀態(tài)及最小費用開機(jī)序列（0：關(guān)機(jī)態(tài) 1：開機(jī)態(tài)）a = Columns 1 through 12 0 0 0 1 1 1 1 1 0 0 0 0 Columns 13 through 24 0 1 1 1 1 1 0 0 0 0 0 1最優(yōu)狀態(tài)序列：e = Columns 1 through 12 0 0 0 120 130 130 130 130 0 0 0 0 Columns 13 through 24

21、 0 130 90 130 130 90 0 0 0 0 0 130調(diào)度得到的最小值mincost = -3.9552e+003最優(yōu)狀態(tài)的圖形表示如下：3用遍歷法得到的結(jié)果為了與動態(tài)規(guī)劃的方法進(jìn)行比較，我們還采用了遍歷的方法用遍歷方法得到的結(jié)果：開機(jī)序列（0：關(guān)機(jī)態(tài) 1：開機(jī)態(tài)）a = Columns 1 through 12 0 0 0 1 1 1 1 1 0 0 0 0 Columns 13 through 24 0 1 1 1 1 1 0 0 0 0 0 1最優(yōu)狀態(tài)序列：e = Columns 1 through 12 0 0 0 120 130 130 130 130 0 0 0 0

22、Columns 13 through 24 0 130 90 130 130 90 0 0 0 0 0 130調(diào)度得到的最小值mincost = -3.9552e+003開機(jī)序列（0：關(guān)機(jī)態(tài) 1：開機(jī)態(tài)）a = Columns 1 through 12 0 0 0 1 1 1 1 1 0 0 0 0 Columns 13 through 24 0 1 1 1 1 1 0 0 0 0 0 1最優(yōu)狀態(tài)序列：e = Columns 1 through 12 0 0 0 100 130 130 130 130 0 0 0 0 Columns 13 through 24 0 130 90 130 130 90 0 0 0 0 0 130調(diào)度得到的最小值mincost = -3.6202e+003遍歷結(jié)果的圖形輸出如下：4兩種方法的比較