1. 项目概述从一道赛题到一套完整的解决方案最近在整理过往的竞赛资料翻到了去年带队参加数维杯国际赛时关于D题“洗衣房清洁计算”的完整解题论文和程序代码。这道题当时在圈内讨论度挺高因为它完美地结合了经典的运筹优化思想和实际的生活场景没有特别偏门的理论但非常考验对问题的建模能力和求解工具的熟练度。简单来说题目模拟了一个大学或公寓社区的公共洗衣房你有若干台不同容量、不同能耗、不同运行时间的洗衣机每天有若干批学生带着不同脏污程度、不同紧急程度的衣物前来。你需要设计一个调度方案决定哪批衣物在哪台洗衣机、什么时间开始清洗目标是在满足所有衣物都被清洗的前提下最小化总能耗或者总等待时间具体看题目设定。这本质上是一个带复杂约束的资源调度与排程问题。对于刚接触数学建模的同学这道题是个绝佳的练手材料。它不像一些纯理论题那样抽象你能立刻想象出洗衣房人满为患的场景同时它的求解又需要你动用到线性规划、整数规划、甚至是动态规划或启发式算法等“硬核”工具。我当时的团队用Python和MATLAB双线作战最终构建了一个混合整数线性规划模型并用Gurobi求解器得到了不错的结果。今天我就把这道题的解题全流程包括问题分析、模型建立、算法实现附核心代码以及我们踩过的那些坑毫无保留地分享出来。无论你是正在备战数维杯、美赛、国赛还是单纯对运筹优化感兴趣相信这篇长文都能给你带来直接的帮助。2. 问题核心拆解把洗衣房问题翻译成数学语言面对一个数学建模问题第一步也是最关键的一步就是抛开具体场景抽象出核心的数学元素。我们得先搞清楚题目到底给了我们什么又要我们输出什么。2.1 输入与输出定义首先我们明确一下题目中的“角色”洗衣机有M台。每台洗衣机i有其固有属性最大容量比如10公斤、单次运行的标准耗时比如45分钟、单次运行的标准能耗比如1.5度电。有些题目还会考虑洗衣机的类型如快洗、标准洗、大件洗。洗衣任务有N批。每批任务j代表一个学生或一个宿舍的一筐衣服也有其属性衣物重量必须小于等于洗衣机的容量、脏污等级可能影响清洗时间、最晚完成时间或期望完成时间。时间通常以离散的时间片为单位比如以15分钟或30分钟为一个间隔。我们假设一天从早上8点开始到晚上10点结束总共T个时间片。我们的目标是生成一个调度方案。这个方案需要明确指定每批任务j被分配到哪台洗衣机i以及在哪个时间片t开始清洗。方案必须满足所有物理和逻辑约束并优化某个目标函数最常见的是总能耗最小或平均等待时间最短。2.2 关键约束条件分析模型之所以复杂就在于这些约束。我们必须把它们无一遗漏地用数学等式或不等式表达出来容量约束任务j的重量必须小于等于其分配到的洗衣机i的容量。时间唯一性约束一台洗衣机在同一时间只能执行一个任务。这是排程问题的核心。任务完整性约束每个任务必须被完成且只能被完成一次。时间窗约束任务必须在最晚完成时间之前结束。开始时间 清洗耗时 最晚完成时间。顺序约束如果一个任务在某个洗衣机上开始它必须连续占用该洗衣机若干个时间片等于其清洗耗时期间不能被中断或插入其他任务。启动能耗有些模型会考虑洗衣机启动时的额外能耗这会让问题更复杂接近带设置时间的调度问题。2.3 模型选择为什么我们选了混合整数线性规划面对这个问题常见的建模思路有好几种动态规划如果任务数量N很少且时间片T不多理论上可以用DP求解。状态可以定义为“在时间t各洗衣机的占用状态以及已完成的任务集合”。但“维数灾难”会使其在稍大规模下就变得不可行。M台洗衣机、N个任务的状态空间会爆炸。启发式算法如遗传算法、模拟退火。这类方法适合快速得到一个“还不错”的解特别适用于比赛后期对模型进行改进和求近似最优解。但作为主模型其解的质量和理论保证性不如精确算法。整数规划/混合整数线性规划这是我们最终选择的方法。它的优势在于能够精确、严谨地描述所有约束并且利用成熟的商业或开源求解器如Gurobi, CPLEX找到全局最优解对于中小规模问题。虽然计算复杂度高但对于数维杯这类规模适中的赛题在合理时间内求最优解是可行的。我们的思路是定义0-1决策变量x[i,j,t]其值为1当且仅当任务j在洗衣机i上于时间t开始清洗。这样所有约束都可以转化为关于x[i,j,t]的线性表达式。目标函数总能耗也是这些变量的线性组合。这就构成了一个MILP模型。这个模型的建立过程是整篇论文的基石。注意在比赛中清晰地将上述思考过程写在论文的“模型假设与建立”部分至关重要。评审专家首先看的就是你的问题转化能力。3. 混合整数线性规划模型构建详解下面我们来把这个思路具体化。我会给出关键的数学公式并解释每一个公式的由来。3.1 集合与参数定义首先我们定义模型的基础集合:I: 所有洗衣机的集合i ∈ I。J: 所有洗衣任务的集合j ∈ J。T: 所有时间片的集合t ∈ T。参数:Cap[i]: 洗衣机i的最大容量。Weight[j]: 任务j的衣物重量。Duration[j]: 任务j所需的清洗时间片数可能根据脏污等级调整。Energy[i]: 洗衣机i运行一个时间片的能耗。Deadline[j]: 任务j的最晚完成时间片索引。M: 一个很大的正数Big-M方法中常用。3.2 决策变量这是模型的核心x[i,j,t] ∈ {0, 1}: 二元变量。1 表示任务j在洗衣机i上于时间t开始清洗。可选C[j]: 连续变量表示任务j的完成时间。有时为了表达时间窗约束更方便。3.3 目标函数假设我们的目标是最小化总能耗。总能耗等于每台洗衣机运行的时间片数乘以它的单位能耗。一个任务一旦开始就会连续运行Duration[j]个时间片。Minimize Z Σ_{i∈I} Σ_{j∈J} Σ_{t∈T} (Energy[i] * Duration[j] * x[i,j,t])这个求和意味着遍历所有洗衣机、所有任务、所有可能的开始时间。如果x[i,j,t]1那么这项任务的能耗Energy[i] * Duration[j]就会被计入总能耗。3.4 约束条件数学表达每个任务必须被分配且仅被分配一次Σ_{i∈I} Σ_{t∈T} x[i,j,t] 1, ∀ j ∈ J对于任意一个任务j所有洗衣机、所有可能开始时间对应的决策变量加起来必须等于1保证了有且仅有一个开始方案。容量约束Weight[j] Cap[i] M*(1 - x[i,j,t]), ∀ i∈I, j∈J, t∈T这是一个使用Big-M技巧的约束。它的逻辑是如果x[i,j,t]1即任务j真的被分配给了洗衣机i那么不等式右边的大M项为0约束简化为Weight[j] Cap[i]即必须满足容量要求。如果x[i,j,t]0那么右边会加上一个巨大的M这个约束自动成立因为Weight[j]不可能大于Cap[i]M相当于失效。这样就优雅地将逻辑判断转化为了线性不等式。洗衣机同一时间片最多处理一个任务防重叠 这是最复杂的约束之一。对于一台给定的洗衣机i和一个给定的时间片τ我们要确保在这个时间片τ内最多只有一个任务正在运行。 一个任务j如果在时间t开始它会占用时间片[t, tDuration[j]-1]。因此对于洗衣机i和时间片τ所有满足“开始时间t τ”且“结束时间 tDuration[j]-1 τ”的任务j它们的x[i,j,t]加起来不能超过1。Σ_{j∈J} Σ_{t: t τ tDuration[j]-1} x[i,j,t] 1, ∀ i∈I, τ∈T在编程实现时我们需要用循环来生成这个约束。任务时间窗约束 任务j必须在Deadline[j]之前完成。Σ_{i∈I} Σ_{t∈T} (t Duration[j] - 1) * x[i,j,t] Deadline[j], ∀ j ∈ J左边计算的是任务j的实际完成时间开始时间耗时-1它必须小于等于最晚完成时间。变量域约束x[i,j,t] ∈ {0, 1}实操心得在写论文时不仅要列出这些公式最好能用一两句话解释每个约束的物理意义和数学上的表达技巧比如Big-M。这能极大提升模型的可读性和专业性。另外注意检查约束的索引范围避免出现“时间片溢出”的错误例如tDuration[j]-1不能超过总时间T。4. 算法实现Python与MATLAB双核心代码解析模型建立后下一步就是求解。我们使用了Python的PuLP库调用Gurobi求解器和MATLAB的Optimization Toolbox进行实现和对比验证。这里分享最核心的Python实现部分。4.1 Python实现基于PuLP和Gurobi首先确保安装pulp库和Gurobi求解器学术版免费。pip install pulpGurobi需要从其官网下载并安装获取学术许可import pulp import numpy as np def solve_laundry_scheduling(num_machines, num_jobs, time_slots, capacities, weights, durations, energies, deadlines): 求解洗衣房调度问题 参数: num_machines (int): 洗衣机数量 M num_jobs (int): 任务数量 N time_slots (int): 时间片数量 T capacities (list): 每个洗衣机的容量 [Cap1, Cap2, ...] weights (list): 每个任务的重量 [W1, W2, ...] durations (list): 每个任务耗时 [D1, D2, ...] energies (list): 每个洗衣机单位时间能耗 [E1, E2, ...] deadlines (list): 每个任务最晚完成时间 [L1, L2, ...] # 创建问题实例使用Gurobi作为求解器 prob pulp.LpProblem(Laundry_Scheduling_MinEnergy, pulp.LpMinimize) # 1. 创建决策变量字典 x pulp.LpVariable.dicts(x, ((i, j, t) for i in range(num_machines) for j in range(num_jobs) for t in range(time_slots - durations[j] 1)), # 开始时间不能太晚要保证能洗完 lowBound0, upBound1, catBinary) # 2. 设置目标函数总能耗最小 prob pulp.lpSum([energies[i] * durations[j] * x[i, j, t] for i in range(num_machines) for j in range(num_jobs) for t in range(time_slots - durations[j] 1)]) # 3. 添加约束 # 3.1 每个任务必须被分配一次 for j in range(num_jobs): prob pulp.lpSum([x[i, j, t] for i in range(num_machines) for t in range(time_slots - durations[j] 1)]) 1, fAssign_Task_{j} # 3.2 容量约束 (使用Big-M这里M取一个较大的值如100) M 100 for i in range(num_machines): for j in range(num_jobs): for t in range(time_slots - durations[j] 1): prob weights[j] capacities[i] M * (1 - x[i, j, t]), fCapacity_M{i}_J{j}_T{t} # 3.3 洗衣机防重叠约束关键且计算量较大 for i in range(num_machines): for tau in range(time_slots): # 对于每一个时间片tau # 找出所有可能在这个时间片tau占用洗衣机i的任务-开始时间组合 sum_vars [] for j in range(num_jobs): for t in range(max(0, tau - durations[j] 1), min(time_slots - durations[j] 1, tau 1)): # 条件t tau t durations[j] - 1 # 即开始时间t在 [tau - durations[j] 1, tau] 区间内 if t tau and tau t durations[j] - 1: sum_vars.append(x[i, j, t]) if sum_vars: # 避免添加空约束 prob pulp.lpSum(sum_vars) 1, fNoOverlap_M{i}_T{tau} # 3.4 时间窗约束 for j in range(num_jobs): prob pulp.lpSum([(t durations[j] - 1) * x[i, j, t] for i in range(num_machines) for t in range(time_slots - durations[j] 1)]) deadlines[j], fDeadline_Task_{j} # 4. 求解问题 # 指定使用Gurobi求解器并设置一些参数以加速 solver pulp.GUROBI_CMD(timeLimit300, msgTrue) # 设置5分钟超时并显示求解日志 prob.solve(solver) # 5. 输出结果 print(f求解状态: {pulp.LpStatus[prob.status]}) print(f最小总能耗: {pulp.value(prob.objective)}) schedule [] for i in range(num_machines): for j in range(num_jobs): for t in range(time_slots - durations[j] 1): if pulp.value(x[i, j, t]) 0.5: # 判断变量是否为1考虑浮点误差 schedule.append({ machine: i, job: j, start: t, end: t durations[j] - 1, energy: energies[i] * durations[j] }) print(f任务{j} - 洗衣机{i}, 开始时间片: {t}, 结束时间片: {tdurations[j]-1}) return schedule, pulp.value(prob.objective) # 示例数据调用 if __name__ __main__: M, N, T 3, 5, 20 # 3台洗衣机5个任务20个时间片 capacities [10, 8, 12] weights [4, 7, 9, 5, 6] durations [3, 4, 3, 2, 4] # 每个任务需要的时间片数 energies [1.2, 1.0, 1.5] # 每时间片能耗 deadlines [15, 18, 12, 20, 16] # 最晚完成时间片 schedule, total_energy solve_laundry_scheduling(M, N, T, capacities, weights, durations, energies, deadlines)4.2 MATLAB实现要点在MATLAB中我们可以使用intlinprog函数来求解MILP。步骤类似但需要将模型转化为标准形式min f*x满足A*x b,Aeq*x beq,lb x ub其中部分变量为整数。定义决策变量向量将所有x[i,j,t]按一定顺序如按i、再按j、再按t展开成一个长向量x。构建目标函数向量ff中每个元素对应一个x[i,j,t]其值为Energy[i] * Duration[j]。构建线性约束矩阵A, b, Aeq, beq“每个任务分配一次”是等式约束对应Aeq和beq。“容量约束”和“防重叠约束”是不等式约束对应A和b。构建A矩阵是编码中最繁琐的部分需要仔细处理索引。定义变量上下界和整数约束lb zeros(...),ub ones(...),intcon 1:length(f)表示所有变量都是0-1整数。调用求解器[x, fval, exitflag] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);踩坑记录在MATLAB中构建大型稀疏约束矩阵A时直接使用zeros预分配然后赋值效率极低且容易内存不足。务必使用sparse函数来构建稀疏矩阵。先创建三个数组i_index,j_index,s_values分别存储非零元素的行索引、列索引和值最后用A sparse(i_index, j_index, s_values, num_constraints, num_variables)一次性生成。这是提升MATLAB求解效率的关键。5. 模型求解的优化技巧与实战调参直接求解上述MILP模型对于稍大规模的问题例如20台洗衣机50个任务48个时间片求解时间可能会非常长甚至无法在比赛时间内得到最优解。因此必须采用一些优化技巧。5.1 削减变量与约束缩小搜索空间时间窗剪枝对于任务j它可能的开始时间t必须满足t Duration[j] - 1 Deadline[j]且t 0。因此在创建变量x[i,j,t]时对于每个任务jt的循环范围可以大大缩小而不是0到T-1。这能直接减少变量数量。容量预过滤在创建变量时只对满足Weight[j] Cap[i]的洗衣机i-任务j组合创建变量。不满足容量要求的组合其x[i,j,t]变量根本无需定义。这也能显著减少变量数。对称性破缺如果有多台容量、能耗完全相同的同质洗衣机模型会产生很多对称解增加求解器分支定界的负担。可以添加约束强制要求任务按某种顺序如任务编号优先分配给编号小的洗衣机来打破对称性。例如对于两个相同的洗衣机1和2可以添加约束使得如果任务a分配给洗衣机2那么编号比a小的任务不能全部分配给洗衣机1。这需要巧妙的建模但效果显著。5.2 求解器参数调优以Gurobi为例在PuLP中可以通过字典传递参数solver pulp.GUROBI_CMD(timeLimit300, msgTrue, options[(MIPGap, 0.01), (Threads, 4)])MIPGap: 设置最优间隙。设为0.01表示当找到的解与理论下界的差距在1%以内时可以提前停止。在时间紧迫时用1%或5%的Gap换求解速度是值得的。Threads: 使用的CPU线程数。设置为你的电脑核心数。Heuristics: 启发式算法强度可以调高以更快找到初始可行解。Presolve: 预求解强度通常设为激进Aggressive可以简化模型。5.3 启发式初始解热启动可以先运行一个快速的启发式算法如按任务截止时间升序排序然后贪心地将其分配给当前可用的、能满足容量且能耗较低的洗衣机得到一个可行的调度方案。然后将这个方案转化为决策变量x[i,j,t]的初始赋值传递给求解器。这能为分支定界树提供一个高质量的上界大大加速求解过程。 在PuLP中可以在定义变量后、求解前通过x[i,j,t].setInitialValue(1)来设置初始值。5.4 分阶段求解对于大规模问题可以考虑“分而治之”先分配后排程先建立一个简化的模型只决定“哪个任务分配给哪台洗衣机”忽略具体的时间片。这可以是一个简单的分配问题变量少很多。得到分配方案后再对每台洗衣机上的任务集合分别求解一个单机调度问题这可以用动态规划高效求解。虽然可能损失全局最优性但在可接受时间内能得到优质解。时间聚合如果时间片划分得很细如5分钟一片可以先以更粗的粒度如30分钟一片进行求解得到一个粗略的调度然后再在细粒度上对每个时间段进行微调和优化。个人体会在数学建模比赛中“先求可行再求优化”的策略非常重要。不要一开始就追求完美的全局MILP模型。先用贪心等简单方法快速出一个基础解和结果保证论文有东西可写。然后在此基础上逐步引入更精确的模型和优化作为模型的改进部分。这样论文结构更丰满也更能体现你的思考过程。6. 结果可视化与方案分析求解得到schedule后如何呈现结果同样重要。一个清晰的甘特图Gantt Chart胜过千言万语。6.1 使用Python Matplotlib绘制调度甘特图import matplotlib.pyplot as plt import matplotlib.patches as patches def plot_gantt_chart(schedule, num_machines, total_time_slots): 绘制洗衣机调度甘特图 schedule: 求解函数返回的调度列表每个元素是包含machine,job,start,end的字典 fig, ax plt.subplots(figsize(12, 6)) # 为每个任务分配一个颜色 jobs list(set([s[job] for s in schedule])) colors plt.cm.tab20(np.linspace(0, 1, len(jobs))) job_color_map {job: colors[i] for i, job in enumerate(jobs)} # 绘制每个任务块 for s in schedule: machine_idx s[machine] job_idx s[job] start s[start] duration s[end] - s[start] 1 # 创建一个矩形块 rect patches.Rectangle((start, machine_idx - 0.4), duration, 0.8, linewidth1, edgecolorblack, facecolorjob_color_map[job_idx], alpha0.7) ax.add_patch(rect) # 在块中央添加任务编号 ax.text(start duration/2, machine_idx, fJ{job_idx}, hacenter, vacenter, colorwhite, fontweightbold) # 设置图表属性 ax.set_xlabel(时间片) ax.set_ylabel(洗衣机) ax.set_title(洗衣房调度甘特图) ax.set_yticks(range(num_machines)) ax.set_yticklabels([f洗衣机 {i} for i in range(num_machines)]) ax.set_xlim(0, total_time_slots) ax.set_ylim(-0.5, num_machines - 0.5) ax.grid(axisx, linestyle--, alpha0.7) # 添加图例 from matplotlib.patches import Patch legend_elements [Patch(facecolorjob_color_map[j], labelf任务 {j}) for j in jobs] ax.legend(handleslegend_elements, bbox_to_anchor(1.05, 1), locupper left) plt.tight_layout() plt.show() # 调用绘图函数 plot_gantt_chart(schedule, num_machines3, total_time_slots20)6.2 结果分析与模型验证得到调度方案和甘特图后需要进行分析方案可行性验证人工检查几个关键点是否有任务未分配同一台洗衣机的任务时间是否重叠任务是否在截止时间前完成容量是否满足这是最基本的检验。资源利用率分析计算每台洗衣机的“忙碌时间片 / 总时间片”得到利用率。分析是否存在洗衣机闲置过多而其他洗衣机负载过重的情况。这可以反馈到模型比如如果目标是平衡负载可以在目标函数中加入负载均衡项。灵敏度分析这是论文的加分项。可以探讨如果某个参数变化结果会如何改变。任务量激增如果任务数量N增加20%我们的调度方案是否仍然可行总能耗会增加多少可以通过重新输入数据求解来验证。洗衣机故障模拟一台洗衣机在某个时间段不可用我们的模型能否快速重新调度这体现了模型的鲁棒性。能耗价格变化如果不同时间段的电费不同峰谷电价如何修改模型只需将目标函数中的Energy[i]替换为与开始时间t相关的Energy[i, t]即可。模型对比如果时间允许可以用贪心算法如最早截止时间优先EDD、最短处理时间优先SPT也求一个解对比其总能耗和最优解的差距。这能凸显出你构建的精确模型的优越性。7. 参赛论文写作要点与程序打包最后聊聊如何将以上所有工作整合成一篇优秀的数维杯或任何数学建模比赛论文。7.1 论文结构框架摘要重中之重用300-500字概括整个工作针对什么问题、建立了什么模型、采用了什么算法、得到了什么结果、有何结论与创新。务必精炼、完整、突出亮点。问题重述与分析用自己的话复述题目并进行分析指出问题的难点资源竞争、时间约束、优化目标和本质组合优化、排程问题。模型假设与符号说明列出所有合理的假设如“每个任务一旦开始不能被中断”、“忽略衣物放入取出的时间”。清晰列出所有用到的符号、集合、参数、变量。模型的建立与求解这是核心章节。7.4.1 模型建立详细阐述MILP模型的构建过程包括目标函数和每一个约束条件的数学公式及其解释。7.4.2 求解方法说明使用的求解工具Gurobi/intlinprog以及为了加速求解采用的技巧变量剪枝、启发式初始解等。7.4.3 算法流程可以用流程图描述整体求解步骤。模型求解与结果分析给出针对题目所给数据或自己设计的标准测试数据的求解结果。展示关键数据如总能耗、各洗衣机利用率表格。必须附上甘特图直观展示调度方案。进行灵敏度分析或模型对比分析。模型的评价与推广客观评价模型的优点严谨、最优解和缺点大规模问题求解慢。提出模型的可能改进方向如考虑不确定任务到达时间改用随机规划或在线算法以及在其他场景如车间作业调度、计算资源分配的应用潜力。参考文献规范引用。附录附上核心的程序代码不必全部关键部分即可。7.2 程序代码打包与提交比赛通常要求提交可运行的源代码。环境说明在README.txt中详细说明运行环境Python 3.8 / MATLAB R2020b、所需库PuLP, numpy, matplotlib及版本、如何安装pip install -r requirements.txt。代码结构Laundry_Optimization/ ├── data/ │ └── input_data.xlsx # 输入数据文件 ├── src/ │ ├── model.py # 主要建模与求解函数 │ ├── heuristic.py # 启发式算法用于初始解 │ ├── visualize.py # 结果可视化函数 │ └── main.py # 主程序入口 ├── results/ │ ├── schedule.csv # 输出的调度方案 │ └── gantt_chart.png # 生成的甘特图 ├── requirements.txt # Python依赖库列表 └── README.txt # 项目说明文档数据接口程序最好能从外部文件如Excel、CSV读取输入数据这样测试不同案例时只需修改数据文件无需改动代码。结果输出程序应能将最优调度方案、目标函数值等关键结果输出到文件如CSV或JSON并自动生成可视化图表。7.3 比赛中的时间管理72小时的比赛时间分配至关重要第一天上午团队集中讨论彻底吃透题目确定大方向我们用什么方法。完成问题分析和初步模型构思。第一天下午至晚上开始建模和初步编程。至少要用简单方法贪心跑出一个基础结果。第二天全天完善模型实现精确算法MILP调试代码得到优化结果。开始撰写论文的“模型建立”和“求解”部分。第三天上午进行结果分析、灵敏度分析、绘制图表。完成论文初稿。第三天下午集中精力撰写摘要、修改全文、检查格式、打包代码。摘要一定要反复打磨。最后几小时最终检查提交。这道“洗衣房清洁计算”题从一个生活化的场景引出了一个经典的数学优化问题。通过它我们实践了从问题抽象、模型建立、算法实现、到求解优化的完整数学建模流程。其中关于MILP建模的Big-M技巧、防重叠约束的写法、求解加速的策略以及结果可视化的方法都是可以迁移到无数其他资源调度问题中的宝贵经验。希望这份超详细的拆解能帮助你不仅搞定这道题更能掌握解决一类问题的方法论。在数学建模的路上多动手、多思考、多总结每一个项目都是通向更深入理解的阶梯。 数学建模实战：基于混合整数规划的洗衣房资源调度优化
1. 项目概述从一道赛题到一套完整的解决方案最近在整理过往的竞赛资料翻到了去年带队参加数维杯国际赛时关于D题“洗衣房清洁计算”的完整解题论文和程序代码。这道题当时在圈内讨论度挺高因为它完美地结合了经典的运筹优化思想和实际的生活场景没有特别偏门的理论但非常考验对问题的建模能力和求解工具的熟练度。简单来说题目模拟了一个大学或公寓社区的公共洗衣房你有若干台不同容量、不同能耗、不同运行时间的洗衣机每天有若干批学生带着不同脏污程度、不同紧急程度的衣物前来。你需要设计一个调度方案决定哪批衣物在哪台洗衣机、什么时间开始清洗目标是在满足所有衣物都被清洗的前提下最小化总能耗或者总等待时间具体看题目设定。这本质上是一个带复杂约束的资源调度与排程问题。对于刚接触数学建模的同学这道题是个绝佳的练手材料。它不像一些纯理论题那样抽象你能立刻想象出洗衣房人满为患的场景同时它的求解又需要你动用到线性规划、整数规划、甚至是动态规划或启发式算法等“硬核”工具。我当时的团队用Python和MATLAB双线作战最终构建了一个混合整数线性规划模型并用Gurobi求解器得到了不错的结果。今天我就把这道题的解题全流程包括问题分析、模型建立、算法实现附核心代码以及我们踩过的那些坑毫无保留地分享出来。无论你是正在备战数维杯、美赛、国赛还是单纯对运筹优化感兴趣相信这篇长文都能给你带来直接的帮助。2. 问题核心拆解把洗衣房问题翻译成数学语言面对一个数学建模问题第一步也是最关键的一步就是抛开具体场景抽象出核心的数学元素。我们得先搞清楚题目到底给了我们什么又要我们输出什么。2.1 输入与输出定义首先我们明确一下题目中的“角色”洗衣机有M台。每台洗衣机i有其固有属性最大容量比如10公斤、单次运行的标准耗时比如45分钟、单次运行的标准能耗比如1.5度电。有些题目还会考虑洗衣机的类型如快洗、标准洗、大件洗。洗衣任务有N批。每批任务j代表一个学生或一个宿舍的一筐衣服也有其属性衣物重量必须小于等于洗衣机的容量、脏污等级可能影响清洗时间、最晚完成时间或期望完成时间。时间通常以离散的时间片为单位比如以15分钟或30分钟为一个间隔。我们假设一天从早上8点开始到晚上10点结束总共T个时间片。我们的目标是生成一个调度方案。这个方案需要明确指定每批任务j被分配到哪台洗衣机i以及在哪个时间片t开始清洗。方案必须满足所有物理和逻辑约束并优化某个目标函数最常见的是总能耗最小或平均等待时间最短。2.2 关键约束条件分析模型之所以复杂就在于这些约束。我们必须把它们无一遗漏地用数学等式或不等式表达出来容量约束任务j的重量必须小于等于其分配到的洗衣机i的容量。时间唯一性约束一台洗衣机在同一时间只能执行一个任务。这是排程问题的核心。任务完整性约束每个任务必须被完成且只能被完成一次。时间窗约束任务必须在最晚完成时间之前结束。开始时间 清洗耗时 最晚完成时间。顺序约束如果一个任务在某个洗衣机上开始它必须连续占用该洗衣机若干个时间片等于其清洗耗时期间不能被中断或插入其他任务。启动能耗有些模型会考虑洗衣机启动时的额外能耗这会让问题更复杂接近带设置时间的调度问题。2.3 模型选择为什么我们选了混合整数线性规划面对这个问题常见的建模思路有好几种动态规划如果任务数量N很少且时间片T不多理论上可以用DP求解。状态可以定义为“在时间t各洗衣机的占用状态以及已完成的任务集合”。但“维数灾难”会使其在稍大规模下就变得不可行。M台洗衣机、N个任务的状态空间会爆炸。启发式算法如遗传算法、模拟退火。这类方法适合快速得到一个“还不错”的解特别适用于比赛后期对模型进行改进和求近似最优解。但作为主模型其解的质量和理论保证性不如精确算法。整数规划/混合整数线性规划这是我们最终选择的方法。它的优势在于能够精确、严谨地描述所有约束并且利用成熟的商业或开源求解器如Gurobi, CPLEX找到全局最优解对于中小规模问题。虽然计算复杂度高但对于数维杯这类规模适中的赛题在合理时间内求最优解是可行的。我们的思路是定义0-1决策变量x[i,j,t]其值为1当且仅当任务j在洗衣机i上于时间t开始清洗。这样所有约束都可以转化为关于x[i,j,t]的线性表达式。目标函数总能耗也是这些变量的线性组合。这就构成了一个MILP模型。这个模型的建立过程是整篇论文的基石。注意在比赛中清晰地将上述思考过程写在论文的“模型假设与建立”部分至关重要。评审专家首先看的就是你的问题转化能力。3. 混合整数线性规划模型构建详解下面我们来把这个思路具体化。我会给出关键的数学公式并解释每一个公式的由来。3.1 集合与参数定义首先我们定义模型的基础集合:I: 所有洗衣机的集合i ∈ I。J: 所有洗衣任务的集合j ∈ J。T: 所有时间片的集合t ∈ T。参数:Cap[i]: 洗衣机i的最大容量。Weight[j]: 任务j的衣物重量。Duration[j]: 任务j所需的清洗时间片数可能根据脏污等级调整。Energy[i]: 洗衣机i运行一个时间片的能耗。Deadline[j]: 任务j的最晚完成时间片索引。M: 一个很大的正数Big-M方法中常用。3.2 决策变量这是模型的核心x[i,j,t] ∈ {0, 1}: 二元变量。1 表示任务j在洗衣机i上于时间t开始清洗。可选C[j]: 连续变量表示任务j的完成时间。有时为了表达时间窗约束更方便。3.3 目标函数假设我们的目标是最小化总能耗。总能耗等于每台洗衣机运行的时间片数乘以它的单位能耗。一个任务一旦开始就会连续运行Duration[j]个时间片。Minimize Z Σ_{i∈I} Σ_{j∈J} Σ_{t∈T} (Energy[i] * Duration[j] * x[i,j,t])这个求和意味着遍历所有洗衣机、所有任务、所有可能的开始时间。如果x[i,j,t]1那么这项任务的能耗Energy[i] * Duration[j]就会被计入总能耗。3.4 约束条件数学表达每个任务必须被分配且仅被分配一次Σ_{i∈I} Σ_{t∈T} x[i,j,t] 1, ∀ j ∈ J对于任意一个任务j所有洗衣机、所有可能开始时间对应的决策变量加起来必须等于1保证了有且仅有一个开始方案。容量约束Weight[j] Cap[i] M*(1 - x[i,j,t]), ∀ i∈I, j∈J, t∈T这是一个使用Big-M技巧的约束。它的逻辑是如果x[i,j,t]1即任务j真的被分配给了洗衣机i那么不等式右边的大M项为0约束简化为Weight[j] Cap[i]即必须满足容量要求。如果x[i,j,t]0那么右边会加上一个巨大的M这个约束自动成立因为Weight[j]不可能大于Cap[i]M相当于失效。这样就优雅地将逻辑判断转化为了线性不等式。洗衣机同一时间片最多处理一个任务防重叠 这是最复杂的约束之一。对于一台给定的洗衣机i和一个给定的时间片τ我们要确保在这个时间片τ内最多只有一个任务正在运行。 一个任务j如果在时间t开始它会占用时间片[t, tDuration[j]-1]。因此对于洗衣机i和时间片τ所有满足“开始时间t τ”且“结束时间 tDuration[j]-1 τ”的任务j它们的x[i,j,t]加起来不能超过1。Σ_{j∈J} Σ_{t: t τ tDuration[j]-1} x[i,j,t] 1, ∀ i∈I, τ∈T在编程实现时我们需要用循环来生成这个约束。任务时间窗约束 任务j必须在Deadline[j]之前完成。Σ_{i∈I} Σ_{t∈T} (t Duration[j] - 1) * x[i,j,t] Deadline[j], ∀ j ∈ J左边计算的是任务j的实际完成时间开始时间耗时-1它必须小于等于最晚完成时间。变量域约束x[i,j,t] ∈ {0, 1}实操心得在写论文时不仅要列出这些公式最好能用一两句话解释每个约束的物理意义和数学上的表达技巧比如Big-M。这能极大提升模型的可读性和专业性。另外注意检查约束的索引范围避免出现“时间片溢出”的错误例如tDuration[j]-1不能超过总时间T。4. 算法实现Python与MATLAB双核心代码解析模型建立后下一步就是求解。我们使用了Python的PuLP库调用Gurobi求解器和MATLAB的Optimization Toolbox进行实现和对比验证。这里分享最核心的Python实现部分。4.1 Python实现基于PuLP和Gurobi首先确保安装pulp库和Gurobi求解器学术版免费。pip install pulpGurobi需要从其官网下载并安装获取学术许可import pulp import numpy as np def solve_laundry_scheduling(num_machines, num_jobs, time_slots, capacities, weights, durations, energies, deadlines): 求解洗衣房调度问题 参数: num_machines (int): 洗衣机数量 M num_jobs (int): 任务数量 N time_slots (int): 时间片数量 T capacities (list): 每个洗衣机的容量 [Cap1, Cap2, ...] weights (list): 每个任务的重量 [W1, W2, ...] durations (list): 每个任务耗时 [D1, D2, ...] energies (list): 每个洗衣机单位时间能耗 [E1, E2, ...] deadlines (list): 每个任务最晚完成时间 [L1, L2, ...] # 创建问题实例使用Gurobi作为求解器 prob pulp.LpProblem(Laundry_Scheduling_MinEnergy, pulp.LpMinimize) # 1. 创建决策变量字典 x pulp.LpVariable.dicts(x, ((i, j, t) for i in range(num_machines) for j in range(num_jobs) for t in range(time_slots - durations[j] 1)), # 开始时间不能太晚要保证能洗完 lowBound0, upBound1, catBinary) # 2. 设置目标函数总能耗最小 prob pulp.lpSum([energies[i] * durations[j] * x[i, j, t] for i in range(num_machines) for j in range(num_jobs) for t in range(time_slots - durations[j] 1)]) # 3. 添加约束 # 3.1 每个任务必须被分配一次 for j in range(num_jobs): prob pulp.lpSum([x[i, j, t] for i in range(num_machines) for t in range(time_slots - durations[j] 1)]) 1, fAssign_Task_{j} # 3.2 容量约束 (使用Big-M这里M取一个较大的值如100) M 100 for i in range(num_machines): for j in range(num_jobs): for t in range(time_slots - durations[j] 1): prob weights[j] capacities[i] M * (1 - x[i, j, t]), fCapacity_M{i}_J{j}_T{t} # 3.3 洗衣机防重叠约束关键且计算量较大 for i in range(num_machines): for tau in range(time_slots): # 对于每一个时间片tau # 找出所有可能在这个时间片tau占用洗衣机i的任务-开始时间组合 sum_vars [] for j in range(num_jobs): for t in range(max(0, tau - durations[j] 1), min(time_slots - durations[j] 1, tau 1)): # 条件t tau t durations[j] - 1 # 即开始时间t在 [tau - durations[j] 1, tau] 区间内 if t tau and tau t durations[j] - 1: sum_vars.append(x[i, j, t]) if sum_vars: # 避免添加空约束 prob pulp.lpSum(sum_vars) 1, fNoOverlap_M{i}_T{tau} # 3.4 时间窗约束 for j in range(num_jobs): prob pulp.lpSum([(t durations[j] - 1) * x[i, j, t] for i in range(num_machines) for t in range(time_slots - durations[j] 1)]) deadlines[j], fDeadline_Task_{j} # 4. 求解问题 # 指定使用Gurobi求解器并设置一些参数以加速 solver pulp.GUROBI_CMD(timeLimit300, msgTrue) # 设置5分钟超时并显示求解日志 prob.solve(solver) # 5. 输出结果 print(f求解状态: {pulp.LpStatus[prob.status]}) print(f最小总能耗: {pulp.value(prob.objective)}) schedule [] for i in range(num_machines): for j in range(num_jobs): for t in range(time_slots - durations[j] 1): if pulp.value(x[i, j, t]) 0.5: # 判断变量是否为1考虑浮点误差 schedule.append({ machine: i, job: j, start: t, end: t durations[j] - 1, energy: energies[i] * durations[j] }) print(f任务{j} - 洗衣机{i}, 开始时间片: {t}, 结束时间片: {tdurations[j]-1}) return schedule, pulp.value(prob.objective) # 示例数据调用 if __name__ __main__: M, N, T 3, 5, 20 # 3台洗衣机5个任务20个时间片 capacities [10, 8, 12] weights [4, 7, 9, 5, 6] durations [3, 4, 3, 2, 4] # 每个任务需要的时间片数 energies [1.2, 1.0, 1.5] # 每时间片能耗 deadlines [15, 18, 12, 20, 16] # 最晚完成时间片 schedule, total_energy solve_laundry_scheduling(M, N, T, capacities, weights, durations, energies, deadlines)4.2 MATLAB实现要点在MATLAB中我们可以使用intlinprog函数来求解MILP。步骤类似但需要将模型转化为标准形式min f*x满足A*x b,Aeq*x beq,lb x ub其中部分变量为整数。定义决策变量向量将所有x[i,j,t]按一定顺序如按i、再按j、再按t展开成一个长向量x。构建目标函数向量ff中每个元素对应一个x[i,j,t]其值为Energy[i] * Duration[j]。构建线性约束矩阵A, b, Aeq, beq“每个任务分配一次”是等式约束对应Aeq和beq。“容量约束”和“防重叠约束”是不等式约束对应A和b。构建A矩阵是编码中最繁琐的部分需要仔细处理索引。定义变量上下界和整数约束lb zeros(...),ub ones(...),intcon 1:length(f)表示所有变量都是0-1整数。调用求解器[x, fval, exitflag] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);踩坑记录在MATLAB中构建大型稀疏约束矩阵A时直接使用zeros预分配然后赋值效率极低且容易内存不足。务必使用sparse函数来构建稀疏矩阵。先创建三个数组i_index,j_index,s_values分别存储非零元素的行索引、列索引和值最后用A sparse(i_index, j_index, s_values, num_constraints, num_variables)一次性生成。这是提升MATLAB求解效率的关键。5. 模型求解的优化技巧与实战调参直接求解上述MILP模型对于稍大规模的问题例如20台洗衣机50个任务48个时间片求解时间可能会非常长甚至无法在比赛时间内得到最优解。因此必须采用一些优化技巧。5.1 削减变量与约束缩小搜索空间时间窗剪枝对于任务j它可能的开始时间t必须满足t Duration[j] - 1 Deadline[j]且t 0。因此在创建变量x[i,j,t]时对于每个任务jt的循环范围可以大大缩小而不是0到T-1。这能直接减少变量数量。容量预过滤在创建变量时只对满足Weight[j] Cap[i]的洗衣机i-任务j组合创建变量。不满足容量要求的组合其x[i,j,t]变量根本无需定义。这也能显著减少变量数。对称性破缺如果有多台容量、能耗完全相同的同质洗衣机模型会产生很多对称解增加求解器分支定界的负担。可以添加约束强制要求任务按某种顺序如任务编号优先分配给编号小的洗衣机来打破对称性。例如对于两个相同的洗衣机1和2可以添加约束使得如果任务a分配给洗衣机2那么编号比a小的任务不能全部分配给洗衣机1。这需要巧妙的建模但效果显著。5.2 求解器参数调优以Gurobi为例在PuLP中可以通过字典传递参数solver pulp.GUROBI_CMD(timeLimit300, msgTrue, options[(MIPGap, 0.01), (Threads, 4)])MIPGap: 设置最优间隙。设为0.01表示当找到的解与理论下界的差距在1%以内时可以提前停止。在时间紧迫时用1%或5%的Gap换求解速度是值得的。Threads: 使用的CPU线程数。设置为你的电脑核心数。Heuristics: 启发式算法强度可以调高以更快找到初始可行解。Presolve: 预求解强度通常设为激进Aggressive可以简化模型。5.3 启发式初始解热启动可以先运行一个快速的启发式算法如按任务截止时间升序排序然后贪心地将其分配给当前可用的、能满足容量且能耗较低的洗衣机得到一个可行的调度方案。然后将这个方案转化为决策变量x[i,j,t]的初始赋值传递给求解器。这能为分支定界树提供一个高质量的上界大大加速求解过程。 在PuLP中可以在定义变量后、求解前通过x[i,j,t].setInitialValue(1)来设置初始值。5.4 分阶段求解对于大规模问题可以考虑“分而治之”先分配后排程先建立一个简化的模型只决定“哪个任务分配给哪台洗衣机”忽略具体的时间片。这可以是一个简单的分配问题变量少很多。得到分配方案后再对每台洗衣机上的任务集合分别求解一个单机调度问题这可以用动态规划高效求解。虽然可能损失全局最优性但在可接受时间内能得到优质解。时间聚合如果时间片划分得很细如5分钟一片可以先以更粗的粒度如30分钟一片进行求解得到一个粗略的调度然后再在细粒度上对每个时间段进行微调和优化。个人体会在数学建模比赛中“先求可行再求优化”的策略非常重要。不要一开始就追求完美的全局MILP模型。先用贪心等简单方法快速出一个基础解和结果保证论文有东西可写。然后在此基础上逐步引入更精确的模型和优化作为模型的改进部分。这样论文结构更丰满也更能体现你的思考过程。6. 结果可视化与方案分析求解得到schedule后如何呈现结果同样重要。一个清晰的甘特图Gantt Chart胜过千言万语。6.1 使用Python Matplotlib绘制调度甘特图import matplotlib.pyplot as plt import matplotlib.patches as patches def plot_gantt_chart(schedule, num_machines, total_time_slots): 绘制洗衣机调度甘特图 schedule: 求解函数返回的调度列表每个元素是包含machine,job,start,end的字典 fig, ax plt.subplots(figsize(12, 6)) # 为每个任务分配一个颜色 jobs list(set([s[job] for s in schedule])) colors plt.cm.tab20(np.linspace(0, 1, len(jobs))) job_color_map {job: colors[i] for i, job in enumerate(jobs)} # 绘制每个任务块 for s in schedule: machine_idx s[machine] job_idx s[job] start s[start] duration s[end] - s[start] 1 # 创建一个矩形块 rect patches.Rectangle((start, machine_idx - 0.4), duration, 0.8, linewidth1, edgecolorblack, facecolorjob_color_map[job_idx], alpha0.7) ax.add_patch(rect) # 在块中央添加任务编号 ax.text(start duration/2, machine_idx, fJ{job_idx}, hacenter, vacenter, colorwhite, fontweightbold) # 设置图表属性 ax.set_xlabel(时间片) ax.set_ylabel(洗衣机) ax.set_title(洗衣房调度甘特图) ax.set_yticks(range(num_machines)) ax.set_yticklabels([f洗衣机 {i} for i in range(num_machines)]) ax.set_xlim(0, total_time_slots) ax.set_ylim(-0.5, num_machines - 0.5) ax.grid(axisx, linestyle--, alpha0.7) # 添加图例 from matplotlib.patches import Patch legend_elements [Patch(facecolorjob_color_map[j], labelf任务 {j}) for j in jobs] ax.legend(handleslegend_elements, bbox_to_anchor(1.05, 1), locupper left) plt.tight_layout() plt.show() # 调用绘图函数 plot_gantt_chart(schedule, num_machines3, total_time_slots20)6.2 结果分析与模型验证得到调度方案和甘特图后需要进行分析方案可行性验证人工检查几个关键点是否有任务未分配同一台洗衣机的任务时间是否重叠任务是否在截止时间前完成容量是否满足这是最基本的检验。资源利用率分析计算每台洗衣机的“忙碌时间片 / 总时间片”得到利用率。分析是否存在洗衣机闲置过多而其他洗衣机负载过重的情况。这可以反馈到模型比如如果目标是平衡负载可以在目标函数中加入负载均衡项。灵敏度分析这是论文的加分项。可以探讨如果某个参数变化结果会如何改变。任务量激增如果任务数量N增加20%我们的调度方案是否仍然可行总能耗会增加多少可以通过重新输入数据求解来验证。洗衣机故障模拟一台洗衣机在某个时间段不可用我们的模型能否快速重新调度这体现了模型的鲁棒性。能耗价格变化如果不同时间段的电费不同峰谷电价如何修改模型只需将目标函数中的Energy[i]替换为与开始时间t相关的Energy[i, t]即可。模型对比如果时间允许可以用贪心算法如最早截止时间优先EDD、最短处理时间优先SPT也求一个解对比其总能耗和最优解的差距。这能凸显出你构建的精确模型的优越性。7. 参赛论文写作要点与程序打包最后聊聊如何将以上所有工作整合成一篇优秀的数维杯或任何数学建模比赛论文。7.1 论文结构框架摘要重中之重用300-500字概括整个工作针对什么问题、建立了什么模型、采用了什么算法、得到了什么结果、有何结论与创新。务必精炼、完整、突出亮点。问题重述与分析用自己的话复述题目并进行分析指出问题的难点资源竞争、时间约束、优化目标和本质组合优化、排程问题。模型假设与符号说明列出所有合理的假设如“每个任务一旦开始不能被中断”、“忽略衣物放入取出的时间”。清晰列出所有用到的符号、集合、参数、变量。模型的建立与求解这是核心章节。7.4.1 模型建立详细阐述MILP模型的构建过程包括目标函数和每一个约束条件的数学公式及其解释。7.4.2 求解方法说明使用的求解工具Gurobi/intlinprog以及为了加速求解采用的技巧变量剪枝、启发式初始解等。7.4.3 算法流程可以用流程图描述整体求解步骤。模型求解与结果分析给出针对题目所给数据或自己设计的标准测试数据的求解结果。展示关键数据如总能耗、各洗衣机利用率表格。必须附上甘特图直观展示调度方案。进行灵敏度分析或模型对比分析。模型的评价与推广客观评价模型的优点严谨、最优解和缺点大规模问题求解慢。提出模型的可能改进方向如考虑不确定任务到达时间改用随机规划或在线算法以及在其他场景如车间作业调度、计算资源分配的应用潜力。参考文献规范引用。附录附上核心的程序代码不必全部关键部分即可。7.2 程序代码打包与提交比赛通常要求提交可运行的源代码。环境说明在README.txt中详细说明运行环境Python 3.8 / MATLAB R2020b、所需库PuLP, numpy, matplotlib及版本、如何安装pip install -r requirements.txt。代码结构Laundry_Optimization/ ├── data/ │ └── input_data.xlsx # 输入数据文件 ├── src/ │ ├── model.py # 主要建模与求解函数 │ ├── heuristic.py # 启发式算法用于初始解 │ ├── visualize.py # 结果可视化函数 │ └── main.py # 主程序入口 ├── results/ │ ├── schedule.csv # 输出的调度方案 │ └── gantt_chart.png # 生成的甘特图 ├── requirements.txt # Python依赖库列表 └── README.txt # 项目说明文档数据接口程序最好能从外部文件如Excel、CSV读取输入数据这样测试不同案例时只需修改数据文件无需改动代码。结果输出程序应能将最优调度方案、目标函数值等关键结果输出到文件如CSV或JSON并自动生成可视化图表。7.3 比赛中的时间管理72小时的比赛时间分配至关重要第一天上午团队集中讨论彻底吃透题目确定大方向我们用什么方法。完成问题分析和初步模型构思。第一天下午至晚上开始建模和初步编程。至少要用简单方法贪心跑出一个基础结果。第二天全天完善模型实现精确算法MILP调试代码得到优化结果。开始撰写论文的“模型建立”和“求解”部分。第三天上午进行结果分析、灵敏度分析、绘制图表。完成论文初稿。第三天下午集中精力撰写摘要、修改全文、检查格式、打包代码。摘要一定要反复打磨。最后几小时最终检查提交。这道“洗衣房清洁计算”题从一个生活化的场景引出了一个经典的数学优化问题。通过它我们实践了从问题抽象、模型建立、算法实现、到求解优化的完整数学建模流程。其中关于MILP建模的Big-M技巧、防重叠约束的写法、求解加速的策略以及结果可视化的方法都是可以迁移到无数其他资源调度问题中的宝贵经验。希望这份超详细的拆解能帮助你不仅搞定这道题更能掌握解决一类问题的方法论。在数学建模的路上多动手、多思考、多总结每一个项目都是通向更深入理解的阶梯。