基于整數(shù)規(guī)劃的調(diào)度計劃算法研究

【摘要】本文以實際的地市級供電公司為研究對象，對其停電檢修計劃的優(yōu)化調(diào)度問題開展了研究。優(yōu)化調(diào)度問題數(shù)學(xué)模型的建立、優(yōu)化算法的選取和算法性能的比較分析，并對計算結(jié)果分析對比分析，選取了相對高效的算法。

【關(guān)鍵詞】檢修計劃；整數(shù)規(guī)劃；完全枚舉法

引言

隨著我國經(jīng)濟的持續(xù)高速增長，作為基礎(chǔ)能源的電力行業(yè)也處于高速增長的時期。電網(wǎng)規(guī)模不斷擴大、輸變電設(shè)備不斷增多，一方面提高電網(wǎng)輸送能力、增加了供電的可靠性，為經(jīng)濟社會發(fā)展提供了支撐；另一方面，設(shè)備數(shù)量的迅猛增長也使維護難度增大，設(shè)備數(shù)量的不斷增多，維護人員數(shù)量卻不變甚至減少，這使人員不足的矛盾更加凸顯。

隨著電網(wǎng)規(guī)模的不斷擴大，檢修工作的數(shù)量逐年增多，但專業(yè)人員數(shù)量基本維持不變，逐年遞增的檢修工作和穩(wěn)定不變的檢修人員數(shù)量必然會增大檢修計劃的安排難度。

1、數(shù)學(xué)建模

1.1檢修計劃現(xiàn)狀分析

檢修計劃是由供電公司的生產(chǎn)調(diào)度主管組織多個部門共同討論確定，如圖1.1表示，檢修計劃的制定受很多因素制約，本研究中只選取專業(yè)檢修人員、儀器儀表、車輛等經(jīng)常短缺的資源，這些資源一般數(shù)量穩(wěn)定，規(guī)律性較強，不考慮電網(wǎng)運行方式、保電任務(wù)這類隨機性較強，較為不確定的因素，使其更適合數(shù)學(xué)分析和計算機實現(xiàn)。

1.2數(shù)學(xué)模型的建立

對實際工作的分析可以看出，檢修工作的目的是為了消除電力設(shè)備存在的缺陷，使電力設(shè)備安全運行，而電力設(shè)備的缺陷是根據(jù)嚴重程度可以劃分為不同的緊急程度的，消除了越緊急的缺陷，對電網(wǎng)的幫助越大，所以可以將檢修計劃制定的目標(biāo)理解為：執(zhí)行的檢修計劃緊急程度之和最大。

為了進行定量分析，將各類資源、所有等待安排的檢修計劃以及緊急程度繪制成下面的表1.1：

以每列的計劃作為決策變量，記為Xa，Xb，Xc，……，以可調(diào)配人員作為約束條件，以完成的緊急程度數(shù)值最大為目標(biāo)，這樣這個問題就變成了

目標(biāo)函數(shù)：

2、整數(shù)規(guī)劃算法簡述

2.1完全枚舉法

完全枚舉法又被稱為窮舉法，是將所有可能的組合全部列出，逐一進行目標(biāo)約束條件比較和目標(biāo)函數(shù)比較，算法的時間復(fù)雜度很高，達到2n，對于n較大的情況不使用，考慮到本研究中的數(shù)據(jù)規(guī)模較小，可以嘗試使用完全枚舉法進行求解。

2.2分支定界法

分支定界法是一種求解整數(shù)規(guī)劃問題的常用算法。如果將決策變量的范圍限定為{0，1}，則可以進行0-1規(guī)劃的計算。

第1步：求該問題線性規(guī)劃的最優(yōu)解，若最優(yōu)解為整數(shù)，計算結(jié)束。否則進行下一步。

第2步：選取任意非整數(shù)變量x01進行分支，分別在松弛問題中加上約束x1≤x01和x1≥x01，組成兩個新的松弛問題。

第3步：檢查所有分支的解和目標(biāo)值，如果出現(xiàn)某分支的解的目標(biāo)值大于等于其他分支的目標(biāo)值并且為整數(shù)，則找到最優(yōu)解，若不存在則繼續(xù)分支。

2.3隱枚舉法

隱枚舉法的計算過程與完全枚舉法類似，也是將所有的可能解一一驗證，不同的是將約束條件逐一進行判斷，如果出現(xiàn)一個約束條件不滿足資源限量時，當(dāng)前解的計算結(jié)束，開始驗證下一個解。隱枚舉法在約束條件較多、資源限量較低的情況下，可以有效減少計算時間。

3、算法性能對比

本文采用完全枚舉法、分支定界法、隱枚舉法等三種算法，對地市公司4個季節(jié)選取的檢修計劃數(shù)據(jù)進行計算，通過分析實驗數(shù)據(jù)，討論每種算法的效率，從而選擇適合的算法進行計算。

實驗采用MATLAB作為實驗工具，主要利用其統(tǒng)計功能進行數(shù)據(jù)分析，實驗對3種常用的0-1規(guī)劃算法進行比較，分別是完全枚舉法、分支定界法、隱枚舉發(fā)，將從計算精度、計算用時兩方面進行比較。

參與計算的數(shù)據(jù)選取4個不同時段的日檢修計劃進行，代表了電力企業(yè)生產(chǎn)的幾類典型工作，第一組選取檢修工作量較少的冬天，包含6項檢修工作，用于測試小數(shù)據(jù)量的算法效率；第二組選取春季，選取預(yù)防性試驗的檢修工作，該工作持續(xù)時間較長，包含13項檢修工作，并且涉及專業(yè)較多；第三組選取夏季大負荷時段，該時段危急缺陷較多，存在部分必須處理的缺陷，包含11項檢修工作；第四組選取秋冬季節(jié)，設(shè)備改造為主的檢修工作，共17項。

通過實驗發(fā)現(xiàn)，三種算法均能夠正確的計算出緊急程度最高的解決方案，但是在面對不同的數(shù)據(jù)量時，三種算法的計算效率略有不同，表3.2匯總了4組數(shù)據(jù)使用不同算法的數(shù)據(jù)。

第一組數(shù)據(jù)的數(shù)據(jù)量較少，n=6，三種算法計算效率均很高。

第二組數(shù)據(jù)n=13，代表了地市供電公司春季最繁忙的工作狀態(tài)，分支定界法的計算時間稍長，其他兩種算法用時相近，總體用時可以接受。

第三組數(shù)據(jù)n=11，數(shù)據(jù)取自地市供電公司夏季大負荷時段較典型的工作內(nèi)容，其中包括對危急缺陷的處理，三種算法均很好的完成了計算，值得注意的是分支定界法的計算用時很少，主要原因是訪問節(jié)點數(shù)量減少。

第四組數(shù)據(jù)取自秋季，秋季預(yù)防性試驗、新建變電站投運、設(shè)備大修、技術(shù)改造等多方面工作集中進行，n=17，基本代表了一年中工作最繁忙的狀態(tài)，三種算法對這組數(shù)據(jù)的計算效率均一般，值得關(guān)注的是完全枚舉法和隱枚舉的計算用時和矩陣計算次數(shù)，從矩陣計算次數(shù)來看，完全枚舉法是隱枚舉法的近10倍，但計算用時相近，相差0.09秒，其原因主要是隱枚舉法的矩陣計算雖少，但是邏輯跳轉(zhuǎn)語句的調(diào)用次數(shù)很多，大約為171437×2=342874次，這大大降低了程序的效率。

4、結(jié)束語

按地市供電公司的數(shù)據(jù)量進行算法效率實驗，三種算法的計算用時可以接受，最嚴重的情況在1.8秒左右，普遍情況在0.1秒左右，不會影響用戶體驗和工作效率。實際應(yīng)用中，若在服務(wù)器上運行，機器性能優(yōu)于實驗使用的PC機，計算時間將進一步縮短。完全枚舉法在資源變量一定的情況下，具有性能穩(wěn)定、判斷分支少、易于擴展的優(yōu)點，較適合地市公司檢修計劃的計算。鑒于以上分析，完全枚舉法可以作為地市級供電公司檢修計劃調(diào)度問題的核心算法，用于解決有限的檢修資源分配問題。