静态和动态规划求解下料方法的比较研究

刘海金 贾春玉

（广东培正学院管理学院，广东 广州 510830）

下料问题是木材、玻璃、纺织品、钢材以及建筑业等众多行业的常见问题。这类问题涉及生产下料、装箱（即下料的反向问题）配送等。下料方式和方法对降低企业运营成本、高效并快速求得较少的下料方案和提高材料利用率至关重要。目前，已有的研究成果主要涵盖启发式算法、整数规划法以及智能搜索法[1]等。然而，整数规划法在求解规模较大的下料问题过程中经常受限制，耗时较长，甚至无法找出可行解。为应对这类挑战，学界相继提出了初始一大一小法[2]、平均数法和再平均法等改进后的一大一小法[3]。尽管这3 种方法在某种程度上解决了相关问题，但它们只考虑了初始原材料尺寸、各产品尺寸及产量要求，而没有充分考虑已选定下料方案的影响。因此，这些方法仍有改进空间。该文提出了以动态规划为基础的求解方法，以改进现有解法并提高优化程度。该方法不仅停留在对原材料尺寸、产品尺寸和产量要求的考虑，还进一步考虑了已选定下料方案的影响，实现了下料问题的全面优化。期待这种新的求解方法能为实际生产带来更高效的解决方案，进一步推动相关行业的发展。

1 有关符号、名词和参数的界定

设原材料长度为H，生产产品品种数为n，产品尺寸为hj，下料方案种数为m，各种产品的产量为Qj，下料上限为UNj（不考虑产量大小时，一根原材料最多可下料第j种产品的个数），实际下料上限RNj（考虑产量大小时，一根原材料最多应该下料第j种产品的个数），需要个数（每种产品生产时所需原材料个数）为XNj，下料个数（在某个下料方案中各产品下料个数）Cij，代表第i个下料方案中第j个产品的下料个数。方案中，下料个数上限（为了选择代表性良好的方案，在某个下料方案中对下料个数的限制）为CNj。其中i=1，2，…，m，j=1，2，…，n。

大比例和小比例方案的确定根据3 个参数进行，大比例参数KDj是确定某产品大比例方案的参数。为了满足各种产品的产量要求，确保一个方案的某个产品下料个数大于等于该产品实际下料上限乘以大比例参数，使该产品下料个数足够大。KDj取值范围为0 ＜KDj≤1，通常取0.75左右。

小比例参数KXj是指为了保证各种产品的可下料总数与产量要求尽可能一致，便于优化组合并提高优化程度而设置的该产品下料上限的一定比例。KXj可保证在某个方案中该产品下料个数足够小，并且下料个数小于等于该系数乘下料上限。KXj取值范围通常为0.01 ＜KXj≤0.3，一般取0.1 左右。

下料个数上限比例参数为KSj。KSj是指为了便于优化组合，确保代表性良好，在小比例方案中尽可能出现较多产品而设置的各产品下料上限的一定比例。KSj可保证各产品下料个数大小适中，使下料个数小于等于该系数乘下料上限（注意这里取下料上限，而不是实际下料上限RNj，否则数据过小，影响优化程度）。KSj取值范围一般为0.2＜KSj≤0.7，一般取0.5 左右。

综上所述，可得如下文所示的重要计算公式。

下料上限UNj如公式（1）所示。

式中：符号“[]1”代表向下取整。

下文中（在大比例和小比例方案中）的符号“[]1”代表向上取整。

实际下料上限RNj如公式（2）所示。

需要个数XNj如公式（3）所示。

小比例方案中的下料个数上限CNj如公式（4）所示。

最优解下限LN如公式（5）所示。

式中：符号“[]1”代表向上取整。

优化程度Yp计算公式如（6）所示。

式中：Np为优化结果，原材料需要个数。

2 静态和动态解法介绍

2.1 静态解法介绍

静态解法具体如下。

方法1，根据大比例参数KDj、小比例参数KXj和上限参数KSj统一设置，每种产品确保具有一个大比例方案。方案中下料个数Nj≥KDj·RNj，其余产品下料个数不限。每种产品确保具有一个小比例方案，方案中下料个数满足1 ≤Nj≤KXj·RNj约束条件。其余产品下料个数满足N≤KS·RN的约束条件。

方法2，可称为平均数法，即根据各产品需要个数与该数的平均数进行比较，把产品分为2 种类型，一是各产品需要个数大于等于该数的平均数，界定为短缺。该类产品第一个参数不变，后2 个参数分别加k2和k3。其余产品为不短缺，将不短缺的产品的第一个参数减k1，其余2 个参数不变。其余与方法1 相同。

方法3，可称为再平均数法，即在方法2 平均数基础上再求平均数，根据各产品需要个数与再平均数进行比较，把产品分为2 种类型，一是各产品需要个数大于等于再平均数，界定为紧缺，其余为不紧缺。在平均法的基础上，将紧缺的产品KDj调整为KDj+k2，不紧缺KDj调整为KXj，其余不变。KXj系数与方法2 参数相同。紧缺的产品KSj调整为KSj+k1，不紧缺产品KSj调整为KXj，其余不变。其余与方法2 相同。

2.2 动态解法介绍

该文提出了2 种动态解法，一是根据方法2 进行动态调整，选择入选小比例方案，称为方法4；二是根据方法3 进行动态调整，选择入选小方案，称为方法5。2 种动态解法方法如下。

方法4：在方法2 求解、确定各产品大比例方案后，计算各产品各方案累计下料个数及其平均数，将小于平均数为一类，称为短缺，其余为不短缺。只进一步限制不短缺一类的取值上限，该文采用上限为1（也可用小比例上限代替1），其余与方法2 相同。

方法5：在方法3 求解、确定各产品大比例方案后，计算各产品各方案累计下料个数、累计下料个数平均数和再平均数，小于再平均数为一类，称为紧缺，其余为不紧缺。进一步限制不紧缺一类的取值上限，该文采用上限为1。如果紧缺累计尺寸小于等于原材料尺寸，确保紧缺产品在小方案中出现，即下限为1，否则为0。避免都出现，否则会出现矛盾，其余与方法3 相同。

3 静态和动态解法优势与劣势分析

3.1 静态解法的优势与劣势分析

3.1.1 静态解法的优势

静态解法没有考虑求解过程中已入选下料方案的代表性、各产品数量和优化保证程度，即各产品在已有入选下料方案中的出现次数及累计数量。静态解法优势相对简单，计算工作量相对较少，便于编写求解程序，优化程度较高，便于掌握和运用。该方法只需要事先确定好相关比例和入选规则，进行规划求解，确定入选方案。规划求解如果优化程度不够理想，可微调选相关比例参数，再求解2～3 组，通常可获得满意近似最优解。

3.1.2 静态解法的劣势

静态解法没有考虑求解过程中已入选下料方案、各产品数量和优化保证程度，有时会导致有些产品出现次数相对多或累计数量大，有些却很少出现或累计数量不大，严重影响入选方案代表性程度，导致最终优化程度不够理想。静态解法的现有方法主要包括一大一小法、平均数法和再平均法等改进后的一大一小法。尽管这3 种方法在某种程度上解决了相关问题，但它们只考虑了初始原材料尺寸、各产品尺寸及产量要求，没有充分考虑已选定下料方案的影响，因此有时代表性不够理想。

3.2 动态解法的优势与劣势分析

3.2.1 动态解法的优势

动态解法考虑求解过程中已入选的下料方案、各产品数量和优化保证程度，即各产品在已有入选下料方案中的产品出现次数及累计数量。根据已入选的下料方案，决定后续入选方案，在多数情况下可有效克服静态解法劣势，最大限度地避免有些产品出现次数相对多或累计数量大，有些却很少出现或累计数量不大，进而影响入选方案代表性程度，导致最终优化程度可能不够理想。

3.2.2 动态解法的劣势

动态解法的劣势主要是计算工作量相对多，方法比静态略复杂，因组合方案多样性和产品尺寸、数量以及原材料尺寸组合特殊性，有时动态解法优化程度比静态提高幅度不大。

4 求解原理与步骤

求解步骤可分为2 个阶段。第一阶段，优化确定入选下料方案。第二阶段，最终求解，即在入选优化组合方案中规划求解出近似最优解。以方法1 为例，求解步骤如下。

第一阶段，设计3 个参数数值，然后确定每种产品的2 种下料方案，一是根据大比例参数（KDj）规划求解出一个大比例方案；二是根据小比例参数（KXj）和上限参数（KSj）规划求解出一个小比例方案。设变量xij为第i个下料方案第j个产品的下料个数，则第一阶段下料方案数学模型如下：1）第一阶段第w（1 ≤w≤n）个产品第w个下料大比例方案数学模型为目标函数。其中，xiw≥RNw·KDj，xij为非负整数（i≠w，j≠w），RNw代表第w个产品实际下料上限。2）第一阶段第y（y=w+n）个下料方案第w个产品小比例方案数学模型为目标函数。其中，，xiw≤RNw×KXj，xij≤CNj（j≠w），xiw≥1，xij为非负整数。

第二阶段，最终求解。为了提高求解速度，在入选的若干个优化组合方案中判断是否有相同的方案，如果有，就将对应下料个数赋值为0；否则保持原样，剔出相同方案，在剩余最终入选的方案中规划求解出近似最优解。该方法在多数情况下可获得满意近似最优解，但有时也会不理想。为了提高优化程度，获得更理想的近似最优解，一方面可反复求解若干次（原因是有时有多个解），通常会提高优化程度。另一方面，可微调参数，再求解若干次，可获得满意的近似最优解。多数情况下只需求解一次就可获得非常理想的近似最优解。设变量xi为第i个最终入选下料方案采用个数，则第二阶段数学模型为目标函数，xi为非负整数。

5 求解实例

使用原材料200cm 棒料，生产产品（也可称为毛坯，以下统称为产品）长度分别为77cm、53cm、42cm、27cm和20cm，5 种产品产量分别为32、156、56、119 和80个，如果忽略切割宽度工艺损耗，求解最省原材料的下料方法，解法如下。

计算相关数据见表1。3 个参数（KDj、KXj、KSj）分别取0.95、0.07 和0.6，微调系数（k1、k2、k3）分别取0.08、0.03 和0.15，微调后的3 个参数见表2，采用方法4 进行求解。

表1 实例1 相关数据计算

表2 方法4 微调后的3 个参数（KDj、KXj、KSj）

第一步，确定第一个产品大比例方案。设5 种产品在第一个产品大比例方案中的下料个数分别为x1，1、x1，2、x1，3、x1，4和x1，5，因为要确保下料方案中第一个产品下料个数足够大，因此应满足x1，1≥[2×0.87]1=2，则可确定第一种产品大比例下料方案数学模型为目标函数maxZ=77x1，1+53x1，2+42x1，3+27x1，4+20x1，5，其中77x1，1+53x1，2+42x1，3+27x1，4+20x1，5≤200，x1，1≥2，变量为非负整数。

运用Excel 规划求解软件解得x1，1=2，x1，3=1，其余均为0。此时目标函数为maxZ=77×2+42×1=196cm。第一个方案为2、0、1、0、0。余下产品求解过程与第一个方案类似，其余4 个大比例方案分别如下：第二个方案为0、3、0、0、2；第三个方案为0、0、4、1、0；第四个方案为0、0、0、7、0；第五个方案为0、0、0、0、10。然后确定各产品小比例方案，根据表2 中的KXj、KSj数值确定约束条件。

第二步，确定第一个产品小比例方案。计算前5 个大方案各产品累计下料个数，各产品累计下料个数分贝为2、3、5、8 和12，平均数为6，其中第4 和第5 个产品累计下料个数分别是8 和12，大于平均数6，因此这2 个产品是不短缺产品，需要限制其出现个数，增加约束x1，4≤1 和x1，5≤1。设5 种产品在第一个产品小比例方案中的下料个数分别为x6，1、x6，2、x6，3、x6，4和x6，5。因为要确保下料方案中第一个产品所在比例足够小且必须有，所以第一个产品在小比例方案中应满足x6，1≥1，x6，1≤[2×0.07]1=1，其余产品下料个数分别满足小于等于（CNj）3、3、5、6，则第一种产品小比例方案数学模型为目标函数maxZ=77x1，1+53x1，2+42x1，3+27x1，4+20x1，5。其中77x1，1+53x1，2+42x1，3+27x1，4+20x1，5≤200，x6，1≤1，x6，2≤3，x6，3≤3，x6，4≤5，x6，5≤6，x6，4≤1，x6，5 ≤1，x6，1≥1，变量为非负整数。解得x6，1=1，x6，2=1，x6，3=1，x6，4=1，x6，5=0，目标函数为maxZ=77×1+53×1+42×1+27×1=199cm。

第六个方案为1、1、1、1、0。余下产品求解过程与第六个方案类似，先计算上述各产品累计下料个数，再计算该数的平均数，其余4 个小比例方案分别如下：第七个方案为1、1、1、1、0；第八个方案为1、1、1、1、0；第九个方案为1、1、1、1、0；第十个方案为0、2、1、1、1。

第三步，规划求解。经比较，第六～第九方案相同，去掉第七、第八和第九方案（即去掉方案对应下料个数分别赋值为0），再规划求解。设实际7 个最终入选方案所采用的数量分别为x1、x2、x3、x4、x5、x6和x10，此时最终规划求解数学模型为目标函数minNp=x1+x2+x3+x4+x5+x6+x10。其中2x1+x6≥32，3x2+x6+2x10≥156，x1+4x3+x6+x10≥56，x3+7x4+x6+x10≥119，2x2+10x5+x10≥80，xi为非负整数（i=1，2，...，10）。解得x1=0、x2=38、x3=5、x4=11、x5=0、x6=32、x10=5，目标函数Np=38+5+11+32+5=91 根。5 种产品可下料总数分别为32、156、57、119 和81 个，其中第3 个和第5 个产品比要求的产量各多1 个，其余与产量相等，能满足各产品产量要求。因优化结果Np=91，最优解下限LN=[（77×32+53×156+42×56+27×119+20×80）/200]1=90，优化程度至少为[1-（91-90）/90]×100%≈98.9%。

5 种方法求解的Np分别为93、93、94、91 和94，优化程度至少分别为96.7%、96.7%、95.6%、98.9%和95.6%。因此该例题方法4 最好，比方法2 优化程度提高了3.3%。

6 试验数据分析

该文随机选取100 个样本，其中需求个数差异大的（最大与最小相差5 倍及以上）和不大的样本各50 个。产品种数为4～5 个，产品尺寸为12cm～187cm，产品产量为20～300个，原材料尺寸为200cm～600cm，大比例参数为0.65～0.95，小比例参数为0.01～0.3，上限参数为0.3～0.7。

在差异大的样本中，5 种方法优化程度相对最好的出现次数分别为15、18、26、33 和24 次，分别占30%、36%、52%、66%和48%，平均优化程度至少分别为91.2%、91.8%、95.92%、95.99%和96%。方法4 单独出现最好次数为10 次，占比20%，其余均为0 次。5 种方法差异较明显，方法1 最差，方法4 最好。动态规划解法方法4 比静态解法方法2 的优化程度平均提高4.1%，动态解法6 与静态解法方法3 几乎无差异。

在差异不大的样本中，5 种方法优化程度相对最好出现次数分别为39、39、32、39 和39 次，分别占78%、78%、64%、78%和78%。平均优化程度至少分别为98.32%、98.28%、97.65%、98.1%，97.39%和98.2%，方法2 和方法5 单独出现最好次数分别为2 和4，占比4%和8%，只有方法3 略差，其余均相等。动态与静态解法几乎无差异，5 种方法也无明显差异，5 种方法都应采用，取最好的方案作为最终优化方案。

在100 个样本中，5 种方法优化程度相对最好出现次数分别为54、57、58、72 和63 次，分别占54%、57%、58%、72%和63%。5 种方法平均优化程度只少分别为94.76%、95.03%、96.78%、97.04%和97.03%，具有一定差异，优化程度级差为2.3%。方法2 的单独最好出现次数为2 次，方法4 为10 次，方法5 为4 次，占比分别为2%、4%和10%。说明这3 种方法不能被替代，最好结合使用，并择优作为最终优化结果。动态解法4 比静态解法2 的优化程度平均提高了2%。动态解法6 与静态解法3 相比几乎无差异，优化程度平均提高了0.23%。

7 结论

虽然静态规划求解方法在多数情况下能得到可接受的近似最优解，但其仅考虑初始状态，并未充分考虑已选取方案对后续方案选择的影响，因此其优化能力仍有提升空间。特别是在产品需求差异显著的情况下（例如最大需求与最小需求相差5 倍以上），这种局限性更突出。动态规划解法在平均数法中的优化程度可比静态解法平均提高4.1%，但在再平均法中，两者的差异几乎可以忽略不计。因此，该文建议将上述策略并行使用，并根据实际结果进行优选，以获得最终的优化结果。然而，动态解法由于仅考虑绝对入选方案累计下料个数，而忽视了相对数，因此仍有改进余地。

综上所述，该文提供的下料优化策略为解决实际生产中的问题提供了可行的解决方案，但仍有改进空间。未来的研究将针对该问题进行深入探索，以使生产更高效。