简介：运输问题与指派问题是运筹学中经典的资源优化分配模型，广泛应用于物流调运、生产调度与任务分配场景。这份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 | 供应量 | |
|---|---|---|---|---|
| 产地1 | 4 | 2 | 8 | 60 |
| 产地2 | 6 | 3 | 5 | 80 |
| 需求量 | 50 | 40 | 50 |
对应的线性规划模型很紧凑：目标函数是最小化所有 cᵢⱼ × xᵢⱼ 的累加；约束分两组，一组保证每个产地运出的总量等于它的供应量，另一组保证每个销地收到的总量等于它的需求量，所有 xᵢⱼ 非负。这个形式虽然简单，却是整个运输问题教案的核心骨架。你后面看到的表上作业法、西北角法、最小元素法，本质上都是在用不同策略求这个模型的可行解和最优解。
2.2 平衡表、虚拟节点和退化：教案里容易被带过的三个前提
真正动手算之前，第一件事是检查产销是否平衡，也就是总供应量是否等于总需求量。教案里的例题几乎都是平衡的，但实际业务数据很少恰好相等。常见做法是不平衡时补一个虚拟节点：总供应大于总需求时，增加一个虚拟销地，它吸收多余供应量，运价全部填 0；总需求大于总供应时，增加一个虚拟产地，它补足缺口，运价同样填 0。加虚拟节点不是只在表上填一行/一列的活儿，它意味着你的建模代码里也要动态扩展 supply 和 demand 两个字典。
第二种容易带过的情况是退化。用表上作业法手算时，基变量的数量应该等于 m+n-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(), lowBound=0, cat="Continuous") # 目标：总运费最小 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) 为键的决策变量字典，lowBound=0保证非负；约束里== 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 | |
|---|---|---|---|
| 人1 | 4 | 2 | 8 |
| 人2 | 6 | 3 | 5 |
| 人3 | 5 | 7 | 2 |
第一步，每一行减去该行的最小值。人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 | |
|---|---|---|---|
| 人1 | 0 | 0 | 6 |
| 人2 | 1 | 0 | 2 |
| 人3 | 1 | 5 | 0 |
第三步，判断能否选出 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, dtype=float) print("原始矩阵:\n", M) M = M - M.min(axis=1, keepdims=True) print("行归约:\n", M) M = M - M.min(axis=0, keepdims=True) print("列归约:\n", M) return M hungarian_steps(cost)axis=1表示按行找最小值，keepdims=True保证减法的广播维度正确；axis=0对应按列归约。这个函数只负责展示归约过程，真正求最优解仍然用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 退化解导致闭回路断在半路，检验数算不出来
现象：表上作业法已经用最小元素法给出了初始方案，但算检验数时，某个非基变量无论如何画不出一条回到自身的闭合回路，只能停在那里。
原因：这是退化问题。运输问题的基变量数量应该等于 m+n-1，但初始分配过程中如果某一步恰好同时划掉一行一列，基变量数量就少了一个，导致闭回路中必要的“中转格”缺失。
解决：在同时被划掉的行列交点处补一个运量为 0 的基变量占位，让基变量数量恢复到 m+n-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。算完以后交叉验证：先看求解状态是否显示“最优解”，再看总运费是否等于手算结果。如果不等，优先检查约束区域是否覆盖了完整的 m+n 个供需等式。
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)], cat="Binary") 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 规划求解结果互相校验，能覆盖大部分手算错误。“程序跑通了”从来不是终点，“程序和人算结果一致”才是真正的验收标准。希望帮到你。
本文还有配套的精品资源，点击获取
