运筹学算法模型

Ⅰ 运筹学中大M法的理论依据是什么

对于一般形式的线性规划问题，化为标准型后，大M法和两阶段法都可以求解。如果手算求解，两种算法的应用没有差别。

如果是计算机编程，首选两阶段算法。原因是大M法可能会由于大M的取值而出现计算误差。

在极大化问题中，对人工变量赋于一M作为其系数；在极小化问题中，对人工变量赋于一个M作为其系数，M为一任意大（而非无穷大）的正数。把M看作一个代数符号参与运算，用单纯形法求解。

(1)运筹学算法模型扩展阅读：

用单纯形法在改进目标函数的过程中，如果原问题存在最优解，必然使人工变量逐步变为非基变量，或使其值为零。目标函数值将不可能达到最小或最大。

在迭代过程中，若全部人工变量变成非基变量，则可把人工变量所在的列从单纯形表中删去，此时便找到原问题的一个初始基可行解。若此基可行解不是原问题的最优解，则继续迭代，直至所有的检验数都小于等于0，求得最优解为止。

Ⅱ 运筹学中的图论问题

很多实际的生产问题都能被抽象成一张大的图。具体一点的例子，比如需要在若干个城市之间铺设铁路或者架设电网，那么城市就是图里面的点，铁路电网就是图里面的边。抽象一点的例子，比如完成一个项目的过程中所有可能出现的状态都可以视为一个点，而状态到状态之间的转换就是边。上一篇文章中我们说过运筹学是处理实际生产生活中遇到的问题的。一旦实际问题被抽象成了一个图的模型（注意与机器学习里面的图模型区分开来），很多图论里面的算法就可以用来解决实际问题，所以图论是运筹学当中的一个很大的分支。今天我们就介绍一下几个图论的基本算法及其在生产生活中的应用。

一最小生成树

比如现在要在若干个村子之间架设电网，保证每个城市都通上电（先不考虑电网输电能力大小）。虽然理论上讲，任何两个村子之间都可以架设电线，不过那样的话成本很到，不划算，我们需要在所有可能的连线里面找到一组总长最短的边，保证这些边把每个村子都连上了。在图论中，这是一个典型的最小生成树问题。有两种解决最小生成树的方法，第一种办法是把所有的边按照从小到大的顺序添加到图里面，如果产生回路就舍弃它，直到覆盖了所有的点。另一种方法是把图上的边按照从大到小的顺序删除，直到再删下去就一定会产生离散的点为止。

二最短路径

图论中应用最广的问题可能就是最短路径问题了。地图上很多城市之间都有道路相连，想从一个城市到另一个城市，往往有多种选择，可是走那条路距离最短呢？如果地图规模不大，我们可以一眼就看出来。可是随着地图规模变大，就很难再一眼看出来了，需要有严格的算法保证找到最短路径。目前已经有了很多种最短路径算法，他们的基本思想也不尽相同。以着名的Dijkstra算法为例，它每次会选择距离“所有已经选择过了的点”中距离最近的下一个点，一步步的迭代下去。这个流程保证了算法会按照距离出发点由近到远的顺序选择每一个点。

三最大流-最小割问题

油气输送网络又许多不同的边组成，每一条边的运输能力有限。输送油气资源的时候，为了最大化运输量，需要合理安排通过每一条边的油气流量。这就是在一个网络寻找最大流的问题（等价于寻找最小割）。解决问题的想法很简单，找到一组边，它们把整个网络分成了两部分，流的源和目的地址分属于这两个部分。我们称这样一组边为图的一个分割。由于所有的油气流都要通过分割中的边，所以最大流其实受制于分割的流通能力的。于是最大流应该等于流通能力最小的分割。剩下的问题，就是一步步调整，找到最小分割了。

Ⅲ 运筹学有哪些算法

图像法，单纯形法，对偶单纯法，两阶段法。
图像法只能解一般的含两个未知数的不等式。
后3种是解多个未知数的不等式。
运筹学还有整数规划，一般有分支定界法，隐枚举法，匈牙利法。
运输问题——一般为产销问题，用最小元素法先做，再用位势法调整
目标规划问题——先建模，再用单纯形法解，一般现在用excel解决
动态规划——逆序法，顺序法
最小支撑树图——避圈法，破圈法
最短路问题——dijkstra算法