17.1运筹方法关键路径法、线性规划、动态规划17.2随机函数模型17.3数学建模17.4图论应用-最小生成树Minimum Spanning Tree, MST常用两大经典算法1.Kruskal 算法思想按边权从小到大排序依次把不形成环的边加入集合。2.Prim 算法思想从任意起点开始每次把连接“已选点集”与“未选点集”的最短边加入直到所有点连通。17.5图论应用-最短路径1.Dijkstra贪心优先队列每次把离源点最近且未被访问的点松弛一遍只适用于非负边权时间 O((VE) 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年最大总收益决策者应BA.建大厂总收益超500万元B.建大厂总收益略多于300万元C.建小厂总收益超500万元D.建小厂总收益略多于300万元17.8不确定型决策论乐观主义准则也成为“最大最大准则”其决策原则是“大中取大”。决策者依次在决策表中的各个投资方案所对应的各个结果中选择出最大结果并记录最后再从这些结果中选出最大者其所对应的方案就是应该采取的决策方案。悲观主义准则也称为“最大最小准则”其决策原则是“小中取大”。决策者依次在决策表中的各个投资方案所对应的各个结果中选择出最小结果并记录再从这些结果中选出最大者其所对应的方案就是应该采取的决策方案。后悔值准则也称为“最小最大后悔值”该决策法的基本原理为将每种自然状态的最小值指收益矩阵如果是损失矩阵英取最低值定为该状态的理想目标并将该状态中的其他值与最高值相比所得之差作为未达到理想的后悔值。为了提高决策的可靠性在每一方案中选取最大的后悔值再在各个方案中的最大后悔值中选取最小值作为决策依据与该值所对应的方案即为入选方案。