运输问题的表上作业法.docxVIP

§2运输问题的表上作业法

2.1初始解的求法

同单纯形法一样，首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常见的是左上角法（或西北角法）、最小元素法和Vogl近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法加以介绍。

最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。

例1设有某种物质要从A1,A2,A3三个仓库运往四个销售点B1,B2,B3,B4.。各发点（仓库）的发货量、各收点（销售点）的收货量以及Ai到Bj的单位运费Cij如表3-2（i=1,2,3；j=1,2,3,4）.组织运输才能使总运费最少？

表3-2

由表3-2知，总的发量=总的收量，供销平衡。现从cij取最小值的格子开始（若有几个cij同时取最小值，则可取其中之一）。在本例中c13=1最小。这说明，将A1的物质调给B3是最便宜的，故应给c13所对应的变量x13以尽可能大的数值。显然应取x13=min(9,7)=7。在x13处填上7。由于B3的需求已经得到满足（或者说B3列已被满足），故x23,x33应为零，在x23,x33处打×将B3列划去，并将A1的发量相应地改为2（见表3-3）。

在表3-3未划线的格子中，最小的cij为c22=6。有x22=min(10,9)即令x22=9，并在第二列的其它空格（即在x12,x32）处打×,于是第二列又被划去，且A2的发量只有

1了。

表3-3

接下去的做法是：

在x11处填上2，此时，A1的发量已分配完毕（一般说成：A1行被满足），故应在第一行的其它空格处（实际上只有x14）打上×,划去第一行。

在x21处填上1，在第二行的其它空格处（实际上只有x24了）打上×,划去第二行。在x31处填上1，在第一列的其它空格处（实际上已无空格）打上×,划去第一列。

在x34处填上5，在第四列（或第3行）的其它空格处（实际上已无空格）打上×,划去第四列（或第三行），见表3-4。

至此，所有方格都已填上数或打上×,总共填了3＋4－1=6个数（等于基变量的个数）其余方格均已打×。每填一数就划去了一行或一列，总共划去的行数与列数之和也是6。可

以证明，用最小元素法所得到的一组解xij是基可行解，而且填数处是基变量，打×处是非基变量。它对应的目标函数为

z=9×2+1×7+11×1+6×9+14×1+16×5=184

在用最小元素法确定初始调运方案的

值得注意的是，如xij是空格，但的物质已调完）不需要（或

不可能）Ai再调运物质到Bj，此时必须禽，以保证最后填数的个数m+n一1个。

这一点对于以下的计算是重要的。

2.2验数的求法

表上作业法同单纯形法一样，也是利用检验数判别已取得的解是否为最优解。表上作业法求检验数一般有两种方法：位势法和闭回路法。这里我们先介绍位势法。

1位势法

首先构造位势表

我们将运价表中对应于表3-4有运量处划方格，然后在表的右边添加一列，下面添加一行。并且在添加的行、列里填上一些数，使得表中任何划了方格的对应运价正好等于它所在行及所在列中新填入数字之和。（见表3-5）具体作法如下：

将A1行右边空格填入零，则B1列、B3列下面的空格中必须分别填入9、1。由于11=9＋2，所以，A2行的右边空格必须填入2。类似地，B2列的下面应该填入4（因6=4＋2），A3行的右边只能填5（因14=9＋5），最后，由C34=16，所以,B4列必须填入11。这样就得到了表3-5.这个表称为位势表，新填入的数字分别称为行位势和列位势。并分别记为αi和βj（i=1,2,3；j=1,2,3,4）。

再求检验数

设xij所在的格子的检验数为σij，则我们可以证明

σij=cij－(αi＋βj)(i=1，2，…，m；j=1，2，…，n),(3.6)并且当所有的

σij≥0时，对应的调运方案是最优方案。

表3-5

显然，对于那些在方中已确定了调运量的格子的检验数σij应该为零，即有ci