多條件約束下的負(fù)荷分配

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

關(guān)鍵詞：多條件約束；負(fù)荷分配；動(dòng)態(tài)規(guī)劃；二維背包；自動(dòng)化設(shè)計(jì)

中圖分類號(hào)：TM 73" " " " " " " 文獻(xiàn)標(biāo)志碼：A

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

在工程設(shè)計(jì)中，在有限空間（盤(pán)箱柜）內(nèi)應(yīng)使負(fù)荷最大化、連接距離最近，但是總功率不能超出進(jìn)線開(kāi)關(guān)上限。

1 工程中的約束條件

1.1 單條件約束下的負(fù)荷分配

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

1.2 多條件約束下的負(fù)荷分配

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

2 數(shù)學(xué)建模

將在單條件約束下的負(fù)荷分配問(wèn)題視為一個(gè)背包問(wèn)題。

2.1 背包問(wèn)題簡(jiǎn)介

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

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

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

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

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

可將原問(wèn)題轉(zhuǎn)化為；當(dāng)不放第i件物品時(shí)，背包的總價(jià)值為F[i-1，v]；當(dāng)放第i件物品時(shí)，背包的價(jià)值為F[i-1，v-Ci]+Wi，兩者間的較大價(jià)值即前i件物品放入容量為v的背包能夠獲得的最大價(jià)值。

2.3 工程實(shí)施

2.3.1 單條件約束下的負(fù)荷選擇

本文采用分支箱作為案例說(shuō)明。

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

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

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

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

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

load1=Load（“消防負(fù)荷”，60，1）#實(shí)例化一個(gè)消防負(fù)荷，60kW，占用1個(gè)出線，余同

load2=Load（“照明負(fù)荷”，90，1）

load3=Load（“地庫(kù)負(fù)荷”，130，1）

load4=Load（“地庫(kù)負(fù)荷2”，20，1）

load5=Load（“民用負(fù)荷”，30，1）

得到一進(jìn)四出分支箱，在調(diào)用了一維背包的算法后，在只使用3個(gè)出線情況下的最大功率為280 kW。

2.3.1.1 單條件約束的過(guò)程分析與結(jié)果輸出

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

根據(jù)物理意義對(duì)數(shù)組從右下角進(jìn)行倒推，如果F[I，j]gt;F[i-1，j]，則第i個(gè)負(fù)荷選中進(jìn)入分支箱內(nèi)，出線數(shù)應(yīng)當(dāng)減去該負(fù)荷的出線數(shù)。在本文中，每個(gè)負(fù)荷所占的出線數(shù)都是1，應(yīng)當(dāng)進(jìn)行如下判斷，圖中每個(gè)方框如果大于其上一行的數(shù)據(jù)，即存在向上箭頭，則此方框?qū)?yīng)的負(fù)荷索引選入分支箱。游標(biāo)向左移動(dòng)，其移動(dòng)的距離應(yīng)當(dāng)?shù)扔谠撠?fù)荷所具有的出線數(shù)。二維數(shù)組反推負(fù)荷索引過(guò)程如圖3所示。

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

2.3.1.2 單條件約束的問(wèn)題

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

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

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

2.3.2 多條件約束下的負(fù)荷選擇

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

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

2.3.2.1 二維背包簡(jiǎn)介

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

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

費(fèi)用增加一個(gè)維度，相應(yīng)的狀態(tài)也須增加一個(gè)維度。v、u為2種費(fèi)用，F(xiàn)[i，v，u]為前i件物品當(dāng)付出2種費(fèi)用時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程如公式（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分別為矩陣的位置下標(biāo)；F[i，v，u]為矩陣F第i行第v列第u層。當(dāng)不放第i件物品時(shí)，背包的總價(jià)值為F[i-1，v，u]；當(dāng)放第i件物品時(shí)，背包的價(jià)值為F[i-1，v-Ci，u-Di] + Wi，兩者間的較大價(jià)值即前i件物品放入容量為v，u的背包能夠獲得的最大價(jià)值。

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

2.3.2.2 價(jià)值選擇

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

2.3.2.3 距離價(jià)值映射

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

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

（3）

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

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

（4）

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

當(dāng)使用這種映射方法表示距離時(shí)，可以調(diào)整 k 值，對(duì)在特別近距離情況下的負(fù)荷的距離函數(shù)進(jìn)行調(diào)整。

當(dāng)需要選取盡可能近的負(fù)荷時(shí)，將k設(shè)定為一個(gè)較大值，對(duì)距離遠(yuǎn)近進(jìn)行區(qū)分；當(dāng)不需要選取特別近的負(fù)荷時(shí)，將k設(shè)定為一個(gè)較小值，以縮小距離價(jià)值區(qū)間，消除遠(yuǎn)近負(fù)荷的距離價(jià)值差異。

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

2.3.3 算法優(yōu)化

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

2.3.3.1 時(shí)間復(fù)雜度優(yōu)化

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

def zero_one_back_bag1（obj_list，max_volumn）：

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

#生成一個(gè)二維矩陣，橫向?yàn)閿?shù)量遞增，縱向?yàn)樽畲笕莘e遞增

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個(gè)物品，則放入這個(gè)物品

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(luò)從1開(kāi)始循環(huán)，在第七行進(jìn)行一次數(shù)值比較。當(dāng)j開(kāi)始迭代時(shí)在obj_list[i-1]以上.volumn。將第五行的j直接從obj_list[i-1].volumn開(kāi)始循環(huán)，可以減少迭代次數(shù)，同時(shí)取消第七行的判斷

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

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

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

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

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

2.3.4 二維背包問(wèn)題

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

3 二維背包方法存在的問(wèn)題

3.1 僅能完成單個(gè)盤(pán)/箱/柜內(nèi)的負(fù)荷選擇

在工程中，常見(jiàn)重要負(fù)荷需要2路不同電源供電，遇到該情況，無(wú)法靠背包算法求解，需要額外設(shè)計(jì)新算法。備用負(fù)荷長(zhǎng)期不使用，不僅需要解決單個(gè)變壓器內(nèi)主負(fù)荷不能超限的問(wèn)題，還要避免單個(gè)變壓器內(nèi)備用負(fù)荷過(guò)多，防止多個(gè)變壓器負(fù)載長(zhǎng)期不均衡。

3.2 不同應(yīng)用場(chǎng)景中物品的體積需要映射為不同屬性

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

3.3 更高維度的計(jì)算成本高

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

4 結(jié)論

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

參考文獻(xiàn)

[1]楊克昌.計(jì)算機(jī)常用算法與程序設(shè)計(jì)案例教程[M].2版.北京：清華大學(xué)出版社，2015.

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

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

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