简介运输问题与指派问题是运筹学中经典的资源优化分配模型广泛应用于物流调运、生产调度与任务分配场景。这份PPT学习教案面向运筹学初学者及相关专业学生系统讲解两类问题的基本概念、数学模型和电子表格建模方法重点涵盖产销平衡与不平衡运输问题的建模、Excel Solver求解、经典运输实例以及指派问题的匈牙利算法与多种变形问题的处理思路。资源为一份54页的PPT演示文稿文件总数1个压缩包大小328KB结构清晰便于按章节学习。目前已有50名用户浏览学习适合正在修读运筹学、管理科学或准备相关考试的人群。通过实际案例与逐步建模演示读者可掌握用线性规划工具解决资源配置问题的方法降低运营成本提升决策效率。1. 运输问题和指派问题这份PPT学习教案能帮你在调度上省出真金白银一个仓库要给三家门店补货每个门店的订货量不同每段路的运费单价也不同怎么安排调拨计划最省钱一个小团队要把五件事分给五个人每个人做每件事的成本不一样怎么分配总成本最低这类问题每天出现在物流调拨、人员排班、生产排产里运筹学给了它们两个标准名字运输问题和指派问题。很多课程会直接用一份运输问题和指派问题PPT学习教案来讲因为这两个模型结构简单、适合手算演示又能直接套到业务预算上。这篇文章会把它翻译成一套能落地的技术方案从供需矩阵建模到最小元素法和匈牙利算法的每一步再到我用代码验证手算时踩过的五个坑最后给你一个可以反复用的随机对拍脚本。适合正在备课的运筹学老师、做供应链或排班规划的从业者以及准备面试时捡起这两块知识的人。2. 运输问题的模型骨架从“产地-销地”表格到可求解的线性规划2.1 为什么运输问题必须压缩成“供需×运价”的矩阵形式运输问题最朴素的样子是有 m 个产地或仓库n 个销地或门店产地 i 的供应量是 aᵢ销地 j 的需求量是 bⱼ从产地 i 到销地 j 的单位运价是 cᵢⱼ问运量 xᵢⱼ 怎么取总运费最低。教案里几乎都会画一张标准的供需运价表把这三类信息放在同一个矩阵里因为这样做有实际好处决策变量只需要一个下标对 (i, j)不需要再单独维护一长串变量名手算时每一轮分配都在表上操作看得见进度用 Excel 规划求解或 Python 建模时数据可以直接按二维数组读入。下面这张表就是这类教案最常见的载体也是后续所有算法和代码的输入基础。销地1销地2销地3供应量产地142860产地263580需求量504050对应的线性规划模型很紧凑目标函数是最小化所有 cᵢⱼ × xᵢⱼ 的累加约束分两组一组保证每个产地运出的总量等于它的供应量另一组保证每个销地收到的总量等于它的需求量所有 xᵢⱼ 非负。这个形式虽然简单却是整个运输问题教案的核心骨架。你后面看到的表上作业法、西北角法、最小元素法本质上都是在用不同策略求这个模型的可行解和最优解。2.2 平衡表、虚拟节点和退化教案里容易被带过的三个前提真正动手算之前第一件事是检查产销是否平衡也就是总供应量是否等于总需求量。教案里的例题几乎都是平衡的但实际业务数据很少恰好相等。常见做法是不平衡时补一个虚拟节点总供应大于总需求时增加一个虚拟销地它吸收多余供应量运价全部填 0总需求大于总供应时增加一个虚拟产地它补足缺口运价同样填 0。加虚拟节点不是只在表上填一行/一列的活儿它意味着你的建模代码里也要动态扩展 supply 和 demand 两个字典。第二种容易带过的情况是退化。用表上作业法手算时基变量的数量应该等于 mn-1但当某一步同时划掉了一行和一列就会出现实际基变量比要求少一个的情况这就是退化。退化的后果很直接后面算检验数时闭合回路可能断在半路或者找不到完整的回路。遇到这种情况常规处理是在同时被划掉的行列交点处补一个运量为 0 的基变量占位相当于给这张表“续一条路”。我见过不少初学者卡在这里以为是自己计算错误其实只是缺少这个占位动作。第三种容易被带过的是初始可行解方法的选择。西北角法最简单从左上角开始分配但得到的初始解质量差最小元素法优先分配运价最低的格子初始解质量中等伏格尔法差值法考虑每行每列最小两个运价的差值初始解最接近最优但手算工作量最大。三种方法在教案里通常都会讲实际做题时优先推荐最小元素法因为它平衡了计算量和初始解质量做检验数修正时迭代次数不会太多。2.3 三种初始可行解方法怎么选西北角法、最小元素法、伏格尔法用 2.1 的表来对比三种方法的结果差异。西北角法从 (产地1, 销地1) 开始无视运价先把 50 单位填进去然后继续往右填最小元素法会先看到 2 这个最低运价把产地1到销地2的 40 单位优先分配伏格尔法会先算每行每列最短两个运价的差值再按差值从大到小优先分配。结果对比如下。方法初始方案可能后续迭代次数适合场景西北角法产地1-销地1 50产地1-销地2 10产地2-销地2 30产地2-销地3 50通常 2~3 次手算教学演示追求步骤简单最小元素法产地1-销地2 40产地1-销地3 20产地2-销地1 50产地2-销地3 30通常 0~1 次手算做题兼顾效率与质量伏格尔法更接近最优解但计算繁琐通常 0 次对初始解质量要求高、允许较长时间计算如果你只是验证自己手算对不对最小元素法加闭回路调整法就够了。真正做项目时我一般直接用求解器三种手算方法的意义在于它让你理解求解器内部在做什么遇到求解器给出反直觉结果时你能用手算快速定位是哪条约束出了问题。2.4 把最小元素法装进 PuLP一个可以直接改参数跑的最小例子模型层讲清楚了接下来的问题是怎么让机器算。这里用 Python 的 PuLP 库做演示因为它语法贴近自然语言适合把教案里的数学符号一对一翻译成代码。先安装依赖pip install pulp然后是完整的运输问题求解脚本数据直接沿用 2.1 的表格。from pulp import LpProblem, LpMinimize, LpVariable, LpStatus, value supply {A: 60, B: 80} demand {1: 50, 2: 40, 3: 50} cost { (A, 1): 4, (A, 2): 2, (A, 3): 8, (B, 1): 6, (B, 2): 3, (B, 3): 5, } prob LpProblem(Transportation, LpMinimize) # x[i, j] 表示从产地 i 运到销地 j 的数量非负连续变量 x LpVariable.dicts(x, cost.keys(), lowBound0, catContinuous) # 目标总运费最小 prob sum(x[i, j] * cost[i, j] for i, j in cost), 总运费最小化 # 供应约束每个产地运出的总量等于供应量 for i in supply: prob sum(x[i, j] for j in demand) supply[i], f产地{i}供应约束 # 需求约束每个销地收到的总量等于需求量 for j in demand: prob sum(x[i, j] for i in supply) demand[j], f销地{j}需求约束 prob.solve() print(求解状态:, LpStatus[prob.status]) for i, j in sorted(cost.keys()): if value(x[i, j]) 0: print(f{i} - {j}: {value(x[i, j]):.1f}) print(总运费:, value(prob.objective))运行后能看到类似下面的结果求解状态: Optimal A - 2: 40.0 A - 3: 20.0 B - 1: 50.0 B - 3: 30.0 总运费: 690.0代码逻辑说明LpVariable.dicts创建以 (i, j) 为键的决策变量字典lowBound0保证非负约束里 supply[i]和 demand[j]对应教案里的两组等式约束prob.solve()调用默认求解器CBC求最优解。值得注意的一点是如果 supply 和 demand 的总和不相等这段代码会直接报 Infeasible因为等式约束无法同时满足——这引出了下一章的坑不平衡问题必须先补虚拟节点。换业务数据时只需要改supply、demand、cost三个字典模型结构不需要动。3. 指派问题的本质与匈牙利算法从“人-事”矩阵到最小成本匹配3.1 指派是运输问题的一个特例为什么每行每列只有一个1指派问题的标准描述是有 n 个人、n 项任务第 i 个人做第 j 项任务的成本为 cᵢⱼ每个人只能做一项任务每项任务只能由一个人做问怎么指派总成本最小。如果把“人”看成产地把“任务”看成销地每个人的供应量是 1每个任务的需求量也是 1指派问题就是一个供应量和需求量全部为 1 的运输问题。区别在于决策变量 xᵢⱼ 只能取 0 或 1表示“指派”或“不指派”。这个看似微小的差别带来了两个重要性质。第一运输问题的解可能是小数比如某个产地往两个销地各运 0.5 的货但指派问题要求的是 0/1 整数解第二指派问题的约束矩阵是幺模矩阵单纯形法在顶点上自然得到整数解所以不需要额外加整数约束也能保证结果正确。教案里单独讲指派问题主要原因是它可以用更高效的匈牙利算法手算而不需要走完整的运输单纯形法。用代码描述就是把 3.2 的成本矩阵喂给linear_sum_assignment它会返回两组索引一组是人一组是任务配对之后就是最优指派。这正是“特例”带来的好处——运输问题要用通用线性规划指派问题有专用算法计算复杂度从多项式级别进一步降低到 O(n³)。3.2 匈牙利算法的三步掩码行归约、列归约、最小未覆盖值回路匈牙利算法手算步骤看起来像一套固定模板但每一步其实都有明确目的。以 3×3 成本矩阵为例任务1任务2任务3人1428人2635人3572第一步每一行减去该行的最小值。人1 行最小值为 2整行变成 [2, 0, 6]人2 行最小值为 3变成 [3, 0, 2]人3 行最小值为 2变成 [3, 5, 0]。第二步每一列减去该列的最小值。此时第一列最小值是 2第二列最小值是 0第三列最小值是 0所以只对第一列操作整列 2 减成 [0, 1, 1]得到任务1任务2任务3人1006人2102人3150第三步判断能否选出 3 个位于不同行不同列的零。这里人1可以选任务1或任务2人2选任务2人3选任务3已经能选出 3 个独立零直接得到最优解人1-任务1人2-任务2人3-任务3。如果独立零不够就需要用最少的直线覆盖所有零元素然后找到所有未被覆盖元素中的最小值让未覆盖的行减去这个值已覆盖的列加上这个值再重复第三步。这条计算路径的本质是行归约和列归约不改变最优解只是把成本矩阵整体做了平移让零元素暴露出来覆盖线的数量等于当前能匹配的最大数量如果覆盖线数小于 n说明还能通过调整继续增加匹配。手算时最容易被绕进去的是“最小未覆盖值”的调整方向记住一句话未被覆盖的行减已覆盖的列加其他元素不动。3.3 用 scipy 把匈牙利算法跑起来并把每一步输出出来做教学对照手算步骤清楚了但真要快速验证一份作业或业务方案直接调库更高效。SciPy 提供现成的匈牙利算法实现两行就能求最优指派。from scipy.optimize import linear_sum_assignment cost [ [4, 2, 8], [6, 3, 5], [5, 7, 2], ] row_ind, col_ind linear_sum_assignment(cost) print(人员索引:, row_ind) print(任务索引:, col_ind) print(最优成本:, sum(cost[r][c] for r, c in zip(row_ind, col_ind)))输出中row_ind和col_ind长度相等row_ind[0]与col_ind[0]构成第一组指派对依此类推。linear_sum_assignment默认求最小化如果做收益最大化只需要把成本矩阵全部取负号再传入即可这个细节会在下一章展开。它的时间复杂度是 O(n³)对几十人的排班问题完全够用几百人时也只需要几秒。如果你想在教学时看到中间过程可以用下面这段分步函数打印行归约和列归约后的矩阵让学生对照手算步骤import numpy as np def hungarian_steps(cost): M np.array(cost, dtypefloat) print(原始矩阵:\n, M) M M - M.min(axis1, keepdimsTrue) print(行归约:\n, M) M M - M.min(axis0, keepdimsTrue) print(列归约:\n, M) return M hungarian_steps(cost)axis1表示按行找最小值keepdimsTrue保证减法的广播维度正确axis0对应按列归约。这个函数只负责展示归约过程真正求最优解仍然用linear_sum_assignment两者配合可以完整还原教案里的手算演示。4. 运输问题与指派问题训练时的5个典型避坑细节4.1 不平衡运输问题直接套算法求解器返回无解现象用 2.4 的 PuLP 代码跑手头数据求解状态不是 Optimal而是 Infeasible手工检查供需表发现数量对不上。原因运输问题的等式约束要求每个产地的运出量恰好等于供应量、每个销地的收到量恰好等于需求量。总供应不等于总需求时这些等式约束不可能同时满足求解器给出的无解结论在数学上是正确的。解决建模前先做一次平衡检查并在不平衡时补虚拟节点。代码习惯是total_supply sum(supply.values()) total_demand sum(demand.values()) diff total_supply - total_demand if diff 0: demand[虚拟销地] diff else: supply[虚拟产地] -diff虚拟节点对应的运价全部填 0含义是“多余的货就地留存”或“缺的货由虚拟来源补足”。补完再跑模型得到的解才是业务上可执行的方案。4.2 指派问题要做最大化收益却忘了转换矩阵现象想把“谁做哪件事收益最大”的排班问题丢给linear_sum_assignment结果返回了一个很小、完全不合理的目标值仔细一看是把收益当成成本求了最小化。原因匈牙利算法针对最小成本设计。收益矩阵直接输入算法会优先匹配“成本最低”也就是收益最低的项方向完全相反。解决把收益矩阵转成成本矩阵再求解。常用两种做法cost -profit直接取负或者cost max(profit) - profit做平移。取负后的最小化等价于原收益的最大化平移法保证所有元素非负手算时更直观。转换完之后再用一个变量记录原始收益矩阵最后把目标值换算回去。4.3 退化解导致闭回路断在半路检验数算不出来现象表上作业法已经用最小元素法给出了初始方案但算检验数时某个非基变量无论如何画不出一条回到自身的闭合回路只能停在那里。原因这是退化问题。运输问题的基变量数量应该等于 mn-1但初始分配过程中如果某一步恰好同时划掉一行一列基变量数量就少了一个导致闭回路中必要的“中转格”缺失。解决在同时被划掉的行列交点处补一个运量为 0 的基变量占位让基变量数量恢复到 mn-1。这个 0 运量格子不改变总运输成本只负责把回路接通。手算时建议用铅笔做标记等检验数全部算完再决定是否去掉这个占位格。4.4 浮点数精度把零元素变成 1e-9程序判断全部失灵现象手算归约矩阵时明明有零元素但在 Python 里打印出来的矩阵是 0.0000001 或 8.881784197001252e-16导致判断“是否是零”的逻辑全部失效linear_sum_assignment也给出微妙偏差的结果。原因浮点数的二进制表示无法精确表达部分十进制小数减法和比较运算会累积微小误差。成本矩阵一旦来自浮点除法或带小数的单价这个问题几乎必现。解决在模型外面做一个容差判断。比如所有小于 1e-8 的值都当作 0 参与算法逻辑如果是整数成本矩阵建模前用round或int统一转换。遇到单价都是小数时可以先整体乘 100 转成整数算完再除以 100 还原。4.5 用 Excel 规划求解复现教案结果和手算对不上现象按教案步骤在 Excel 里搭好供需表、运价表、可变单元格和总运费公式点规划求解后要么提示“非线性条件不满足”要么结果和手算最小元素法得到的最优解不一致。原因Excel 规划求解默认条件是“非线性”或“自动选择”运输问题本质是线性规划求解器走了错误的算法分支另一个常见原因是可变单元格区域设置不规范把公式单元格也选进了可变区或者漏掉了“非负”约束。解决在规划求解参数的选项里勾选“采用线性模型”和“假定非负”约束条件分别写成供需等式约束和可变单元格的0。算完以后交叉验证先看求解状态是否显示“最优解”再看总运费是否等于手算结果。如果不等优先检查约束区域是否覆盖了完整的 mn 个供需等式。5. 用随机矩阵对拍两种实现验证手算结果的最佳习惯学了模型但又不敢完全相信手算结果的时候我习惯写一个随机对拍脚本随机生成多组成本和供需数据分别用 scipy 的匈牙利算法和 PuLP 的整数规划模型求解然后把两个最优成本做差值比较。这相当于给手算题提供了自动化的标准答案教学时也特别有用——你可以随手生成一套新题当随堂练习。import random from scipy.optimize import linear_sum_assignment from pulp import LpProblem, LpMinimize, LpVariable, value def verify_assignment(cost): row, col linear_sum_assignment(cost) scipy_cost sum(cost[r][c] for r, c in zip(row, col)) n len(cost) prob LpProblem(verify, LpMinimize) x LpVariable.dicts(x, [(i, j) for i in range(n) for j in range(n)], catBinary) prob sum(x[i, j] * cost[i][j] for i in range(n) for j in range(n)) for i in range(n): prob sum(x[i, j] for j in range(n)) 1 for j in range(n): prob sum(x[i, j] for i in range(n)) 1 prob.solve() assert abs(scipy_cost - value(prob.objective)) 1e-6 print(对拍通过最优成本:, scipy_cost) for _ in range(50): cost [[random.randint(1, 20) for _ in range(5)] for _ in range(5)] verify_assignment(cost)对拍的价值不只是让两个库的结果互相确认更在于帮你发现建模时的隐性问题。比如我踩过的坑某个版本里我在 PuLP 约束中少写了一条“每列恰好一个 1”匈牙利算法自动满足该约束两边结果长期一致但当我换成非方阵数据时scipy 正常跑PuLP 却给出错误结果对拍才把这条缺失的约束揪出来。从那以后我讲这份教案时任何新跑的用例都必须经过随机对拍再下结论。这套习惯同样适用于运输问题用 2.4 的 PuLP 模型作为基准把它和 scipy 里的线性规划接口或 Excel 规划求解结果互相校验能覆盖大部分手算错误。“程序跑通了”从来不是终点“程序和人算结果一致”才是真正的验收标准。希望帮到你。本文还有配套的精品资源点击获取
