C#实现一维下料优化：贪心、动态规划与多策略寻优

简介面向制造业与物料管理场景的c#一维优化下料源码解决给定多种长度需求件与有限长条原料时如何最小化浪费的切割方案问题。源码围绕需求件类、原料类、切割策略、输出结果与界面展示等模块展开切割策略覆盖贪心、动态规划、线性规划等多种优化思路并额外包含整数规划、材料定义等相关算法实现便于对照学习。压缩包共24个文件以9个.cs主程序为骨架另有4个txt说明文档、2个resx资源文件及sln/csproj工程配置文件整体仅34KB结构紧凑便于快速浏览与二次开发。已有2938人学习下载。通过研读该源码可理解一维下料优化算法的代码落地方式掌握在.NET环境下使用LINQ、WinForms等构建实用生产计划工具的完整思路适合从事生产计划、物料管理的开发者参考、定制与扩展。1. 一维优化下料是什么一次型材切割场景里的优化问题车间里最常见的画面是这么一幕一堆 6 米定尺的铝型材堆在角落手边是几十种不同长度的零件需求排料的人拿着一份 Excel 表格来回凑凑到最后发现每种材料都剩下一截 40 厘米左右的尾巴越凑越乱。所谓一维优化下料就是把长度各异的零件需求排到固定长度的原材料上让消耗的原料根数最少、剩余废料最少。这个问题的数学本质是组合优化放在 C# 里实现就是要写一个能自动生成切割方案的排料引擎。一维下料的技术难点不在“能切出来”而在“切得省”。同样一组需求手工排料可能消耗 120 根原料算法排料可能只要 112 根差出来的 8 根就是真金白银。本文面向两类读者一类是工厂里做型材、管材、线缆切割软件开发的工程师想在自己的系统里嵌入排料模块另一类是正在研究下料问题的学生需要一个能跑、能改、能验证的 C# 基线实现。接下来的内容全部围绕一份可复现的源码思路展开从建模、算法、参数到踩坑一次讲透。2. 一维下料建模长度、数量、刀缝怎么用 C# 表示2.1 问题的数学表达目标函数与约束条件一维下料问题的标准描述是给定一种固定长度的原材料比如 6000mm给定 n 种零件的长度和需求数量求一个切割方案使得消耗的原材料根数最少。每根原材料上可以放置多种零件组合但所有零件长度之和加上切割刀缝损耗不能超过原材料长度。这个问题的决策变量是“每种切割模式使用多少次”目标是最小化使用根数约束是每种零件的产出数量不低于需求数量。这个问题是典型的 NP-hard 问题零件种类一多、数量一大穷举根本不可能。现场常见的做法是把问题拆成两层来解外层决定“用哪几种切割模式”内层决定“每种模式用几根原料”。C# 实现时外层通常用贪心加迭代搜索内层用动态规划或者整数规划。建模的第一步不是写算法而是先把长度、数量、刀缝这些物理量在代码里表示清楚表示错了后面全错。2.2 C# 数据结构设计零件、切割模式与解决方案我习惯把长度统一用 int 表示单位是毫米。不要用 double原因在避坑章节会详细讲。下面是一组最基础的数据结构直接复制到你的项目里就能用。// 零件需求名称、长度、需求数量 public class DemandItem { public string Name { get; set; } // 零件名称如 L-1200 public int LengthMm { get; set; } // 零件长度单位 mm public int Quantity { get; set; } // 需求数量 } // 切割模式一根原料上切哪些零件 public class CutPattern { public ListCutPatternEntry Entries { get; set; } new(); // 零件总长度不含刀缝 public int TotalPartLength Entries.Sum(e e.LengthMm * e.Count); // 当前模式的总使用长度 零件总长 刀缝 × (总件数 - 1) public int TotalUsedLength(int kerfMm) TotalPartLength kerfMm * (Entries.Sum(e e.Count) - 1); // 余料长度 public int WasteLength(int stockLength, int kerfMm) stockLength - TotalUsedLength(kerfMm); } public class CutPatternEntry { public string Name { get; set; } public int LengthMm { get; set; } public int Count { get; set; } }TotalUsedLength 方法是整段代码最容易出错的地方。刀缝只产生在相邻零件之间如果一根原料上只切一根零件不需要切刀刀缝是 0如果切了 3 根零件只需要切 2 刀刀缝是 2 × kerfMm。所以计算总使用长度时必须先算出总零件件数再减 1 得到切口数量。很多初版源码在这里直接乘以件数导致排料表看起来不超长现场一切就发现最后一段长度不够这就是典型的建模错误。2.3 输入数据准备从 CSV 到内存对象的完整流程实际生产中的数据不会以对象形式存在通常是一张 Excel 表或者 ERP 导出的 CSV。读取这一步很简单但有一个关键动作同长度的零件必须合并数量。如果同一长度分多行输入算法会把它们当成不同种类组合搜索时爆炸性增长。public static ListDemandItem LoadDemands(string csvPath) { var demands File.ReadAllLines(csvPath) .Skip(1) // 跳过表头 .Where(line !string.IsNullOrWhiteSpace(line)) .Select(line line.Split(,)) .Select(cols new DemandItem { Name cols[0].Trim(), LengthMm int.Parse(cols[1].Trim()), Quantity int.Parse(cols[2].Trim()) }) .GroupBy(d d.LengthMm) // 相同长度合并 .Select(g new DemandItem { Name g.First().Name, LengthMm g.Key, Quantity g.Sum(d d.Quantity) }) .OrderByDescending(d d.LengthMm) .ToList(); return demands; }这段代码有两个参数值得注意。第一个是 GroupBy 按长度合并合并后名称取第一行的实际使用时如果同长度不同名称有工艺差异合并会丢信息这种场景要改成按“长度 名称”分组。第二个是 OrderByDescending把最长零件排在最前面这是后续贪心算法的输入顺序基础。CSV 的格式约定为每行三列名称、长度、数量长度必须写整数毫米带小数会直接 Parse 报错这也算一道格式校验。3. 贪心算法与动态规划C# 实现最小原料根数的核心代码3.1 降序贪心FFD先排大料再塞小料的最快方案贪心算法是下料问题里最容易理解、也最快出结果的基线方案。FFDFirst Fit Decreasing的做法是先把所有零件按长度降序排列然后逐个尝试放入已有的原料中如果所有已打开的原料都放不下就新开一根原料。这个算法在绝大多数场景下能在毫秒级给出一个可用方案缺点是根数往往比最优解多 5% 到 10%。public static ListCutPattern GreedyCut( ListDemandItem demands, int stockLength, int kerfMm) { // 展开成单个零件按长度降序 var pieces new List(string Name, int Length)(); foreach (var d in demands) for (int i 0; i d.Quantity; i) pieces.Add((d.Name, d.LengthMm)); pieces pieces.OrderByDescending(p p.Length).ToList(); var patterns new ListCutPattern(); foreach (var piece in pieces) { bool placed false; // 尝试放进已有的每一根原料 for (int i 0; i patterns.Count; i) { var p patterns[i]; int currentCount p.Entries.Sum(e e.Count); int addKerf currentCount 0 ? 0 : kerfMm; if (p.TotalUsedLength(kerfMm) piece.Length addKerf stockLength) { p.Entries.Add(new CutPatternEntry { Name piece.Name, LengthMm piece.Length, Count 1 }); placed true; break; } } if (!placed) { var newPattern new CutPattern(); newPattern.Entries.Add(new CutPatternEntry { Name piece.Name, LengthMm piece.Length, Count 1 }); patterns.Add(newPattern); } } return patterns; }这段代码的关键在 addKerf 的计算当前模式已经切了 currentCount 个零件再塞入一个新零件切口数量从 currentCount - 1 变成 currentCount所以多消耗一刀 kerfMm。如果当前模式是空的加第一根零件不需要刀缝addKerf 为 0。FFD 的贪心选择是“放得下就放”它不考虑放哪个零件能留出更规整的余料所以余料的形状很随机这也为第 4 章的逐根寻优留出了优化空间。3.2 单根原料最优切割模式用 0-1 背包思路找组合贪心的短板在于“短视”。要逼近最优解核心是解决一个子问题给定剩余需求在容量 stockLength 内选哪些零件放同一根原料能让这根原料的零件总长度最大。这就是背包问题。为了处理刀缝这里有个很实用的建模技巧把每个零件的重量定义为 Length kerf把背包容量定义为 stockLength kerf价值仍用原始长度。这样总重量约束自然变成 sum(Length) kerf × n stock kerf等价于 sum(Length) kerf × (n - 1) stock数学上完全对齐。public static CutPattern? BestPatternForStock( ListDemandItem remaining, int stockLength, int kerfMm) { int capacity stockLength kerfMm; // 把每个零件的多个数量展开成单件物品重量 长度 刀缝价值 长度 var items new List(int Weight, int Value, string Name, int Length)(); foreach (var d in remaining) { for (int i 0; i d.Quantity; i) { items.Add((d.LengthMm kerfMm, d.LengthMm, d.Name, d.LengthMm)); } } var dp new int[capacity 1]; var chosen new bool[items.Count, capacity 1]; // 0-1 背包外层遍历物品内层逆序遍历容量 for (int i 0; i items.Count; i) { var (w, v, _, _) items[i]; for (int c capacity; c w; c--) { if (dp[c - w] v dp[c]) { dp[c] dp[c - w] v; chosen[i, c] true; } } } // 找最优容量位置不一定装满 int bestCap 0; for (int c 0; c capacity; c) if (dp[c] dp[bestCap]) bestCap c; // 回溯出具体选中的零件 var result new ListCutPatternEntry(); int cur bestCap; for (int i items.Count - 1; i 0 cur 0; i--) { if (cur items[i].Weight chosen[i, cur]) { result.Add(new CutPatternEntry { Name items[i].Name, LengthMm items[i].Length, Count 1 }); cur - items[i].Weight; } } if (result.Count 0) return null; var pattern new CutPattern(); pattern.Entries.AddRange(result.GroupBy(e e.Name).Select(g new CutPatternEntry { Name g.Key, LengthMm g.First().LengthMm, Count g.Count() })); return pattern; }这个实现有几个值得说清的地方。第一chosen 数组是二维的空间复杂度 O(物品数 × 容量) 容量是几千、物品是几百时问题不大如果零件量上万就要换成路径压缩版本。第二回溯时从最后一个物品往前扫这是一种可行的 0-1 背包路径还原前提是更新 chosen 时只在严格更优时置位否则会出现“选了但并非最优”的误判。第三返回的模式会按名称合并条目方便后续扣减库存时一次性更新。3.3 逐根寻优把单根最优组合变成整体方案有了单根最优模式生成器整体求解就变成一个循环每轮调用 BestPatternForStock 找当前剩余需求下的最优单根模式扣减数量继续下一轮。这种做法叫“顺序启发式”虽然每一根都是当前局面的最优整体却不一定全局最优但结果通常显著优于纯贪心。public static ListCutPattern SolveBySequential( ListDemandItem demands, int stockLength, int kerfMm) { var remaining demands .Select(d new DemandItem { Name d.Name, LengthMm d.LengthMm, Quantity d.Quantity }) .ToList(); var patterns new ListCutPattern(); int guard 0; while (remaining.Any(d d.Quantity 0)) { // 防止不可解数据造成死循环 if (guard 100000) throw new Exception(超过迭代上限检查输入数据); var pattern BestPatternForStock(remaining, stockLength, kerfMm); if (pattern null) throw new Exception($剩余零件长度超过原料长度: {remaining.First(d d.Quantity 0).Name}); // 扣减需求 foreach (var e in pattern.Entries) { var item remaining.First(d d.Name e.Name); item.Quantity - e.Count; } patterns.Add(pattern); } return patterns; }这里的 guard 变量是防御性编程。现场数据经常有异常比如某个零件长度写成了 6001mm比原料还长DP 永远选不出包含它的合法模式循环就会卡死。抛出一个带零件名称的异常排料人员一眼就能定位是哪个数据录错了。另一个容易忽略的点是 remaining 必须深拷贝不能直接修改调用方的 demands 列表否则一次求解后输入数据就被污染了。4. 从“能切”到“切得省”逐根寻优的进阶策略与参数调优4.1 为什么单根最优不等于全局最优顺序效应逐根寻优有个隐藏问题先处理哪根料会决定后面剩下什么需求。比如有 3000mm 和 4000mm 两种零件原料 6000mm如果第一根料选了 4000 2000剩下全是 3000第二根只能切一根 3000余料 3000浪费巨大。如果第一根选 3000 3000第二根选 4000两根料全部切完余料为 0。单根最优算法每次看到 4000 和 3000 同时存在时倾向于选 4000 2000 这种高利用率组合但 2000 可能只有一个用完 2000 之后 3000 就变得孤零零的。这就是顺序效应。解决顺序效应的常见手段是“换顺序重跑”。不改变算法本身只改变输入顺序多次求解取根数最少的那组。实现上可以准备几种固定的排序策略按长度降序、按长度升序、按数量降序、按“长度 × 数量”降序甚至加一个随机顺序作为扰动项。多跑几次的成本很低但收益往往很明显。4.2 多策略竞拍用排序策略池压低原料根数我一般会写一个外层调度器把第 3 章的 SolveBySequential 当成黑匣子用不同的排序方式调用它最后取根数最少的方案。这个思路比去改内部算法简单得多配合并行还能进一步提速。public static ListCutPattern SolveByMultiStrategy( ListDemandItem demands, int stockLength, int kerfMm) { ListCutPattern? best null; // 策略池降序 / 升序 / 数量优先 / 随机扰动 var strategies new ListFuncListDemandItem, ListDemandItem() { list list.OrderByDescending(d d.LengthMm).ToList(), list list.OrderBy(d d.LengthMm).ToList(), list list.OrderByDescending(d d.Quantity).ThenByDescending(d d.LengthMm).ToList(), list list.OrderBy(d Guid.NewGuid()).ToList() }; foreach (var strategy in strategies) { var orderedDemands strategy(demands); var solution SolveBySequential(orderedDemands, stockLength, kerfMm); if (best null || solution.Count best.Count) best solution; } return best ?? new ListCutPattern(); }这里最值得玩味的是随机扰动策略。Guid.NewGuid 的排序没有固定种子每次运行结果都不同但它存在的意义恰恰是引入随机性让顺序效应产生不同走向。如果时间允许可以在循环里跑 20 次随机排序记录历史最优。实测中这种“无脑重跑”的方式经常能压过精心设计的启发式规则因为下料问题局部最优解太多多试几次本身就是最朴素的搜索。这个方案的参数只有一个策略数量和随机次数。策略越多耗时越长但根数改善幅度会迅速收敛一般 5 到 8 个策略就够用了。4.3 剪枝参数最大迭代次数与最小改善阈值如果需求规模特别大比如几十种零件、总件数上万逐根寻优的求解时间会变得不可接受。这时候需要给算法加两个开关最大迭代次数和最小改善阈值。前者限制整个求解最多跑几轮后者控制“根数没有明显改善就提前停止”。public static ListCutPattern SolveWithTimeLimit( ListDemandItem demands, int stockLength, int kerfMm, int maxIterations 50, double minImproveRate 0.001) { ListCutPattern? best null; int bestCount int.MaxValue; for (int iter 0; iter maxIterations; iter) { // 每次迭代用不同随机种子达到类似扰动的效果 var rnd new Random(iter); var sorted demands.OrderBy(d rnd.Next()).ToList(); var solution SolveBySequential(sorted, stockLength, kerfMm); if (solution.Count bestCount) { double improveRate (bestCount - solution.Count) / (double)bestCount; best solution; bestCount solution.Count; // 改善幅度小于阈值提前终止 if (improveRate minImproveRate iter 10) break; } } return best ?? new ListCutPattern(); }这段代码引入了两个可调参数。maxIterations 控制的是随机重排的最大次数设置太大会浪费时间在无意义的重复搜索上太小又可能错过后面的好解常见取值在 20 到 100 之间。minImproveRate 的意义是如果最近一次改善只让根数减少了不到 0.1%再往下跑大概率也差不多就可以收手了。注意这里的 improveRate 计算用 bestCount 作分母当 bestCount 很大时改善率天然很小需要注意阈值合理性。生产环境里我更推荐把时间上限作为第一约束比如“最多跑 5 秒取这 5 秒里的历史最优”这样排料人员在现场不会等得着急。5. 一维下料源码的避坑指南精度、刀缝与性能三条红线5.1 浮点精度0.1 0.2 不等于 0.3 的经典翻车现象用 double 存长度排料表显示余料 0.3mm实际现场一切最后一段短了 0.1mm零件报废。原因二进制无法精确表示 0.1 和 0.2累加后误差会传到余料判断上。最要命的是“总长度 原料长度”这个比较浮点误差可能在边界处把不可行方案判成可行。解决统一用整数。最常见的做法是全部按毫米整数存储如果有 0.1mm 精度的需求就整体乘以 10用“十分之一毫米”作为最小单位。// 错误写法double 累加导致余料误判 double length 0.1; double sum 0.0; for (int i 0; i 3; i) sum length; // sum 0.30000000000000004 // 正确写法读取时立即转整数 public static int ToIntMm(double lengthMm) { return (int)Math.Round(lengthMm * 10); // 以 0.1mm 为单位 }这条规则要贯彻到读取、计算、写入三个环节。只要某个环节出现 double误差就会趁虚而入。现场还有更隐蔽的情况Excel 单元格里看起来是整数但单元格格式带小数位导出来就变成了 100.0000001 这种值Parse 之前一定要做四舍五入。5.2 刀缝损耗排料表看着不超长实际切不出来现象算法输出的切割方案零件总长刚好等于原料长度余料显示 0拉到现场切切到最后一刀时发现型材不够长了。原因排料方案里没有计入刀缝。两根零件之间要切一刀锯片本身的宽度就是损耗3mm 的锯片切 20 刀就是 60mm足以让原本刚好卡满的方案超长。解决如第 2 章所述在 TotalUsedLength 中计入刀缝切口数等于零件件数减 1。但要注意一个细节如果一根料上所有零件长度相同有些切法可以用“并排多根一起切”来减少刀数这种工艺优化属于更高级的排样问题标准源码里不处理但至少要留一个 kerfMm 的全局参数供现场调整。检查超长逻辑必须用带刀缝的总使用长度不能用零件净长。5.3 零件合并导致方案不可行名称一样但工艺不同的坑现象算法排出的方案里某个模式放入了 3 个名为“L-1200”的零件但现场这种零件有两种表面处理颜色不能混在同一个模式里切。原因输入数据只按长度合并忽略了零件的工艺属性。第 2 章的 LoadDemands 里 GroupBy 是按 LengthMm 合并的这是为了减少组合数量但同时也抹掉了工艺差异。解决合并规则改为“长度 工艺属性”组合。如果系统里零件带材质、颜色、表面处理等字段分组键就应该是这些字段的组合。合并后打印方案时模式条目要能追溯到原始零件编号否则现场没法领料。5.4 巨大数量导致性能雪崩展开成单件不是免费的现象需求表里某个零件数量写了 5000 件BestPatternForStock 里展开单件后 items 列表暴涨DP 数组和 chosen 二维数组的内存直接溢出。原因展开成单件做 0-1 背包物品数等于需求总量当需求总量上万时DP 的计算量是 物品数 × 容量轻松破亿次操作内存同样爆炸。解决对同长度同工艺的零件不要展开成单件而是用多重背包的二进制拆分法把 5000 件拆成若干个“代表 1、2、4、8… 件”的组组数从 5000 降到十几个。// 二进制拆分把数量拆成 1,2,4,8... 与剩余部分 public static List(int Count, string Name, int Length) ExpandByBinary(int quantity) { var result new List(int, string, int)(); int k 1; while (quantity 0) { int take Math.Min(k, quantity); result.Add((take, , 0)); quantity - take; k 1; } return result; }这个片段只演示了拆分逻辑实际接入 DP 时每个“组”作为一个物品重量 Count × (Length kerf)价值 Count × Length。这样 5000 件同长度零件只产生约 13 个物品性能差异是数量级的。注意二进制拆分只适用于同长度同工艺的零件不同长度之间不能混组。6. 验证算法正确性从随机压测到现场数据回放的技巧写代码的人最怕的不是算法慢而是算法错了但是没发现。下料问题的错误往往藏在“刚好卡满”和“超长 1mm”这种边界上。我习惯在交付排料模块时额外写一个验证函数对每一组输出方案做两件事检查每根料的带刀缝总使用长度是否小于等于原料长度检查所有模式的零件产出总量是否满足需求数量且没有多余。验证函数本身不难写难的是找充分的测试数据。随机压测是第一步用 Random 生成几百组随机需求每组都跑一次求解和验证只要有一组不通过就说明算法有 bug。public static bool ValidateSolution( ListCutPattern solution, ListDemandItem originalDemands, int stockLength, int kerfMm) { // 检查每根料不超长 foreach (var p in solution) { if (p.TotalUsedLength(kerfMm) stockLength) return false; } // 统计产出对比需求 var produced solution .SelectMany(p p.Entries) .GroupBy(e e.Name) .ToDictionary(g g.Key, g g.Sum(e e.Count)); foreach (var d in originalDemands) { if (!produced.ContainsKey(d.Name) || produced[d.Name] d.Quantity) return false; } return true; }随机压测跑完之后更重要的验证是“现场数据回放”把过去三个月手工排料的真实需求拿出来让算法重新排一遍对比根数差异。这个环节最能打动现场的人因为用的是他们的真实数据结果里每一根料都能回推。回放时如果发现算法排出的某根料只有一根 300mm 的短料余料 5700mm这种方案虽然合法但明显不合理通常是需求里存在某种“长零件”导致短零件只能靠后处理这时就要考虑调整策略池的排序规则。我个人的习惯是把所有验证函数写进一个独立的测试工程跑完随机压测后保留历史最优方案方便后续改了算法做对比回归。排序策略池从 4 个扩到 8 个时根数可能只少了一根但耗时翻倍值不值得做要以真实数据为准别盲目堆策略。做一维下料优化算法只占一半另一半是在跟数据、现场工艺和边界打交道。把精度、刀缝、性能这三条红线守住你的 C# 源码才真正敢交给车间用。希望帮到你。本文还有配套的精品资源点击获取