1. 从“家政服务”到“数学建模”一个被低估的实战场景最近在整理一些过往的数学建模案例时翻到了一个关于“家政服务”的题目。很多人第一反应可能是家政服务不就是找阿姨、做保洁吗这跟数学建模有什么关系恰恰是这种看似日常、接地气的场景背后隐藏着非常典型的运筹优化问题比如人员排班、路径规划、资源调度这些都是运筹学里的经典模型。而题目里提到的“lingo求解”更是直接点明了解决这类问题的核心工具——一个在学术界和工业界都备受推崇的优化求解器。我之所以想把这个案例拿出来详细拆解是因为它完美地诠释了如何将一个现实生活中的模糊需求转化为一个清晰的数学模型并最终通过专业的工具得到最优解。这个过程远比单纯学会用lingo敲几行代码更重要。它考验的是你定义问题的能力、抽象建模的思维以及将数学结果翻译回业务语言的本事。无论你是正在备战数学建模竞赛的学生还是工作中需要处理排班、调度问题的从业者这个从“家政服务”切入的案例都能给你带来一套完整、可复现的方法论。很多人一听到“优化”、“建模”就觉得头大感觉是数学家才玩的东西。其实不然它的内核非常朴素在有限的资源比如阿姨的数量、时间下如何安排任务比如去哪些客户家、做什么服务才能让总体效益比如收入最高、成本最低、客户满意度最好达到最优。接下来我就以这个“家政服务1”的题目为引子带大家走一遍完整的流程从问题分析、模型建立到lingo求解和结果分析最后还会分享几个我踩过的坑和总结的实用技巧。2. 问题拆解家政服务背后的优化逻辑是什么拿到一个题目切忌直接上手写公式。第一步永远是理解问题把口语化的描述翻译成数学语言。我们假设这个“家政服务1”的题目大致是这样的某家政公司有若干名服务人员阿姨每天需要为分布在城市不同区域的客户提供保洁服务。每个客户的服务需求时长已知服务人员的工作时间有限且从一位客户家到另一位客户家需要花费一定的交通时间。公司希望合理安排每位服务人员当天的服务路线即按什么顺序去哪些客户家使得在满足所有客户需求的前提下所使用的服务人员总数尽可能少或者总的工作时间、交通成本等尽可能低。这短短几句话其实包含了优化问题的几个核心要素2.1 决策变量我们到底要决定什么这是建模的起点。在这个场景里我们要做的决策就是派哪位服务人员去哪位客户那里以及如果一位服务人员要服务多个客户这些客户的访问顺序是什么通常我们会定义一种叫做“0-1决策变量”的东西。例如定义 \(x_{ijk} 1\) 表示服务人员k从客户i的位置前往客户j的位置进行服务否则为0。同时可能还需要辅助变量来记录服务人员k是否被启用以及客户i被服务的开始时间等。2.2 目标函数我们要朝哪个方向优化题目中说“使得…尽可能少/低”这就是目标。常见的优化目标有最小化总成本可能包括人员工资、车辆油耗等。最小化总工作时间让所有阿姨加起来干的时间最短。最小化使用人数用最少的阿姨完成所有任务这对控制固定成本很有意义。最大化客户满意度比如尽可能在客户期望的时间段内上门。在初版模型中我们通常先选择一个最核心、最容易量化的目标比如“最小化所需服务人员总数”。复杂的多目标问题可以后续再进阶。2.3 约束条件必须遵守哪些规矩现实世界没有无限的自由优化必须在条条框框里进行每个客户必须被服务且仅被服务一次不能漏掉客户也不能一个客户被两个阿姨重复服务。服务人员的工作时长上限一个阿姨每天最多工作8小时这包括了交通时间和实际服务时间。服务时间窗有些客户要求必须在上午10点到12点之间上门。路径连续性如果一个阿姨从客户i去了客户j那么她到达j后必须从j再去往下一个客户或返回公司不能“断掉”。容量约束如果阿姨需要携带大型清洁设备那么她的“载重”或“车厢容积”可能有限制。把上面这三要素变量、目标、约束用自然语言理清楚建模就成功了一半。你会发现这本质上是一个经典的车辆路径问题Vehicle Routing Problem, VRP或其变种带时间窗的VRPTW。家政服务场景可以看作是VRP问题中“车辆”换成“阿姨”“货物”换成“服务任务”的一个生动实例。3. 模型建立将业务逻辑转化为数学公式基于上一节的分析我们可以尝试建立一个简化版的模型。我们假设目标是最小化使用的服务人员数量并且暂时忽略服务时间窗只考虑总工作时间限制。3.1 模型假设与符号说明为了让模型可解我们需要先明确一些假设所有服务人员同质技能、效率相同。公司有一个统一的出发和返回点比如公司总部。客户点之间的交通时间是已知且确定的。每位服务人员每天最大工作时间为T例如8小时。每个客户的服务时长是已知的。定义集合和参数\(N\)客户集合客户编号为1, 2, ..., n。\(V \{0\} \cup N\)节点集合其中0代表公司仓库1到n代表客户。\(K\)服务人员集合编号为1, 2, ..., mm是一个足够大的数比如等于客户数n表示最多每人服务一个客户。\(t_{ij}\)从节点i到节点j的交通时间i, j ∈ V。\(s_i\)在客户i处所需的服务时长i ∈ N。\(T_{max}\)每个服务人员最大总工作时间含交通与服务。定义决策变量\(x_{ijk} \in \{0, 1\}\)二进制变量。若服务人员k从节点i前往节点j则为1否则为0i, j ∈ V, k ∈ K。\(y_k \in \{0, 1\}\)二进制变量。若服务人员k被启用即至少服务一个客户则为1否则为0。\(u_{ik}\)辅助变量用于消除子回路防止一个人员的路径形成不包含公司的小循环可以理解为服务人员k访问客户i的顺序号。3.2 数学模型公式目标函数最小化被启用的服务人员总数。 \[ \text{Minimize} \quad Z \sum_{k \in K} y_k \]约束条件每个客户必须被恰好服务一次对于每个客户i必须有一个服务人员k从某个节点可能是公司0或其他客户j过来服务他。 \[ \sum_{j \in V, j \neq i} \sum_{k \in K} x_{ijk} 1, \quad \forall i \in N \]流量平衡服务人员k进入一个客户点也必须离开该点。 \[ \sum_{i \in V, i \neq h} x_{ihk} \sum_{j \in V, j \neq h} x_{hjk}, \quad \forall h \in N, \forall k \in K \]人员启用约束如果服务人员k从公司出发去任何客户点则他必须被启用。 \[ \sum_{j \in N} x_{0jk} \leq y_k, \quad \forall k \in K \] 同时被启用的服务人员必须从公司出发并最终返回公司这两条通常隐含在路径连续性中也可显式写出。工作时间约束每个服务人员k的总时间交通服务不能超过上限。 \[ \sum_{i \in V} \sum_{j \in V, j \neq i} (t_{ij} s_j) \cdot x_{ijk} \leq T_{max}, \quad \forall k \in K \]注意这里\(s_j\)加在弧(i,j)上表示到达j后执行服务。这是一种常见的建模技巧。子回路消除约束这是VRP模型的关键防止解中出现不包含公司0的循环。采用MTZMiller-Tucker-Zemlin约束 \[ u_{ik} - u_{jk} n \cdot x_{ijk} \leq n-1, \quad \forall i, j \in N, i \neq j, \forall k \in K \] \[ 1 \leq u_{ik} \leq n, \quad \forall i \in N, \forall k \in K \]变量域约束 \[ x_{ijk} \in \{0, 1\}, \quad y_k \in \{0, 1\}, \quad u_{ik} \geq 0 \]这个模型已经具备了VRP的基本骨架。当然真实的“家政服务1”题目数据可能更简单或更复杂但建模思路是相通的定义谁去哪、优化什么、遵守什么规则。4. Lingo求解实战从公式到可运行代码模型建立后就到了用工具求解的阶段。Lingo正是处理这类线性、非线性、整数规划问题的利器。它语法相对直观接近数学表达。下面我们看看如何将上面的模型“翻译”成Lingo代码。4.1 数据准备与输入假设我们有4个客户n4最多准备4个服务人员m4。公司为节点0客户为节点1-4。交通时间矩阵 \(t_{ij}\) (小时)从\到01234000.50.80.60.410.500.30.90.720.80.300.50.630.60.90.500.440.40.70.60.40注通常假设 \(t_{ij} t_{ji}\)即对称的服务时长 \(s_i\) (小时): s12, s21.5, s32.5, s41.8。最大工作时间 \(T_{max} 8\)小时。在Lingo中我们可以用集合SETS和参数数据DATA段来定义这些。4.2 Lingo代码编写MODEL: ! 集合定义; SETS: node /0..4/: s; ! 节点集合属性s为服务时长公司0的s为0; person /1..4/; ! 服务人员集合; link(node, node): t; ! 节点间的交通时间; route(link, person): x; ! 决策变量x(i,j,k); visit(node, person): u; ! MTZ辅助变量u(i,k); ENDSETS ! 参数数据; DATA: ! 交通时间矩阵 t(i,j); t 0 0.5 0.8 0.6 0.4 0.5 0 0.3 0.9 0.7 0.8 0.3 0 0.5 0.6 0.6 0.9 0.5 0 0.4 0.4 0.7 0.6 0.4 0; ! 服务时长公司0为0; s 0 2 1.5 2.5 1.8; ! 最大工作时间; Tmax 8; ENDDATA ! 定义y(k)为人员是否启用等于他是否从公司出发; FOR(person(k): BIN(y(k)); y(k) SUM(node(j) | j #GT# 0: x(0, j, k)); ! 从公司0出发去任何客户j则y(k)1; ); ! 决策变量x是0-1变量; FOR(route(i,j,k): BIN(x)); ! 目标函数最小化启用人数; MIN SUM(person(k): y(k)); ! 约束1: 每个客户必须被服务一次; FOR(node(i) | i #GT# 0: ! i0 表示客户节点; SUM(link(i,j) | j #NE# i: SUM(person(k): x(i,j,k))) 1; ); ! 约束2: 流量平衡进入离开; FOR(node(h) | h #GT# 0: FOR(person(k): SUM(node(i) | i #NE# h: x(i, h, k)) SUM(node(j) | j #NE# h: x(h, j, k)) ); ); ! 约束4: 工作时间约束简化版这里计算每条弧上的总时间交通目的地服务; FOR(person(k): SUM(link(i,j) | j #GT# 0: (t(i,j) s(j)) * x(i,j,k)) Tmax; ); ! 注意上述约束对于从客户点返回公司0的弧只计算了交通时间t(i,0)因为s(0)0这是合理的。 ! 约束5: MTZ子回路消除约束; FOR(person(k): FOR(node(i) | i #GT# 0: FOR(node(j) | j #GT# 0 #AND# i #NE# j: u(i,k) - u(j,k) SIZE(node) * x(i,j,k) SIZE(node) - 1 ); ); ); FOR(visit(i,k) | i #GT# 0: u(i,k) 1); ! u(i,k)至少为1; ! 可选确保被启用的人员其路径从公司开始并结束于公司由流量平衡和约束1、4共同作用通常可省略显式约束; END4.3 代码要点与调试心得集合索引Lingo的索引从1开始但我们的节点编号是0-4所以用node /0..4/定义。在条件判断时i #GT# 0表示客户节点。MTZ约束的写法SIZE(node)返回节点集合的大小这里是5用n来替代。这是消除子回路的标准写法之一。变量定义y(k)没有在SETS中显式定义我们通过BIN(y(k))直接生成并二值化然后用一个等式将其与x(0,j,k)关联起来。这是一种简洁的写法。调试建议先跑小模型像这个4客户的例子可以先运行看有无语法错误能否得到可行解。检查解的报告在Lingo菜单点击Solution查看变量x和y的值。重点关注y(k)哪些是1以及x(i,j,k)1的路径是否构成从公司0出发、服务若干客户、再回到公司0的合理回路。理解不可行Infeasible如果模型无解首先检查工作时间约束Tmax是否设得太小。对于我们的数据可以粗略估算总服务时间21.52.51.87.8小时加上交通时间8小时可能非常紧张甚至不够。这时需要放松约束比如增大Tmax或检查模型逻辑。使用FOR和SUM这是Lingo向量化建模的核心能极大简化代码避免写冗长的标量式子。5. 结果分析与模型拓展解读输出与应对复杂需求运行上述Lingo代码可能需要根据实际Lingo版本微调语法如老版本可能需要用GIN代替BIN来声明整数变量我们可能会得到一个解。假设求解成功我们需要学会解读输出报告。5.1 解读Lingo求解报告Lingo的求解报告会包含全局最优解Global optimal solution找到与否对于线性整数规划Lingo能保证找到全局最优。状态显示“Global optimal solution found”是最好的。目标函数值Objective value:后面就是最小化的服务人员数量Z。比如可能是2表示至少需要2位阿姨。变量值Variable Value这是关键。你需要筛选出所有x(i,j,k)1的变量。例如你可能会看到X(0,1,1) 1,X(1,3,1)1,X(3,0,1)1- 这表示人员1的路径是公司(0)-客户1-客户3-公司。X(0,2,2)1,X(2,4,2)1,X(4,0,2)1- 人员2的路径是公司(0)-客户2-客户4-公司。Y(1)1,Y(2)1,Y(3)0,Y(4)0- 启用了人员1和2人员3和4未启用。松弛变量Slack or Surplus查看约束的松弛情况可以知道哪些约束是“紧”的松弛为0即刚好达到边界。比如如果某位人员的工作时间约束松弛很小说明她/他的日程排得非常满。5.2 根据业务反馈调整模型模型第一次跑出的结果往往需要拿回业务场景中检验。结果合理吗路径上的交通时间加上服务时间是否真的没超过8小时用计算器复核一下。业务上有特殊要求吗比如客户1和客户4是邻居希望同一位阿姨服务或者某位阿姨只服务某个区域的客户。这些都可以作为额外的约束加入模型。目标函数是否需要调整如果最小化人数导致个别阿姨工作强度极大接近8小时可能要考虑“最小化总工作时间”或“最小化最长单人工作时间”等更均衡的目标。5.3 模型拓展方向“家政服务1”很可能只是一个基础版本。实际问题会更复杂模型也需要相应拓展加入时间窗VRPTW这是最常见的拓展。每个客户有一个期望的服务时间范围[e_i, l_i]。需要引入新的决策变量a_{ik}表示人员k开始服务客户i的时间并添加约束e_i a_{ik} l_i以及服务顺序的时间递推约束a_{jk} a_{ik} s_i t_{ij} - M*(1-x_{ijk})其中M是一个很大的数。考虑技能匹配阿姨可能有不同技能如普通保洁、深度保洁、收纳整理。客户需求也不同。这时需要在约束中增加“匹配”条件只有技能符合时x_{ijk}才能为1。多目标优化比如既要人数少又要总路程短。可以尝试加权求和法或者先固定一个目标如人数优化另一个目标如路程观察帕累托前沿。动态与随机性现实中可能有客户临时取消或新增订单。这就进入了随机规划或动态规划的领域难度更大通常需要结合启发式算法。对于这些复杂变种Lingo依然可以建模但问题规模客户数、人员数稍大求解时间会急剧增加。这时就需要考虑使用专门的VRP求解器如VROOM、OR-Tools或编写启发式算法如遗传算法、模拟退火。但无论如何用Lingo建立并求解这个简化版模型是理解问题本质、验证算法正确性的绝佳第一步。6. 常见踩坑点与Lingo使用技巧最后分享一些我在用Lingo解决这类排班、路径优化问题时积累的经验和踩过的坑希望能帮你少走弯路。6.1 模型构建阶段的坑子回路消除Subtour Elimination这是VRP建模中最经典的坑。如果不加MTZ约束或DFJ约束模型可能会给出多个不连通的小循环解比如人员1的路径是客户1-客户2-客户1这显然不合理。MTZ约束简单但可能影响求解效率对于大规模问题DFJDantzig-Fulkerson-Johnson约束即割平面法结合回调函数是更专业的选择但在Lingo中实现较复杂。心得对于小规模问题先用MTZ如果求解变慢再考虑其他方法或换用更专业的求解器。“大M”法处理逻辑关系在建模“如果…那么…”这类逻辑条件时例如“如果服务客户i那么必须也服务客户j”常用“大M”法。关键是M的值要足够大以保证约束生效但又不能太大否则会造成数值计算困难影响求解精度和速度。通常取一个比问题规模大一个数量级的数即可。目标函数与约束的单位一致性确保目标函数里的成本、时间等单位与约束中的单位一致。比如目标是最小化“总成本”元约束里是“工作时间”小时如果涉及换算时薪要确保系数正确。6.2 Lingo求解与调试技巧从松弛问题开始如果整数规划模型直接求解困难或报错可以尝试先求解其线性松弛把所有整数变量BIN或GIN暂时注释掉或改为FREE。如果能快速得到松弛解且目标函数值看起来合理说明模型逻辑基本正确。然后再恢复整数约束求解。利用FILE和OLE函数读写数据当客户点很多时把交通时间矩阵、服务时长等数据写在DATA段里非常痛苦。可以将数据保存在文本文件如data.txt或Excel文件中在Lingo中用FILE(data.txt)或OLE(data.xlsx)读取。输出结果也可以写入文件方便分析。设置求解器选项在Lingo - Options - General Solver里可以调整一些参数。比如“Dual Computations”可以选择“Prices Range”这样在报告里能看到变量的缩减成本和对偶价格有助于敏感性分析。“Integer Pre-Solver”可以尝试调整有时能加快整数规划求解。善用WRITE和WRITEFOR输出调试信息在模型中间插入WRITE(某个集合的和是, SUM(...))可以将中间计算结果输出到报告窗口帮助定位错误。内存与时间限制对于大规模整数规划问题Lingo可能会消耗大量内存和时间。在Options里可以设置求解时间上限和迭代次数上限。如果时间到了还没找到最优解它会给出当前找到的最好解可行解。6.3 对“家政服务”场景的特别提醒交通时间的对称性我们通常假设t(i,j) t(j,i)但城市交通可能存在单行道或高峰拥堵导致去程和回程时间不同。建模时需要使用非对称矩阵。服务时间的波动性实际服务时间可能不是一个固定值而是一个区间或随机变量。可以考虑用鲁棒优化或随机规划来处理但这会大大增加模型复杂度。在初期用平均值或一个保守估计值是可行的。解的鲁棒性与可执行性数学上的最优解在现实中可能因为阿姨临时请假、交通意外等因素变得不可行。因此在实际应用中最优解更多是提供一个高质量的参考基准可能需要调度员在此基础上进行微调。通过这个“家政服务1”的案例我们完成了一次完整的数学建模与求解之旅从业务理解到模型抽象再到Lingo实现和结果分析。这个过程锻炼的是一种用结构化、定量化的方式解决实际复杂问题的能力。无论你未来是用更专业的优化软件还是自己写算法这套从问题到模型再到代码的思维框架都是通用的核心技能。