多条件约束下的负荷分配

摘 要：为了解决广泛存在于电力工程设计中的带条件约束的负荷分配问题，本文采用动态规划中的01背包算法，将电力工程中不同的约束条件映射至背包算法中的体积，利用背包算法的过程矩阵含义倒推放入背包的物品。对01背包进行拓展，将负荷的多个约束条件映射至不同价值，在多条件约束下进行负荷分配。讨论背包算法的复杂度，对负荷分配中的典型约束条件——距离提出2种反比例函数，在不同情况下对距离进行映射，并与寻路算法联立。经验证，本方法可较好地解决单个设备内的多条件约束下的负荷分配问题。

关键词：多条件约束；负荷分配；动态规划；二维背包；自动化设计

中图分类号：TM 73" " " " " " " 文献标志码：A

在各个电压等级的电力设计中，负荷分配始终是一个绕不开的问题，应用场景不同，负荷分配方式不同，例如在确定总开关位数的前提下，求最大负荷的分配方式；在确定总出线数和总功率情况下，求最近负荷的分配方式。这似乎是一个排列组合问题，但是利用排列组合来求解，在负荷和限制条件较多的情况下，会导致时间复杂度过高。本文将该问题转化为背包问题，采用动态规划的方法降低计算复杂度，在可接受的时间内完成在多条件约束下的负荷自动分配。

在工程设计中，在有限空间（盘箱柜）内应使负荷最大化、连接距离最近，但是总功率不能超出进线开关上限。

1 工程中的约束条件

1.1 单条件约束下的负荷分配

热控电源柜开关排布如图 1所示，热控电源柜内基本是一些传感器或电动阀门，功率一般很难超过进线开关上限，2p开关模数为36 mm，3p开关模数为54 mm。需要在有限模数空间内放下更多负荷。

1.2 多条件约束下的负荷分配

在配网设计中，一进六出的分支箱中，分配负荷有以下4个约束条件。1）进线总电流不超过400 A。2）每个出线的负荷电流不超过160 A。3）出线数不超过5个，要预留1个出线作为备用。4）负荷要距离分支箱尽可能近。强电箱内的空气开关的负荷分配、变压器的负荷分配和MCC柜抽屉分配等原理相似，本文解决上述提到的带条件约束的负荷分配问题。

2 数学建模

将在单条件约束下的负荷分配问题视为一个背包问题。

2.1 背包问题简介

有N件物品和1个容量为V的背包，放入第i件物品耗费的费用是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大[1]。

2.2 状态转移方程

最基础的背包问题即每种物品仅有1件，可以选择放或不放。用子问题定义状态，即F[i，v]为前i件物品放入1个容量为v的背包可以获得的最大价值。其状态转移方程如公式（1）所示。

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

式中：i，v分别为矩阵的位置下标；F[i，v]为矩阵F第i行第v列的数值，其物理含义为前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个分支箱的出线数为4，求在一系列负荷中可以使分支箱总功率最大的负荷分配方式。

映射方法：将分支箱的出线数映射为背包的体积。每个负荷的体积为1，背包的体积为4。将负荷的功率映射为背包物品的价值。

代码架构：在程序中设计一种负载类，具有名称、出线数（容积）和功率属性，再设计一种盘箱柜类，具有名称、额定最大功率和最大出线数属性。随意生成5个负荷，分配至1个最多四出线，要预留其中1个作备用出线的分支箱内。

本文提到的类的初始化参数如上文所示，为方便说明，本文实例化的数据如代码如下。

branch1=Carbinet（“一进四出低压分支箱”，220， 4）#实例化一个最大功率为220 kW，最大出线数为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 单条件约束的过程分析与结果输出

上文虽然得到了单个分支箱的最大功率，但是无法得知选择了哪些负荷，为解决这个问题，须先了解生成的二维数组的物理意义，如图2所示。在图2中，纵坐标为负荷数量，横坐标为出线数，表中数值为在当前负荷数量约束和当前出线数约束下能获得的最大价值，价值映射为功率。

根据物理意义对数组从右下角进行倒推，如果F[I，j]gt;F[i-1，j]，则第i个负荷选中进入分支箱内，出线数应当减去该负荷的出线数。在本文中，每个负荷所占的出线数都是1，应当进行如下判断，图中每个方框如果大于其上一行的数据，即存在向上箭头，则此方框对应的负荷索引选入分支箱。游标向左移动，其移动的距离应当等于该负荷所具有的出线数。二维数组反推负荷索引过程如图3所示。

对代码中的F数组即res_arr进行以下处理，如果在二维数据中每个对象的数值大于其上一行对象的数值，那么输出这个对象的名称。

2.3.1.2 单条件约束的问题

根据《居住区供配电设施建设标准》 （DGJ32/TJ 11—2016）[2]，单根电缆供电容量=1.5×∑供电范围内居民住宅负荷×Kp，Kp为配置系数，在进线开关400 A的前提下，取系数1.5进行计算，1个分支箱总功率最高为220 kW。

针对总负荷超标的问题，对总负荷做一个循环，用01背包法求得解以后，对所选的所有负荷进行功率求和，如果所选负荷的总功率大于功率上限，则少1回出线数，继续用01背包法求解。

利用常规的决策树+循环方法来解决多条件约束，有以下问题。1）分支箱利用率不高，利用减少出线数来限制总功率会导致出现多回备用的情况。2）无法衡量负荷远近，在工程中不能将所有满足功率条件的负荷都放入分支箱内。

2.3.2 多条件约束下的负荷选择

针对上述问题，重新审视基本思路。在工程中实际求解的是在限定总功率和总出线数的情况下，距离分支箱最近的负荷分配问题。将01背包问题进行拓展，使其变为一个二维背包问题。生成1个将图3增加一维的三维数组。分支箱的接线如图4所示。

将图3中的矩阵增加一个功率维度，得到矩阵如图5所示，在3个约束条件下求分支箱的最小负荷分配情况。

2.3.2.1 二维背包简介

二维费用的背包问题为每件物品有2种不同的费用，选择这件物品必须同时支出这2种费用。每种费用都有1个可付出的最大值（背包容量）。

设第i件物品所需的2种费用分别为Ci和Di，2种费用可付出的最大值（即2种背包容量）分别为V和U，物品的价值为Wi。

费用增加一个维度，相应的状态也须增加一个维度。v、u为2种费用，F[i，v，u]为前i件物品当付出2种费用时可获得的最大价值。状态转移方程如公式（2）所示。

F[i，v，u]=max{F[i-1，v，u]，F[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，将负荷所占的出线数映射为费用2，重新选择衡量负荷的价值尺度。

2.3.2.2 价值选择

在工程中可以采用寻路算法一[3]对距离进行精确量取[4]。将距离映射一个与其成反比的距离价值即可对距离进行约束，负荷距离分支箱越大，其价值越低；负荷距离分支箱越小，其价值越高。保证算法始终选择分支箱周围的负荷，同时满足其他约束条件。

2.3.2.3 距离价值映射

综上所述，需要1个y与x成反比的函数，当x[0，∞]

时ygt;0。经过筛选得到函数，其函数图像如图6所示，其计算过程如公式（3）所示。

（3）

式中：y为距离价值；x为实际距离输入；k为人为设定的参数。

使用该映射方法表示距离会导致与分支箱特别近的负荷距离价值趋于无穷大。当需要使盘箱柜优先选择近距离的负荷时可以采用。另一种方法是利用人工神经元中常用的激活函数Sigmoid的变形，将距离价值映射至[0，k]的值域，距离越近，距离价值越无限趋近于k；距离越远，距离价值越无限趋近于0。其函数图像如公式（4）所示。

（4）

式中：R为实数。

当使用这种映射方法表示距离时，可以调整 k 值，对在特别近距离情况下的负荷的距离函数进行调整。

当需要选取尽可能近的负荷时，将k设定为一个较大值，对距离远近进行区分；当不需要选取特别近的负荷时，将k设定为一个较小值，以缩小距离价值区间，消除远近负荷的距离价值差异。

增加了一个新的距离价值属性，因此对原先设计的负荷类新增1个传入参数——距离，计算其距离价值属性。

2.3.3 算法优化

由上文可知，2次迭代针对一维背包的时间复杂度和空间复杂度均为O（VN），可以进一步优化时间复杂度和空间复杂度。

2.3.3.1 时间复杂度优化

时间复杂度优化代码如下。

def zero_one_back_bag1（obj_list，max_volumn）：

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

#生成一个二维矩阵，横向为数量递增，纵向为最大容积递增

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）#将此数组赋值成最大可放下的体积

从上面代码的第五行可以看到j从1开始循环，在第七行进行一次数值比较。当j开始迭代时在obj_list[i-1]以上.volumn。将第五行的j直接从obj_list[i-1].volumn开始循环，可以减少迭代次数，同时取消第七行的判断

2.3.3.2 空间复杂度优化

在背包问题的含义中可以看到，随着数组迭代，F[I，j]的数值不断增加，没有必要保留二维数组。

在01背包问题中，只需要保留最后1个一维数组即可知道最大价值。

在二维背包问题中，只需要保留最后1个二维数组即可知道最大价值。

因为降低空间复杂度后出现另一个问题，即无法根据降维后的数组判断在分支箱中加入了哪些负荷，所以在针对工程的算法中，不用降低空间复杂度。

2.3.4 二维背包问题

使用上文的二维背包法，满足工程背景4个约束条件中的3个，对分支箱的出线电流没有进行限制，因此需要限制背包中单元格的大小。在功率维度中，功率单位单元格大小不能超过分支箱出线开关最大电流所限制的出线功率，在负荷录入阶段直接对负荷进行分类能够解决这个问题，可以使用基于人工定义规则的决策树方法进行分类。

3 二维背包方法存在的问题

3.1 仅能完成单个盘/箱/柜内的负荷选择

在工程中，常见重要负荷需要2路不同电源供电，遇到该情况，无法靠背包算法求解，需要额外设计新算法。备用负荷长期不使用，不仅需要解决单个变压器内主负荷不能超限的问题，还要避免单个变压器内备用负荷过多，防止多个变压器负载长期不均衡。

3.2 不同应用场景中物品的体积需要映射为不同属性

在强电箱、热控电源柜中，背包算法中的体积须映射为断路器模数；在MCC低压柜内，体积需要映射为抽屉开关模数；在分支箱中，体积需要映射为出线数。该方法虽然通用，但是还需要针对不同的负荷分法设计不同的类属性，代码函数的传递参数还有优化空间。需要在软件设计中取得方法通用性与专业性的平衡。

3.3 更高维度的计算成本高

根据二维背包的算法设计原理，本文方法可以拓展至更高的维度，形成三维背包与四维数组甚至四维背包与五维数组的形式，其与时间复杂度有统计学意义。由于计算成本上升，因此可能影响其在实际工程中的应用，可以采用其他约束方法。

4 结论

本文方法可较好地完成在单个设备内和多条件约束下的负荷分配问题，其算法的复杂度与约束条件个数有统计学意义，在负荷分配过程中，距离可根据反比例函数映射为距离价值。

参考文献

[1]杨克昌.计算机常用算法与程序设计案例教程[M].2版.北京：清华大学出版社，2015.

[2]江苏住房和城乡建设厅.居住区供配电设施建设标准：DGJ32/TJ 11—2016[S].南京：江苏凤凰科学出版社，2017：1.

[3]俞洋.基于BIM信息和A*算法改良实现工程线路线缆的自动规划与统计[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