运输问题的表上作业法

1、§2 运输问题的表上作业法  2.1初始解的求法  同单纯形法一样，首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常见的是左上角法（或西北角法）、最小元素法和Vogl近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法加以介绍。最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。  例1 设有某种物质要从 三个仓库运往四个销售点 。各发点（仓库）的发货量、各收点（销售点）的收货量以及 到 的单位运费 如表3-2（ =1,

2、2,3； =1,2,3,4）.组织运输才能使总运费最少？  表3-2由表3-2知，总的发量=总的收量，供销平衡。现从 取最小值的格子开始（若有几个 同时取最小值，则可取其中之一）。在本例中 最小。这说明，将 的物质调给 是最便宜的，故应给 所对应的变量 以尽可能大的数值。显然应取 。在 处填上7。由于 的需求已经得到满足（或者说 列已被满足），故 应为零，在 处打×将 列划去，并将 的发量相应地改为2（见表3-3）。在表3-3未划线的格子中，最小的 为 。有 即令 ，并在第二列的其它空格（即在 ）处打×，于是第二列又被划去，且 的发量只有1了。  表3-

3、3  接下去的做法是：在 处填上2，此时， 的发量已分配完毕（一般说成： 行被满足），故应在第一行的其它空格处（实际上只有 ）打上×，划去第一行。在 处填上1，在第二行的其它空格处（实际上只有 了）打上×，划去第二行。在 处填上1，在第一列的其它空格处（实际上已无空格）打上×，划去第一列。在 处填上5，在第四列（或第3行）的其它空格处（实际上已无空格）打上×，划去第四列（或第三行），见表3-4。  至此，所有方格都已填上数或打上×，总共填了341=6个数（等于基变量的个数）其余方格均已打×。每填一数就划去了一行或一

4、列，总共划去的行数与列数之和也是6。可以证明，用最小元素法所得到的一组解 是基可行解，而且填数处是基变量，打×处是非基变量。它对应的目标函数为  在用最小元素法确定初始调运方案的 基本步骤：  值得注意的是，如 是空格，但 的需求已满足，（或 的物质已调完）不需要（或不可能） 再调运物质到 ，此时必须禽 ，以保证最后填数的个数 个。这一点对于以下的计算是重要的。  2.2验数的求法   表上作业法同单纯形法一样，也是利用检验数判别已取得的解是否为最优解。表上作业法求检验数一般有两种方法：位势法和闭回路法。这里我们先介绍位势法。  1位

5、势法  首先构造位势表我们将运价表中对应于表3-4有运量处划方格，然后在表的右边添加一列，下面添加一行。并且在添加的行、列里填上一些数，使得表中任何划了方格的对应运价正好等于它所在行及所在列中新填入数字之和。（见表3-5）具体作法如下：将 行右边空格填入零，则 列、 列下面的空格中必须分别填入9、1。由于11=92，所以， 行的右边空格必须填入2。类似地， 列的下面应该填入4（因6=42）， 行的右边只能填5（因14=95），最后，由 ，所以, 列必须填入11。这样就得到了表3-5.这个表称为位势表，新填入的数字分别称为行位势和列位势。并分别记为 和 （ =1,2,3； =1,2,3

6、,4）。  再求检验数设 所在的格子的检验数为 ，则我们可以证明= ( )( =1，2， ； =1，2， ),(3.6)并且当所有的 0时，对应的调运方案是最优方案。  表3-5  显然，对于那些在方中已确定了调运量的格子的检验数 应该为零，即有 = ，上面我们在求行位势与列位势时就利用了这一关系。下面我们来求其余格子所对应的检验数。；  2 闭回路法  首先介绍闭回路的概念：如果已确定了某一调运方案，我们从某一空格出发（无调运量的格子），沿水平方向或垂直方向前进，遇到某一个适当有调运量的格子就转向 继续前进。如此继续下去，经过若干次，就一定回

7、到原来出发的空格。这样形成的一条由水平和垂直线段组成的封闭折线称为闭回路。  在表上作业法中，闭回路中重要的概念之一，它既可以计算检验数又可以调整调运方案。由于数字格对应着基变量，其检验数均为零，而我们考虑的是非基变量的检验数，所以只研究从空格出发所形成的闭回路。  由闭回路的构成可见，除起点是空格外，其余所有的拐角点都是填有调运量的。我们可以证明一个重要的事实：从每一个空格出发都存在唯一的闭回路。  例如在表3-5所示的初始调运方案中作出从（3.2）对应的空格为起点的闭回路为（3,2） (2,2) (2,1) (3,1) (3,2)这条闭合回路，除出发格（3,2

8、）为空格外，其余都是数字格，如表3-6所示。为确定空格（ ）的检验数，便可以从空格（ ）出发作闭回路，并对该回路的顶点进行编号，即以（ ）格为第一个顶点，所经过的顶点依次为第二个、第三个。则闭回路上奇数顶点的单位运价之和减去偶数顶点的单位运价之和所得到的差，就是空格（ ）的检验数。其经济意义是非基变量 取值增加一个单位所引起的总运费的变化量。  现以计算（3,2）格的检验数为例加以说明。若让（3,2）格的调运量增加一个单位，为保证产销平衡，则其奇数顶点的调运量也都要增加一个单位此同时，所有偶数顶点的调运量也都要减少一个单位。如表3-7所示。经过这样调整后，就会得到一个新的调运方案如表

9、3-8。    现在考虑按上述方法调整方案后，总运费将如何变化。因为闭回路上所有奇数顶点的调运量都增加了1个单位，单考虑这一因素，总运费的增加量等于闭回路奇数顶点单位运价之和；另一方面，闭回路上所有偶数顶点的调运量都减少了1个单位，单考虑这一因素，总运费的减少量等于闭回路偶数顶点单位运价之和。如果同时考虑这两方面的因素，总运费的增加量就等于该闭回路上奇数顶点的单位运价之和减去偶数顶点单位运价之和所得的差，其差值就是空格的检验数。所以，（2,3）格的检验数为    这表明，如果让（3,2）格的调运量（ 运往 的货物量）增加一个单位，总运费将增加3元（这与前

10、面用位势法求检数的结果是一致的。）同样可以求得表3-7所示的基本可行方案每个空格检验数列于表3-9每个相应方格的括号内。  表3-9  2.3最优方案的判别准则  在讨论闭回路法求检验数时，我们看到如果某人空格的检验数为正，那么若使该空格的调运量增加（即由非基变量变为基变量），总运费就会增加之，如果某个空格的检验数为负，若使该空格的调运量增加，总运费就会减少。我们自然会想到：如果没有负的检验，总运费就不能再减少了。一般我们有如下结论，即判别最优方案准则：对于运输问题的一个基本可行方案，如果所有的检验数非负，即 ,那么该方案就是一具最优方案。这里的结论和前面线性规划

11、的结论是一致的。因为运输问题是极小化线性规划问题。所以，最优判别准则乃是所有检验数非负。用上述最优判别准则检查表3-9，由于表中还有负的检验，所以，现在得到的方案还不是最优方案。  2.4调运方案的改进  如果所得的基本可行方案不是最优的，就要对其进行改进，这一步工作想当于普通单纯形法的换基迭代，其运算法则和步骤是：第一步确定进基格。选取绝对值最大的负检验数格为进基格，标以“*”，进基格所对应的变量就是单纯形法所对应的变量；第二步作从进基格出发作闭回路，并沿任一方向对该闭回路的顶点进行编号，但进基格必须为第一个顶点；第三步确定调整量，求出闭回路上所有偶数顶点调运量的极小值

12、, 叫做调整量；第四步调整方案，令此闭回路上所有奇数顶点的调运量加 ，所有偶数顶点的调运量减 ，其余调运量不变。调整后进基格由空格变为数字格，在闭回路的偶数顶点中选取一个调运量为零的顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其中一个顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其中一个顶点改为空格，这个变为空格的偶数顶点所对应的变量，就是单纯形法是所说的出基变量。如表3-9， 是绝对值最大的负检验数，以（3,3）格为空格出发的闭合回路（3,3）(1,3)(1,1)(3,1)用 表示该闭合回路上的调整量，则 。沿着该闭合回路奇数顶点的调运量加 ，偶数顶点的调运量减 ，得表3-10。  对表3-10所示的基本可行方案，用闭合回路法重新计算检验数，见表3-11。    其中以（2,4）格为空格的闭回路是(2,4)(2,1)(1,1)(1,3)(3,3)(3