★ FEATURED ARTICLE 1. 从一根钢管说起这个经典问题到底在解决什么第一次接触“钢管切割问题”是在一个生产排程的小项目里。车间主任拿着一张三米长的原料清单问我客户要 1.2 米、0.8 米、0.5 米三种规格每种几十根怎么切最省料当时我脑子里第一反应是“这不就是个排列组合吗”结果真动手算才发现组合数量随规格种类呈指数级膨胀手工排根本排不过来。这就是钢管切割问题最朴素的样子给定若干种需求长度和对应数量以及固定长度的原料钢管如何决定每一根原料上切哪些段使得总用料最少、废料最短。它属于运筹学里经典的一维下料问题One-dimensional Cutting Stock Problem本质是一个带约束的整数规划。别看名字里带“钢管”实际应用远不止金属加工木材开料、玻璃裁切、纸卷分切、铝型材下料、甚至布料裁剪只要是把长料切成短料底层模型都是同一套。所以学会这一个问题等于拿到了一类问题的通用解法。这篇文章适合谁看如果你是工厂里负责下料的工艺员想摆脱“凭经验排料、废料一堆”的状态如果你是写生产管理系统的开发者需要把排料算法嵌进业务或者你只是学生想找一个能真正跑起来的整数规划练手案例这篇都能给你可直接复现的东西。我会从建模思路讲到代码实现再到实际排产时那些文档里不会写的坑尽量把每一步的“为什么”说清楚。需要先明确一个前提钢管切割问题有多个变种常见的有只用一种原料长度和多种原料长度可选两类还有是否允许余料入库再利用的区别。本文以最典型的“单一原料长度、需求给定、追求废料最小”为主线展开其他变种在对应位置会点出来。这个选择不是随意的——单一原料是绝大多数中小车间的真实场景先把这条主线吃透扩展才有根基。2. 建模之前先想清楚为什么不能靠“贪心”硬凑2.1 贪心排料的直觉陷阱很多人第一反应是贪心每根钢管都尽量先切最长的需求切不下了再切短的。这个思路听起来合理实际会翻车。举个具体例子原料长 3 米需求是 1.6 米 2 根、1.1 米 3 根、0.6 米 4 根。如果贪心先切 1.6 米一根原料切一根 1.6 后剩 1.4 米再塞一根 1.1 剩 0.3 米废掉第二根同样处理。结果 1.6 米占了两根原料1.1 米还得再开原料废料累计很难看。而如果换一种组合一根原料切 1.11.10.62.8 米另一根切 1.61.12.7 米废料立刻降下来。贪心失败的根本原因在于局部最优不等于全局最优。每一刀的选择会影响后续所有钢管的剩余空间这是一个前后耦合的决策链。所以正规解法必须站在全局视角把所有可能的切割组合先枚举出来再决定每种组合用几次。这个“先枚举组合、再定次数”的两阶段思路是钢管切割问题所有成熟解法的共同骨架。2.2 两种主流建模路线怎么选枚举出组合之后怎么定每种组合的使用次数有两条路可走。第一条是整数规划直接建模。设每种可行切割方案为一个变量变量取值是该方案使用的原料根数目标是最小化总原料根数或总废料约束是每种需求长度被切出的数量不少于订单量。这条路数学上最干净用现成的求解器如开源的 CBC、GLPK或商业求解器几十行代码就能跑。缺点是当规格种类多、原料长时可行组合数量会爆炸变量规模可能上万求解时间不可控。第二条是列生成Column Generation。它不一次性枚举所有组合而是先给一小部分组合求个松弛解再通过一个子问题本质是背包问题动态找出“能改进当前解”的新组合加进来迭代到无法改进为止。这条路适合大规模场景但实现复杂度高一个量级需要理解对偶变量和定价子问题。我的实操建议很直接规格种类在 20 种以内、原料长度常规的优先用整数规划直接建模因为组合枚举完全扛得住代码简单、结果可解释、调试方便。只有当规格上百种、组合数上万导致求解器卡死时才值得上列生成。别一上来就追求“高级算法”工程上能稳定跑出结果、业务方能看懂方案比算法炫技重要得多。下面第 3 节我就按整数规划这条主线把完整实现拆开讲。3. 核心实现拆解从枚举组合到求解落地3.1 第一步枚举所有可行切割组合枚举的逻辑是递归搜索从当前剩余长度出发依次尝试每种需求长度只要不超过剩余长度就切一刀继续往下搜搜到无法再切时把当前组合记录下来。这里有两个关键细节必须处理好否则结果会错得莫名其妙。第一个细节是去重。同样的组合会因为切割顺序不同被重复枚举比如“1.11.10.6”和“1.10.61.1”是同一个方案。解决办法是搜索时强制需求长度按非降序或非升序选取保证每种组合只出现一次。这个约束加在递归参数里一行代码的事但漏了会让变量规模翻好几倍。第二个细节是余料阈值。实际生产中剩余长度小于某个值比如 5 厘米就没法再利用了直接算废料但如果剩余长度还比较可观理论上可以留着下次用。本文主线按“余料全部计为废料”处理这是最保守也最常用的口径。如果你的车间有余料入库制度枚举时就要把“剩余长度大于阈值”的组合单独标记后续目标函数里对这部分余料打折计算模型会复杂一些但思路一致。下面是一段可直接跑的枚举代码用 Python 写逻辑清晰def enumerate_patterns(stock_len, demands, min_waste0.0): # demands: [(length, qty), ...]length 为需求长度 lengths sorted([d[0] for d in demands]) patterns [] def dfs(start_idx, remaining, current): # 记录当前组合剩余长度小于阈值即视为一种完整方案 if remaining min(lengths): if current: patterns.append(tuple(current)) return for i in range(start_idx, len(lengths)): if lengths[i] remaining 1e-9: current.append(lengths[i]) dfs(i, remaining - lengths[i], current) current.pop() dfs(0, stock_len, []) # 去重dfs 已保证非降序这里再兜底一次 return list(set(patterns))这段代码里start_idx参数就是去重的关键它保证后续选取的长度不小于当前选取的天然排除了顺序重复。1e-9是浮点误差容差长度用小数时必须有否则0.10.2这类精度问题会让你漏掉合法组合。3.2 第二步把组合翻译成整数规划模型枚举出组合后建模就顺理成章了。设组合集合为 P第 j 个组合中长度 i 出现的次数记为 a_ij决策变量 x_j 表示第 j 个组合使用几次非负整数需求长度 i 的订单量为 d_i。模型如下目标最小化 Σ x_j即总原料根数最少等价于废料最少因为原料总长固定。约束对每种长度 iΣ_j a_ij · x_j ≥ d_i即切出的数量不少于订单。变量x_j ∈ 非负整数。这里有个容易被忽略的点约束用的是“≥”而不是“”。因为整数规划下很难刚好切出精确数量多切出来的部分作为库存或备用是合理的。如果你的业务要求严格等于订单量多切算浪费那就得改成“”但很可能无解需要放宽。实际排产中“≥”是主流多出的几根短料通常不亏。用 Python 的 PuLP 库实现代码量很小import pulp def solve_cutting(stock_len, demands, patterns): prob pulp.LpProblem(cutting, pulp.LpMinimize) x [pulp.LpVariable(fx_{j}, lowBound0, catInteger) for j in range(len(patterns))] prob pulp.lpSum(x) # 目标原料根数最少 for length, qty in demands: prob pulp.lpSum( patterns[j].count(length) * x[j] for j in range(len(patterns)) ) qty prob.solve(pulp.PULP_CBC_CMD(msg0)) return [(patterns[j], int(x[j].value())) for j in range(len(patterns)) if x[j].value() 0]solve_cutting返回的就是每种组合用几根原料。拿第 2.1 节那个例子跑一遍你会看到求解器给出的方案废料明显低于贪心这就是全局优化的价值。3.3 第三步结果校验与方案输出求解器返回结果后千万别直接拿去车间用必须做一轮校验。校验至少包含三项一是每种需求长度的实际切出量是否满足订单二是每根原料上各段长度之和是否不超过原料长度防止枚举或浮点误差导致的非法组合三是总废料长度是否与理论值吻合。这三项用几行代码就能算但能挡住绝大多数“模型对、数据错”的事故。方案输出也有讲究。给车间看的排料单不能只写“组合 A 用 5 根”而要写成“第 1 到 5 根原料每根切 1.11.10.6余 0.2 米”让工人一眼能照着切。我习惯把结果整理成表格每行一根原料列出切割序列和余料末尾汇总总根数、总废料、利用率。利用率这个指标业务方最爱看算法算得再好利用率上不去照样被质疑。4. 实操中的坑与排查这些经验文档里没有4.1 组合爆炸导致求解卡死怎么办规格种类一多枚举出的组合数会指数级增长。我遇到过 30 种规格、原料 6 米的场景组合数直接冲到十几万PuLP 建模阶段就卡住求解更是遥遥无期。这时候有几个递进的应对手段。第一招是剪枝枚举时如果当前剩余长度已经小于最短需求长度立即停止如果某种组合的废料超过原料长度的某个比例比如 30%直接丢弃因为这种组合几乎不可能出现在最优解里。这一招通常能砍掉一半以上的组合。第二招是合并相同长度的需求减少规格种类数。很多订单里存在长度相同但批次不同的需求合并后种类数下降组合数随之骤减。第三招才是上列生成。列生成的实现要点是主问题用当前组合子集求线性松弛拿到每种长度约束的对偶价格子问题用这些对偶价格做背包找出“减少成本最多”的新组合把新组合加进主问题再迭代。这套流程实现起来要一两百行调试周期长所以放在最后考虑。实测下来前两招能解决八成以上的规模问题别急着上重武器。4.2 浮点长度带来的隐蔽错误钢管长度用小数表示时浮点误差是头号隐形杀手。0.1 0.2 ! 0.3这个经典问题在枚举和约束校验里都会冒出来明明剩余 0.3 米程序判断 0.3 0.3 为真于是漏掉一个合法组合或者约束校验时切出量算成 9.999999 根判定不满足订单 10 根。解决办法有两个一是全程用整数把米换算成毫米这是最稳的强烈推荐二是如果必须用小数所有比较都带容差如a b 1e-9并且结果校验时对数量做四舍五入。我个人的习惯是一律转成整数毫米。原料 3000 毫米需求 1200、800、500 毫米全程整数运算浮点问题彻底消失代码还更快。这个转换在数据入口做一次就行输出时再换回米成本极低收益极大。4.3 求解结果“看起来对但业务不认”的排查有时候模型跑出的方案数学上最优车间却拒绝执行原因往往在模型没考虑的隐性约束。常见的有三类一是切割次数限制某些设备一刀下去有最小间隔一根原料上切太多段不现实二是锯缝损耗每切一刀会损耗几毫米规格多时累计起来不可忽略三是优先级某些订单必须优先满足不能为了省料牺牲交期。排查这类问题的思路是先拿被拒的方案和车间老师傅的排法对比找出差异点再判断差异是否对应某个未建模的约束。锯缝损耗最容易补枚举时把每次切割的长度加上锯缝宽度即可切割次数限制可以在枚举时限制递归深度优先级则要在约束里加权重或分层求解。这些补充都不难难的是你得先意识到它们存在——这也是为什么排料系统上线前一定要让一线人员试用他们的直觉能帮你发现模型盲区。常见问题典型表现排查方向解决手段组合爆炸建模或求解卡死统计组合数量剪枝、合并规格、列生成浮点误差漏组合、校验误判检查小数比较处转整数毫米、加容差方案被拒数学最优但不可执行对比老师傅排法补锯缝、限切割次数、加优先级无可行解求解器报 infeasible检查约束是否过严约束改 ≥、放宽订单5. 从能跑到好用让排料方案真正落地5.1 把算法包成业务能用的工具算法跑通只是起点真正产生价值得让它变成车间能用的东西。最轻量的做法是写一个命令行脚本输入订单表格CSV 即可输出排料单表格工艺员双击就能跑。再进一步可以做成带界面的小工具输入框填原料长度和需求点按钮出结果这对不熟悉命令行的用户友好得多。如果嵌进现有生产管理系统就把求解逻辑封装成一个服务接口前端传订单、后端返回方案注意加超时保护求解超过设定时间就返回当前最优可行解别让页面一直转圈。我在封装时踩过一个坑求解器默认可能跑很久业务方等不及就重复点击导致任务堆积。后来加了任务队列和结果缓存相同订单直接返回上次结果体验立刻顺了。这类工程细节不影响算法正确性但直接决定工具能不能被用起来。5.2 余料再利用的扩展思路主线模型把余料全算废料实际车间往往会把较长的余料收起来下次用。要支持这个思路是把“余料”也当成一种特殊需求参与后续排料本次排料产生的余料长度和数量记录下来下次排料时作为“免费原料”优先消耗。实现上可以在目标函数里给余料加一个折扣系数或者在约束里优先满足余料匹配。这个扩展会让模型从单次优化变成多批次滚动优化复杂度上升但对长期用料成本的影响很实在值得有余料管理需求的场景投入。5.3 一个可复用的验证清单每次改完模型或数据我都会过一遍这个清单几分钟的事能省掉大量返工订单总量和切出总量是否对得上每根原料的切割序列之和是否不超原料长总原料根数乘以原料长减去总需求长是否等于总废料利用率是否在合理区间通常 90% 以上算好方案里有没有明显违背车间常识的组合。这份清单看着朴素但它是算法结果和车间现实之间的最后一道闸门别省。我个人在实际操作中的体会是钢管切割问题难的不是数学数学部分几十行代码就写完了难的是把车间的真实约束一条条挖出来、翻译进模型再让方案以工人看得懂的形式呈现。算法是骨架业务理解才是血肉。后续如果要做多原料长度可选、多批次滚动排料骨架不用动往约束和目标里加东西就行这也是先吃透单一原料主线的好处——地基打牢了往上盖什么都稳。
阅读完成 · 觉得有帮助？
