学运筹学的时候班里一大半人都在线性规划上栽过跟头。一开始我用 Excel 求解变量多了就手忙脚乱。后来被朋友安利了 Python 的 scipy.optimize.linprog 和 LINGO这两个工具一个偏代码、一个偏建模配合起来几乎能把线性规划的最大值、最小值问题都吃得死死的。这篇笔记就是我从建模到求解、从报错到避坑的全过程希望能帮到正在学运筹学、或者工作中碰巧要用线性规划的同学。1. 动手求解之前先把线性规划模型“标准化”这件事做明白1.1 为什么 linprog 只认最小化最大值要绕一个弯scipy.optimize.linprog 的文档写得很清楚它求解的标准形式是min c^T x也就是说它默认把所有目标函数都当成“求最小”来处理。这时候很多人第一次用就懵了我明明要算最大利润怎么传入 c 和约束之后结果变成了一个负数原因不在求解器而在数学形式转换。回顾一下线性规划的基础知识对于 max z c^T x令目标函数取负变成 min (-c)^T x。求出最优解之后再把最优值取负号就是原问题的最大值。我见过不少同学在这里栽跟头还以为是程序出 bug 了。其实这个转换在运筹学教材里讲单纯形法时也会提到只是到了写代码环节大家往往忘了这茬。类似的“标准化”还有一个更隐蔽的点linprog 的默认不等式约束方向只接受 A_ub x b_ub。如果你是大于等于约束比如 x1 x2 10必须两边同时乘一个负号写成 -x1 - x2 -10才能塞进 linprog。这两个转换几乎是 linprog 使用中 80% 报错和结果对不上的根源。下文案例部分我会再演示一遍确保你真的会转。1.2 LINGO 在建模自由度上确实更接近数学表达相比之下LINGO 在建模时非常“任性”MAX、MIN 都可以直接写大于等于、小于等于也能直接写求解器内部会自动做标准化转换。对于学习和快速验证模型来说这个体验至关重要。比如同样一个约束 x1 x2 10在 LINGO 里就写x1 x2 10;不用乘负号不用整理成矩阵。我第一次用 LINGO 时最大的感受就是“这玩意儿像把数学作业抄进电脑里”。它还有一点和 linprog 默认行为一致LINGO 里普通变量默认就是非负的不需要额外声明而 linprog 的 bounds 默认值也是 (0, None)也就是 x 0。所以两个工具虽然底层算法同源都离不了单纯形法和内点法那套东西但建模入口的思维模式完全不同。我的建议是理解标准化用 Python快速验证模型用 LINGO两边一对照线性规划那些弯弯绕绕就通透了。1.3 建模四要素动手前先写在纸面上不管用哪个工具我强烈建议先把以下四要素写清楚再打开软件决策变量x1、x2代表什么目标函数要求最大还是最小表达式是什么约束条件每个约束是 ≤、≥ 还是 变量范围非负、有上下界还是自由变量无界这个习惯看起来简单却是节省调试时间的利器。矩阵形式一旦写错报错信息往往模棱两可排查起来比建模还痛苦。而写在纸面上之后转化到代码或 LINGO 就是纯机械操作了。2. scipy.optimize.linprog 实战参数弹坑逐个踩2.1 一个表格看懂 linprog 核心参数先给出最常用的参数清单方便你抄作业参数含义注意点c目标函数系数向量求最大值时记得传 -cA_ub不等式约束系数矩阵每行对应一个 ≤ 约束b_ub不等式约束右侧常数向量与 A_ub 行数对应A_eq等式约束系数矩阵不是必需没有就不传b_eq等式约束右侧常数向量与 A_eq 行数对应bounds每个变量的上下界默认 (0, None)即非负method求解方法新版本推荐 highs其中 A_ub 和 b_ub 是一对A_eq 和 b_eq 是一对千万不能混。一旦混了结果算出来一定莫名其妙。还有一点特别容易踩A_ub 必须是二维矩阵格式哪怕只有一个约束也要写成 [[...]]不能直接写成一维列表。我第一次写的时候因为约束少随手填了个一维数组直接被 ValueError 教育了。2.2 一个最简单的可运行示例直接看代码更直观。假设要求解max z 40x1 30x2s.t.2x1 3x2 ≤ 1204x1 2x2 ≤ 160x1 x2 ≤ 50x1, x2 ≥ 0这是一个非常典型的生产计划问题。用 linprog 的写法是import numpy as np from scipy.optimize import linprog c [-40, -30] A_ub [ [2, 3], [4, 2], [1, 1] ] b_ub [120, 160, 50] bounds [(0, None), (0, None)] res linprog(c, A_ubA_ub, b_ubb_ub, boundsbounds, methodhighs) print(res.x) # [30. 20.] print(res.fun) # -1800.0 print(-res.fun) # 1800.0这里 c 用 [-40, -30] 而不是 [40, 30]就是为了把 max 变成 min。最终 res.fun 是 -1800所以真正的最大利润是 1800。然后看 res.x最优生产安排是 x130、x220。这个例子里所有约束的最优解处 slack 都是 0表示三种资源全部用完。如果某个约束有剩余资源slack 就会是正数。2.3 返回值里藏着的“体检报告”linprog 返回的是一个 OptimizeResult 对象里面有几个字段建议每次都检查一下res.success布尔值麻烦的话就是 Falseres.status0 是成功1 是迭代次数限制2 是不可行3 是无界res.message人类可读的诊断信息res.slack不等式约束的松弛变量值res.con等式约束的残差我最常用的是 status 和 slack。status 一眼看出问题类型slack 能告诉我哪个约束是“紧”的对做敏感性分析和优化方向判断特别有用。比如你发现某个约束 slack 很大说明这个资源其实很宽裕去跟业务方聊的时候就可以说“这项资源目前不是瓶颈”。这种判断在运筹学实际应用中价值很高。2.4 大规模求解与稀疏矩阵当变量和约束数量上到几百、几千时直接用 Python 列表构造矩阵会非常痛苦内存和速度都不乐观。这时候可以换成 scipy.sparse 的稀疏矩阵来传 A_ub 和 A_eqhighs 方法天然支持稀疏输入。我做过一个约束条件上千的训练计划排程实验稀疏矩阵配合 highs 求解速度比普通列表快很多。如果只是课堂作业完全用不到这一步但如果你以后工作中要做排产、调度、路径规划提前知道这个技巧能省不少事。另外新版本 linprog 还支持 integrality 参数可以求解混合整数线性规划。不过说实话真遇到整数规划我更推荐去用专门的求解器linprog 的整数支持属于够用但不算强。3. LINGO 建模像抄数学作业一样写优化模型3.1 最基础的 LINGO 模型长什么样LINGO 的语法结构非常简单一个模型文件基本由目标函数、约束和可选的数据段组成。还是拿刚才那个生产计划问题举例MODEL: MAX 40*x1 30*x2; 2*x1 3*x2 120; 4*x1 2*x2 160; x1 x2 50; END把这段内容粘进 LINGO 的模型窗口点击求解按钮几秒钟后你就能在报告窗口看到最优解x130x220目标值 1800。注意几个细节每句结尾的分号不能丢而且最好用英文输入法打中文分号会让你浪费十分钟变量不需要预先声明直接用普通变量默认非负如果某个变量允许取负值需要加 FREE(x)注释用英文感叹号 !不加也没关系3.2 用集合语法解决运输问题如果只是几个变量LINGO 直接写最省事。可一旦遇到运输问题、分配问题这类天然带有二维结构的模型手写每一个变量就太蠢了必须用集合SETS。运输问题的典型结构是有多个产地、多个销地每个产地有供应量每个销地有需求量每一条运输线路有单位成本要求总运输成本最小。LINGO 的集合建模思路是这样MODEL: SETS: ORIGIN /O1, O2/: supply; DEST /D1, D2, D3/: demand; ROUTE(ORIGIN, DEST): cost, x; ENDSETS DATA: supply 60 70; demand 40 50 40; cost 8 6 10 9 12 7; ENDDATA MIN SUM(ROUTE(I,J): cost(I,J) * x(I,J)); FOR(ORIGIN(I): SUM(DEST(J): x(I,J)) supply(I) ); FOR(DEST(J): SUM(ORIGIN(I): x(I,J)) demand(J) ); END这里 ROUTE 是一个派生集合x 和 cost 都是二维的。SUM 负责求和FOR 负责批量生成约束。这种写法的好处是产地和销地数量一变只需改 DATA 段里的数据模型本身不用动。对比一下 linprog同样的问题你要先手工展开 6 个运输变量再拼出 5 个约束矩阵稍有不慎索引就错位。LINGO 在建模效率上完胜。3.3 全局最优求解器和它的使用场景LINGO 默认求的是局部最优对线性规划来说局部就是全局问题不大。但如果你以后在 LINGO 里写非线性模型就得小心了。可以打开菜单中的全局求解器选项启用 Global Solver这样它会花更多时间来找全局最优。我实验过一个带二次项的组合优化问题默认求解器给了一个局部最优开全局求解器之后结果明显更好当然等待时间也上去了。线性规划阶段不需要改这个知道有这么个选项就行。4. 完整案例实操最大利润与最小成本两个求解器对比跑一遍4.1 案例一生产计划问题求最大利润问题背景很常见某车间生产两种产品 A、B需要考虑三种资源约束。单位利润分别为 40 和 30三种资源的消耗系数和上限如下资源一2x1 3x2 ≤ 120资源二4x1 2x2 ≤ 160资源三x1 x2 ≤ 50目标是最大化总利润。前面已经在 2.2 节展示过 linprog 版本这里把 LINGO 版本再贴一遍并对比输出MODEL: MAX 40*x1 30*x2; 2*x1 3*x2 120; 4*x1 2*x2 160; x1 x2 50; END两个求解器给出的结果完全一致。这说明模型转换没犯错。如果结果不一致问题几乎必然出在符号方向或者矩阵拼写错误上。这个案例有一个值得注意的特征三个约束的最优值处资源全部耗尽属于供应链里典型的“满负荷生产”。碰到这种情况下一步就可以考虑敏感性分析看看哪种资源增加 1 个单位带来的边际收益最大那就是你的瓶颈资源。4.2 案例二营养配料问题求最小成本再来一个目标为“最小”的案例。假设要配置一种饲料至少需要 80 单位蛋白质和 200 单位能量。两种原料 X、Y 的成本和营养成分如下X成本 5 元/kg每 kg 提供蛋白质 0.2 单位、能量 0.5 单位Y成本 4 元/kg每 kg 提供蛋白质 0.1 单位、能量 1 单位目标是成本最小化min z 5x1 4x2s.t.0.2x1 0.1x2 ≥ 800.5x1 x2 ≥ 200x1, x2 ≥ 0注意这里是 ≥ 约束。用 linprog 必须先乘负号import numpy as np from scipy.optimize import linprog c [5, 4] A_ub [ [-0.2, -0.1], [-0.5, -1.0] ] b_ub [-80, -200] res linprog(c, A_ubA_ub, b_ubb_ub, methodhighs) print(res.x) # [400. 0.] print(res.fun) # 2000.0最优解是只买原料 X 400kg成本 2000。LINGO 版本就友好多了不需要转方向MODEL: MIN 5*x1 4*x2; 0.2*x1 0.1*x2 80; 0.5*x1 x2 200; END这个案例我想强调两件事。第一最小值问题在 linprog 里不需要像最大值那样对 c 取负因为我们本来就是最小化c [5, 4] 直接传就行。第二约束方向转换是最容易出错的位置如果你不想每次手算符号建议在草稿纸先把数学模型的每个约束标注成标准形态。4.3 两个工具结果互验的思路我学习时有个笨办法同一道题先用 LINGO 建一次模型再用 linprog 写一次。两边结果一致我就放心了。这个方法看起来重复劳动实际极其高效因为求解器本身很少出错出错的多半是建模时方向搞反、矩阵错位、边界漏设。互验还有一个好处强迫你把同一个问题用两种范式表达一种是矩阵思维一种是数学表达式思维两种思维切换时脑子必须清醒练几次之后建模能力会有肉眼可见的提升。5. 常见报错与排查技巧实录5.1 linprog 高频报错速查表现象大概率原因解决思路ValueError: A_ub must be a 2-dimensional matrix把 A_ub 写成二维数组单约束也要用 [[...]]Unknown solver xxxmethod 参数拼写错误或版本太旧升级 SciPy改用 highsstatus2 / 不可行约束方向写反或约束之间矛盾检查 ≥ 约束是否乘了负号status3 / 无界漏了某个约束或变量边界写成了 None确认可行域是否有界结果里有负号跟预期目标值对不上求最大值时没有对 res.fun 取负最终最大值 -res.fun结果出现 nan约束矩阵中有 NaN检查数据预处理最坑的一次我在循环里批量生成多个线性规划其中一个模型的某个变量忘了设上界导致它一路涨到无穷求解器提示无界。排查半天才发现是数据里有个产量上限没读进去程序没报错直接给了个无界状态。所以一定养成习惯跑完先看 status不要只看 x。5.2 LINGO 高频问题LINGO 的报错更“原始”一些但常见问题很固定Syntax error 且光标停在分号附近八成是中文分号变量名显示为红色拼写不一致或者集合定义有误No feasible solution found约束组矛盾检查符号方向求解结果出现小数但你期望整数LINGO 默认变量是连续的需要加 GIN(x)大型模型求解很久可以关掉报告生成或改用全局求解器并调整时间上限我建议在 LINGO 里写模型时先不写数据把集合和约束结构跑通再往 DATA 段填数据。这样如果报错至少能区分是结构问题还是数据问题排查范围小一半。5.3 判断线性规划是否可解的“三板斧”如果你对模型很陌生别急着交给求解器先按这个顺序走一遍画图如果有 2 到 3 个变量直接把可行域画在纸上或坐标轴里观察它是不是一个有界凸多边形顶点在哪里手算顶点把每个顶点代入目标函数找出最大或最小值用求解器验证把纸面上的最优解和软件输出对比这个方法虽然老土但对于理解线性规划的本质非常有用。尤其遇到“无界”和“不可行”这两种情况时画图能一眼看穿而纯看代码提示往往只能猜。6. 工具选型建议以及我最后想补充的一个验证小技巧6.1 scipy.optimize.linprog 和 LINGO 选哪个简单说能写 Python 的地方用 linprog想快速建模验证用 LINGO。具体对比看这张表维度scipy.optimize.linprogLINGO成本开源免费SciPy 自带商业软件通常有学术试用版建模方式矩阵/数组适合程序化生成接近数学表达式集合语法强大自动化集成天然适合 Python 数据分析流程不好嵌入其他系统教学演示需要讲解标准化转换直观适合课堂快速建模大规模问题highs 配合稀疏矩阵可以打也支持但商业版许可证成本高报告信息status、slack、con 等有 slack、dual price、敏感性分析报告我的个人结论是如果你是运筹学课程学生两个都装上作业用 LINGO 检查代码作业用 linprog 交如果你是工程师主要在 Python 生态里混那就把 linprog 练熟偶尔需要快速验证思路时再用 LINGO 顶一下。6.2 一个我从实践里提炼的验证小技巧最后分享一个让我少走很多弯路的小习惯不要在拿到结果后直接写入报告先用一个极简的二维例子验证你写的“工具调用代码”本身是对的。比如随手构造一个 x1 x2 ≤ 1、x1, x2 ≥ 0、max x1 x2 的模型最优解显然是 x11、x20 或 x10、x21。如果这种简单模型都算不对那一定是你对 API 的用法有问题和复杂模型无关。我每次在项目里写新的优化模块时都会留一套这样的“冒烟测试”用例。看似多花五分钟实际省掉无数次深夜排查 bug 的痛苦强烈建议你试试。6.3 后续还能怎么扩展学完线性规划之后你会发现这套思路能平滑迁移到很多方向整数规划、目标规划、运输问题、指派问题、网络流、生产排程。linprog 只是入门后面还有 PuLP、OR-Tools、Gurobi 这些更专业的工具等着你。LINGO 则适合继续深入敏感性分析和参数分析。我的体会是工具永远是手段模型思维才是核心。你能不能在拿到一个业务问题后快速抽出决策变量、目标函数、约束条件决定了你使用这些工具的上限。线性规划恰恰是训练这种思维最好的起点。