第17章 数学与经济管理

17.1运筹方法（关键路径法、线性规划、动态规划）

17.2随机函数模型

17.3数学建模

17.4图论应用-最小生成树（Minimum Spanning Tree, MST）

常用两大经典算法：

1.Kruskal 算法
思想：按边权从小到大排序，依次把不形成环的边加入集合。

2.Prim 算法
思想：从任意起点开始，每次把连接“已选点集”与“未选点集”的最短边加入，直到所有点连通。

17.5图论应用-最短路径

1.Dijkstra：

贪心＋优先队列，每次把离源点最近且未被访问的点松弛一遍，只适用于非负边权，时间 O((V+E) log V)。
2.Bellman-Ford：

对所有边做 V-1 轮松弛，可处理负权边并在第 V 轮检测负环，时间 O(VE)。

17.6图论应用-网络与最大流量

17.7运筹方法-决策分析

定义：

决策分析指从若干可能的方案中通过决策分析技术，例如期望值法或决策树法等选择其一的决策过程，是一种定量分析方法。

针对问题：

期望值问题、决策树问题

预期货币价值或者期望货币值（Expected Monery Value, EMV）：把某方案的每个可能结果所获得的收益与其发生概率相乘之后加总，即得到方案的EMV。通过比较各方案的EMV来决策采用哪一个方案。该方法常常与决策树技术相辅相成。

解题技巧：

决策树在最左边做决策，所以需要从右向左逐层计算化简，特别是条件复杂时更应如此。

例题：

生产某种产品有两个建厂方案。（1）建大厂：需要初期投资500万元。如果产品销路好，每年可以获利200万元，如果销路不好，每年会亏损20万元。（2）建小厂，需要初期投资200万元。如果产品销路好，每年可以获利100万元；如果销路不好，每年只能获利20万元。市场调研表明，未来2年，这种产品销路好的概率为70%。如果这2年销路好，则后续5年销路好的概率上升为80%;如果这2年销路不好，则后续5年销路好的概率仅为10%。为取得7年最大总收益，决策者应（B）

A.建大厂，总收益超500万元

B.建大厂，总收益略多于300万元

C.建小厂，总收益超500万元

D.建小厂，总收益略多于300万元

17.8不确定型决策论

乐观主义准则，也成为“最大最大准则”，其决策原则是“大中取大”。决策者依次在决策表中的各个投资方案所对应的各个结果中选择出最大结果并记录，最后再从这些结果中选出最大者，其所对应的方案就是应该采取的决策方案。

悲观主义准则，也称为“最大最小准则”，其决策原则是“小中取大”。决策者依次在决策表中的各个投资方案所对应的各个结果中选择出最小结果并记录，再从这些结果中选出最大者，其所对应的方案就是应该采取的决策方案。

后悔值准则，也称为“最小最大后悔值”，该决策法的基本原理为：将每种自然状态的最小值（指收益矩阵，如果是损失矩阵英取最低值）定为该状态的理想目标，并将该状态中的其他值与最高值相比，所得之差作为未达到理想的后悔值。为了提高决策的可靠性，在每一方案中选取最大的后悔值，再在各个方案中的最大后悔值中选取最小值作为决策依据，与该值所对应的方案即为入选方案。