摘 要：為了解決廣泛存在于電力工程設計中的帶條件約束的負荷分配問題，本文采用動態(tài)規(guī)劃中的01背包算法，將電力工程中不同的約束條件映射至背包算法中的體積，利用背包算法的過程矩陣含義倒推放入背包的物品。對01背包進行拓展，將負荷的多個約束條件映射至不同價值，在多條件約束下進行負荷分配。討論背包算法的復雜度，對負荷分配中的典型約束條件——距離提出2種反比例函數(shù)，在不同情況下對距離進行映射，并與尋路算法聯(lián)立。經驗證，本方法可較好地解決單個設備內的多條件約束下的負荷分配問題。

關鍵詞：多條件約束；負荷分配；動態(tài)規(guī)劃；二維背包；自動化設計

中圖分類號：TM 73" " " " " " " 文獻標志碼：A

在各個電壓等級的電力設計中，負荷分配始終是一個繞不開的問題，應用場景不同，負荷分配方式不同，例如在確定總開關位數(shù)的前提下，求最大負荷的分配方式；在確定總出線數(shù)和總功率情況下，求最近負荷的分配方式。這似乎是一個排列組合問題，但是利用排列組合來求解，在負荷和限制條件較多的情況下，會導致時間復雜度過高。本文將該問題轉化為背包問題，采用動態(tài)規(guī)劃的方法降低計算復雜度，在可接受的時間內完成在多條件約束下的負荷自動分配。

在工程設計中，在有限空間（盤箱柜）內應使負荷最大化、連接距離最近，但是總功率不能超出進線開關上限。

1 工程中的約束條件

1.1 單條件約束下的負荷分配

熱控電源柜開關排布如圖 1所示，熱控電源柜內基本是一些傳感器或電動閥門，功率一般很難超過進線開關上限，2p開關模數(shù)為36 mm，3p開關模數(shù)為54 mm。需要在有限模數(shù)空間內放下更多負荷。

1.2 多條件約束下的負荷分配

在配網設計中，一進六出的分支箱中，分配負荷有以下4個約束條件。1）進線總電流不超過400 A。2）每個出線的負荷電流不超過160 A。3）出線數(shù)不超過5個，要預留1個出線作為備用。4）負荷要距離分支箱盡可能近。強電箱內的空氣開關的負荷分配、變壓器的負荷分配和MCC柜抽屜分配等原理相似，本文解決上述提到的帶條件約束的負荷分配問題。

2 數(shù)學建模

將在單條件約束下的負荷分配問題視為一個背包問題。

2.1 背包問題簡介

有N件物品和1個容量為V的背包，放入第i件物品耗費的費用是Ci，得到的價值是Wi。求解將哪些物品裝入背包可使價值總和最大[1]。

2.2 狀態(tài)轉移方程

最基礎的背包問題即每種物品僅有1件，可以選擇放或不放。用子問題定義狀態(tài)，即F[i，v]為前i件物品放入1個容量為v的背包可以獲得的最大價值。其狀態(tài)轉移方程如公式（1）所示。

F[i，v] = max{F[i-1，v]；F[i-1，v-Ci] +Wi}" " （1）

式中：i，v分別為矩陣的位置下標；F[i，v]為矩陣F第i行第v列的數(shù)值，其物理含義為前i件物品放進1個容量為v的背包可以獲得的最大價值；Ci為放入第 i 件物品耗費的費用；Wi為得到的價值。

可將原問題轉化為；當不放第i件物品時，背包的總價值為F[i-1，v]；當放第i件物品時，背包的價值為F[i-1，v-Ci]+Wi，兩者間的較大價值即前i件物品放入容量為v的背包能夠獲得的最大價值。

2.3 工程實施

2.3.1 單條件約束下的負荷選擇

本文采用分支箱作為案例說明。

已知1個分支箱的出線數(shù)為4，求在一系列負荷中可以使分支箱總功率最大的負荷分配方式。

映射方法：將分支箱的出線數(shù)映射為背包的體積。每個負荷的體積為1，背包的體積為4。將負荷的功率映射為背包物品的價值。

代碼架構：在程序中設計一種負載類，具有名稱、出線數(shù)（容積）和功率屬性，再設計一種盤箱柜類，具有名稱、額定最大功率和最大出線數(shù)屬性。隨意生成5個負荷，分配至1個最多四出線，要預留其中1個作備用出線的分支箱內。

本文提到的類的初始化參數(shù)如上文所示，為方便說明，本文實例化的數(shù)據(jù)如代碼如下。

branch1=Carbinet（“一進四出低壓分支箱”，220， 4）#實例化一個最大功率為220 kW，最大出線數(shù)為4的分支箱

load1=Load（“消防負荷”，60，1）#實例化一個消防負荷，60kW，占用1個出線，余同

load2=Load（“照明負荷”，90，1）

load3=Load（“地庫負荷”，130，1）

load4=Load（“地庫負荷2”，20，1）

load5=Load（“民用負荷”，30，1）

得到一進四出分支箱，在調用了一維背包的算法后，在只使用3個出線情況下的最大功率為280 kW。

2.3.1.1 單條件約束的過程分析與結果輸出

上文雖然得到了單個分支箱的最大功率，但是無法得知選擇了哪些負荷，為解決這個問題，須先了解生成的二維數(shù)組的物理意義，如圖2所示。在圖2中，縱坐標為負荷數(shù)量，橫坐標為出線數(shù)，表中數(shù)值為在當前負荷數(shù)量約束和當前出線數(shù)約束下能獲得的最大價值，價值映射為功率。

根據(jù)物理意義對數(shù)組從右下角進行倒推，如果F[I，j]gt;F[i-1，j]，則第i個負荷選中進入分支箱內，出線數(shù)應當減去該負荷的出線數(shù)。在本文中，每個負荷所占的出線數(shù)都是1，應當進行如下判斷，圖中每個方框如果大于其上一行的數(shù)據(jù)，即存在向上箭頭，則此方框對應的負荷索引選入分支箱。游標向左移動，其移動的距離應當?shù)扔谠撠摵伤哂械某鼍€數(shù)。二維數(shù)組反推負荷索引過程如圖3所示。

對代碼中的F數(shù)組即res_arr進行以下處理，如果在二維數(shù)據(jù)中每個對象的數(shù)值大于其上一行對象的數(shù)值，那么輸出這個對象的名稱。

2.3.1.2 單條件約束的問題

根據(jù)《居住區(qū)供配電設施建設標準》 （DGJ32/TJ 11—2016）[2]，單根電纜供電容量=1.5×∑供電范圍內居民住宅負荷×Kp，Kp為配置系數(shù)，在進線開關400 A的前提下，取系數(shù)1.5進行計算，1個分支箱總功率最高為220 kW。

針對總負荷超標的問題，對總負荷做一個循環(huán)，用01背包法求得解以后，對所選的所有負荷進行功率求和，如果所選負荷的總功率大于功率上限，則少1回出線數(shù)，繼續(xù)用01背包法求解。

利用常規(guī)的決策樹+循環(huán)方法來解決多條件約束，有以下問題。1）分支箱利用率不高，利用減少出線數(shù)來限制總功率會導致出現(xiàn)多回備用的情況。2）無法衡量負荷遠近，在工程中不能將所有滿足功率條件的負荷都放入分支箱內。

2.3.2 多條件約束下的負荷選擇

針對上述問題，重新審視基本思路。在工程中實際求解的是在限定總功率和總出線數(shù)的情況下，距離分支箱最近的負荷分配問題。將01背包問題進行拓展，使其變?yōu)橐粋€二維背包問題。生成1個將圖3增加一維的三維數(shù)組。分支箱的接線如圖4所示。

將圖3中的矩陣增加一個功率維度，得到矩陣如圖5所示，在3個約束條件下求分支箱的最小負荷分配情況。

2.3.2.1 二維背包簡介

二維費用的背包問題為每件物品有2種不同的費用，選擇這件物品必須同時支出這2種費用。每種費用都有1個可付出的最大值（背包容量）。

設第i件物品所需的2種費用分別為Ci和Di，2種費用可付出的最大值（即2種背包容量）分別為V和U，物品的價值為Wi。

費用增加一個維度，相應的狀態(tài)也須增加一個維度。v、u為2種費用，F(xiàn)[i，v，u]為前i件物品當付出2種費用時可獲得的最大價值。狀態(tài)轉移方程如公式（2）所示。

F[i，v，u]=max{F[i-1，v，u]，F(xiàn)[i-1;v-Ci;u-Di]+Wi} （2）

式中：i、v和u分別為矩陣的位置下標；F[i，v，u]為矩陣F第i行第v列第u層。當不放第i件物品時，背包的總價值為F[i-1，v，u]；當放第i件物品時，背包的價值為F[i-1，v-Ci，u-Di] + Wi，兩者間的較大價值即前i件物品放入容量為v，u的背包能夠獲得的最大價值。

本文將負荷的功率映射為費用1，將負荷所占的出線數(shù)映射為費用2，重新選擇衡量負荷的價值尺度。

2.3.2.2 價值選擇

在工程中可以采用尋路算法一[3]對距離進行精確量取[4]。將距離映射一個與其成反比的距離價值即可對距離進行約束，負荷距離分支箱越大，其價值越低；負荷距離分支箱越小，其價值越高。保證算法始終選擇分支箱周圍的負荷，同時滿足其他約束條件。

2.3.2.3 距離價值映射

綜上所述，需要1個y與x成反比的函數(shù)，當x[0，∞]

時ygt;0。經過篩選得到函數(shù)，其函數(shù)圖像如圖6所示，其計算過程如公式（3）所示。

（3）

式中：y為距離價值；x為實際距離輸入；k為人為設定的參數(shù)。

使用該映射方法表示距離會導致與分支箱特別近的負荷距離價值趨于無窮大。當需要使盤箱柜優(yōu)先選擇近距離的負荷時可以采用。另一種方法是利用人工神經元中常用的激活函數(shù)Sigmoid的變形，將距離價值映射至[0，k]的值域，距離越近，距離價值越無限趨近于k；距離越遠，距離價值越無限趨近于0。其函數(shù)圖像如公式（4）所示。

（4）

式中：R為實數(shù)。

當使用這種映射方法表示距離時，可以調整 k 值，對在特別近距離情況下的負荷的距離函數(shù)進行調整。

當需要選取盡可能近的負荷時，將k設定為一個較大值，對距離遠近進行區(qū)分；當不需要選取特別近的負荷時，將k設定為一個較小值，以縮小距離價值區(qū)間，消除遠近負荷的距離價值差異。

增加了一個新的距離價值屬性，因此對原先設計的負荷類新增1個傳入?yún)?shù)——距離，計算其距離價值屬性。

2.3.3 算法優(yōu)化

由上文可知，2次迭代針對一維背包的時間復雜度和空間復雜度均為O（VN），可以進一步優(yōu)化時間復雜度和空間復雜度。

2.3.3.1 時間復雜度優(yōu)化

時間復雜度優(yōu)化代碼如下。

def zero_one_back_bag1（obj_list，max_volumn）：

\"\"\" 01背包 \"\"\"

#生成一個二維矩陣，橫向為數(shù)量遞增，縱向為最大容積遞增

res_arr=np.zeros（（len（obj_list）+1，max_volumn+1），np.float）

for i in range（1，len（obj_list）+1）：#物品遍歷

for j in range（1，max_volumn+1）：#分支箱出線上漲

if j gt;=obj_list[i-1].volumn：#如果體積膨脹到可以放下第i個物品，則放入這個物品

res_arr[i，j]=max（res_arr[i-1，j]，res_arr[i-1][j-obj_list[i-1].volumn]+obj_list[i-1].power）#將此數(shù)組賦值成最大可放下的體積

從上面代碼的第五行可以看到j從1開始循環(huán)，在第七行進行一次數(shù)值比較。當j開始迭代時在obj_list[i-1]以上.volumn。將第五行的j直接從obj_list[i-1].volumn開始循環(huán)，可以減少迭代次數(shù)，同時取消第七行的判斷

2.3.3.2 空間復雜度優(yōu)化

在背包問題的含義中可以看到，隨著數(shù)組迭代，F(xiàn)[I，j]的數(shù)值不斷增加，沒有必要保留二維數(shù)組。

在01背包問題中，只需要保留最后1個一維數(shù)組即可知道最大價值。

在二維背包問題中，只需要保留最后1個二維數(shù)組即可知道最大價值。

因為降低空間復雜度后出現(xiàn)另一個問題，即無法根據(jù)降維后的數(shù)組判斷在分支箱中加入了哪些負荷，所以在針對工程的算法中，不用降低空間復雜度。

2.3.4 二維背包問題

使用上文的二維背包法，滿足工程背景4個約束條件中的3個，對分支箱的出線電流沒有進行限制，因此需要限制背包中單元格的大小。在功率維度中，功率單位單元格大小不能超過分支箱出線開關最大電流所限制的出線功率，在負荷錄入階段直接對負荷進行分類能夠解決這個問題，可以使用基于人工定義規(guī)則的決策樹方法進行分類。

3 二維背包方法存在的問題

3.1 僅能完成單個盤/箱/柜內的負荷選擇

在工程中，常見重要負荷需要2路不同電源供電，遇到該情況，無法靠背包算法求解，需要額外設計新算法。備用負荷長期不使用，不僅需要解決單個變壓器內主負荷不能超限的問題，還要避免單個變壓器內備用負荷過多，防止多個變壓器負載長期不均衡。

3.2 不同應用場景中物品的體積需要映射為不同屬性

在強電箱、熱控電源柜中，背包算法中的體積須映射為斷路器模數(shù)；在MCC低壓柜內，體積需要映射為抽屜開關模數(shù)；在分支箱中，體積需要映射為出線數(shù)。該方法雖然通用，但是還需要針對不同的負荷分法設計不同的類屬性，代碼函數(shù)的傳遞參數(shù)還有優(yōu)化空間。需要在軟件設計中取得方法通用性與專業(yè)性的平衡。

3.3 更高維度的計算成本高

根據(jù)二維背包的算法設計原理，本文方法可以拓展至更高的維度，形成三維背包與四維數(shù)組甚至四維背包與五維數(shù)組的形式，其與時間復雜度有統(tǒng)計學意義。由于計算成本上升，因此可能影響其在實際工程中的應用，可以采用其他約束方法。

4 結論

本文方法可較好地完成在單個設備內和多條件約束下的負荷分配問題，其算法的復雜度與約束條件個數(shù)有統(tǒng)計學意義，在負荷分配過程中，距離可根據(jù)反比例函數(shù)映射為距離價值。

參考文獻

[1]楊克昌.計算機常用算法與程序設計案例教程[M].2版.北京：清華大學出版社，2015.

[2]江蘇住房和城鄉(xiāng)建設廳.居住區(qū)供配電設施建設標準：DGJ32/TJ 11—2016[S].南京：江蘇鳳凰科學出版社，2017：1.

[3]俞洋.基于BIM信息和A*算法改良實現(xiàn)工程線路線纜的自動規(guī)劃與統(tǒng)計[J].中國高新科技，2022（13）：42-44.

[4] CUI T Y.背包問題9講2.0 beta1.2[EB/OL].[2012-05-28].https：//github.com/tianyicui/pack/blob/master/V2.pdf