A B C 销量（ 销量（bj）
第一步：从表4 中找出最小运价“1”， 第一步：从表4-1中找出最小运价“1”， 最小运 价所确定的供应关系为（ ），在 价所确定的供应关系为（B，甲），在（B，甲） 的交叉格处填上“3”，形成表4 的交叉格处填上“3”，形成表4-2；将运价表的 甲列运价划去得表4 甲列运价划去得表4-3.
8.伏格尔法 8.伏格尔法
伏格尔法的基本步骤： 伏格尔法的基本步骤： 1.计算每行、列两个最小运价的差； 1.计算每行、列两个最小运价的差； 计算每行 2.找出最大差所在的行或列 找出最大差所在的行或列； 2.找出最大差所在的行或列； 3.找出该行或列的最小运价 确定供求关系， 找出该行或列的最小运价， 3.找出该行或列的最小运价，确定供求关系，最大量 的供应 ； 4.划掉已满足要求的行或 4.划掉已满足要求的行或 (和) 列，如果需要同时划 去行和列， 去行和列，必须要在该行或列的任意位置填个 0”； “0”； 5.在剩余的运价表中重复1~4步 在剩余的运价表中重复1~4 5.在剩余的运价表中重复1~4步，直到得到初始基可 行解。 行解。
2.表上作业法与单纯形法的关系 2.表上作业法与单纯形法的关系
表上作业法中的最小元素法和伏格尔法实质 上是在求单纯形表中的初始基可行解； 上是在求单纯形表中的初始基可行解； 表上作业法中的“位势法” 表上作业法中的“位势法”实质上是在求单 纯形表中的检验数； 纯形表中的检验数； 调运方案表中数字格的数实质上就是单纯形 法中基变量的值； 法中基变量的值； 调运方案表上的“闭回路法” 调运方案表上的“闭回路法”实质上是在做 单纯形表上的换基迭代。 单纯形表上的换基迭代。
甲 A B C 销量（ 销量（bj） 表4-14 A B C
两最小元素之差
乙
丙
丁
产量（ 产量（ai） 7 4 9
6
3 甲 3 1 7 6 乙 11 9 4 5 5 丙 3 2 10 6 丁 10 8
两最小元素之差
5 3
0 1 2
2
1
表4-15 甲 A B C 销量（ 销量（bj） 表4-16 A B C
3.表上作业法的基本步骤 3.表上作业法的基本步骤
（1）找出初始基可行解： m+n-1个数字格（基变 找出初始基可行解： m+n- 个数字格（ 量）； （2）求各非基变量（空格）的检验数。 求各非基变量（空格）的检验数。 （3）确定入基变量，若min{σ ij | σ ij < 0} = σ lk ,那么 确定入基变量， 那么 选取x 为入基变量； 选取 ij为入基变量； （4）确定出基变量，找出入基变量的闭合回路； 确定出基变量，找出入基变量的闭合回路； （5）在表上用闭合回路法调整运输方案； 在表上用闭合回路法调整运输方案； （6）重复2、3、4、5步骤，直到得到最优解。 重复2 步骤，直到得到最优解。
A B C
销量（bj） 销量（
3 3
产量（ 产量（ai） 7 4 9
最后在产销平衡表上得到一个调运方案， 最后在产销平衡表上得到一个调运方案，见 这一方案的总运费为86个单位。 86个单位 表4-6。这一方案的总运费为86个单位。
最小元素法各步在运价表中划掉的行或列是需求得 到满足的列或产品被调空的行。一般情况下， 到满足的列或产品被调空的行。一般情况下，每填 入一个数相应地划掉一行或一列， 入一个数相应地划掉一行或一列，这样最终将得到 一个具有m+n 个数字格（基变量）的初始基可行解。 m+n一个具有m+n-1个数字格（基变量）的初始基可行解。
表4-1 A B C 销量（ 销量（bj）
表4-12 甲 3 1 7 乙 11 9 丙 3 2 10 丁 10 8 5
两最小元素之差
甲 3 1 7 3
乙 11 9 4 6
丙 3 2 10 5
丁 10 8 5 6
产量（ 产量（ai） 7 4 9
A B C
两最小元素之差
4 5
0 1 1
2
1
3
表4-13
3 6
6 5
3
6
A B C
两最小元素之差
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
2 1 3
6
产量（ 产量（ai） 7 4 9
A B C
乙 11 9 4
丙 3 2 10
丁 10
7. 举例
将例4 的各工厂的产量做适当调整（ 将例4-1的各工厂的产量做适当调整（调 整结果见表4 ），就会出现上述特殊情况 就会出现上述特殊情况。 整结果见表4-7），就会出现上述特殊情况。 表4-7
A B C 销量（ 销量（bj） 甲 3 1 7 3 甲 A B C 销量（ 销量（bj） 3 乙 11 9 4 6 乙 丙 3 2 10 5 丙 丁 10 8 5 6 丁 产量（ 产量（ai） 4 4 12
4.2.2 基可行解的最优性检验
对初始基可行解的最优性检验有闭合回路法 对初始基可行解的最优性检验有闭合回路法 位势法两种基本方法 闭合回路法具体、 两种基本方法。 和位势法两种基本方法。闭合回路法具体、 直接，并为方案调整指明了方向； 直接，并为方案调整指明了方向；而位势法 具有批处理的功能，提高了计算效率。 具有批处理的功能，提高了计算效率。 所谓闭合回路 闭合回路是 所谓闭合回路是在已给出的调运方案的运输 表上从一个代表非基变量的空格出发， 表上从一个代表非基变量的空格出发，沿水 平或垂直方向前进， 平或垂直方向前进，只有遇到代表基变量的 填入数字的格才能向左或右转90 90度 填入数字的格才能向左或右转90度（当然也 可以不改变方向）继续前进，这样继续下去， 可以不改变方向）继续前进，这样继续下去， 直至回到出发的那个空格， 直至回到出发的那个空格，由此形成的封闭 折线叫做闭合回路。 折线叫做闭合回路。一个空格存在唯一的闭 回路。 回路。
A B C 销量（ 销量（bj）
第三步：在表4 中再找出最小运价“3”， 第三步：在表4-5中再找出最小运价“3”， 这样一步步地进行下去， 这样一步步地进行下去，直到单位运价表上 的所有元素均被划去为止。 的所有元素均被划去为止。
表4-6 A B C 销量（ 销量（bj） 表4-7 甲 乙 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丙 4 1 6 6 3 5 6 丁 10 8 5 6 丁 3 产量（ 产量（ai） 7 4 9
表4-8 0 3 6
6 5
4 1 6
6
产量（ 产量（ai） 4 4 12
8.伏格法尔法 8.伏格法尔法
每次从当前运价表上，计算各行各列 每次从当前运价表上， 中两个最小运价之差值（行差值h 中两个最小运价之差值（行差值hi，列差 ），优先取最大差值的行或列中最小 值kj），优先取最大差值的行或列中最小 的格来确定运输关系，直到求出初始方案。 的格来确定运输关系，直到求出初始方案。
最小元素法
最小元素法的基本思想是就近供应， 最小元素法的基本思想是就近供应，即 从单位运价表中最小的运价开始确定产 销关系，依此类推， 销关系，依此类推，一直到给出基本方 案为止。 案为止。
最小元素法的应用（以引例4 为例） 最小元素法的应用（以引例4-1为例）
表4-1 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 产量（ 产量（ai） 7 4 9
两最小元素之差
乙
丙
丁
6
3 甲 3 6 乙 11 9 4 丙 3 2 10 5 丁 10 8 5
3
6
产量（ 产量（ai） 7 4 9
两最小元素之差
1
7
0 1
2
1
2
表4-17 甲 A B C 销量（ 销量（bj） 表4- 18 甲 3 1 7 乙 11 9 4 丙 3 乙 丙 丁 产量（ 产量（ai） 7 4 9
两最小元素之差
85Biblioteka 2表4-23 甲 A B C 销量（ 销量（bj） 乙 丙 丁
5 3 6
3 6 5 6
2 1 3
产量（ 产量（ai） 7 4 9
总运费为85 总运费为 由以上可见， 由以上可见，伏格尔法同最小元素法除在确 定供求关系的原则上不同外， 定供求关系的原则上不同外，其余步骤是完 全相同的。伏格尔法给出的初始解比最小元 全相同的。 素法给出的初始解一般来讲会更接近于最优 解。
甲 A B C 销量（ 销量（bj） 3 3 甲 3 1 7 3
表4-4 乙
丙 1
丁
产量（ 产量（ai） 7 4 9
6 表4-5 乙 11 9 4 6
5 丙 3 2 10 5
6 丁 10 8 5 6 产量（ 产量（ai） 7 4 9
A B C 销量（ 销量（bj）
表4-5 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 产量（ 产量（ai） 7 4 9
4、确定初始基可行解
与一般的线性规划不同， 与一般的线性规划不同，产销平衡的运输问 题一定具有可行解（ 题一定具有可行解（同时也一定存在最优 解）。 最小元素法（ 最小元素法（the least cost rule）和伏格尔法 ） （Vogel’s approximation method）。 ）。 最小元素法 最小元素法的基本思想是就近供应， 最小元素法的基本思想是就近供应，即从单位 就近供应 运价表中最小的运价开始确定产销关系， 运价表中最小的运价开始确定产销关系，依此 类推，一直到给出基本方案为止. 类推，一直到给出基本方案为止
甲 A B C 销量（ 销量（bj） 3 3 甲 3 1 7 3