3.表上作业法的基本步骤
（1）找出初始基可行解： m+n-1个数字格（基变
量）； （2）求各非基变量（空格）的检验数。
（3）确定入基变量，若min{ ij | ij 0} lk ,那么
选取xij为入基变量；
（4）确定出基变量，找出入基变量的闭合回路； （5）在表上用闭合回路法调整运输方案； （6）重复2、3、4、5步骤，直到得到最优解。
下面就以表4-6中给出的初始基可行解（最 小元素法所给出的初始方案）为例，讨论闭合 回路法。
表4-24 甲 A B C （+3） 3 -1） （ 6 6 乙 丙 4（-3） 1 （+2） 3 6 丁 3 产量（ai） 7 4 9
3 5 销量（bj） 从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对 于空格（A，甲）在初始方案的基础上将A生产的产品调运一个 单位给甲，为了保持新的平衡，就要依次在（A，丙）处减少 一个单位、（B，丙）处增加一个单位、（B，甲）处减少一个 单位；即要寻找一条除空格（A，甲）之外其余顶点均为有数 字格（基变量）组成的闭合回路。表4-24中用虚线画出了这条 闭合回路。闭合回路顶点所在格括号内的数字是相应的单位运
最小元素法的应用（以引例4-1为例）
表4-1
A B C 销量（bj） 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 产量（ai） 7 4 9
第一步：从表4-1中找出最小运价“1”， 最小运 价所确定的供应关系为（B，甲），在（B，甲） 的交叉格处填上“3”，形成表4-2；将运价表的 甲列运价划去得表4-3.
2.表上作业法与单纯形法的关系
表上作业法中的最小元素法和伏格尔法实质
上是在求单纯形表中的初始基可行解； 表上作业法中的“位势法”实质上是在求单 纯形表中的检验数； 调运方案表中数字格的数实质上就是单纯形 法中基变量的值； 调运方案表上的“闭回路法”实质上是在做 单纯形表上的换基迭代。
4.2
表上作业法
表上作业法 表上作业法与单纯形法的关系 表上作业法的基本步骤 确定初始基可行解 最小元素法的基本步骤 伏格尔法
三、 运输问题的求解
1.表上作业法
运输问题的求解采用表上作业法，即用列 表的方法求解线性规划问题中的运输模型的 计算方法，实质上是单纯形法。 表上作业法是一种特定形式的单纯形法， 它与单纯形法有着完全相同的解题步骤，所 不同的只是完成各步采用的具体形式。
表4-24 甲 A 乙
B C
销量（bj）
（+3） 3 -1） （
3 6 6
丙 4（-3）
丁 3 3 6
产量（ai） 7
1 （+2）
5
4 9
对应这样的方案调整，运费会有什么变化呢？可以
看出（A，甲）处增加一个单位，运费增加3个单位； 在（A，丙）处减少一个单位，运费减少3个单位；在 （B，丙）处增加一个单位，运费增加2个单位；在 （B，甲）处减少一个单位，运费减少1个单位。增减 相抵后，总的运费增加了1个单位。由检验数的经济 含义可以知道，（A，甲）处单位运量调整所引起的 运费增量就是（A，甲）的检验数，即σ 11=1。
仿照此步骤可以计算初始方案中所有空
格的检验数，表4-25～表4-30展示了各 检验数的计算过程，表4-30给出了最终 结果。可以证明，对初始方案中的每一 个空格来说“闭合回路存在且唯一”。
表4-25
甲
A B
11 = 1 3
乙
（+11）
丙
4 1
丁
3（-10）
产量（ai）
7 4
C
销量（bj） 表4-26
4.2.2
基可行解的最优性检验
对初始基可行解的最优性检验有闭合回路法
和位势法两种基本方法。闭合回路法具体、 直接，并为方案调整指明了方向；而位势法 具有批处理的功能，提高了计算效率。 所谓闭合回路是在已给出的调运方案的运输 表上从一个代表非基变量的空格出发，沿水 平或垂直方向前进，只有遇到代表基变量的 填入数字的格才能向左或右转90度（当然也 可以不改变方向）继续前进，这样继续下去， 直至回到出发的那个空格，由此形成的封闭 折线叫做闭合回路。一个空格存在唯一的闭 回路。
丙
4（+3） 1（-2）
丁
3（-10） （+8） 3
产量（ai）
7 4 9
5
6
表4-28
甲 A
11 = 1
乙
12 = 2
丙
4（-3）
丁
3（+10）
产量（ai）
7
B C
销量（bj）
3
22 = 1
6 6
1
（+10） 5
24 = -1
3（-5） 6
4
9
3
表4-29 甲 A B C 销量（bj） 表4-30 A
甲
A B C 销量（bj） 3 3 甲 3 1 7 3
表4-2 乙
丙
丁
产量（ai） 7 4 9
6 表4-3 乙 11 9 4 6
5 丙 3 2 10 5
6 丁 10 8 5 6 产量（ai） 7 4 9
A B C
销量（bj）
表4-3 A B C 销量（bj） 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 产量（ai） 7 4 9
表4-6 A B C 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 6 丁 3 3 5 6 产量（ai） 7 4 9
销量（bj）
表4-7
3
甲
6
乙
5
丙 4 1
A B C
销量（bj）
3 3 6 6
产量（ai） 7 4 9
最后在产销平衡表上得到一个调运方案，见
表4-6。这一方案的总运费为86个单位。
4、确定初始基可行解
与一般的线性规划不同，产销平衡的运输问
题一定具有可行解（同时也一定存在最优 解）。 最小元素法（the least cost rule）和伏格尔法 （Vogel’s approximation method）。 最小元素法 最小元素法的基本思想是就近供应，即从单位 运价表中最小的运价开始确定产销关系，依此 类推，一直到给出基本方案为止.
产量（ai） 4 4 12
8.伏格法尔法
每次从当前运价表上，计算各行各列 中两个最小运价之差值（行差值hi，列差 值kj），优先取最大差值的行或列中最小 的格来确定运输关系，直到求出初始方案。
8.伏格尔法
伏格尔法的基本步骤：
1.计算每行、列两个最小运价的差； 2.找出最大差所在的行或列； 3.找出该行或列的最小运价，确定供求关系，最大量 的供应 ； 4.划掉已满足要求的行或 (和) 列，如果需要同时划 去行和列，必须要在该行或列的任意位置填个 “0”； 5.在剩余的运价表中重复1~4步，直到得到初始基可 行解。
表4-1 A B C 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 产量（ai） 7 4 9
销量（bj）
表4-12 A B C
两最小元素之差
3
甲 3 1 7
6
乙 11 9
5
丙 3 2 10 丁 10 8 5
6
两最小元素之差
4
0 1 1
2
5
1
3
表4-13
甲 A B C 销量（bj） 3 甲 3 乙 丙 丁 产量（ai） 7 4 9 5 乙 11 丙 3 6 丁 10
1.闭合回路
所谓闭合回路法，就是对于代表非基变量的
空格（其调运量为零），把它的调运量调整 为1，由于产销平衡的要求,我们必须对这个 空格的闭回路的顶点的调运量加上或减少1。 最后我们计算出由这些变化给整个运输方案 的总运输费带来的变化。如果所有代表非基 变量的空格的检验数也即非基变量的检验数 都大于等于零，则已求得最优解，否则继续 迭代找出最优解。
2
表4-17
甲
A B
乙
丙
丁
3
3
C
销量（bj） 表4- 18 A B C
两最小元素之差
6
6 5
3
6
产量（ai） 7 4 9
甲 3 1 7
乙 11 9 4
丙
3
2 10
丁 10 8 5
两最小元素之差
7
6
1
2
表4-19
甲
A B C 销量（bj） 表4-20 甲 3 1 7
两最小元素之差
乙
丙
丁
5
3 6
3 6 5
3
6（-4）
6 5
3（+5）
6
9
乙 甲 A B C 销量（bj）
11 = 1 3 12 = 2 （+9） 6（-4） 3 6
丙
4（+3） 1（-2）
丁
3（-10）
产量（ai）
7 4
3（+5） 5 6
9
表4-27
甲
A B C 销量（bj）
3 11 = 1 3
乙
12 = 2 22 = 1 6 6
两最小元素之差
6
6
表4-14
A
B C
两最小元素之差
1 7
9 4
5
2 10
8
5 3
0 1 2
2
1
表4-15 甲 乙 丙 丁
A B C 销量（bj）
表4-16
6
3
甲 3
3
5
丙 3 2 10 丁 10 8 5
产量（ai） 7 4 9
6