1. 从一道经典赛题说起露天矿卡车调度问题的本质如果你接触过数学建模尤其是早期的国赛题目2003年的B题“露天矿生产的车辆安排”绝对是一个绕不开的经典。这道题之所以经典不仅因为它背景清晰、贴近实际更因为它精准地卡在了“手工计算几乎不可能但用合适的工具又能优雅求解”的那个点上。题目要求我们为一个露天矿设计一套卡车调度方案核心目标是在满足矿石产量和品位要求的前提下如何安排卡车在铲位和卸点之间的往返路线使得总运量吨公里最小并且使用的卡车数量最少。这听起来像是一个复杂的运输问题但仔细拆解你会发现它有几个鲜明的特点第一资源是有限的铲车和卡车都有固定数量和工作时长第二需求是刚性的每个卸点矿石漏和岩石漏对矿石和岩石的产量、品位有明确要求第三路径是确定的从每个铲位到每个卸点的距离是已知的。这几乎就是为线性规划或整数规划量身定做的场景。当年很多队伍用手工试凑、启发式规则来求解费时费力且难以保证最优。而今天回头看用LINGO这类专业的优化软件来求解几乎是“降维打击”。我最近重新翻出这道题用LINGO 10完整地跑了一遍不仅验证了模型的正确性更对如何将实际问题转化为LINGO模型、如何解读结果、如何规避求解中的坑有了更深的理解。这篇文章我就来详细拆解这个过程手把手带你用LINGO 10复现这个经典案例的求解。2. 问题拆解与数学模型构建把现实装进公式里在打开LINGO之前最重要的一步是把文字描述的问题翻译成严谨的数学语言。这一步做得好后面的编程和求解才能顺畅。2.1 定义决策变量我们到底要决定什么整个调度方案的核心决策就是每一辆卡车在每一个班次8小时内应该执行多少次从某个铲位i到某个卸点j的运输任务。因此最自然的决策变量是x(i,j)表示从铲位i到卸点j的运输次数次/班。 这里i的取值范围是铲位编号题目中为10个铲位j的取值范围是卸点编号题目中为5个卸点包括2个矿石漏和3个岩石漏。x(i,j)必须是非负整数因为卡车运输次数不可能是小数。但仅仅有这个变量够吗仔细读题会发现卡车数量也是要优化的目标之一。我们还需要知道完成这样一个调度方案最少需要多少辆卡车。这就需要引入第二个关键的决策变量或者通过第一个变量推导出来。一种更直接的建模方式是将“使用的卡车数量”也作为一个决策变量但需要建立它与运输次数x(i,j)之间的约束关系。2.2 梳理约束条件现实世界的条条框框约束是模型的骨架它确保了求出的解是可行的、符合题意的。1. 产量约束卸点需求每个卸点对矿石或岩石有明确的产量要求。对于矿石漏卸点1和2需要满足指定的矿石吨数对于岩石漏卸点3、4、5需要满足指定的岩石吨数。假设从铲位i到卸点j运输一次装载的货物重量为load吨/次题目中卡车载重量固定那么对于某个卸点j所有铲位运到它的总吨数必须等于其需求demand(j)。 公式sum(i, load * x(i,j)) demand(j)对每个卸点j 这里demand(j)是已知参数。2. 品位约束矿石质量这是本题的一个关键约束。两个矿石漏卸点1和2对收到的矿石混合后的品位铁含量有上下限要求。每个铲位i的矿石品位grade(i)是已知的。因此运到某个矿石漏j的所有矿石其加权平均品位必须在指定范围内。 公式lower_bound(j) sum(i, grade(i) * load * x(i,j)) / sum(i, load * x(i,j)) upper_bound(j)这是一个比例约束在LINGO中需要转化为两个线性不等式来处理即sum(i, (grade(i) - upper_bound(j)) * load * x(i,j)) 0sum(i, (lower_bound(j) - grade(i)) * load * x(i,j)) 03. 资源约束铲车能力每个铲位配备的铲车有最大装车能力即一个班次内最多能装多少车。假设铲位i的装车能力上限为shovel_cap(i)车/班。 公式sum(j, x(i,j)) shovel_cap(i)对每个铲位i 这意味着从该铲位发出的所有运输车次之和不能超过其装车能力。4. 时间约束卡车能力这是连接运输次数与卡车数量的核心约束。一辆卡车在一个班次480分钟内能完成的运输次数是有限的。完成一次从i到j的运输需要时间装车时间t_load 行驶时间t_travel(i,j) 卸车时间t_unload。其中行驶时间与距离dist(i,j)和卡车速度有关。 假设完成一次运输i-j的循环时间为cycle_time(i,j)分钟。 那么所有运输任务的总耗时不能超过所有投入使用的卡车所能提供的总时间。设我们使用了K辆卡车则sum(i, sum(j, cycle_time(i,j) * x(i,j))) K * 480这里K就是我们要求解的“最少卡车数”它本身也应该是一个整数变量。目标函数中会最小化它。5. 整数与非负约束x(i,j)为非负整数K为正整数。2.3 确立目标函数什么是最好的方案题目有两个目标总运量吨公里最小并且卡车数量K最小。这是一个双目标优化问题。常见的处理方法是将其转化为单目标比如将卡车数量作为首要目标在其最小的前提下再最小化总运量或者给两个目标赋予权重。根据题意理解“同时考虑”往往意味着可以分层优化先求最少卡车数K_min然后在卡车数等于K_min的约束下再求最小化总运量。 总运量的计算公式为sum(i, sum(j, load * dist(i,j) * x(i,j)))因此我们可以建立两个模型或者在一个模型中通过调整目标函数优先级来实现。3. LINGO 10模型实现代码与技巧详解有了清晰的数学模型用LINGO实现就相对直接了。下面我给出核心的LINGO模型代码并穿插讲解关键点。MODEL: ! 2003国赛B题露天矿卡车调度优化; ! 定义集合; SETS: shovel /1..10/: grade, shovel_cap; ! 铲位集合属性品位装车能力(车/班); dump /1..5/: demand, type, lower_grade, upper_grade; ! 卸点集合属性需求(吨)类型(1矿石/2岩石)品位下限品位上限; link(shovel, dump): dist, x, cycle_time; ! 从铲位到卸点的连接属性距离(km)运输次数(决策变量)循环时间(分钟); ENDSETS ! 数据初始化; DATA: ! 铲位数据品位(%)装车能力(车/班); grade 30, 28, 29, 32, 31, 33, 32, 31, 33, 31; shovel_cap 80, 80, 80, 80, 80, 80, 80, 80, 80, 80; ! 假设均为80车/班根据题目具体数据填写; ! 卸点数据需求(吨)类型(1矿石漏2岩石漏)品位下限(%)品位上限(%); ! 注意岩石漏的品位上下限无意义可设为0; demand 10000, 15000, 8000, 12000, 9000; ! 示例数据需替换为题目真实数据; type 1, 1, 2, 2, 2; lower_grade 28, 28, 0, 0, 0; upper_grade 32, 32, 100, 100, 100; ! 岩石漏品位约束放宽; ! 距离矩阵(km)需替换为题目中的10x5矩阵; dist 5.2, 4.3, 2.1, 3.5, 4.0, 4.8, 5.1, 3.2, 2.9, 3.8, ... (此处省略需填写完整10行5列数据); ! 常数参数; load 100; ! 卡车载重(吨); v_empty 40; ! 空载速度(km/h); v_full 30; ! 重载速度(km/h); t_load 5; ! 装车时间(分钟); t_unload 3; ! 卸车时间(分钟); shift_time 480; ! 班次时间(分钟); ENDDATA ! 计算循环时间(分钟): 行驶时间(往返) 装车 卸车; FOR(link(i,j): cycle_time(i,j) (dist(i,j)/v_full dist(i,j)/v_empty) * 60 t_load t_unload; ); ! 定义决策变量; ! x(i,j) 为从铲位i到卸点j的运输次数非负整数; FOR(link(i,j): GIN(x(i,j))); ! GIN表示整数变量; ! K 为使用的卡车数量正整数; K SUM(link(i,j): x(i,j) * cycle_time(i,j)) / shift_time; GIN(K); ! 卡车数也应为整数但这里通过总时间计算后取整更严谨的做法是将其也设为变量并增加约束; ! 目标函数最小化总运量(吨公里); MIN SUM(link(i,j): load * dist(i,j) * x(i,j)); ! 注意这是单目标。更严谨的双目标处理见下文说明; ! 约束条件; ! 1. 产量约束每个卸点的总接收量等于其需求; FOR(dump(j): SUM(shovel(i): load * x(i,j)) demand(j); ); ! 2. 品位约束仅对矿石漏(type1)有效; FOR(dump(j) | type(j) #EQ# 1: ! 条件索引只对矿石漏; ! 品位上限约束; SUM(shovel(i): (grade(i) - upper_grade(j)) * load * x(i,j)) 0; ! 品位下限约束; SUM(shovel(i): (lower_grade(j) - grade(i)) * load * x(i,j)) 0; ); ! 3. 铲车能力约束每个铲位发出的总车次不超过其能力; FOR(shovel(i): SUM(dump(j): x(i,j)) shovel_cap(i); ); ! 4. 卡车能力约束所有运输任务总时间不超过所有卡车总可用时间; ! 这里K由总时间计算得出隐含了此约束。更显式的写法是引入卡车数变量K_var: ! SUM(link(i,j): cycle_time(i,j) * x(i,j)) K_var * shift_time; ! 并将K_var加入目标函数或约束。 ! 5. 非负约束LINGO默认变量非负整数约束已用GIN声明; END关键技巧与注意事项集合定义是核心LINGO的建模优势在于其集合语言。清晰定义shovel、dump、link集合能让后续的约束书写非常简洁避免冗长的下标循环。link(shovel, dump)这种派生集合是处理二维关系的利器。数据与模型分离所有已知参数品位、距离、需求等都放在DATA段。这样如果数据变化只需修改DATA段模型逻辑部分(MODEL)完全不用动维护性极佳。条件约束的写法品位约束只针对矿石漏使用| type(j) #EQ# 1这样的条件索引非常方便。#EQ#是LINGO的关系运算符表示等于。整数变量声明运输次数x(i,j)必须是整数用GIN()函数声明。卡车数量K理论上也应是整数在模型中我们可以先按连续变量求解再对结果取整验证或者直接将其声明为GIN(K)。更严谨的双目标模型中K会作为一个独立的决策变量。双目标处理的策略上述模型只最小化了总运量。要实现“卡车数最少”优先有两种常用方法分层求解法先建立一个模型目标函数是MIN K;最小化卡车数并加上所有其他约束。求解得到最少卡车数K_min。然后修改模型将K K_min;作为一个新增的约束目标函数改为最小化总运量再次求解。加权求和法将两个目标合并为一个如MIN W1 * K W2 * Total_Transport;其中W1和W2是权重且W1远大于W2以体现卡车数优化的优先性。但权重的选择需要谨慎可能影响解的有效性。4. 求解、结果解读与方案分析在LINGO 10中编写好上述模型后点击“Solve”按钮进行求解。LINGO会调用其内置的求解器对于此类混合整数线性规划问题通常使用分支定界法。4.1 求解过程观察与日志解读求解时建议打开“Solver Status”窗口观察求解过程。你会看到“Global Optimum”全局最优解或“Local Optimum”局部最优解的状态。对于线性整数规划LINGO通常能找到全局最优解。日志中会显示迭代次数、目标函数值的变化、整数变量的分支情况等。如果模型规模大或约束复杂求解时间可能会较长这时可以调整LINGO的求解选项比如放宽整数容差(Integer Tolerance)以加速求解但可能会牺牲一点精度。4.2 结果报告分析与提取求解完成后LINGO会弹出“Solution Report”窗口。这是分析结果的核心。变量值(Variable Value)这里列出了所有决策变量的最优值。你需要重点关注x(i,j)的值这直接给出了最优调度方案。例如x(1,2)15表示从1号铲位到2号卸点矿石漏安排15车次。K的值即最少需要的卡车数量。目标函数值即最小的总运量吨公里。松弛变量(Slack or Surplus)对于不等式约束这个值表示约束的“宽松”程度。如果为0表示该约束是“紧的”active即资源被完全利用如某个铲位的装车能力刚好用完。如果大于0表示有剩余能力。分析松弛变量能帮你理解方案的瓶颈在哪里。例如如果所有铲车的松弛变量都为正说明铲车能力不是限制因素如果某些卸点品位约束的松弛变量为0说明品位要求卡得很死。对偶价格(Reduced Cost / Dual Price)对于线性规划问题对偶价格对于变量是Reduced Cost对于约束是Dual Price有重要的经济解释。例如某个铲位装车能力约束的对偶价格很高意味着如果这个铲位的能力增加一单位多装一车目标函数总运量能改善多少。这为方案改进提供了方向。4.3 生成可读的调度方案表LINGO的原始输出对于x(i,j)这样的二维变量可读性不强。你可以在模型末尾添加数据输出语句将结果整理成表格。更常用的方法是将x(i,j)的值复制到Excel中利用数据透视表功能生成一个清晰的“铲位-卸点”运输车次矩阵。这个矩阵就是最终的调度指令表可以直接用于指导生产。基于结果的分析要点卡车利用率计算(总运输时间)/(K * 480)可以评估卡车队伍的繁忙程度。理想情况应接近1但小于1因为有整数约束和离散性。关键路径/瓶颈识别通过分析循环时间cycle_time(i,j)和对应的x(i,j)可以找出那些耗时最长的运输任务它们可能是影响整体效率的关键。如果可能可以考虑优化这些长距离路线的配置。方案鲁棒性可以稍微改变一些参数如某个卸点的需求±5%重新求解观察方案变化是否剧烈。这能评估当前最优方案对数据波动的敏感度。5. 常见问题、调试技巧与模型优化即使模型看起来正确第一次求解也可能遇到各种问题。以下是一些实战中常见的坑和解决思路。5.1 “No Feasible Solution Found” (无可行解)这是最令人头疼的错误之一意味着模型约束太严不存在同时满足所有条件的解。排查步骤逐条放松约束暂时注释掉品位约束、卡车时间约束甚至铲车能力约束只保留最基本的产量约束看模型是否有解。如果此时有解再逐一加回约束定位是哪个约束导致不可行。检查数据一致性仔细核对所有输入数据。例如所有铲位的总装车能力sum(shovel_cap)是否大于总需求车次sum(demand)/load如果总供给小于总需求必然无解。品位上下限是否合理是否存在某个矿石漏所有能向它供矿的铲位品位都不在其要求范围内检查约束公式重点检查品位约束的线性化转换是否正确。确保不等式方向没错。对于矿石漏品位上下限约束是两个独立的0约束。使用LINGO的调试功能生成模型的“Equation List”方程列表逐行检查生成的每一个约束方程看是否符合数学模型的初衷。5.2 求解时间过长或无法得到整数解对于整数规划问题规模整数变量个数很大时求解可能很慢。优化策略提供初始解如果你根据经验能猜测一个较好的可行解哪怕不是最优可以在LINGO的INIT段为x(i,j)和K赋初值。这能大大缩短求解器寻找第一个可行解的时间并引导搜索方向。调整求解器选项在LINGO的Options菜单中进入Integer Solver选项卡。可以尝试增加“Branching Priority”分支优先级对卡车数K设置高优先级让求解器先分支这个对目标影响大的变量。调整“Integer Tolerance”默认是1e-6可以适当放宽到1e-4或1e-3以加速求解接受一个接近最优的整数解。设置时间限制或迭代次数限制。模型重构有时改变模型的表达方式能提高求解效率。例如如果某些x(i,j)明显不可能很大由于距离或时间限制可以为其增加一个上界BND(0, x(i,j), upper_bound)减少搜索空间。5.3 结果不直观或不符合常识检查目标函数确认你最小化的是“总运量”而不是“总车次”或“总时间”。单位是否正确吨公里分析解的结构最优解中是否出现了从很远铲位向某个卸点大量运输而近处铲位却闲置的情况这通常不合常理。原因可能是近处铲位的品位不符合要求或者近处铲位的装车能力已被其他卸点占满。这时需要结合松弛变量和对偶价格来分析理解模型背后的经济驱动因素。验证约束满足手动计算几个关键值进行验证。例如随机选一个卸点将运往它的所有车次乘以载重量看是否等于需求。选一个矿石漏计算其加权平均品位看是否在范围内。5.4 模型扩展与深化在解决基本问题后可以考虑一些更贴近实际的扩展这能极大提升模型的价值多班次调度考虑多个连续班次并考虑卡车交接班、铲位产量随时间变化如品位波动等因素。动态调度引入实时概念如卡车故障、道路拥堵、卸点排队等随机事件模型将向随机规划或仿真优化方向发展。成本最小化目标函数不仅考虑运量还可以加入卡车固定成本使用费、油耗成本与距离和载重相关、司机成本等进行总成本最小化。电动卡车调度如果考虑电动卡车则需要加入电池电量、充电时间、充电桩位置等约束问题会变得更加复杂成为混合整数非线性规划或更复杂的模型。重新用LINGO求解这道近二十年前的赛题最大的感触不是工具本身而是建模思维的精炼。当年受限于工具很多队伍把精力花在了如何“近似”求解上。而现在我们可以更专注于问题本质的抽象和模型边界的刻画。LINGO这样的工具让我们能从繁琐的计算中解放出来去思考更关键的约束、更合理的目标、以及解的现实意义。这道题就像一个经典的练手场熟练之后面对物流配送、生产排程、资源分配等各类优化问题你都能快速抓住核心构建出清晰、可解的模型。最后一个小建议在正式求解前不妨先用简化数据比如减少几个铲位和卸点快速构建和调试模型确保逻辑正确后再代入全量数据这会节省大量调试时间。