基於拉氏鬆弛的生產系統調度子問題序貫更新法的製作方法
2023-06-12 12:50:16
專利名稱：基於拉氏鬆弛的生產系統調度子問題序貫更新法的製作方法
一、所屬領域
本發明屬於系統工程領域的一種可以處理包含同型號設備或資源的複雜生產系統優化調度方法，進一步涉及可以處理同種任務、同型設備、同類資源的生產系統優化調度的基於拉氏鬆弛的子問題序貫更新法。
生產系統優化調度是很多企業日常面臨的重要問題，其目的是合理安排有限地生產資源，以使某個或某些指標達到最優，比如可以是時間最短、成本最低、風險最小、利潤最大等等。到目前為止，已先後有啟發式方法、動態規劃法、混合規劃法、Lagrangian鬆弛法、遺傳算法、神經網絡算法等種類繁多的方法被用於各種生產調度問題的求解。隨著對經濟、社會效益要求的提高及市場競爭的日益激烈，生產系統優化調度的重要性越來越被廣泛認可。根據美國的研究報告，對於一個裝機容量為一千萬至三千萬千瓦的大型電力系統而言，節約1％的生產成本就意味著每年一千萬到三千萬美元的經濟效益(R.C.Grimes and S.J.Jabbour，The DYNAMICS Model for Measuring DynamicOperating Benefits，Technical Report，Decision Focus Incorporated，LosAltos，CA，June 1989)。節約成本還意味著減少資源消耗，從而減少環境汙染，產生的社會效益也極為可觀。
在所有複雜生產系統優化調度方法中，拉氏鬆弛法是最有效的方法之一。與其它方法相比，這種方法有以下重要特點利用拉氏乘子(系統價格)將大規模問題分解為若干子問題求解從而降低了複雜度；便於靈活處理多種約束；計算時間隨問題規模增大僅呈線性增長(其它一些方法有指數增長的趨勢)；計算中得到的對偶函數值可用來評價可行調度方案的優劣(其它方法至多只能給出一個可行調度方案，並不能說明此方案與最優方案「距離」有多遠)。
拉氏鬆弛法的基本思想是並不直接求解原調度問題，而去求解一個與之相應的對偶問題，無論原問題有多麼複雜，對偶問題都是一個凸規劃，對偶函數值和拉氏乘子等信息在很多現實問題中都有重要的經濟意義。
然而，拉氏鬆弛法存在算法結構導致的缺陷，一個很早就被認識到的嚴重缺陷是所謂的同構難題，即在算法執行過程中，無論乘子如何修正，相應於相同設備或任務子問題的對偶解完全相同。同構難題反映了拉氏鬆弛法在求解具有同型號設備的生產調度問題時的固有困難和缺陷。目前，對於拉氏鬆弛法框架下的同構難題，尚無有效的解決方法見諸文獻。下面先用一個例子說明什麼是同構難題。
考慮下述簡單的調度問題，該問題具有兩套相同設備這裡1＝xi≤xi(1)≤xi＝3，i＝1，2，zi(1)∈{0，1}；di(xi(1)，zi(1))定義如下
費用函數Ci(xi(1)，zi(1))定義為
很明顯問題的最優解為
z1(1)＝1，z2(1)＝0，x1(1)＝2，x2(1)＝任意，或
z1(1)＝0，z2(1)＝1，x2(1)＝2，x1(1)＝任意。
目標函數的最優值為104。
用標準的Lagrangian鬆弛法求解上述問題時，會產生下述兩個相同子問題
minLi，withLi≡Ci(xi(1)，zi(1))-λxi(1)·zi(1)，i＝1，2，
s.t.1≤xi(1)≤3
這裡λ是對應於原問題等式約束的乘子。子問題的最優解如下
因此可見無論乘子取值如何，離散變量zi(1)要麼全為0，要麼全為1，根本不會出現一個取0、一個取1的情況。這就遠離了最優解。
圖1給出了
隨λ的變化曲線。
無論乘子在算法中如何被更新，都始終得不到原問題的最優解。後文中我們將說明用本發明提出的序貫更新法則可以得到原問題的最優解。
同構難題產生的根本原因在於拉氏鬆弛法是一種基於價格的調度方法，拉氏乘子是價格的反映。在拉氏鬆弛法框架下，對於一個含有很多同型設備的系統，如果每套設備對應一個子問題，由於同型號設參數完全相同，相應的子問題也完全相同，導致對應的對偶解完全相同。當乘子改變時，這些解一起改變並始終保持相同。如果調度中存在一些離散決策變量(比如決定設備開關機狀態的變量)，則乘子的任何微小改變都可能使這些變量取值發生一致的跳變。比如，某個生產系統有10套相同型號的設備，最優生產計劃是某時刻只開5套進行生產，但用拉氏鬆弛法求解時任何時候10套設備都是要麼一起關，要麼一起開，永遠不會出現開5套關5套的解。這種同構難題導致的一個後果是對偶解嚴重偏離了原問題的最優解，換句話說對偶解未能包括足夠的關於最優解的信息，以此為基礎構造的可行調度方案其質量將受到影響。背景技術：
本發明的目的是在保留拉氏鬆弛法優點的同時，解決同構難題。提出一種基於拉氏鬆弛的新方法子問題序貫更新法，使相同設備子問題的對偶解不再相同並更接近於最優解，並保證了方法的收斂性。本發明的關鍵思想是針對系統約束加入非線性懲罰項和序貫求解、更新子問題，以便根本上解決此難題。
非線性懲罰項曾用於增廣拉氏鬆弛法。由於懲罰項耦合了各個設備，對偶問題不再具有可分性，導致該方法幾乎不可能用於實際計算(由組合爆炸或維數災難引起)。因此在現有文獻中的增廣拉氏鬆弛法，其則懲罰項一般被線性化或用其它方法處理以解耦(G.Cohen and D.Zhu，「DecompositionCoordination Methods in Large Scale Optimization ProblemsThe Non-differentiable Case and the Use of Augmented Lagrangian，」Advances inLarge Scale SystemsTheory and Applications，Vol.27，JAI Press Inc.CT，USA，1988，pp.203-266；J.Batut and A.Renaud，「Daily GenerationScheduling Optimization with Transmission ConstraintsA New Class ofAlgorithms，」IEEE Transaction on Power System，Vol.7，No.3，1992，pp.982-989；S.J.Wang，S.M.Shahidehpour，D.S.Kirschen，S.Mokhtariand G.D.Irisarri，Short-term Generation Scheduling with Transmissionand Environmental Constraints Using an Augmented Lagrangian Relaxation，IEEE Transactions on Power Systems，Vol.10，No.3，1995，pp.1294-1301)，在這樣的結構下同型號設備對應的子問題還是完全相同，同構難題依然存在。
一種偽次梯度法(X.Zhao，P.B.Luh，and J.Wang，Surrogate SubgradientAlgorithm for Lagrangian Relaxation，Journal of Optimization Theory andApplications，Vol.100，No.3，1999，pp.609-712)以偽次梯度作為修正Lagrangian乘子的方向，只需要求解一個或幾個子問題就可以獲得偽次梯度，減少了計算量，但不能保證對偶解與原問題的最優解足夠接近。
發明內容
根據上述現有技術存在的缺陷或不足，本發明的目的是，提供一種可處理同種任務、同型設備、同類資源的生產系統優化調度的基於拉氏鬆弛的子問題序貫更新法。
本發明創新點是在降低計算量的前提下，將非線性懲罰與序貫求解的思想相結合，從而得到與原問題最優調度更接近的調度方案，並保證方法的收斂性；按以下方法進行
假定有I套設備的生產系統生產某種產品，調度周期為T個時段，生產時需要J種原料，本發明考慮的生產系統調度問題可描述為
其中pi(t)是設備i在第t時段內的產量；Ci(pi(t))為設備i在第t時段內的生產成本；xi(t)為設備i在第t時段所處的開關機狀態，它記錄到第t時段為止設備i已開(正值)或已關(負值)的時段數；Si(xi(t-1)，xi(t))為開、關機費用，僅當xi(t)與xi(t-1)異號時取非零值；
是設備i在第t時段內產量為pi(t)時對原料j的消耗量；pd(t)是第t時段的合同產量；
是第t時段內原料j的供應限制。除了(2)和(3)兩個系統約束外，各設備還有自身的物理及運行約束，主要包括
生產能力限制約束
其中pimax(t)，pimin(t)分別為設備i在第t時段內的最大、最小產量。
最小開關機時間約束
其中τiup，τidown分別為設備i的最小開、關機時段數。
此外還有檢修計劃約束(即某些時段內某些設備必須開機或關機)、產量變化限制約束(同一設備在連續兩個開機時段產量變化不能過大)等等，所有這些都視具體的生產系統而定。
針對問題(1)-(5)的增廣拉氏函數為
式中一些記號含義為P＝[pi(t)]l×T，X＝[xi(t)]l×T是兩個矩陣，且P和X要滿足(4)-(5)兩個約束和其它的單設備約束；λ＝[λ(1)，λ(2)，Λ，λ(T)]是對應於約束(2)的乘子向量，μ＝[μj(t)]J×T是對應於約束(3)的乘子矩陣，且μj(t)≥0。w≥0是罰因子。
與之相應的對偶問題為
其中對增廣拉氏函數求極小時P和X要滿足(4)-(5)兩個約束和其它的單設備約束。
經過對式(6)的整理，可得到其中k∈{1，2，Λ，I}，P(i)，X(i)分別為P和X的第k行，且 (9)第k個子問題為其中 (11)
本發明申請保護的一種新的生產調度方法，其專有的特點是在拉氏鬆弛的框架下，每個設備或任務相對應的子問題帶有與其它設備或任務有關的懲罰項，只對一個子問題採用序貫求解或更新後，就對拉氏乘子(系統價格)更新，從而根本解決了拉氏鬆弛框架下優化調度算法的同構難題，其描述如下
1.初始化置迭代次數l＝0；給定乘子的初始值λl＝λ0，μl＝μ0≥0。在(6)中置w＝0並應用標準拉氏鬆弛調度方法對各個設備或任務獨立進行調度(此時相同設備或任務的調度方案是相同的)，取得P0和X0，見(X.Guan，P.Luh，H.Yan，and J.A.Amalfi，A Optimization-Based Method for Unit Commitment，International Journal of Electric Power & Energy Systems，Vol.14，No.1，1992，pp.9-17)。給定罰因子w0，然後，重置λ0為其中
。記L0＝L(λ0，μ0，P0，X0，w0)，則(13)保證了L0＜Φ*(w0)。
2.更新乘子(系統價格)其中為相應的偽次梯度，sl是第1次迭代時的步長，且滿足0＜sl＜(Φ*(w0)-Ll)/‖gl‖2 (18)
3.依序對一個設備或任務調度並更新P和X
基於對(10)的求解對一個設備或任務進行調度，直到
Ll+1＝L(λl+1，μl+1，Pl+1，Xl+1，w0)≤L(λl+1，μl+1，Pl，Xl，w0)(20)滿足，轉到下一步。
4.更新迭代次數l+1l，判斷收斂準則是否滿足，若滿足則停止計算，否則轉2。可以用迭代次數限制或相鄰兩次迭代解的變化量或偽次梯度範數作為收斂性判據。
本發明描述的方法同時保留了拉氏鬆弛的框架、偽次梯度法和增廣拉氏鬆弛法的優點，並克服了它們各自的缺點，另外，從方法描述中可以看到，在第3步，每次極小化
後，若k變化則yk(t)和zkj(t)已發生變化，因此即便兩套設備型號相同，對應的對偶解一般也不同(無論乘子是否改變)，從而解決了同構難題。需要說明，即便生產系統中不含有同型號設備，本發明中提出的方法依然適用，且效果也比標準偽次梯度法和標準拉氏鬆弛法好。本發明提出的序貫更新法的收斂性證明在附錄中給出。
用本發明提出的方法對前述例子調度，步長取為sl＝0.95×0.01×Ll/‖gl‖2結果如下
表1本說明例子的計算結果
可見應用子問題序貫更新法，使相同設備得到了相異的調度方案，即原問題最優調度方案p1＝2，p2＝0，解決了同構難題。四
圖1是現有技術中子問題的解與乘子的關係示意圖2是對偶解對系統約束的違反程度隨迭代次數變化趨勢示意圖。五具體實施例方式
以下結合實施例對本發明作進一步的詳細描述。
本發明的實施實例
按照本發明的技術方案，選擇電力系統生產調度問題做為實施本發明的具體例子，但這裡強調本發明的原理和方法適合於任何包含多套設備的生產系統調度問題。
該實施例中共有10臺機組，其中1號與2號機組為同型機組，3-8號機組為同型機組，調度周期包含24個時段，需要說明，電力系統中的旋轉備用約束可以看作是原料限制，因為該約束具有(3)的形式。機組生產參數及系統信息(初始狀態、合同產量、原料限制等等)如表2。
由於機組4-8與機組3的有關參數完全相同，故未列出。在該實施例中，Si(xi(t-1)，xi(t))為線性啟動費用函數，定義為
該實施例的系統數據在表3中給出。
本發明的方法用Matlab語言在PIII667MHz微機上進行計算，並同標準拉氏鬆弛法相比較總結見表4，其中SLR、SSU分別表示標準拉氏鬆弛法和序貫更新法。從結果看，本發明提出的方法明顯優於標準拉氏鬆弛法。在表4中，系統約束違反程度指對偶解對約束(2)和(3)的違反程度，按1-範數定義，通常情況下，違反程度越小，則對偶解越容易調整為可行解，且質量較好。
為進一步說明本發明中提出的方法能克服同構難題，表5列出了兩種方法求得的4個相同機組3、4、5、6的對偶解。
表2實施實例1的機組參數表
表3系統數據表
表4計算結果
表5對偶解
從表中可見，在標準拉氏鬆弛法框架下存在同構難題，但本發明提出的方法均克服了同構難題。
參見圖2，圖2描繪了對偶解對系統約束的違反程度隨迭代次數變化趨勢，這裡為了畫圖方便進行了單位變換。從圖中可清晰地看出用標準拉氏鬆弛法時的由同構難題引起的震蕩特性。
本發明中提出的方法求解其它一些生產調度問題，結果也相當令人滿意。
本發明中提出的方法已經用C++語言實現，並嵌入了集成化電力系統資源優化軟體包中計算效果良好，在P-III800微機上求解包含50機組、24小時的優化調度問題所用時間不超過5秒。下面是本發明序貫更新法的收斂性證明
以λ*，μ*表示對偶問題(7)的最優解，先給出三個引理。
引理1.設λa，μa；λb，μb是兩組乘子，則
直接代入(6)式即可證明此引理。
引理2.在算法執行過程中，下式恆成立
Ll＝L(λl，μl，Pl，Xl，w0)＜Φ*(w0) (A2)
證明用歸納法證。l＝0時由算法的第1步可知結論成立(見(13)式)，假設(A2)對l成立，則有
Ll+1＝Ll+1(λl+1，μl+1，Pl+1，Xl+1，w0)
由(20) ≤L(λl+1，μl+1，Pl，Xl，w0)
＝L(λl+1，μl+1，Pl，Xl，w0)-L(λl，μl，Pl，Xl，w0)+L(λl，μl，Pl，Xl，w0)由(A1)由(14)，(15)式由(16)-(19)式
＝Ll+sl‖gl‖2
＜Ll+Φ*(w0)-Ll
＝Φ*(w0)
因此由歸納法原理知(A2)恆成立。注意引理2說明了(18)式中步長因子是存在的。
引理3.在算法執行過程中，下式恆成立證明Φ*(w0)-Ll＝Φ(λ*，μ*，w0)-Ll由(7)≤L(λ*，μ*，Pl，Xl，w0)-Ll再由引理1即得結論。下面是主要結論。定理.在序貫更新算法中，乘子逐步逼進最優解，即有下式成立證明由(A3)-2sl(Φ*(w0)-Ll)由(18)-(19)再由(18)和(A2)從而(A4)成立。
權利要求
1.一種可處理同種任務、同型設備、同類資源的優化調度的基於拉氏鬆弛的生產系統調度子問題序貫更新法，其特徵在於在降低計算量的前提下，將非線性懲罰與序貫求解的思想相結合，從而得到與原問題最優調度更接近的調度方案，並保證方法的收斂性；按以下方法進行
假定有I套設備的生產系統生產某種產品，調度周期為T個時段，生產時需要J種原料，本發明考慮的生產系統調度問題可描述為
其中pi(t)是設備i在第t時段內的產量；Ci(pi(t))為設備i在第t時段內的生產成本；xi(t)為設備i在第t時段所處的開關機狀態，它記錄到第t時段為止設備i已開(正值)或已關(負值)的時段數；Si(xi(t-1)，xi(t))為開、關機費用，僅當xi(t)與xi(t-1)異號時取非零值；
是設備i在第t時段內產量為pi(t)時對原料j的消耗量；pd(t)是第t時段的合同產量；
是第t時段內原料j的供應限制。除了(2)和(3)兩個系統約束外，各設備還有自身的物理及運行約束，主要包括
生產能力限制約束
其中pimax(t)，pimin(t)分別為設備i在第t時段內的最大、最小產量；
最小開關機時間約束
其中τiup，τidown分別為設備i的最小開、關機時段數；
此外還有檢修計劃約束(即某些時段內某些設備必須開機或關機)、產量變化限制約束(同一設備在連續兩個開機時段產量變化不能過大)等等，所有這些都視具體的生產系統而定；
針對問題(1)-(5)的增廣拉氏函數為
式中一些記號含義為P＝[pi(t)]l×T，X＝[xi(t)l×T是兩個矩陣，且P和X要滿足(4)-(5)兩個約束和其它的單設備約束；λ＝[λ(1)，λ(2)，Λ，λ(T)]是對應於約束(2)的乘子向量，μ＝[μj(t)]l×T是對應於約束(3)的乘子矩陣，且μj(t)≥0。w≥0是罰因子；
與之相應的對偶問題為其中對增廣拉氏函數求極小時P和X要滿足(4)-(5)兩個約束和其它的單設備約束；
經過對式(6)的整理，可得到其中k∈{1，2，Λ，I}，P(i)，X(i)分別為P和X的第k行，且(9)第k個子問題為其中 (11)
在拉氏鬆弛的框架下，每個設備或任務相對應的子問題帶有與其它設備或任務有關的懲罰項，只對一個子問題採用序貫求解或更新後，就對拉氏乘子(系統價格)更新，其描述如下
1)初始化置迭代次數l＝0；給定乘子的初始值λl＝λ0，μl＝μ0≥0。在(6)中置w＝0並應用標準拉氏鬆弛調度方法對各個設備或任務獨立進行調度(此時相同設備或任務的調度方案是相同的)，取得P0和X0，給定罰因子w0，然後，重置λ0為其中
。記L0＝L(λ0，μ0，P0，X0，w0)，則(13)保證了L0＜Φ*(w0)；
2)更新乘子(系統價格)其中為相應的偽次梯度，sl是第1次迭代時的步長，且滿足0＜sl＜(Φ*(w0)-Ll)/‖gl‖2(18)
3)依序對一個設備或任務調度並更新P和X
基於對(10)的求解對一個設備或任務進行調度，直到
Ll+1＝L(λl+1，μl+1，Pl+1，Xl+1，w0)≤L(λl+1，μl+1，Pl，Xl，w0)(20)滿足，轉到下一步；
4)更新迭代次數l+1l，判斷收斂準則是否滿足，若滿足則停止計算，否則轉2)；可以用迭代次數限制或相鄰兩次迭代解的變化量或偽次梯度範數作為收斂性判據。
全文摘要
本發明公開了一種可以處理同種任務、同型設備、同類資源的生產系統優化調度的基於拉氏鬆弛的子問題序貫更新法,其特點是在拉氏鬆弛的框架下,每個設備或任務相對應的子問題帶有與其它設備或任務有關的懲罰項,只對一個子問題採用序貫求解或更新後,就對拉氏乘子(系統價格)更新,從而根本解決了拉氏鬆弛框架下優化調度算法的同構難題,同時保留了拉氏鬆弛的框架、偽次梯度法和增廣拉氏鬆弛法的優點,即便生產系統中不含有同型號設備,本發明中提出的方法依然適用,且效果也比標準偽次梯度法和標準拉氏鬆弛法好。
文檔編號G06F9/45GK1359066SQ02114410
公開日2002年7月17日 申請日期2002年1月16日 優先權日2002年1月16日
發明者管曉宏, 翟橋柱 申請人:西安交通大學