资源描述：
《运输问题的表上作业法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、§2运输问题的表上作业法 2.1 初始解的求法 同单纯形法一样，首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常 见的是左上角法（或西北角法）、最小元素法和Vogl近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法加以介绍。最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。 例1设有某种物质要从三个仓库运往四个销售点。各发点（仓库）的发货量、各收点（销售点）的收货量以及到的单
2、位运费如表3-2（=1,2,3；=1,2,3,4）.组织运输才能使总运费最少？ 表3-2由表3-2知，总的发量=总的收量，供销平衡。现从取最小值的格子开始（若有几个同时取最小值，则可取其中之一）。在本例中最小。这说明，将的物质调给是最便宜的，故应给所对应的变量以尽可能大的数值。显然应取。在处填上7。由于的需求已经得到满足（或者说列已被满足），故应为零，在处打×将列划去，并将的发量相应地改为2（见表3-3）。在表3-3未划线的格子中，最小的为。有即令，并在第二列的其它空格（即在）处打×，于是第二列又被划去，且的发量
3、只有1了。 表3-3 接下去的做法是：在处填上2，此时，的发量已分配完毕（一般说成：行被满足），故应在第一行的其它空格处（实际上只有）打上×，划去第一行。在处填上1，在第二行的其它空格处（实际上只有了）打上×，划去第二行。在处填上1，在第一列的其它空格处（实际上已无空格）打上×，划去第一列。在处填上5，在第四列（或第3行）的其它空格处（实际上已无空格）打上×，划去第四列（或第三行），见表3-4。 至此，所有方格都已填上数或打上×，总共填了3＋4－1=6个数（等于基变量的个数）其余方格均已打×。每填一数就划去了一行
4、或一列，总共划去的行数与列数之和也是6。可以证明，用最小元素法所得到的一组解是基可行解，而且填数处是基变量，打×处是非基变量。它对应的目标函数为 在用最小元素法确定初始调运方案的基本步骤： 值得注意的是，如是空格，但的需求已满足，（或的物质已调完）不需要（或不可能）再调运物质到，此时必须禽，以保证最后填数的个数个。这一点对于以下的计算是重要的。 2.2验数的求法 表上作业法同单纯形法一样，也是利用检验数判别已取得的解是否为最优解。表上作业法求检验数一般有两种方法：位势法和闭回路法。这里我们先介绍位势法。 1 位势
5、法 首先构造位势表我们将运价表中对应于表3-4有运量处划方格，然后在表的右边添加一列，下面添加一行。并且在添加的行、列里填上一些数，使得表中任何划了方格的对应运价正好等于它所在行及所在列中新填入数字之和。（见表3-5）具体作法如下：将行右边空格填入零，则列、列下面的空格中必须分别填入9、1。由于11=9＋2，所以，行的右边空格必须填入2。类似地，列的下面应该填入4（因6=4＋2），行的右边只能填5（因14=9＋5），最后，由，所以,列必须填入11。这样就得到了表3-5.这个表称为位势表，新填入的数字分别称为行位势
6、和列位势。并分别记为和（=1,2,3；=1,2,3,4）。 再求检验数设所在的格子的检验数为，则我们可以证明=－(＋)(=1，2，…，；=1，2，…，),(3.6)并且当所有的0时，对应的调运方案是最优方案。 表3-5 显然，对于那些在方中已确定了调运量的格子的检验数应该为零，即有=＋，上面我们在求行位势与列位势时就利用了这一关系。下面我们来求其余格子所对应的检验数。；；；；；； 2闭回路法 首先介绍闭回路的概念：如果已确定了某一调运方案，我们从某一空格出发（无调运量的格子），沿水平方向或垂直方向前进，遇到
7、某一个适当有调运量的格子就转向继续前进。如此继续下去，经过若干次，就一定回到原来出发的空格。这样形成的一条由水平和垂直线段组成的封闭折线称为闭回路。 在表上作业法中，闭回路中重要的概念之一，它既可以计算检验数又可以调整调运方案。由于数字格对应着基变量，其检验数均为零，而我们考虑的是非基变量的检验数，所以只研究从空格出发所形成的闭回路。 由闭回路的构成可见，除起点是空格外，其余所有的拐角点都是填有调运量的。我们可以证明一个重要的事实：从每一个空格出发都存在唯一的闭回路。 例如在表3-5所示的初始调运方案中作出从（3
8、.2）对应的空格为起点的闭回路为（3,2）(2,2)(2,1)(3,1)(3,2)这条闭合回路，除出发格（3,2）为空格外，其余都是数字格，如表3-6所示。为确定空格（）的检验数，便可以从空格（）出发作闭回路，并对该回路的顶点进行编号，即以（）格为第一个顶点，所经过的顶点依次为第二个、第三个……。则闭回路上奇数顶点的单位运价之和减去偶数顶点的单位运价之和所得到的差，就是空
