第20章 · 播客 第1集
应用数学 · 图论应用：关键路径与网络优化
🎙️ 本集播客：第1集：从运筹学四步骤切入，把关键路径法 CPM 拆到零件级——AOV 网与 AOE 网逐字辨析，Ve、Vl、e、l 四个量的定义与两步递推，关键活动判据 l(i)=e(i) 与总时差，网络优化三种口径，直接费用率公式的分子分母方向，最后把 25 个月工期那道综合实例的三问逐步算完。 语音由微软 Edge 神经网络语音预生成（女声·晓伊，男声·云希）。点击下方任意对话可直接从该句开始播，当前句朗读时下一句已预先加载，无缝衔接。
明
阿明
师姐，我对着一张工程网络图算了半小时，越算越邪门——完成整个工程的最少时间，怎么会是图上最长的那条路？最少不该配最短吗？
雅
小雅
恭喜，你一脚踩在第 20 章最大的陷阱上。这章叫应用数学，原文说：应用数学虽然涉及的内容很多，但经常考查的知识点却往往集中于运筹方法与数据建模。本集只吃计算题最密的一块——网络计划技术，也就是关键路径法。
明
阿明
先给我垫个底，运筹学到底是干什么的？
雅
小雅
原文定义要记准：运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决——前者提供模型，后者提供理论和方法，最后提出综合性的合理安排，以达到最好的效果。
明
阿明
听着挺虚，有没有可以直接背的固定套路？
雅
小雅
有，而且是送分题。运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制订方案、建立模型、制订解法。四个词，顺序背死。
明
阿明
我复述一遍：目标、方案、模型、解法。可为什么不是先建模型再定目标？总觉得模型是地基。
雅
小雅
因为模型是为目标服务的，连要优化什么都没定，建出来的模型优化谁？考场上就是四个词洗牌：「建立模型」排在「确定目标」前面的选项直接划掉，「制订解法」必须垫底，一眼毙。
明
阿明
记住了。那网络计划技术呢？
雅
小雅
原文原话：用网络分析的方法编制的计划称为网络计划，是一种编制大型工程项目进度计划的有效方法；计划借助于网络表示各项工作与所需时间及相互关系，通过网络分析研究工程费用与工期的关系，并找出关键路径——这种方法称为关键路径法，英文 Critical Path Method，缩写 CPM。
明
阿明
然后就是 AOV 网和 AOE 网这对双胞胎了。我每次都认反。
雅
小雅
别靠感觉，靠拆字母。在有向图中，若以顶点表示活动、弧表示活动之间的先后关系，这样的图简称为 AOV 网，A-O-V 是 Activity On Vertex，活动在顶点上；若以顶点表示事件、弧表示活动、权表示完成该活动所需的时间，这样的图称为 AOE 网，A-O-E 是 Activity On Edge，活动在边上。这个时间原文叫活动历时或持续时间。
明
阿明
那我这么记：V 是 Vertex 顶点，活动趴在顶点上，所以 AOV 网的顶点是活动；E 是 Edge 边，活动趴在边上，所以 AOE 网的顶点只能是事件。
雅
小雅
对，一句话推完，不用死记。再补一层辨析：原文描述 AOV 网只说「弧表示活动之间的先后关系」，没有提权；权是 AOE 网才有的，而且含义被钉死为完成该活动所需的时间。原文图 20-1 就是一个具有 10 个活动的工程的 AOE 网，有 7 个顶点表示事件 1 到 7，其中 1 表示工程开始状态，7 表示结束状态。
明
阿明
10 个活动配 7 个事件，数量对得上。那回到我开头那个邪门问题——关键路径到底怎么定义？
雅
小雅
原文一句话，一个字都别改：因 AOE 网中的某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，也叫临界路径，关键路径上的活动为关键活动。
明
阿明
「最少时间」等于「最长路径」，这话说出来就像绕口令。
雅
小雅
把「可以并行地进行」读进去就通了：几件活动同时开工，整体何时结束，由最慢的那一串决定，跟散场看最长的队一样。想让工程更快，就得砍最长那条路；砍短的路没用，它本来就在等别人。
雅
小雅
这题选项肯定往「最短」上引，四个干扰项一次讲全。「从源点到汇点的最短路径」错在方向反了；「从开始顶点到结束顶点的最长路径」才是对的；「包含活动数最多的路径」错在偷换度量：比的是时间总长，不是活动个数；「所有边权值之和最小的路径」恰是最长的反面。记一句：比时间总长，取最大，不数个数。
明
阿明
定义我服了。可给我一张网络图，我怎么把关键活动一个个找出来？
雅
小雅
原文说得很清楚：为了找出给定的 AOE 网络的关键活动，先定义几个重要的量，一共两组四个。Ve(j) 和 Vl(j)，V 是顶点，这一组是顶点 j 事件的最早、最迟发生时间；e(i) 和 l(i)，小写对应活动，这一组是活动 i 的最早、最迟开始时间。
明
阿明
大写带 V 的管事件，小写光身子的管活动。那它们各自怎么求？
雅
小雅
Ve(j)：从源点 V1 到某顶点 Vj 的最长路径长度，称为事件 Vj 的最早发生时间。又是「最长」——所有指向这个事件的活动都得干完，它才算发生。还有句桥梁句要背：Ve(j) 也是以 Vj 为起点的出边所表示的活动 ai 的最早开始时间 e(i)。
雅
小雅
对，e(i) 不用另算，抄 Ve 就行。剩下两个：Vl(j) 是在不推迟整个工程完成的前提下，一个事件 Vj 允许的最迟发生时间；l(i) 有公式要能默写——l(i) 等于 Vl(j) 减去 ai 所需时间，其中 j 为 ai 活动的终点。注意 j 是终点不是起点，写反全错。
明
阿明
为什么是拿终点的 Vl 往回减？
雅
小雅
活动最晚何时动手是被终点事件卡死的：终点最迟得在 Vl(j) 发生，活动要花掉自己的历时，开工的最后期限就是终点期限倒扣掉工期，天然是倒推。判据原文原句：满足条件 l(i) 等于 e(i) 的活动为关键活动，关键活动所组成的路径称为关键路径。
明
阿明
这题四个选项我猜是：e 大于 l、e 小于 l、l 等于 e、l 减 e 最大。
雅
小雅
答案就是 l(i) 等于 e(i)。前两个直接否掉：最迟开始时间不可能早于最早开始时间，l 永远大于等于 e，e 大于 l 根本不存在；e 小于 l 说明有富余，那正是非关键活动。最狠的是「l(i) 减 e(i) 最大」——这个差值叫活动的总时差，原文括号里给了定义：最迟开始时间减最早开始时间。关键活动是总时差等于零，不是最大；总时差最大的恰恰是最闲的活动。
明
阿明
总时差等于零和 l 等于 e 是一回事。那四个量的计算顺序有讲究吗？
雅
小雅
原文两步，方向相反。第一步，由源点开始向汇点递推算 Ve，其中 E1 是网络中以 Vj 为终点的入边集合——算最早看谁流进来；第二步，由终点即汇点开始向源点递推算 Vl，其中 E2 是以 Vj 为起点的出边集合——算最迟看往哪流出去。一句话：Ve 正推看入边，Vl 倒推看出边。
明
阿明
算完怎么读出结论？
雅
小雅
算完怎么读出结论？原文做法：根据以上变量列出一张表格，逐个检查。图 20-1 的结论：关键活动为 a1、a2、a4、a8 和 a9，对应的关键路径有两条，分别是 V1 到 V2 到 V5 到 V7，和 V1 到 V4 到 V5 到 V7，长度都是 10。注意最长可以并列，两条都得盯住，压缩工期的例题就栽在这上面。
雅
小雅
没有，拿到关键路径就完事了吗？没有。原文说在得到了关键路径后，就相当于得到了项目的计算工期和一个初始的计划方案，还要根据进度、资源、费用等目标调整完善，即网络优化，共三种。第一种时间优化：可采取技术措施；或组织措施——充分利用非关键活动的总时差，合理调配技术力量及人财物，缩短关键活动的持续时间；还可改变工作之间的逻辑关系，采用并行方式缩短工期。
明
阿明
时间-资源优化的坑在哪？
雅
小雅
原文做法三条：优先安排关键活动所需要的资源；利用非关键活动的总时差，错开各活动的开始时间，拉平资源需要量的高峰；在确实受到资源限制，或者在考虑综合经济效益的条件下，也可以适当地推迟工程完工时间。题目的杀招是把第一条改成「优先安排非关键活动所需要的资源」，就多一个「非」字——资源永远先给没有时差、一卡就卡总工期的关键活动；第三条看着刺眼，却是原文允许的，别选。
明
阿明
第三种时间-费用优化，就是那个费用率公式吧？
雅
小雅
两个概念打底：完成工程的费用分直接费用和间接费用；项目有不可压缩的最短时间，称为极限时间，指采取一切可能的技术和组织措施后可能达到的最短时间。公式必须默写：直接费用率等于极限时间的活动直接费用，减去正常时间的活动直接费用，除以正常时间减去极限时间。分子是费用差、分母是时间差，且方向相反——分子极限在前、分母正常在前，这样才得正数，即每压缩一天多花的钱。做题时优先压缩直接费用率最小的关键活动。
明
阿明
25 个月那道综合实例，逐步过一遍？
雅
小雅
题面：某信息系统开发工程合同工期 25 个月。第一问：图里有 2 条虚线弧，表示虚活动，即不需要任何资源（时间、费用等）、只表示逻辑关系的活动。关键路径为 A 到 E 到 H 到 I 到 K，长度 25，正好等于合同工期，满足要求；A、E、H、I、K 是重点控制对象，因为它们是关键工作。
明
阿明
第二问，执行 7 个月后 C 和 D 完成、E 拖后 2 个月，慌吗？
雅
小雅
判断原则就两条：分析拖延工作是否在关键路径上，拖延的时间是否超过工作的总时差。C 和 D 已完成且不在关键路径上，是干扰项。E 是关键工作，其总时差为 0——这就是 l 等于 e 的另一种说法，一天都拖不起，所以 E 拖延 2 个月将影响总工期 2 个月。保证总工期不延长的调整方法有 2 种：一是改变某些工作之间的逻辑关系，二是缩短某些工作的持续时间。
明
阿明
第三问掏钱压缩，先挑最便宜的 K？
雅
小雅
候选逐级淘汰：只能调整关键路径上的 A、E、H、I、K；从第 7 个月开始时 A 已完成；表里 E 不可以压缩，剩 H、I、K。直接费用率最小的是 K，原计划 6 个月、极限 4 个月，可压缩 2 个月，看似正好，但原文提醒：K 压缩 2 个月会引起关键路径的变化。K 压缩 1 个月后关键路径就有 2 条：A-E-H-I-K 和 A-E-H-I-L，再压 K 全是白花钱。最终把 I 压缩 1 个月，费用 4.5 万元，所以最优方案是压缩 K、I 各 1 个月，增加费用 4.0 加 4.5 等于 8.5 万元。口诀：每压一步重算关键路径，下一刀落在关键路径的公共活动上。
明
阿明
本集的账给我盘一下？
雅
小雅
必背清单：运筹学四步骤——确定目标、制订方案、建立模型、制订解法；AOV 网顶点是活动、弧是先后关系，AOE 网顶点是事件、弧是活动、权是活动历时；关键路径是开始顶点到结束顶点的最长路径，完成工程的最少时间就是它的长度，可多条并列；Ve 由源点正推、看入边集合 E1，Vl 由汇点倒推、看出边集合 E2；l(i) 等于 Vl(j) 减 ai 所需时间，j 取终点；
雅
小雅
l(i) 等于 e(i) 的是关键活动，差值是总时差；时间-资源优化优先安排关键活动资源；直接费用率分子是极限减正常的费用差、分母是正常减极限的时间差。下一集讲线性规划与决策论——图解法、最优解为什么落在可行域顶点、无界解和无可行解说明模型哪里出错，再上不确定型决策的五种准则。先把那两条关键路径在纸上画一遍再来。