一、最小生成树

最小生成树是在一个无向图中找到一棵包含所有顶点的树，使得树上所有边的权重之和最小。常用的算法有Prim算法和Kruskal算法。

最小生成树 (Minimum Spanning Tree, MST)

最小生成树是在一个带权连通无向图中找到一棵包含所有顶点的树，使得所有边的权重之和最小。

（一）Prim算法

Prim算法是从任意一个顶点开始，逐步添加最近的顶点及其相连的边，直到所有顶点都被加入为止。

Prim算法步骤：
1、选择任意一个顶点作为起始顶点，将其加入到生成树中。
2、从未加入生成树的顶点中选择一个与已加入顶点距离最近的顶点，并3、将这个顶点及其与生成树中顶点相连的最短边加入到生成树中。
重复步骤2，直到所有顶点都被加入到生成树中。

（二）Kruskal算法

Kruskal算法是先对所有的边按照权重从小到大排序，然后逐条考虑每条边是否加入生成树中，只要这条边的加入不会形成环，则就将其加入到生成树中。

Kruskal算法步骤：
1、将所有边按权重从小到大排序。
2、初始化一个空的生成树T。
3、遍历排序后的边列表，对于每一条边(e1, e2)，检查e1和e2是否已经在生成树中属于同一个连通分量。如果不是，则将这条边添加到生成树T中。
4、当生成树包含所有顶点时停止。

（三）计算题示例

最小生成树.png

P算法.jpg

K算法.jpg

二、最大流量

最大流问题是指在一个网络图中寻找从源节点到汇节点的最大传输量。该问题可以用Ford-Fulkerson算法解决，其中最著名的增广路算法就是Edmonds-Karp算法。

计算题示例

最大流量.png

最大流量.jpg

三、决策论（最大最大原则、最大最小原则、最小最大后悔值）

乐观、悲观.jpg

后悔值.jpg

（一）最大最大原则：选择所有可能方案中的最大收益。

乐观主义：最大最大准则，大中取大
积极方案——500
稳健方案——300
保守方案——400

（二）最大最小原则：选择在最坏情况下能够获得的最大收益。

悲观主义：最大最小原则，小中取大
积极方案——50
稳健方案——100
保守方案——200

（三）最小最大后悔值：选择最小化最大后悔值的方案。后悔值是指在事后看来，如果选择了另一个方案可能会得到更好的结果时所感到的“后悔”。

将每种自然状态的最高值（收益矩阵则取最高值，损失矩阵取最低值）定为该状态的理想目标。
后悔值=|该方案的最大收益-当前选择收益|，取绝对值
收益矩阵——最高值；损失矩阵——最低值
如图中步骤所示：
“不景气”列，用原矩阵的数值-400，再求绝对值；
“不变”列，用原矩阵的数值-250，再求绝对值；
“景气”列，用原矩阵的数值-500，再求绝对值。

每一行的最大值，为该类型投资的最大后悔值；
三者再取最小值，得到最终答案。

四、灵敏度分析

灵敏度分析是指研究模型参数变化对模型解的影响程度。在优化问题中，灵敏度分析可以用来评估目标函数系数或约束条件的变化如何影响最优解。
假设有外表完全相同的不透明盒子100个，将其分为两组，一组70个盒子装白球；一组30个盒子装黑球。若从这100个盒子中任选一盒，如果装的是白球，猜对了得500分，猜错了扣200分。如果装的是黑球，猜对了得1000，猜错了扣150。为了使期望值得分最高，应该怎么选？

根据题干：猜白球，是白球的概率是0.7，得分+500；是黑球的概率0.3，得分-200。
猜黑球，是黑球的概率是0.3，得分+1000；是白球的概率是0.7，得分-150。

期望值E（猜白）=0.7500-0.3200=290
期望值E（猜黑）=0.31000-0.7150=195
故猜白球是最优方案。

五、线性规划

线性规划是在一组线性不等式约束条件下求解线性目标函数的最大值或最小值。常用的方法是单纯形法。
线性规划——列方程求解。
某厂计划生产甲乙两种产品。生产每套产品所需的设备时，AB原材料、利润及可利用资源数值如下所示，为获利最大，应该按照哪种方案安排？

线性规划.png

线性规划.jpg

六、动态规划

动态规划是一种通过把原问题分解成相对简单的子问题来求解复杂问题的方法。它适用于具有重叠子问题和最优子结构特点的问题。

（作者正在学习中，没找到合适的案例）

动态规划1.png

动态规划2.png

七、追及问题

追及问题是指在给定初始位置和速度的情况下，一个移动物体试图追上另一个移动物体的问题。这类问题可以通过微分方程来建模并求解。

追及问题.png