24-应用数学（第24小时）
软考-系统架构设计师 | 第5篇 架构设计补充知识 出题形式：上午选择题 分值占比：2-3 分（运筹学）
0. 考点分析
- 图论之最小生成树（普里姆 vs 克鲁斯卡尔）
- 图论之最大流量（路径求和 + 残余流量法）
- 线性规划（图解法 + 联立方程组法）
- 动态规划（装货最大价值问题）
- 决策分析（决策树 + EMV期望货币值）
- 不确定型决策（乐观/悲观/后悔值/折中/等可能 5 种准则）
1. 核心知识点
1.1 图论之最小生成树
定义
- 生成树：包含图中所有顶点的树
- 最小生成树：在连通的带权图的所有生成树中，权值和最小的那棵
- 边数 = 顶点数 - 1
两种算法
- 普里姆（Prim）算法：从某一顶点出发逐步扩展（适合稠密图）
- 克鲁斯卡尔（Kruskal）算法：按边长从小到大依次选取（不形成闭环），常考
典型解法步骤（Kruskal）
- 将所有边按权值从小到大排序
- 依次选取权值最小的边
- 若形成闭环则舍弃
- 直到选取了 n-1 条边（n 为顶点数）
1.2 图论之最大流量
定义
- 最大流量问题是一个特殊的线性规划问题
- 适用于：道路运输能力、管道流量等问题
解题步骤
- 找出一条从源到汇的路径
- 该路径最大流量 = 各段流量的最小值
- 该路径上各段流量都减去已用流量
- 流量为 0 的线段删除（断开）
- 重复 1-4 步直到无可通路径
- 总最大流量 = 各条路径最大流量之和
1.3 线性规划
定义
- 在有限资源条件下，如何有效使用这些资源达到预定目标
- 数学上：在一组约束条件下寻找目标表达式的极值问题
两种解法
| 方法 | 特点 | 适用 |
|---|---|---|
| 图解法 | 直观、有解/无解/最优解位置一目了然 | 2 变量、约束较少（计算量 O(n)） |
| 联立方程组法 | 联立直线交点，逐个验证 | 3 变量及以上（计算量 O(n²)） |
线性规划问题解的可能
- 唯一最优解：在解区间多边形的某个顶点上
- 无穷多最优解：能找到两个不同的最优解
- 无界解：有无穷多解但无最优解（缺少必要约束）
- 无可行解：约束条件互相矛盾
整数解
- 联立求出的解若非整数，需枚举相邻整数验证（如 P1 不符合 → P3(1,4) 符合）
1.4 动态规划
定义
- 将问题分解为更小的、相似的子问题
- 存储子问题的解避免计算重复
- 解决最优化问题
典型应用
- 装货最大价值问题：
- 计算每种货物的单位利润（总利润/重量）
- 按单位利润从大到小依次装
- 直到装满载重限制
- 剩余空间用次优物品填充
1.5 决策分析
期望货币值（EMV）
- EMV = Σ(每种可能结果的收益 × 发生概率)
- 通过比较各方案的 EMV 决策
- 决策树最左边做决策 → 从右向左逐层计算化简
解题技巧
- 画决策树：方框节点（决策点）→ 圆圈节点（机会点）
- 从右向左逐层计算每个机会点的 EMV
- 决策点选择 EMV 最大的方案
1.6 不确定型决策（5 种准则）
| 准则 | 别名 | 原则 |
|---|---|---|
| 乐观主义 | 最大最大 | 大中取大（每个方案选最大，再选最大） |
| 悲观主义 | 最大最小 | 小中取大（每个方案选最小，再选最大） |
| 折中主义 | — | 乐观系数 α：H = α·最大 + (1-α)·最小 |
| 等可能性 | Laplace | 各状态概率相等，求平均 |
| 后悔值 | 最小最大后悔值 | 见下 |
后悔值准则（重点）
- 取每种自然状态的最高值作为理想目标
- 用最高值 - 该状态其他值 = 后悔值
- 每个方案中取最大后悔值
- 在各方案的最大后悔值中取最小值作为决策
2. 关键概念速查
| 概念 | 公式/方法 | 适用场景 |
|---|---|---|
| 最小生成树 | Kruskal 按边长排序 | n 个顶点选 n-1 条边不形成环 |
| 最大流量 | 路径流量 = min(各段流量)，求和 | 运输网、管道网 |
| 线性规划 | 图解法/联立方程组 | 资源约束下求极值 |
| 动态规划 | 分解子问题 + 记忆 | 装货最大价值 |
| EMV | Σ(收益×概率) | 概率已知 |
| 后悔值 | max(state) - 实际值 | 概率未知 |
3. 典型例题
题目1（最小生成树）：某小区有七栋楼房①~⑦，各楼房之间可修水管路线的长度已标记在连线旁。为修建连通各个楼房的水管，该小区内部水管的总长度至少为（ ）百米。 A. 20 B. 21 C. 24 D. 27
答案：A（20 百米）
解析：采用 Kruskal 算法：
- 找所有长 2 的边：①③、④⑥ → 可行
- 找所有长 3 的边：①⑦、③⑥ → 可行
- 找所有长 4 的边：①② 和 ②⑥，全部连接会闭环，舍弃 ①②
- 找所有长 5 的边：③④，连接形成闭环，舍弃
- 找所有长 6 的边：①④（形成闭环，舍弃）、⑤⑥（可行）
- 总长度 = 2×2 + 3×2 + 4 + 6 = 20 百米
题目2（最大流量）：某运输网从节点①到节点⑥的最大运输能力可以达到（ ）万吨每小时。
- 选项：A. 26 B. 23 C. 22 D. 21
答案：B（23 万吨）
解析：依次找路径：
- 路径 ①③⑤⑥：最大 10 万吨（①③之间断开）
- 路径 ①②⑤⑥：最大 6 万吨（①②之间断开）
- 路径 ①④⑥：最大 5 万吨（④⑥之间断开）
- 路径 ①④③⑤⑥：最大 1 万吨
- 路径 ①④②⑤⑥：最大 1 万吨
- 总最大流量 = 10 + 6 + 5 + 1 + 1 = 23 万吨
题目3（线性规划）：某工厂生产甲、乙两种产品，已知约束 2x+3y≤14, 8x≤16, 3y≤12, 求利润最大方案。 A. 生产甲2套，乙3套 B. 生产甲1套，乙4套 C. 生产甲3套，乙4套 D. 生产甲4套，乙2套
答案：B（生产甲1套，乙4套）
解析：
- 联立 ①+② 求得 (x=2, y=10/3) → 利润 14，但 y 不是整数
- 联立 ②+③ 求得 (x=2, y=4) → 不满足 ①
- 联立 ①+③ 求得 (x=1, y=4) → 满足约束，利润 = 2+12 = 14
整数约束下最优解为 (1, 4)，利润 14 万元。
题目4（动态规划）：用 10 吨卡车装运货物，各种货物的重量与利润见表。最大总利润为（ ）元。
- 选项：A. 530 B. 534 C. 536 D. 538
答案：D（538 元）
解析：计算单位利润（利润/重量）：
- A: 53/1=53, B: 104/2=52, C: 156/3=52
- D: 216/4=54（最大）, E: 265/5=53, F: 318/6=53
选单位利润最大的 D 装 2 件（8 吨），剩余 2 吨选单位利润次大的 A 装 2 件（2 吨），共 10 吨。 总利润 = 216×2 + 53×2 = 432 + 106 = 538 元
题目5（决策分析）：某货运公司要从A地向B地发送价值 9000 元货物。走陆路成本 1000 元；走水路成本 700 元，但遇暴风雨（概率 15%）会损失 10% 货物。应选哪个方案？
答案：走水路
解析：
- 走水路期望成本 = 700×85% + 1600×15% = 595 + 240 = 835 元
- 走陆路期望成本 = 1000×100% = 1000 元
- 走水路期望成本 < 走陆路，选走水路
题目6（后悔值）：某公司投资策略，三种经济趋势下三种投资方案收益表，用后悔值法应选（ ）。
- 后悔值矩阵计算后：A 最大后悔值 350，B 最大后悔值 250，C 最大后悔值 300
- 选各方案最大后悔值中最小者（250）→ 稳健投资方案 B
答案：B（稳健投资方案）
解析：后悔值准则 = 各方案最大后悔值中取最小。本例中稳健方案 250 最小。
4. 高频考点
- 最小生成树：Kruskal 按边长排序 + 不形成环（n-1 条边）
- 最大流量：路径流量求和 + 每用一次扣减该路径所有线段流量
- 线性规划：3 变量以下图解法，3 变量以上联立方程组；注意整数约束
- 动态规划：装货问题先算单位利润，按单位利润从大到小装
- 决策树 EMV：从右向左计算，每层选最大 EMV
- 后悔值法：每状态 max - 实际 = 后悔值；每方案取 max；各 max 中取 min
- 乐观主义 vs 悲观主义 vs 后悔值：三种不确定决策易混淆，注意区分原则