1. 项目概述与问题拆解最近在整理过往的竞赛资料翻到了2022年研究生数学建模竞赛B题“方形件组批优化问题”的解题笔记。这个题目当时让不少队伍“又爱又恨”爱的是它问题背景清晰来自实际的板材切割行业恨的是它规模大、约束多想拿高分对建模和编程能力都是不小的考验。题目核心是解决一个典型的二维排样与生产组批联合优化问题给定一系列不同尺寸的方形订单件需要将它们安排到更大尺寸的方形原材料板上进行切割同时还要决定这些订单分成几个批次来生产。目标很明确就是在满足所有订单需求的前提下让总的生产成本主要是原材料成本和与批次相关的固定成本降到最低。这本质上是一个NP-hard的组合优化问题涉及到整数规划、几何约束和复杂的逻辑判断。今天我就结合当时的解题思路和后续的一些思考把这个问题的核心解法、代码实现中的关键技巧以及那些容易踩的“坑”系统地梳理一遍希望能给正在备战数模竞赛或者对运筹优化感兴趣的朋友们一些实实在在的参考。2. 问题核心与数学模型构建2.1 问题要素与难点分析拿到题目第一步永远是彻底理解问题。B题给出了几个关键输入首先是N种方形订单件每种有长、宽、需求数量三个属性其次是标准尺寸的方形原材料板最后是生产成本结构包括每块板材的单价和每个生产批次的固定启动成本。输出则是两个决策一是每个订单件具体被分配到哪块板材、在板材上的什么位置坐标进行切割二是这些板材被划分成几个生产批次。这里的核心难点在于耦合。它不是一个简单的排样问题也不是一个简单的批次划分问题而是两者的交织。排样约束所有放在同一块板材上的订单件其轮廓不能重叠且必须完全位于板材边界内。对于方形件这相对简化了重叠判断只需比较坐标和边长但搜索空间依然巨大。批次约束一个批次包含若干块板材同一批次内的所有板材共享一次固定启动成本。批次划分会影响成本计算而板材上订单件的组合方式又决定了需要多少块板材进而影响批次的构成。目标冲突从排样角度我们希望尽可能提高单张板材的利用率套裁减少板材使用数量以降低材料成本。但从批次角度板材数量减少可能导致批次数量变化进而影响固定成本。材料成本和固定成本之间存在一个需要权衡的trade-off。因此一个高效的模型必须能同时处理几何放置和逻辑分组。直接暴力搜索所有可能的排样和批次组合在计算上是不可行的必须借助严格的数学规划和巧妙的启发式策略。2.2 混合整数线性规划模型构建我们当时采用的混合整数线性规划模型是解决此类问题的经典框架。下面我详细拆解模型的每一个部分并解释为什么这样设计。1. 决策变量定义这是模型的基石设计的好坏直接关系到模型的规模和可解性。x_{i,k}0-1变量。表示订单件i是否被分配到了板材k上。这是最核心的分配变量。y_k0-1变量。表示板材k是否被使用。用于计算板材成本。z_s0-1变量。表示批次s是否被启用。用于计算批次固定成本。u_{k,s}0-1变量。表示板材k是否归属于批次s。用于连接板材和批次。p_{i,k}, q_{i,k}连续变量。表示订单件i在板材k上的左下角x坐标和y坐标。注意这里有一个关键的建模技巧即对板材和批次进行“预编号”。我们预先假设一个足够大的板材数量上限K和一个批次数量上限S。例如K可以设为所有订单件总面积除以板材面积的一个宽松上界S可以设为K最坏情况每板一个批次。在实际求解中y_k和z_s为0的项即表示未被使用。这种方法避免了变量数量动态变化带来的建模困难。2. 目标函数最小化总成本 材料成本 批次固定成本。Minimize: C_m * Σ_{k} y_k C_s * Σ_{s} z_s其中C_m是单板材料成本C_s是单批次固定成本。目标函数清晰地将两部分成本结合起来。3. 约束条件这是模型最精妙也最复杂的地方。需求满足约束每个订单件i必须被生产恰好d_i需求数量次。Σ_{k} x_{i,k} d_i, ∀i。这确保了所有订单都被完成。板材使用逻辑约束如果任何订单件被分配到板材k则该板材必须被标记为使用。x_{i,k} ≤ y_k, ∀i,k。反之如果板材k未被使用(y_k0)则不能有任何订单件分配给它。Σ_{i} x_{i,k} ≤ M * y_k其中M是一个大常数Big-M可以取订单件种类数N。批次逻辑约束类似地如果任何板材被分配到批次s则该批次必须被启用。u_{k,s} ≤ z_s, ∀k,s。且每块被使用的板材必须属于且仅属于一个批次。Σ_{s} u_{k,s} y_k, ∀k。几何不重叠约束核心难点对于方形件判断两个件i和j在板材k上是否重叠可以通过经典的**“四位置”约束**或称“分离约束”来线性化。对于任意两个可能被同时放在板材k上的订单件(i, j)必须满足以下四个不等式至少一个成立p_{i,k} w_i ≤ p_{j,k}i在j的左边p_{j,k} w_j ≤ p_{i,k}i在j的右边q_{i,k} h_i ≤ q_{j,k}i在j的下边q_{j,k} h_j ≤ q_{i,k}i在j的上边 其中w_i, h_i是件i的宽和高。为了将其转化为线性约束需要引入辅助0-1变量b_{ij,k}^1, b_{ij,k}^2, b_{ij,k}^3, b_{ij,k}^4分别对应上述四个位置关系是否成立。然后构建约束p_{i,k} w_i ≤ p_{j,k} M*(1 - b_{ij,k}^1)p_{j,k} w_j ≤ p_{i,k} M*(1 - b_{ij,k}^2)q_{i,k} h_i ≤ q_{j,k} M*(1 - b_{ij,k}^3)q_{j,k} h_j ≤ q_{i,k} M*(1 - b_{ij,k}^4)b_{ij,k}^1 b_{ij,k}^2 b_{ij,k}^3 b_{ij,k}^4 ≥ x_{i,k} x_{j,k} - 1最后一个约束意味着如果件i和件j都被分配到了板材k即x_{i,k}1且x_{j,k}1那么至少有一个位置关系必须成立即至少一个b变量为1从而强制两者不重叠。这个技巧是处理矩形排样线性化的关键。边界约束每个订单件在板材上的位置必须保证其完全在板材内。0 ≤ p_{i,k} ≤ W - w_i和0 ≤ q_{i,k} ≤ L - h_i其中W和L是板材的宽和长。同时这些约束需要和分配变量关联p_{i,k} ≤ M * x_{i,k}q_{i,k} ≤ M * x_{i,k}确保只有当件i被分配到板材k时其位置变量才可能非零。变量域约束定义所有变量的类型和范围。这个完整的MILP模型可以直接丢给Gurobi、CPLEX等商业求解器求解。但对于大规模问题变量和约束数量会爆炸式增长尤其是两两不重叠约束数量级为O(N²*K)直接求解可能非常耗时甚至不可行。因此我们通常需要结合启发式方法或分解策略。3. 求解策略精确与启发式方法结合面对大规模实例纯MILP求解器可能力不从心。我们的策略是采用**“先排样后组批”的两阶段启发式算法**并用MILP模型来优化关键子问题或验证小规模问题。3.1 两阶段启发式算法框架第一阶段高利用率排样生成目标不考虑批次只专注于生成尽可能少的、利用率高的板材排样方案。订单件预处理将所有订单件按面积从大到小排序。大件优先放置通常能获得更好的利用率。采用启发式排样算法我们选择了最低水平线算法Bottom-Left, BL的变种。其核心思想是每次放置一个件时都将其移动到当前板材“轮廓线”上尽可能靠下、靠左的位置。对于方形件可以简化为寻找当前已放置件形成的“天空线”中的最低点。多板材管理采用“顺序填充”策略。从第一块板材开始用BL算法尝试放入排序后的订单件队列。如果当前板材放不下下一个件则开启一块新板材。为了提高全局利用率可以引入贪心重排当一块板材填充到一定程度后例如利用率超过85%暂停对其的放置将剩余未放件尝试与其他板材的剩余空间进行匹配或者启动新的板材避免在低利用率空间上浪费小件。输出此阶段结束后我们得到了一系列板材排样方案以及每块板材上的订单件构成列表。假设生成了K块板材。第二阶段板材聚类组批目标将K块板材划分到若干个批次中以最小化总成本C_m * K C_s * S其中S是批次数量。此时材料成本C_m * K已是定值因为板材数量和构成已固定。问题简化为如何将K个已确定的“物品”板材分成若干组批次以最小化C_s * S。这本质上是一个聚类问题但有一个重要特性批次内的板材无需任何顺序或距离度量只需计数。显然最优策略是尽可能将板材塞进同一个批次直到受到某些隐含约束题目未明说但实际生产可能有的如批次总生产时间上限、同一批次板材必须连续生产等的限制。如果题目没有额外约束那么最优解就是将所有板材放入一个批次从而使S1总成本C_m * K C_s。然而实际问题往往存在隐含约束。例如一个批次的总订单处理量可能有上限或者生产设备有换型时间限制。如果存在这样的约束问题就变成了一个带容量约束的装箱问题每个批次有一个最大“容量”如总板材面积、总零件种类数等我们需要用最少的批次箱子装下所有板材物品。这可以用贪心算法如首次适应递减法FFD快速求解。3.2 关键技巧与代码实现片段这里分享一些在实现上述算法时提高效率和结果质量的关键技巧。技巧1排样算法的“间隙”合并与利用在BL算法中维护一个“可用位置”列表很重要。每当放置一个方形件后会产生新的潜在放置点通常是新件的右上角。我们需要检查这些新点是否被其他已放置件阻挡并合并那些在同一水平线上相邻或重叠的间隙。这能有效减少无效的搜索点加速算法。def find_best_position(item_width, item_height, skyline): skyline: 一个列表每个元素是一个元组 (x_left, x_right, y_height) 表示一段水平线段从x_left到x_right高度为y_height。 best_x, best_y float(inf), float(inf) best_fit float(inf) # 用“浪费空间”或“放置后的最高点”来评估 for i, (x_l, x_r, y_h) in enumerate(skyline): # 尝试将物品的左下角放在(x_l, y_h) if x_l item_width 板材宽度 and y_h item_height 板材长度: # 计算放置后物品右侧上方的轮廓影响 # 这是一个简化计算实际需要更新skyline并评估新轮廓的“平整度” new_max_height y_h item_height # ... 更复杂的评估逻辑可能涉及检查右侧空间 ... if new_max_height best_fit: # 示例选择使总高度增加最小的位置 best_fit new_max_height best_x, best_y x_l, y_h # 也可以尝试其他位置比如在间隙中间放置 return best_x, best_y, best_fit技巧2基于MILP的局部优化当两阶段启发式算法得到一个较好的解后我们可以将其作为初始解提供给MILP求解器并设置一个较短的时间限制让求解器进行局部搜索Local Search或修复优化。例如固定批次分配关系只优化某几个板材内部的排样或者固定排样方案重新优化批次划分。MILP求解器在有好起点的情况下往往能在短时间内找到质量更高的改进解。技巧3对称性破缺在MILP模型中板材和批次都是预先编号的这会导致大量的对称解例如交换两个未被使用的板材编号解不变但变量取值不同从而大大增加求解器的搜索空间。可以添加对称性破缺约束来加速。例如板材按使用顺序强制编号y_k ≥ y_{k1}。这意味着如果板材k1被使用那么板材k也必须被使用。这强制了使用的板材编号是连续的。批次按启用顺序强制编号z_s ≥ z_{s1}。原理同上。 这些约束能显著缩小搜索空间是提升大规模MILP求解速度的实用技巧。4. 模型求解与结果分析实战4.1 求解环境与工具链我们当时的求解环境如下建模语言Python PuLP或Pyomo。Python生态丰富PuLP接口简单易于快速原型开发。对于更复杂、规模更大的模型可以考虑使用Gurobi的Python API直接建模以获得更好的性能。求解器Gurobi Optimizer。它在处理MILP问题上性能卓越特别是提供了强大的启发式策略和切割平面生成能力。对于学术用途可以申请免费的教育许可证。辅助计算NumPy, Pandas。用于数据处理、输入输出和结果分析。可视化Matplotlib。用于绘制最终的排样图直观展示优化结果这在论文中是非常有力的呈现方式。工作流程是用Python脚本读取订单数据根据问题规模选择是直接调用MILP模型求解还是启动两阶段启发式算法。对于启发式算法得到的结果可以输出排样坐标和批次信息并生成可视化图表。同时将关键结果如板材使用数、批次数、总成本、计算时间记录下来用于对比分析。4.2 一个简化案例的求解过程假设一个简化案例板材尺寸10x10成本C_m100,C_s50。有3种订单件 A: 4x4, 需求2个 B: 3x6, 需求2个 C: 2x2, 需求4个。第一阶段排样按面积排序A(16), B(18), C(4)。注意B面积18A面积16使用BL算法放置板材1放置B1左下角(0,0)。剩余空间轮廓复杂。尝试放置A1可以放在B1右侧(3,0)或上方(0,6)。根据BL规则选择(0,6)。放置后剩余空间是“L”型。放置B2可以放在(4,0)或(0,9)等。选择(4,0)。此时板材1已放置B1, A1, B2。剩余空间零散很难放下另一个A或C。利用率(181618)/(100)52%。重新评估这个利用率不高。更好的策略可能是优先放两个A件。让我们换一种思路板材1放置A1(0,0), A2(4,0)。剩余一个6x10的长条。放置B1(0,4), B2(3,4)。此时板材1放置了A1, A2, B1, B2利用率(16161818)/10068%。剩余C件4个2x2。板材2专门放置C件。2x2的小件可以轻松排列。10x10的板可以放5x525个2x2件放4个绰绰有余。利用率(4*4)/10016%。第一阶段结果使用2块板材。板材1方案确定板材2方案确定。第二阶段组批总板材数K2。如果没有批次容量约束最优解是S1一个批次。总成本 2100 150 250。 如果存在批次容量约束例如一个批次最多处理板材总面积为120那么2块板材总面积200120必须分成2个批次。总成本2100250300。MILP验证对于这个小规模案例可以直接构建完整的MILP模型变量和约束数不多用Gurobi求解。可以验证在无批次约束下最优解确实是总成本250且排样方案可能与我们的启发式结果不同可能找到利用率高于68%的单板排样从而只用1块板1个批次成本150。这正体现了精确解法的价值。4.3 结果分析与可视化得到解之后关键的分析步骤包括成本构成分析计算材料成本和固定成本的占比。如果固定成本C_s很高那么算法会倾向于减少批次即使这意味着单板利用率略有下降。反之如果材料成本C_m很高则应极力追求高利用率排样。利用率分析计算每块板材的利用率已放置件总面积/板材面积并分析整体平均利用率。低利用率板材是潜在的优化重点。敏感性分析高级改变关键参数如订单需求、成本比例观察解的变化。这能帮助理解模型的稳健性和成本结构的影响。可视化用不同颜色和边框绘制每块板材上所有订单件的排布图。将属于同一批次的板材用相同背景色或框线标注。一张清晰的排样图胜过千言万语。import matplotlib.pyplot as plt import matplotlib.patches as patches def draw_plate(plate_data, plate_id, batch_id): fig, ax plt.subplots(1, figsize(8,8)) ax.set_xlim(0, plate_width) ax.set_ylim(0, plate_length) ax.set_title(fPlate {plate_id} (Batch {batch_id})) ax.set_aspect(equal) # plate_data 是一个列表每个元素是 (item_id, x, y, w, h) for item in plate_data: rect patches.Rectangle((item[1], item[2]), item[3], item[4], linewidth1, edgecolorblack, facecolorlightblue, alpha0.7) ax.add_patch(rect) # 在矩形中心添加文本标签 ax.text(item[1]item[3]/2, item[2]item[4]/2, str(item[0]), hacenter, vacenter, fontsize8) plt.grid(True, linestyle--, alpha0.5) plt.show()5. 常见问题、调试技巧与进阶思考5.1 典型问题与排查求解器无可行解检查约束矛盾最常见的是几何约束或边界约束过紧。检查订单件尺寸是否有可能大于板材尺寸。检查不重叠约束的Big-M值是否设置得过小。检查需求约束确保Σ x_{i,k} d_i而不是≤。约束更严格。放松约束调试可以先注释掉不重叠约束看模型是否可行。然后逐步添加约束定位导致不可行的具体约束。求解时间过长调整求解器参数设置MIPGap允许的优化间隙为一个合理的值如0.01或0.005而不是追求绝对的0。设置时间限制。提供初始可行解将启发式算法得到的解作为MIPStart输入给求解器能极大加速求解过程。简化模型对于大规模问题考虑使用分解算法如先求解排样松弛忽略部分几何约束再逐步修复。利用对称性破缺如前所述添加板材和批次的顺序约束。启发式算法结果不理想改变放置顺序尝试多种排序规则面积降序、宽度降序、最长边降序、随机排序多次运行取最优。引入随机性在BL算法中当有多个最佳位置评估值相同时随机选择一个而不是总是选第一个。运行算法多次取最好结果。结合局部搜索在得到初始排样后对单块板材内的件进行交换、旋转方形件旋转无意义但其他形状可考虑、重排尝试提高利用率。5.2 进阶优化方向考虑切割工艺约束实际问题中可能有“一刀切”或“两阶段切割”等工艺限制这需要引入切割线连续性的约束模型会变得更加复杂可能需要用网络流或模式生成的方法。动态订单与滚动优化如果订单是陆续到达的问题就变成了在线优化或滚动时域优化需要设计能快速响应的启发式规则。与生产调度集成组批优化后每个批次内的板材还有加工顺序问题可以与车间调度问题结合目标是最小化最大完工时间Makespan等。机器学习辅助可以用历史数据训练模型预测哪些订单件组合在一起容易产生高利用率排样从而指导初始的聚类或排序。回过头看2022年这道B题是一个非常好的运筹学实践案例它把经典的二维排样问题和组合优化中的组批问题巧妙地结合在一起。在实际编程求解时最大的体会是没有“银弹”。纯MILP保证最优但受限于规模纯启发式速度快但质量可能不稳定。将两者结合用启发式快速获得优质初始解再用MILP进行精细化的局部改进往往是应对复杂优化问题的有效路径。在代码实现上清晰的模块化设计至关重要把数据读取、模型构建、算法执行、结果输出和可视化分开这样调试和尝试不同算法变体都会方便很多。最后可视化不仅是论文的加分项更是检验算法结果是否合理、发现潜在bug的利器一张图有时能瞬间揭示出逻辑上的疏漏。