什么是表作业法

最佳答案:

表作业法(hitchock method)是一种与单纯形法相类似的求解运输问题的方法，在表上先确定一个初始方案，然后反复进行调整，最后得到最优解。表作业法的步骤如下：1.用最小元素法制定初始方案(参见“最小元素法”)；2.求出检验数，判别方案是否最优，求检验数的方法有闭回路法、位势法和加圈法；3.求出调整量，在闭回路上进行方案的调整。表作业法的换基迭代，是在调运表上负检验数对应的空格所在的闭回路上进行的，调整后，空格对应的非基变量值由零增到θ，成为新基可行解的基变量，而原方案中这条闭回路的第奇数次拐角点所对应的基变量值中有一个为零，改为空格，成为新基可行解中的非基变量。如果同时出现几个零，规定只将其中最上方那行的最左边出现的那个零改为空格，其他的零均要填上，仍以基变量对待。这就保证了其中填数的格子(即基变量)仍为m+n-1个，新方案相应的总运费下降数值为对应于空格的检验数与调整数之积的绝对值，继续对新方案判别、调整，经过有限次直至所有的检验数都非负，便得出最优解。用表作业法解运输问题，可能有多个最优解。

详情介绍

表作业法(hitchock method)是一种与单纯形法相类似的求解运输问题的方法，在表上先确定一个初始方案，然后反复进行调整，最后得到最优解。表作业法的步骤如下：1.用最小元素法制定初始方案(参见“最小元素法”)；2.求出检验数，判别方案是否最优，求检验数的方法有闭回路法、位势法和加圈法；3.求出调整量，在闭回路上进行方案的调整。表作业法的换基迭代，是在调运表上负检验数对应的空格所在的闭回路上进行的，调整后，空格对应的非基变量值由零增到θ，成为新基可行解的基变量，而原方案中这条闭回路的第奇数次拐角点所对应的基变量值中有一个为零，改为空格，成为新基可行解中的非基变量。如果同时出现几个零，规定只将其中最上方那行的最左边出现的那个零改为空格，其他的零均要填上，仍以基变量对待。这就保证了其中填数的格子(即基变量)仍为m+n-1个，新方案相应的总运费下降数值为对应于空格的检验数与调整数之积的绝对值，继续对新方案判别、调整，经过有限次直至所有的检验数都非负，便得出最优解。用表作业法解运输问题，可能有多个最优解。

中文名

表作业法

外文名

hitchock method

所属学科

数学

属性

求解运输问题的方法

所属问题

运筹学(特殊的线性规划问题)

定义

一种与单纯形法相类似的求解运输问题的方法

表作业法简介

表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。是线性规划一种求解方法，其实质是单纯形法，故也称运输问题单纯形法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成表格，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭合回路法、位势法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。

表作业法表上作业法的步骤

1、找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；

（1）西北角法：

从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基可行解。

（2）最小元素法

从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。方法同西北角法。

注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。

2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；

运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。其对偶问题也应有m+n个变量，据此：

，其中前m个计为

，前n个计为

由单纯形法可知，基变量的

，因此

可以求出。

3、改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；

（因为目标函数要求最小化）

表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数

，非基变量的检验数

。

表示运费减少，

表示运费增加。

4、重复

②，

③，直到找到最优解为止。

表作业法表上作业法的常见问题

1、无穷多最优解

产销平衡的运输问题必定存最优解。如果非基变量的

，则该问题有无穷多最优解。

2、退化

表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。

表作业法表上作业法与单纯形法的关系

（1）运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式；

（2）表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；

（3）表上作业法中的“位势法”实质上是在求单纯形表中的检验数；

（4）调运方案表中数字格的数实质上就是单纯形法中基变量的值；

（5）调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。

表作业法举例

甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运输费用最少的调运方案。

总运输量：

日产量约束：

需求约束：

表作业法最小元素

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

总运价为：

表作业法西北角法

用西北角法确定初始调运方案：

总运价为：

表作业法最优性检验

1、闭回路法：

（1）思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。

（2）检验数：运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用的增加量。

（3）如果有某空格

的检验数为负，说明将

变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。

闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转90°继续前进，直至最终回到初始空格而形成的一条回路。 从每一空格出发，一定可以找到一条且只存在唯一一条闭回路 。

以

空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；

非基变量 xij 的检验数：

=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和） 。

现在，在用最小元素法确定初始调运方案的基础上，计算非基变量X₁₂的检验数 ：

非基变量X₁₂的检验数：

；非基变量X₂₁的检验数：

2、对偶变量法（位势法）

以初始调运方案为例，设置对偶变量

和

，然后构造下面的方程组：

在式中，令u₁=0，可解得其他量进而求出

；

。与前面用闭回路法求得的结果相同。

表作业法解的改进

如检验出初始解不是最优解，即某非基变量检验数为负，说明将这个非基变量变为基变量时运费会下降。根据表上作业法的第三步，需对初始方案进行改进。

解改进的步骤为：

1．（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变量）为换入变量，找出它在运输表中的闭回路；

2．以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；

3．在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量；

4．将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都减去这一数值，最终得出一个新的运输方案。 对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。

因σ₁₂=-20 ，画出以x₁₂为起始变量的闭回路，计算调整量；

按照下面的方法调整调运量：

（1）闭回路上，奇数次顶点的调运量加上ε，偶数次顶点的调运量减去ε；

（2）闭回路之外的变量调运量不变。

得到新的调运方案：

最优调运方案是：

相应的最小总运输费用为：