运筹学期末复习总结——表上作业法

期末考试总是来得突如其来，最近一段时间猛补运筹学，同时也总结一下。

1.根据问题条件列出产销平衡表和运费表

这个比较基础，上个表格大家都能理解。

2.用最小元素法或差值法确定初始方案

2.1最小元素法

最小元素法的原理是先针对运价小的方案先予以满足，比如上标中先满足A1-B1的运输，即先使产地A1运往B1。依次类推，得到初始方案。

2.2差值法

差值法的原理是利用罚数原理，罚数的定义：各行、各列次小、最小运价的差额

差值法在罚数最大处采用最小运费调运。上表的罚数如下表：

第一行的数据中存在最大的罚数4，所以需要优先采用A1发货物，B3作为销地。

3.用闭回路法或位势法求非基变量的检验数

3.1闭回路法

闭回路从非数字格出发，顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。

定理：从每一空格出发一定存在和可以找到唯一的闭回路。

所以一定能找出唯一的闭回路。

空格检验数：闭合回路的奇顶点运费之和 – 偶顶点运费之和。

3.2位势法

添加Vj行，添加Ui列。设定u1=0，按ui+vj=Cij计算Ui与Vj的数值

空格检验数σij= Cij － (ui+vj)

4.若所有空格检验数大于等于0，则为最优方案，计算总运费，否则进入第五步的调整

5.以绝对值最大的负检验数对应的非基变量作为起始变量作闭回路，求出调整量，调整的新的运输方案

5.1确定进基变量：空格检验数负值绝对数最大的即为换入变量。
5.2作闭回路，确定调整量： 从5.1中的空格开始画闭回路，其它转角点都是填有运量的方格；从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。
5.3在闭回路上进行调整：对闭回路上每个-1顶点的调运量－theta，对闭回路上每个+1顶点（含起始格）的调运量+theta。