考点清单

• [x] 最小生成树（n 节点需 n-1 条边，不产生环路）
• [x] 最短路径
• [x] 网络与最大流量
• [x] 线性规划
• [x] 动态规划
• [x] 博弈论
• [x] 决策论（决策树/期望货币价值）
• [x] 数学建模

笔记

一、最小生成树

将 n 个节点连通，至少需要 n-1 条边，同时不产生环路。

解题思路：从最小的边开始选，判断是否产生环路 → 不产生则选定 → 继续找次小的边 → 直到选出 n-1 条边为止。总成本 = 所有选定边的权重之和。

---

二、最短路径

求从起点到终点的最短路径，与关键路径（最长路径）相反。

解题方向：

• 求项目最短工期 → 关键路径法（最长路径）
• 求路径最短距离 → 最短路径算法（Dijkstra 等）

直接计算法：逐层计算每个节点的最短距离，最终得到终点最短距离。

---

三、网络与最大流量

求从源点到汇点通过网络的最大流量，受各段容量限制。

解题思路：找到所有从源到汇的路径，标注每条路径的瓶颈容量（该路径上最小容量的边），依次叠加并减去已用容量，直到无法找到新路径。

---

四、线性规划

在约束条件下求目标函数的最大值或最小值。

解题思路：列出约束条件不等式组 → 画出可行域 → 在顶点处求目标函数值 → 比较得出最优解。

---

五、动态规划

将复杂问题分解为子问题，通过求解子问题逐步得到最优解。核心特征：最优子结构和重叠子问题。

解题思路：定义状态 → 写出状态转移方程 → 自底向上/自顶向下求解。

---

六、博弈论

研究决策主体行为发生直接相互作用时的决策及均衡问题。

基本要素：参与人、策略、收益、均衡（如纳什均衡：任一参与人单独改变策略都不会获得更多收益）。

---

七、决策论 ★

在不确定环境下进行方案选择的数学方法。

决策树分析：画出决策树 → 计算每个分支的期望值（概率 × 收益）→ 选择期望值最大的方案。

期望货币价值分析：EMV = Σ（每种结果的概率 × 该结果的货币价值）。

---

八、数学建模

口诀：模型假设 → 模型建立 → 模型求解 → 模型分析 → 模型检验 → 模型应用。