【虚构案例声明】 本课程中的"美好家园"物业集团、"清华园社区"、"智慧邻里2.0"项目及全部人物均为教学所用的虚拟项目与虚构人物，详见第 01 讲首次声明。
一、上节作业讲评
1.1 路、线、人
上一讲周总在董事会上提了三个问题，财务总监说是运筹学的事。三个问题对应教材 21.2 节三类问题：
推广团队从集团出发跑五个小区路最短，是"路"的问题，教材叫最短路径问题，有两种解法：分阶段的用动态规划的逆序法，一般的有向图用图与网络的标号法。
数据中心到五十个小区的专线怎么拉总费用最低，是"线"的问题，教材叫最小生成树问题，用破圈法：所有小区都连上，不能有圈，总长度最小。
四个项目经理分配五个小区推广任务总工期最短，是"人"的问题，教材叫指派问题，用匈牙利法：每人一件任务，让总时间最少。注意教材的指派问题是 n 个人对 n 项任务，四个人五个任务要先补一个虚拟人，这是本讲第五节会讲的细节。
很多同学第三题写了"最短路径逆序求解思路"举的是导航软件的例子，方向对。逆序法的核心是从终点往回算：先算最后一站到终点的最短距离，再算倒数第二站经过最后一站到终点的最短距离，一层层往前推到起点。它的好处是教材那句"除了得到从起点至终点的最短路径以外，还得到了从其他各点到终点的最短子路径及距离"。
这一讲把 21.2 整节过一遍。运筹学在高项综合知识里每年一到两道，2025 年上半年第 2 批的案例分析题里还出了一道指派问题，分值不低。它的特点是算法多、每种算法套路固定，考的是"认出这是哪类问题，会按步骤算"。
二、运筹学在高项里考什么
2.1 七类问题一张地图
教材口径：运筹学是一门基础性的应用学科，主要研究系统最优化的问题，通过对建立的模型进行求解，为决策者进行决策提供科学依据。教材 21.2 节讲了七个小节：线性规划、运输问题、指派问题、动态规划、图与网络、博弈论、决策分析。
考试怎么落：
| 小节 | 教材例题 | 近年真题 | 考法 |
|---|---|---|---|
| 线性规划 | 例 21-7 建模、例 21-8 图解法 | 偶有两变量图解 | 三要素、可行域顶点 |
| 运输问题 | 例 21-9 表上作业法 | 2022 上第 68 题 | 最小运费 |
| 指派问题 | 例 21-10、21-11 匈牙利法 | 2025 上第 2 批案例题、2026 上第 1 批考生回忆 | 最小总费用或总时间 |
| 动态规划 | 例 21-12 最短路径、21-13 资源分配 | 最短路径类 | 逆序法 |
| 图与网络 | 例 21-14 标号法、21-15 破圈法 | 2022 上第 69 题 | 最短路、最小生成树 |
| 博弈论 | 例 21-16、21-17 | 2024 上第 1 批第 66 题 | 赢得矩阵鞍点 |
| 决策分析 | 例 21-18 至 21-24 | 2022 下第 69 题、2023 下第 4 批第 20 题、2024 上第 1 批第 31 题 | 悔值法最常考 |
决策分析的悔值法三年考了三次，指派问题两年考了两次，这两个是重点。
三、核心内容精讲：线性规划
3.1 三要素与图解法
教材口径：线性规划主要研究和解决两类问题：一是在有限资源（人力、物力、财力）条件下，如何制订一个最优的经营方案，以取得最佳的经济效益；二是在任务确定的前提下，怎样合理安排，统筹规划，使完成该项任务所消耗的资源最少。线性规划问题"是一类特殊的极值问题，它是在一定的线性约束条件下，追求某一个目标函数的最大值或最小值"。数学模型包含三个要素：决策变量、目标函数和约束条件。
建模三步按教材例 21-7：第一步确定决策变量，教材的口诀是"问什么，设什么"，问如何安排四种产品的产量，就设四个产量为变量；第二步确定目标函数，利润最大就是各产品单位利润乘产量求和取最大；第三步确定约束条件，两种原料的供应量有限，每种原料写一个不等式，再加上产量非负。
图解法只适用于两个变量。教材例 21-8：目标函数是第一个变量加三倍第二个变量取最大，约束条件画在坐标系里得到一个凸多边形，这个凸多边形就是可行域，"凸多边形上任一点的坐标都满足约束条件"。找最优解的办法是让目标函数等于一个参数，得到一组平行的等值线，"当 S 值越大，直线离开原点越远"，找那条与可行域相交而又离原点最远的等值线，交点就是最优解。教材算出最优解在顶点 B（1，4），最大值 13。
考试的两变量题记一个结论：最优解一定在可行域的顶点上。机考里把每个顶点代入目标函数，取最大或最小的那个，比画等值线快。三个以上变量考试不会让你算，只考三要素的辨认。
3.2 智慧邻里2.0 的线性规划
李经理做过一道：二期推广团队每月有 200 个人天，每个小区上线要 8 个人天现场加 4 个人天远程支持，远程团队每月只有 60 个人天；每上线一个大型小区月度收入增加 3 万，小型 2 万，大型现场 8 人天远程 4 人天，小型现场 5 人天远程 2 人天。问每月上线多少大型多少小型收入最大。决策变量是大型数量和小型数量；目标函数是 3 倍大型加 2 倍小型取最大；约束是 8 倍大型加 5 倍小型不超过 200，4 倍大型加 2 倍小型不超过 60，两个数非负。画出来是两条直线围出的四边形，顶点代入，答案在两条约束线的交点附近。这题不需要你算到底，需要你能把周总一句话翻译成三要素。案例题里如果出现"如何安排使收入最大"，答题第一步就是写出三要素。
四、核心内容精讲：运输问题
4.1 表上作业法
教材口径：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总运输费用最低的方案。教材的解法叫表上作业法，分三步：确定初始解、方案检验、方案调整。
第一步确定初始解，教材用的是最小元素法：从运价表里找最低运价，先把那个产地的货给那个销地，能给多少给多少；供应完了就划掉那一行，需求满足了就划掉那一列；再从没划掉的运价里找最小的，一步一步直到全部划完。例 21-9 三个产地四个销地，最低运价 1 是产地一到销地四，产地一供应 3 全给销地四，划掉产地一那行，销地四还差 1；再找最小运价 4，产地二给销地四 1，划掉销地四那列；再找 5，这样下去得到初始方案，总运费 79。
教材有三条注意：填数的格子应该恰有 m 加 n 减 1 个，本例 3 加 4 减 1 等于 6 个，这些是基变量；几个格子运价相等都最小时任选一个；选定一个最小元素后如果该行产量恰好等于该列销量，要在相应行或列的任一空格填一个 0 当有数格看待，保证填数格仍是 m 加 n 减 1 个。
第二步方案检验用位势法：把有调运数的运费加圈，同一行或同一列各数加上或减去一个相等的数，使圈中数字都变成 0，这时表中其他各数便是检验数的相反数。检验数全部非正，方案最优；有正的，进入第三步。