运筹学考点归纳，运筹学考试重点

1、最小生成树和最短路径

整个定义(最小生成树)拓扑图中的所有路径和都是最小的，但不能确保任意两点之间的路径是最短的，例如，每个城市的天然气管道铺设、保证最小使用的管道规划等。 P864最短路径：从起点到目的地的路径最小即可，无需连接所有节点。 P867

差异：如果配置了最小生成树，则所有点都连接在一起，但最短路的是到达目的地的最短路径即可，与所有点是否连接无关。

结论： 1、遇到所有路径求和的最小问题，采用最小生成树和校验集解决；

遇到寻求2、2点间最短路径的问题时，使用最短路。 即从一个城市到另一个城市的最短路径问题。

2 .匈牙利法律

算法步骤：

1 )将所分配问题的系数矩阵转换为每行的每列至少一个元素为“0”。

从系数矩阵各行的元素中减去该行的最小元素；

从系数矩阵各列的元素中减去该列的最小元素。

然后，找到0所在的地方进行对应的分配即可：

)从第一行开始，如果该行只有一个零元素，则对该零元素加括号，并在带有加括号的零元素的列中绘制一条线以复盖该列。如果该行没有零元素，或者如果该行有两个或多个零元素，则转到下一行，然后按顺序进行到最后一行。

)3)如果从第一列开始，该列中只有一个零元素。 在此零元素上加括号(同样，不考虑删除的零元素)。 在包含带括号的零元素的行中绘制一条直线以复盖该列。 如果该列没有零元素，或者至少有两个零元素，则转至下一列，然后转至最后一列。

(4)重复上述步骤(1)和(2)，可以考虑以下三种情况。

效率矩阵每行都有带括号的零元素，对应这些元素指令即可找到最优解。

带括号的零元素个数小于m，但未剪切的零元素之间存在闭环。 此时，沿着闭环的流程，在每个间隔的零要素上加上括号，在带有括号的所有零要素所在的行(或列)上画一条直线，同样可以得到最佳解。

应用：

实际上，我们经常遇到这样的问题。 一家公司需要执行n项任务，正好n个人能承担这些任务。 因为每个人的专业性都不一样。 同样的工作因人而异(例如花费的时间和费用)。 于是，就会产生谁应该被分配来完成哪些任务，从而实现这些任务的总效率最高。(例如，总时间最省，总费用最低等)。 这类问题也叫分配问题，也叫分配问题。 [2]根据[1]或[2]

匈牙利法是一种优化利用资源，计算和调整最优分配方案变量的经营分析方法。 其目的和度量标准是在对资源、材料分配中的已知数据进行转换处理的基础上，提出目标对象(估算的产品资源)的最优分配方案，它们的机会成本最小。 也就是说，通过未被采用的方案造成的损失，为了使被选择的方案的设想成本为零，对分配方案的优化程度进行评价。 其特点是在求解最优分配方案时，在满足约束条件的前提下，通过使产品加工的机会成本为零，使总加工成本最小，验证方案变量的最优解和调整的幅度、限度

3、伏尔加法

算法步骤：

1、计算每行各列中最小元素与下一个小元素的差额，显示差额最大的。

2、在差异最大的行或列中的最小要素上填写尽可能大的数字。

3、对于没有画出的矩阵，重复上述步骤直到得到初始解。

实例分析：

例如：某公司生产有3个加工厂A1、A2、A3的产品，每日产量分别为7T、4T、9T，该公司将这些产品分别发往4个销售点B1、B2、B3、B4，各销售点的每日销售量分别为从各工厂到各经销商的单价如表1所示。 您是否询问了该公司如何发运产品，以满足各经销商的需要量，同时将总费用降至最低？

步骤1 :求出各行各列的最小和下一个小要素之差。

在表2中，各行之差分别为0、1、1，各列之差分别为2、5、1、3。 可以看出第二排的差距最大。 首先考虑第二列。 第二列中最小的cij为c32=4，x32=min { 6，9 }=6，第二列饱和，去除该列。

步骤2 :求出剩下的各行各列的最小和次小元素之差。

针对剩下方格重新计算各行的各列的差分值，各行的差分值分别为0、1、2，各列的差分值分别为2、1、3，第四列的差分值最大，第四列中，最小的cij为c34=5，x34=min{6

步骤3 :重复上述过程。

通过x21=3、x13=4、x23=1、x14=3获得另一个基础变量的值。 如下表所示

对应于该示例解的z=1346351028153=85。