1. 项目缘起为什么线性规划是数学建模的“瑞士军刀”如果你参加过数学建模竞赛或者处理过任何涉及资源分配、生产计划、路径优化的问题那么“线性规划”这个词对你来说一定不陌生。它就像工具箱里那把最趁手、最通用的螺丝刀看似简单却能拧开无数复杂问题的外壳。我在带学生队伍和做工业优化项目时无数次看到大家面对一个优化问题第一反应就是去套用各种复杂的神经网络或启发式算法结果往往事倍功半。其实很多问题的本质用线性规划就能优雅、高效地解决。线性规划的核心思想非常直观在满足一系列线性等式或不等式约束的条件下最大化或最小化一个线性目标函数。比如工厂要决定生产A、B两种产品每种产品利润不同消耗的原材料和工时也不同在有限的资源下如何安排生产计划才能让总利润最高这就是一个典型的线性规划问题。它的强大之处在于一旦你能把实际问题“翻译”成线性规划的数学模型即决策变量、目标函数、约束条件剩下的求解工作就可以交给成熟、高效的求解器几乎能在瞬间得到全局最优解。然而从“知道概念”到“能熟练用代码实现并解决实际问题”中间有一道不小的鸿沟。很多教材和课程停留在理论推导和单纯形法的手算上但实战中我们几乎不会去手写单纯形法。Python凭借其强大的科学计算生态成为了连接数学建模理论与工程实践的最佳桥梁。通过scipy.optimize.linprog、PuLP、CVXOPT等库我们可以用极简的代码调用世界顶级的求解器。但问题恰恰出在这里库的接口看似简单但如何正确无误地构建模型、理解求解状态、处理无解或无界的情况才是真正考验功力的地方。这篇内容我就结合自己多次在国赛、美赛以及企业项目中应用线性规划的经验抛开教科书式的说教直接上干货带你从零实现一个完整的线性规划求解流程并重点分享那些容易踩坑的细节和调试技巧。2. 环境搭建与工具选型不止于scipy.optimize工欲善其事必先利其器。在Python中实现线性规划你有好几个选择每个都有其适用的场景。盲目选择一个可能会在后续遇到兼容性、性能或功能上的限制。2.1 主流求解库横向对比我们首先对比三个最常用的工具scipy、PuLP和CVXPY。选择哪一个取决于你的问题规模、对求解器的需求以及编码风格。特性 / 库名scipy.optimize.linprogPuLPCVXPY核心定位SciPy科学计算套件的一部分内置求解器。建模语言接口支持调用多种外部求解器CBC, GLPK, Gurobi等。凸优化建模语言语法更数学化支持更广泛的凸优化问题。求解器内置HiGHS默认、‘revised simplex’单纯形法、‘interior-point’内点法。自身无求解器作为“调度员”调用CBC免费、GLPK免费或商业求解器如Gurobi、CPLEX。自身无求解器支持调用ECOS、OSQP、SCS等用于凸优化以及通过插件调用Gurobi等。语法风格函数式调用需手动构建矩阵A_ub,b_ub,c等。面向对象建模过程更直观类似“创建变量-定义目标-添加约束”。基于矩阵运算书写形式最贴近数学公式非常优雅。优点无需安装额外求解器开箱即用与NumPy/SciPy生态无缝集成。模型与求解器解耦更换求解器方便支持整数规划需配合对应求解器语法易懂。书写直观易于验证模型正确性自动检测凸性社区活跃。缺点接口较为底层构建复杂约束时易出错功能相对基础。需要单独安装求解器如CBC对于纯线性规划语法稍显冗余。对于纯线性规划有点“杀鸡用牛刀”安装稍复杂学习曲线较陡。适用场景快速验证小规模问题原型教育演示与其他SciPy函数协同工作。数学建模竞赛常用CBC求解器需要灵活切换或尝试不同求解器的场景涉及整数规划时。研究领域问题本身是更广泛的凸优化问题追求代码与数学公式的高度一致。对于数学建模入门和大多数中小规模问题我的建议是从PuLP开始。原因有三第一它的建模逻辑最贴近人的思维不易出错第二它默认绑定的CBC求解器完全免费且功能强大能处理整数规划为后续问题扩展留有余地第三在竞赛中PuLPCBC是经过广泛验证的稳定组合。scipy.linprog适合极简的演示而CVXPY更适合科研或凸优化专题。2.2 一步到位的环境配置为了避免版本冲突和依赖问题我强烈推荐使用conda进行环境管理。以下命令将创建一个包含所有必要工具的环境# 创建并激活一个名为“math_modeling”的虚拟环境 conda create -n math_modeling python3.9 conda activate math_modeling # 安装核心科学计算库和PuLP conda install numpy pandas matplotlib scipy pip install pulp安装pulp时它会自动安装其默认的求解器CBC在Windows上可能需要额外步骤但通常pip能搞定。安装完成后可以在Python中验证import pulp print(pulp.listSolvers(onlyAvailableTrue)) # 你应该能看到 [PULP_CBC_CMD] 或更多这表示CBC求解器可用。注意有些教程会建议用pip直接安装scipy和pulp。这通常可行但在某些系统上CBC求解器的二进制文件可能因为网络或权限问题安装失败。如果遇到pulp报错说找不到求解器可以尝试单独安装coin-or-cbc包conda install -c conda-forge coin-or-cbc或者使用scipy.linprog作为临时替代。3. 从问题描述到数学模型的“翻译”艺术这是线性规划应用中最关键、也最容易出错的一步。代码写错尚可调试模型建偏了则全盘皆输。我们通过一个经典的“营养配餐”问题来实战演练。问题描述某食堂需要为学生配餐要求每餐至少提供能量2000千卡蛋白质55克钙800毫克。现有六种食材可供选择其每千克的营养成分、价格及每日可用量上限如下表所示。如何搭配食材才能在满足营养需求的前提下使得总成本最低食材价格元/千克能量千卡/千克蛋白质克/千克钙毫克/千克可用量上限千克大米3.0350080300.5面粉2.5280040200.3鸡蛋8.015001205000.2牛奶5.08006010000.5牛肉25.02000200500.1菠菜2.0200203000.43.1 定义决策变量这是建模的起点。我们必须明确我们要决定的是什么在这个问题里我们要决定的是每种食材的使用量千克。因此定义6个决策变量( x_1 )大米的使用量千克( x_2 )面粉的使用量千克( x_3 )鸡蛋的使用量千克( x_4 )牛奶的使用量千克( x_5 )牛肉的使用量千克( x_6 )菠菜的使用量千克所有这些变量都有一个天然约束非负性即 ( x_i \geq 0 \ (i1,2,...,6) )。这在线性规划中是默认的但需要在心里记住。3.2 构建目标函数我们的目标是最小化总成本。总成本 各食材用量 × 单价 的总和。因此目标函数为 [ \min Z 3.0x_1 2.5x_2 8.0x_3 5.0x_4 25.0x_5 2.0x_6 ] 这是一个线性函数符合“线性”规划的要求。3.3 梳理约束条件这是最需要细心的地方。约束分为两类营养需求和资源上限。营养需求约束至少满足这是“大于等于”约束。能量约束( 3500x_1 2800x_2 1500x_3 800x_4 2000x_5 200x_6 \geq 2000 )蛋白质约束( 80x_1 40x_2 120x_3 60x_4 200x_5 20x_6 \geq 55 )钙约束( 30x_1 20x_2 500x_3 1000x_4 50x_5 300x_6 \geq 800 )资源上限约束最多可用这是“小于等于”约束直接来自题目表格的“可用量上限”。( x_1 \leq 0.5 )( x_2 \leq 0.3 )( x_3 \leq 0.2 )( x_4 \leq 0.5 )( x_5 \leq 0.1 )( x_6 \leq 0.4 )至此我们完成了从文字描述到数学模型的“翻译”。完整的数学模型如下 [ \begin{aligned} \min Z 3.0x_1 2.5x_2 8.0x_3 5.0x_4 25.0x_5 2.0x_6 \ \text{s.t.} 3500x_1 2800x_2 1500x_3 800x_4 2000x_5 200x_6 \geq 2000 \ 80x_1 40x_2 120x_3 60x_4 200x_5 20x_6 \geq 55 \ 30x_1 20x_2 500x_3 1000x_4 50x_5 300x_6 \geq 800 \ 0 \leq x_1 \leq 0.5,\ 0 \leq x_2 \leq 0.3,\ 0 \leq x_3 \leq 0.2,\ 0 \leq x_4 \leq 0.5,\ 0 \leq x_5 \leq 0.1,\ 0 \leq x_6 \leq 0.4 \end{aligned} ]实操心得在纸上或注释里清晰地写出这个数学模型是后续编程不出错的基础。务必检查1) 变量含义是否明确2) 目标函数是min还是max3) 约束条件的方向≥≤和数值是否正确。我习惯把约束按类型分组并给每个约束一个简短的文字标签这在代码调试时非常有用。4. 使用PuLP实现模型并求解现在我们将上面“纸上”的模型转化为PuLP的代码。PuLP的建模过程非常直观几乎是对数学模型的逐句直译。4.1 初始化问题与变量import pulp # 1. 初始化问题 # 参数问题名称 目标函数方向LpMinimize/LpMaximize 求解器 prob pulp.LpProblem(Nutrition_Diet_Problem, pulp.LpMinimize) # 2. 定义决策变量 # 参数变量名 下界 上界 变量类型连续‘Continuous’ 整数‘Integer’ 二进制‘Binary’ x1 pulp.LpVariable(Rice, lowBound0, upBound0.5, catContinuous) x2 pulp.LpVariable(Flour, lowBound0, upBound0.3, catContinuous) x3 pulp.LpVariable(Egg, lowBound0, upBound0.2, catContinuous) x4 pulp.LpVariable(Milk, lowBound0, upBound0.5, catContinuous) x5 pulp.LpVariable(Beef, lowBound0, upBound0.1, catContinuous) x6 pulp.LpVariable(Spinach, lowBound0, upBound0.4, catContinuous)这里我们直接在定义变量时通过lowBound和upBound设置了非负约束和上限约束非常方便。catContinuous表示是连续变量默认就是连续可省略。4.2 构建目标函数与约束# 3. 定义目标函数 prob 3.0*x1 2.5*x2 8.0*x3 5.0*x4 25.0*x5 2.0*x6, Total_Cost # 4. 添加约束条件 # 能量约束 prob 3500*x1 2800*x2 1500*x3 800*x4 2000*x5 200*x6 2000, Energy_Requirement # 蛋白质约束 prob 80*x1 40*x2 120*x3 60*x4 200*x5 20*x6 55, Protein_Requirement # 钙约束 prob 30*x1 20*x2 500*x3 1000*x4 50*x5 300*x6 800, Calcium_Requirement注意prob ...的语法它用于向问题中添加目标函数或约束。逗号后面的字符串是约束的名称强烈建议加上这在输出模型或调试时一目了然。4.3 求解与结果解析# 5. 求解问题 prob.solve(pulp.PULP_CBC_CMD(msgFalse)) # msgFalse关闭求解器日志输出使结果更清晰 # 6. 打印求解状态 print(f求解状态: {pulp.LpStatus[prob.status]}) # 常见状态 Optimal最优, Infeasible无解, Unbounded无界, Undefined未定义 # 7. 打印最优目标函数值 print(f最低总成本: {pulp.value(prob.objective):.2f}) # 8. 打印各变量的最优解 print(\n最优食材采购方案) for var in prob.variables(): print(f {var.name}: {var.varValue:.3f} 千克) # 9. 可选打印约束的松弛/剩余变量了解哪些约束是“紧”的刚好满足 print(\n约束松弛情况分析) for name, constraint in prob.constraints.items(): print(f 约束【{name}】: 松弛值 {constraint.slack:.6f}) # 对于‘’约束slack表示超过下限的量。slack0表示约束刚好满足紧约束。 # 对于‘’约束slack表示剩余上限的量。运行这段代码你将得到类似下面的输出求解状态: Optimal 最低总成本: 10.32 最优食材采购方案 Beef: 0.000 千克 Egg: 0.200 千克 Flour: 0.300 千克 Milk: 0.500 千克 Rice: 0.500 千克 Spinach: 0.400 千克 约束松弛情况分析 约束【Calcium_Requirement】: 松弛值 0.000000 约束【Energy_Requirement】: 松弛值 4350.000000 约束【Protein_Requirement】: 松弛值 49.000000结果解读求解成功状态是Optimal说明找到了全局最优解。成本与方案最低成本为10.32元。方案是大米0.5kg面粉0.3kg鸡蛋0.2kg牛奶0.5kg牛肉0kg菠菜0.4kg。注意到牛肉价格为25元/kg太贵最优解中完全没有采用。约束分析钙约束的松弛值为0说明这个约束是“紧”的即我们配餐的钙含量刚好达到800毫克的最低要求没有浪费。而能量和蛋白质约束的松弛值很大说明最优方案远远超过了最低需求这两个约束不是限制成本的关键因素。避坑指南prob.solve()默认会调用可用的第一个求解器。明确指定pulp.PULP_CBC_CMD()是个好习惯。msgFalse可以避免控制台输出大量求解器迭代日志让结果更干净。但当你遇到问题如无解时可以去掉msgFalse或设为True查看求解器的详细输出这有助于诊断模型哪里出了问题。5. 使用SciPy实现同一模型虽然我推荐PuLP但了解scipy.optimize.linprog的用法也很有必要特别是在你不想安装额外包或者需要与SciPy的其他优化算法协同工作时。它的接口是矩阵形式的需要我们将模型转化为标准型。线性规划的标准型是 [ \begin{aligned} \min c^T x \ \text{s.t.} A_{ub} x \leq b_{ub} \ A_{eq} x b_{eq} \ l \leq x \leq u \end{aligned} ] 注意所有约束都必须是“小于等于”或“等于”。我们的营养需求约束是“大于等于”需要乘以-1来转换方向。5.1 模型标准化我们的模型转换如下目标函数系数向量c:[3.0, 2.5, 8.0, 5.0, 25.0, 2.0]不等式约束A_ub * x b_ub我们没有“小于等于”的营养约束但“大于等于”的约束需要转换。原约束营养矩阵 * x 营养需求等价于-营养矩阵 * x -营养需求因此A_ub -1 * [[3500, 2800, 1500, 800, 2000, 200], [80, 40, 120, 60, 200, 20], [30, 20, 500, 1000, 50, 300]]b_ub -1 * [2000, 55, 800]等式约束A_eq * x b_eq本例没有设为None。变量边界bounds[(0, 0.5), (0, 0.3), (0, 0.2), (0, 0.5), (0, 0.1), (0, 0.4)]5.2 代码实现import numpy as np from scipy.optimize import linprog # 1. 定义目标函数系数c c np.array([3.0, 2.5, 8.0, 5.0, 25.0, 2.0]) # 最小化 c^T * x # 2. 定义不等式约束矩阵和向量 (A_ub * x b_ub) # 原约束营养 需求 - -营养 -需求 A_ub -1 * np.array([[3500, 2800, 1500, 800, 2000, 200], [80, 40, 120, 60, 200, 20], [30, 20, 500, 1000, 50, 300]]) b_ub -1 * np.array([2000, 55, 800]) # 3. 定义等式约束本例无 A_eq None b_eq None # 4. 定义变量边界 bounds [(0, 0.5), (0, 0.3), (0, 0.2), (0, 0.5), (0, 0.1), (0, 0.4)] # 5. 求解 result linprog(c, A_ubA_ub, b_ubb_ub, A_eqA_eq, b_eqb_eq, boundsbounds, methodhighs) # methodhighs 是推荐的最新方法 # 6. 结果解析 print(f求解成功: {result.success}) print(f求解状态: {result.message}) if result.success: print(f最低总成本: {result.fun:.2f}) print(\n最优食材采购方案) ingredients [大米, 面粉, 鸡蛋, 牛奶, 牛肉, 菠菜] for name, val in zip(ingredients, result.x): print(f {name}: {val:.3f} 千克) # 分析约束松弛情况对偶变量/松弛变量 print(f\n不等式约束的松弛量 (slack): {result.slack}) # slack为正表示约束有松弛为0表示约束是紧的。 # 注意这里的slack对应的是转换后的‘’约束。 # 要得到原‘’约束的超额量需要看slack的符号和意义。运行后结果应与PuLP一致。result.slack输出的是转换后A_ub * x b_ub的松弛量。对于我们的转换如果slack[i] 0说明原第i个“大于等于”约束是紧的刚好满足。核心技巧scipy.linprog的method参数很重要。老教程可能用methodsimplex或interior-point。从SciPy 1.6.0开始推荐使用methodhighs它封装了高性能的HiGHS求解器更稳定、更快。务必检查你的SciPy版本并优先使用highs。6. 实战进阶结果分析与灵敏度报告得到一个最优解只是开始。在数学建模中对解的分析和解释往往比求解本身更重要。线性规划求解器不仅能给出最优解还能提供丰富的灵敏度分析信息这在论文中是非常有价值的。6.1 影子价格对偶变量的经济学解释影子价格Shadow Price或称对偶变量Dual Variable指的是在最优解附近约束条件右端常数资源限量每增加一个单位时目标函数最优值的变化量。它衡量了该种资源的“边际价值”。在PuLP中可以方便地获取对偶变量# 接续第4节的PuLP求解代码 print(\n约束的影子价格对偶变量) for name, constraint in prob.constraints.items(): print(f 约束【{name}】: 影子价格 {constraint.pi:.6f})运行后你可能会得到约束的影子价格对偶变量 约束【Calcium_Requirement】: 影子价格 -0.010000 约束【Energy_Requirement】: 影子价格 -0.000000 约束【Protein_Requirement】: 影子价格 -0.000000解读钙约束的影子价格为-0.01这意味着如果钙的最低需求从800毫克增加到801毫克总成本将增加约0.01元因为是最小化问题影子价格为负表示成本增加。反过来如果钙需求放松成本可以降低。这说明了钙需求是当前方案的成本驱动因素之一。能量和蛋白质约束的影子价格为0这说明在当前最优解下这些资源是“富余”的增加或减少一点需求不会影响最优成本。这与我们之前看到的松弛值很大是一致的。在scipy.optimize.linprog中影子价格存储在result.ineqlin.marginals不等式约束和result.eqlin.marginals等式约束中。但需要注意符号约定scipy的对偶变量符号可能与PuLP相反解释时需要结合问题最小化和约束方向来理解。6.2 变量缩减成本与灵敏度范围缩减成本Reduced Cost可以理解为一个当前取值为0的变量即未被采用的方案其目标函数系数需要改善多少才能“挤进”最优解。对于非基变量通常为0缩减成本的绝对值表示该变量要变得有吸引力其单位利润需要提高最大化问题或单位成本需要降低最小化问题的量。在PuLP中变量的缩减成本可以通过var.dj获取print(\n变量的缩减成本) for var in prob.variables(): print(f 变量【{var.name}】: 取值{var.varValue:.3f}, 缩减成本{var.dj:.6f})对于我们的问题牛肉Beef的缩减成本会是一个正数意味着它的成本需要降低这个数值以上才会被考虑加入食谱。灵敏度范围Objective Coefficient Ranges和右端项范围Right-Hand Side Ranges则给出了在保持当前最优基即哪些约束是紧的、哪些变量在基中不变的情况下目标函数系数或资源限量可以变化的范围。这些信息对于评估模型稳定性至关重要。PuLP默认的CBC求解器输出不直接包含这些但高级的商业求解器如Gurobi或通过linprog(method‘highs’)的result对象中的某些属性可以间接分析。在建模竞赛中如果题目要求进行灵敏度分析应选用支持该功能的求解器或库并在论文中详细阐述其含义。7. 常见错误排查与模型调试心法即使经验丰富构建和求解线性规划模型时也难免出错。下面是我总结的几个最常见的问题及其排查思路。7.1 问题无解Infeasible这是最令人头疼的情况。PuLP状态为Infeasiblescipy的success为False且message提示不可行。可能原因与排查步骤检查约束方向这是新手最容易犯的错误。你是否不小心把“≤”写成了“≥”或者把等式约束“”用两个不等式约束“≤”和“≥”代替时两个常数项是否相等解决方案仔细核对每个约束的数学符号和代码中的逻辑运算符,,。检查数据单位约束条件中的数值单位是否一致例如需求是“克”资源含量是“毫克”这就差了1000倍。解决方案统一所有数据的单位并在模型注释中明确写明。检查约束是否自相矛盾例如一个约束要求 ( x_1 x_2 10 )另一个约束又要求 ( x_1 3 ) 且 ( x_2 4 )两者之和最大才7不可能大于等于10。解决方案手动检查约束的“松紧”程度或者尝试逐步注释掉部分约束看问题是否变得可行从而定位冲突的约束组。变量边界过紧变量的上界upBound设置得太小无法满足任何约束。解决方案检查边界值是否合理或者先放宽边界看是否可行。7.2 问题无界Unbounded状态为Unbounded。这意味着目标函数值可以无限优化对于最小化问题可以无限小对于最大化问题可以无限大通常是因为约束不够放任某些变量无限增大而不受惩罚。可能原因忘记添加关键的资源限制约束。约束条件中存在“≥”且右端项为负数同时对应变量的成本系数为负最小化问题导致变量越大成本越低。变量没有上界且其在目标函数和约束中的系数组合允许其无限增长。解决方案回顾实际问题检查是否所有有限的资源都已被建模为约束。确保变量有合理的上下界。7.3 求解器报错或结果异常数值问题如果数据尺度差异巨大如一个系数是0.001另一个是100000可能会引起求解器的数值不稳定。解决方案尝试对数据进行缩放Scaling例如将所有系数除以一个共同的因子使它们处于相近的数量级如1-1000之间。求解器选择scipy的某些老方法如‘simplex’对大型或病态问题可能失败。解决方案切换到methodhighs。结果非预期得到的最优解看起来很奇怪如所有变量都是0。首先检查目标函数的方向是否正确min还是max。然后检查约束是否过于严格导致唯一可行解就是原点。可以通过打印所有约束的松弛值看看是否所有约束都“紧”在0上。7.4 模型调试的“二分法”当模型复杂时定位错误很难。我常用的方法是从简到繁先构建一个只有目标函数和变量边界无其他约束的模型并求解。此时问题应该是无界的如果目标函数系数不为零或有明显 trivial 解如全0。这可以验证你的变量定义和目标函数基本正确。逐个添加约束每次只添加一个或一类约束求解并观察状态和结果的变化。当添加某个约束后问题突然变得不可行或无界那么这个约束就是问题的关键所在。输出模型文件PuLP可以将模型输出为.lp文件一种标准的线性规划格式方便人工检查。prob.writeLP(diet_problem.lp)用文本编辑器打开这个文件可以清晰看到所有变量、目标函数和约束是终极的调试手段。8. 举一反三线性规划在建模竞赛中的典型变体掌握了基础模型我们来看看它在竞赛中常见的几种变体这能极大拓展你的解题思路。8.1 多目标规划现实中我们往往不止一个目标。例如在配餐问题中我们既想成本最低又想口味评分最高。这就是一个双目标优化问题。严格的多目标优化没有单一最优解而是一组“帕累托最优解”。但在数学建模中一个实用的处理方法是线性加权法。思路将多个目标函数按重要性赋予权重合并为一个单一目标。 假设成本目标为 ( Z_1 \text{总成本} )评分目标为 ( Z_2 \text{总评分} )假设评分越高越好。我们可以构造新的目标函数 [ \min Z w_1 \cdot Z_1 - w_2 \cdot Z_2 ] 其中 ( w_1, w_2 ) 是权重且 ( w_1 w_2 1 )。因为 ( Z_2 ) 是最大化所以在最小化问题中前面加负号。通过调整权重比例可以得到不同的最优解从而分析成本与评分之间的权衡关系。8.2 整数规划与0-1规划当决策变量必须取整数时如购买设备的台数、是否选择某个方案问题就变成了整数规划IP。当变量只能取0或1时就是0-1规划常用于选择、指派、选址等问题。示例背包问题。有若干物品每个物品有重量和价值背包容量有限。如何选择物品装入背包使得总价值最大决策变量( x_i \in {0, 1} )表示是否选择第i个物品。目标函数( \max \sum v_i x_i )最大化总价值。约束条件( \sum w_i x_i \leq C )总重量不超过背包容量。在PuLP中只需在定义变量时设置catBinary或catInteger即可。但需要注意的是整数规划求解难度远大于线性规划求解时间可能随问题规模指数增长。在竞赛中如果数据规模不大可以尝试如果规模大可能需要设计启发式算法或使用专门的商业求解器。8.3 运输问题与指派问题这是两类经典的、具有特殊结构的线性规划问题有高效的专用算法但用通用线性规划求解器也能解。运输问题有多个产地供应量已知和多个销地需求量已知以及从每个产地到每个销地的单位运输成本。求总运输成本最小的调运方案。其约束矩阵非常稀疏大部分为0和1模型构建有固定套路。指派问题有n个人和n项任务每个人完成每项任务的效率或成本已知。要求每项任务只能由一个人完成每个人只能完成一项任务如何分配使总效率最高或总成本最低这本质上是0-1规划也可以用匈牙利算法等专门方法求解。对于这类问题在建模时巧妙定义下标变量如x[i][j]表示从产地i到销地j的运量利用循环来构建约束可以大大简化代码。8.4 分段线性化处理非线性线性规划要求目标函数和约束都是线性的。但现实中很多关系是非线性的如折扣、固定成本等。一个重要的技巧是分段线性化。例如采购成本可能随着采购量增加有折扣0-100件单价10元100件以上单价8元。这可以用引入辅助的0-1变量和连续变量来线性化。假设采购量为 ( x )总成本为 ( C )。 引入0-1变量 ( y_1, y_2 ) 表示处于哪个区间连续变量 ( x_1, x_2 ) 表示在各区间的采购量。 约束( x x_1 x_2 )( 0 \leq x_1 \leq 100y_1 )( 0 \leq x_2 \leq M y_2 ) M是一个很大的数表示上界( y_1 y_2 1 ) 只能处于一个区间( C 10x_1 8x_2 )这样就将一个分段线性函数转化为了混合整数线性规划MILP问题。虽然引入了整数变量但使得原本无法用线性规划处理的问题得以求解。这在解决涉及固定成本、启动成本、折扣策略的建模题时非常有用。经过以上八个部分的拆解你应该对如何使用Python实现线性规划并将其应用于数学建模有了一个从入门到进阶的全景认识。关键在于多练习从简单的例子开始亲手敲一遍代码理解每一个参数和结果的含义。当遇到一个新的优化问题时先问自己决策变量是什么目标是什么限制条件有哪些能否用线性或可线性化的关系来描述一旦能成功建模剩下的事情就交给PuLP或scipy吧。记住清晰的建模思维比复杂的代码技巧更重要。