表上作业法
表上作业法
表上作业法与单纯形法的关系
表上作业法的基本步骤
确定初始基可行解
最小元素法的基本步骤
伏格尔法
三、 运输问题的求解
运输问题的求解采用表上作业法，即用列
表的方法求解线性规划问题中的运输模型的
计算方法，实质上是单纯形法。
表上作业法是一种特定形式的单纯形法，
它与单纯形法有着完全相同的解题步骤，所
不同的只是完成各步采用的具体形式。
1.表上作业法
2.表上作业法与单纯形法的关系
表上作业法中的最小元素法和伏格尔法实质
上是在求单纯形表中的初始基可行解；
表上作业法中的“位势法”实质上是在求单
纯形表中的检验数；
调运方案表中数字格的数实质上就是单纯形
法中基变量的值；
调运方案表上的“闭回路法”实质上是在做
单纯形表上的换基迭代。
（1）找出初始基可行解： m+n-1个数字格（基变量）
；
（2）求各非基变量（空格）的检验数。
,那么
选取xij为入基变量；
（3）确定入基变量，若
3.表上作业法的基本步骤
（4）确定出基变量，找出入基变量的闭合回路；
（5）在表上用闭合回路法调整运输方案；
（6）重复2、3、4、5步骤，直到得到最优解。
4、确定初始基可行解
与一般的线性规划不同，产销平衡的运输问
题一定具有可行解（同时也一定存在最优解）
。
最小元素法（the least cost rule）和伏格尔法
（Vogel’s approximation method）。
最小元素法的基本思想是就近供应，即从单位
运价表中最小的运价开始确定产销关系，依此
类推，一直到给出基本方案为止.
最小元素法
找出最小运价，确定供求关系，最大量的供应
；
划掉已满足要求的行或 (和) 列，如果需要同
时划去行和列，必须要在该行或列的任意位置
填个“0”；
在剩余的运价表中重复1、2两步，直到得到初
始基可行解。
5、最小元素法的基本步骤
最小元素法
最小元素法的基本思想是就近供应，即
从单位运价表中最小的运价开始确定产
销关系，依此类推，一直到给出基本方
案为止。
表4-1
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
3 6 5 6
最小元素法的应用（以引例4-1为例）
第一步：从表第一步：从表4-14-1中找出最小运价中找出最小运价“1”“1”，， 最小运最小运
价所确定的供应关系为（价所确定的供应关系为（BB，甲），在（，甲），在（BB，甲），甲）
的交叉格处填上的交叉格处填上“3”“3”，形成表，形成表4-24-2；将运价表的；将运价表的
甲列运价划去得表甲列运价划去得表-3.
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
3 6 5 6
表4-2
表4-3
3
第二步：在表第二步：在表4-34-3的未被划掉的元素中再找出最小的未被划掉的元素中再找出最小
运价运价“2”“2”，最小运价所确定的供应关系为（，最小运价所确定的供应关系为（BB，，
丙），即将丙），即将BB余下的余下的11个单位产品供应给丙，表个单位产品供应给丙，表4-24-2
转换成表转换成表4-44-4。划去。划去BB行的运价，划去行的运价，划去BB行表明行表明BB所所
生产的产品已全部运出，表生产的产品已全部运出，表4-34-3转换成表转换成表4-54-5。。
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
3 6 5 6
表4-3
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
3 6 5 6
表4-4
表4-5
3 1
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
3 6 5 6
表4-5
第三步：在表4-5中再找出最小运价“3”，
这样一步步地进行下去，直到单位运价表上
的所有元素均被划去为止。
表4-7
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
表4-6
甲 乙 丙 丁 产量（ai
）
A 3 11 10 7
B 1 9 8 4
C 7 10 9
销量（bj
）
3 6 5 6
3
2
1
3
4
4
6
5
3
3
最后在产销平衡表上得到一个调运方案，见
表4-6。这一方案的总运费为86个单位。
最小元素法各步在运价表中划掉的行或列是需求得
到满足的列或产品被调空的行。一般情况下，每填入
一个数相应地划掉一行或一列，这样最终将得到一个
具有m+n-1个数字格（基变量）的初始基可行解。
在供需关系格（在供需关系格（ii，，j j ）处填入一数字，刚好）处填入一数字，刚好
使第使第 i i个产地的产品调空，同时也使第个产地的产品调空，同时也使第jj个销地的个销地的
需求得到满足。填入一数字同时划去了一行和一需求得到满足。填入一数字同时划去了一行和一
列，那么最终必然无法得到一个具有列，那么最终必然无法得到一个具有m+n-1m+n-1个数字个数字
格（基变量）的初始基可行解。格（基变量）的初始基可行解。
6.应注意的问题
为了使在产销平衡表上有为了使在产销平衡表上有m+n-1m+n-1个数字格，这时个数字格，这时
需要在第行或第列此前未被划掉的任意一个空格需要在第行或第列此前未被划掉的任意一个空格
上填一个上填一个“0”“0”。填。填“0”“0”格虽然所反映的运输量格虽然所反映的运输量
同空格没有什么不同；但它所对应的变量却是基同空格没有什么不同；但它所对应的变量却是基
变量，而空格所对应的变量是非基变量。变量，而空格所对应的变量是非基变量。
表4-7
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 4
B 1 9 2 8 4
C 7 4 10 5 12
销量（bj
）
3 6 5 6
表4-8
甲 乙 丙 丁 产量（ai
）
A 4
B 4
C 12
销量（bj
）
3 6 5 6
3 1
4
7. 举例
将例4-1的各工厂的产量做适当调整（调
整结果见表4-7），就会出现上述特殊情况。
0
6 6
每次从当前运价表上，计算各行各列
中两个最小运价之差值（行差值hi，列差
值kj），优先取最大差值的行或列中最小
的格来确定运输关系，直到求出初始方案。
8.伏格法尔法
伏格尔法的基本步骤：
8.伏格尔法
1.计算每行、列两个最小运价的差；
2.找出最大差所在的行或列；
3.找出该行或列的最小运价，确定供求关系，最大量
的供应 ；
4.划掉已满足要求的行或 (和) 列，如果需要同时划
去行和列，必须要在该行或列的任意位置填个
“0”；
5.在剩余的运价表中重复1~4步，直到得到初始基可
行解。
表4-1
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
3 6 5 6表4-12
甲 乙 丙 丁 两最小元素之差
A 3 11 3 10
B 1 9 2 8
C 7 10 5
两最小元素之差 1 3
0
1
1
2 5
4
表4-13
甲 乙 丙 丁 产量（ai）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
表4-14
甲 乙 丙 丁 两最小元素之差
A 3 11 3 10
B 1 9 2 8
C 7 4 10
两最小元素之差 5
6
2 1 3
0
1
25
表4-15
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
6 3
表4-16
甲 乙 丙 丁 两最小元素之差
A 3 11 3 10
B 9 2 8
C 7 4 10 5
两最小元素之差 2 1 2
0
11
表4-17
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
6 3
3
表4- 18
甲 乙 丙 丁 两最小元素之差
A 3 11 10
B 1 9 2 8
C 7 4 10 5
两最小元素之差 1 2
6
73
表4-19
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
表4-20
甲 乙 丙 丁 两最小元素之差
A 3 11 3 10
B 1 9 2
C 7 4 10 5
两最小元素之差
6 3
3
5
2
8
1
2
总运费为85
由以上可见，伏格尔法同最小元素法除在确
定供求关系的原则上不同外，其余步骤是完
全相同的。伏格尔法给出的初始解比最小元
素法给出的初始解一般来讲会更接近于最优
解。
表4-23
甲 乙 丙 丁 产量（ai
）
A 7
B 4
C 9
销量（bj
）
3 6 5 6
6 3
3
5
1
2
基可行解的最优性检验
对初始基可行解的最优性检验有闭合回路法
和位势法两种基本方法。闭合回路法具体、
直接，并为方案调整指明了方向；而位势法
具有批处理的功能，提高了计算效率。
所谓闭合回路是在已给出的调运方案的运输
表上从一个代表非基变量的空格出发，沿水
平或垂直方向前进，只有遇到代表基变量的
填入数字的格才能向左或右转90度（当然也
可以不改变方向）继续前进，这样继续下去，
直至回到出发的那个空格，由此形成的封闭
折线叫做闭合回路。一个空格存在唯一的闭
回路。
所谓闭合回路法，就是对于代表非基变量的
空格（其调运量为零），把它的调运量调整
为1，由于产销平衡的要求,我们必须对这个
空格的闭回路的顶点的调运量加上或减少1。
最后我们计算出由这些变化给整个运输方案
的总运输费带来的变化。如果所有代表非基
变量的空格的检验数也即非基变量的检验数
都大于等于零，则已求得最优解，否则继续
迭代找出最优解。
1.闭合回路
下面就以表4-6中给出的初始基可行解（最小
元素法所给出的初始方案）为例，讨论闭合回
路法。
表4-24
甲 乙 丙 丁 产量（ai）
A 4 3 7
B 3 1 4
C 6 3 9
销量（bj
）
3 6 5 6
（+3） （-3）
（+2）（-1）
从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对于
空格（A，甲）在初始方案的基础上将A生产的产品调运一个单
位给甲，为了保持新的平衡，就要依次在（A，丙）处减少一
个单位、（B，丙）处增加一个单位、（B，甲）处减少一个单
位；即要寻找一条除空格（A，甲）之外其余顶点均为有数字
格（基变量）组成的闭合回路。表4-24中用虚线画出了这条闭
合回路。闭合回路顶点所在格括号内的数字是相应的单位运价，
单位运价前的“+”、“-”号表示运量的调整方向。
对应这样的方案调整，运费会有什么变化呢？可以
看出（A，甲）处增加一个单位，运费增加3个单位；
在（A，丙）处减少一个单位，运费减少3个单位；在
（B，丙）处增加一个单位，运费增加2个单位；在
（B，甲）处减少一个单位，运费减少1个单位。增减
相抵后，总的运费增加了1个单位。由检验数的经济
含义可以知道，（A，甲）处单位运量调整所引起的
运费增量就是（A，甲）的检验数，即σ11=1。
表4-24
甲 乙 丙 丁 产量（ai）
A 4 3 7
B 3 1 4
C 6 3 9
销量（bj
）
3 6 5 6
（+3） （-3）
（+2）（-1）
仿照此步骤可以计算初始方案中所有空
格的检验数，表4-25～表4-30展示了各
检验数的计算过程，表4-30给出了最终
结果。可以证明，对初始方案中的每一
个空格来说“闭合回路存在且唯一”。
表4-25
甲 乙 丙 丁 产量（ai）
A 11 = 1 （+11） 4 3（-10） 7
B 3 1 4
C 6（-4） 3（+5） 9
销量（bj
）
3 6 5 6
表4-26
甲
乙 丙 丁 产量（ai）
A 11 = 1 12 = 2 4（+3） 3（-10） 7
B 3 （+9） 1（-2） 4
C 6（-4） 3（+5） 9
销量（bj
）
3 6 5 6
表4-27
甲 乙 丙 丁 产量（ai）
A 11 = 1 12 = 2 4（+3） 3（-10） 7
B 3 22 = 1 1（-2） （+8） 4
C 6 3 9
销量（bj
）
3 6 5 6
表4-28
甲 乙 丙 丁 产量（ai
）
A 11 = 1 12 = 2 4（-3） 3（+10） 7
B 3 22 = 1 1 24 = -1 4
C 6 （+10） 3（-5） 9
销量（bj
）
3 6 5 6
表4-29
甲 乙 丙 丁 产量（ai
）
A 11 = 1 12 = 2 4（-3） 3（+10） 7
B 3（-1） 22 = 1 1（+2） 24 = -1 4
C （+7） 6 33 = 12 3（-5） 9
销量（bj
）
3 6 5 6表4-30
甲 乙 丙 丁 产量（ai
）
A 11 = 1 12 = 2 4 3 7
B 3 22 = 1 1 24 = -1 4
C 31 = 10 6 33 = 12 3 9
销量（bj
）
3 6 5 6
如果检验数表中所有数字均大于等于零，
这表明对调运方案做出任何改变都将导
致运费的增加，即给定的方案是最优方
案。在表4-30中， 24 = -1,说明方案
需要进一步改进。
2.位势法
对于特定的调运方案的每一行给出一个
因子 ui（称为行位势），每一列给出一
个因子vj（称为列位势），使对于目前解
的每一个基变量xij 有cij= ui + vj，这里
的ui 和 vj可正、可负也可以为零。那么
任一非基变量 xij的检验数就是
这一表达式完全可以通过先前所述的闭合
回路法得到。在某一的闭合回路上（如下表
所示），由于基变量的运价等于其所对应的
行位势与列位势之和，即：
非基变量
基变量
（-cik）基变量
（+clk）基变量
（+cij）
（-clj）
于是
所以
对于一个具有m个产地、n个销地的运输问题，应具
有m个行位势、n个列位势，即具有“m+n”个位势。
运输问题基变量的个数只有“m+n-1”个，所以利
用基变量所对应的“m+n-1”个方程，求出“m+n”
个位势，进而计算各非基变量的检验数是不现实的。
通常可以通过在这些方程中对任意一个因子假定一
个任意的值（如u1=0等等），再求解其余的“m+n-
1”个未知因子，这样就可求得所有空格（非基变量）
的检验数。仍以表4-6中给出的初始基可行解（最小
元素法所给出的初始方案）为例，讨论位势法求解
非基变量检验数的过程。
第一步：把方案表中基变量格填入其相应的
运价并令u1=0 ；让每一个基变量xij都有cij=
ui + vj ，可求得所有的位势，如表4-32所
示。
表4-32
甲 乙 丙 丁
A 3 10
B 1 2
C 4 5
第二步：利用 计算各非基变量xij
的检验数，结果见表4-30。
103
-1
-5
92
0
方案的优化
在负检验数中找出最小的检验数，该检验数
所对应的变量即为入基变量。在入基变量所
处的闭合回路上，赋予入基变量最大的增量，
即可完成方案的优化。在入基变量有最大增
量的同时，一定存在原来的某一基变量减少
为“0”，该变量即为出基变量。切记出基
变量的“0”运量要用“空格”来表示，而
不能留有“0”。
在表4-30中， ，故选择
x24为入基变量。在入基变量x24所处的闭合回路上
（如表4-33所示），赋予最大的增量“1”，相应地
有
x23最大的增量“1”，相应地有x23出基, x13=5,x14=2.
利用闭合回路法或位势法计算各空格（非基变量）的
检验数，可得表4-34（同伏格尔法的初始解表4-23）。
表4-30
甲 乙 丙 丁 产量（ai
）
A 11 = 1 12 = 2 4 3 7
B 3 22 = 1 1 24 = -1 4
C 31 = 10 6 33 = 12 3 9
销量（bj
）
3 6 5 6
表4-33
甲
乙 丙 丁 产量（ai）
A 11 = 1 12 = 2 4 3 7
B 3 22 = 1 1 24 = -1 4
C 31 = 10 6 33 = 12 3 9
销量（bj
）
3 6 5 6
表4-34
甲 乙 丙 丁 产量（ai）
A 5 2 7
B 3 1 4
C 6 3 9
销量（bj
）
3 6 5 6
由于表4-33中的检验数均大于等于零，所以表4-33（同伏格尔法
所给出的初始解表4-23）给出的方案是最优方案，这个最优方案的
运费是85个单位。
23 = 1
31 = 9
22 = 2
11 = 1 12 = 2
33 = 12
§运输问题的拓展
总产量大于总销量的运输问题即为产大于
销的运输问题。
在实际问题中，产大于销意味着某些产品
被积压在仓库中。可以这样设想，如果把
仓库也看成是一个假想的销地，并令其销
量刚好等于总产量与总销量的差；那么，
产大于销的运输问题就转换成产销平衡的
运输问题
假想一个销地，相当于在原产销关系表上
增加一列。
产大于销的运输问题
假想列所对应的运价
由于假想的销地代表的是仓库，而我们
优化的运费是产地与销地间的运输费用，
并不包括厂内的运输费用；所以假想列
所对应的运价都应取为“0”。
至此，我们已经将产大于销的运输问题
转换成产销平衡的运输问题，进一步的
求解可利用上节介绍的表上作业法来完
成。
[例4-2] 将表4-35所示的产大于销
的运输问题转换成产销平衡的运输问
题
表4-35
甲 乙 丙 丁 产量（ai）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 12
销量（bj
）
3 6 5 6
解 此运输问题的总产量为23、总销量为20，所以
假设一个销地戊并令其销量刚好等于总产量与总销
量的差“3”。取假想的戊列所对应的运价都为
“0”，可得表4-36所示的产销平衡运输问题。
表4-36
甲 乙 丙 丁 戊 产量（ai
）
A 3 11 3 10 0 7
B 1 9 2 8 0 4
C 7 4 10 5 0 12
销量（bj
）
3 6 5 6 3
销大于产的运输问题
总销量大于总产量的运输问题即为销大于产的运
输问题。
可以这样设想，假想一个产地，并令其产量刚好
等于总销量与总产量的差；那么，销大于产的运
输问题同样可以转换成产销平衡的运输问题
假想的产地并不存在，于是各销地从假想产地所
得到的运量，实际上所表示的是其未满足的需求。
由于假想的产地与各销地之间并不存在实际的运
输，所以假想的产地行所有的运价都应该是“0”。
至此，我们又将销大于产的运输问题转换成了产
销平衡的运输问题。
[例4-3] 将表4-37所示的销大于产
的运输问题转换成产销平衡的运输
问题
表4-37
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
销量（bj
）
11 6 5 6
解 此运输问题的总产量为20、总销量为28，所以
假设一个产地D并令其产量刚好等于总销量与总产量
的差“8”。令假想的D行所对应的运价都为“0”，
可得表4-37所示的产销平衡运输问题。
表4-38
甲 乙 丙 丁 产量（ai
）
A 3 11 3 10 7
B 1 9 2 8 4
C 7 4 10 5 9
D 0 0 0 0 8
销量（bj
）
11 6 5 6
运输问题的应用举例
[例4-4] 设有三个化肥厂供应四个地区的化
肥需求，假定等量化肥在这些地区的使用效
果相同。各化肥厂年产量、各地区年需要量
及从各化肥厂到各地区运送单位化肥的单位
运价如表4-39所示，试求出总的运费最节省
的化肥调拨方案。
表4-39
地区1 地区2 地区3 地区4 年产量
化肥厂A 16 13 22 17 50
化肥厂B 14 13 19 15 60
化肥厂C 19 20 23 M 50
年需要量
/万t
最低需求 30 70 0 10
最高需求 50 70 30 不限
根据现有产量，除满足地区1、地区2和地区3的
最低需求外，地区4每年最多能分配到60万吨，
这样其不限的最高需求可等价认为是60万吨。
解 这是一个产销不平衡的运输问题，总产量
为160万吨，四个地区的最低需求为110万吨，最高
需求为无限。
按最高需求分析，总需求为210万吨，大于总
产量160万吨，将此问题定义为销大于产的运
输问题。
为了求得平衡，在产销平衡表中增加一个假想
的化肥厂D，令其年产量为50万吨。
各地区的需要量包含最低和最高两部分：如地
区1，其中30万吨是最低需求，故这部分需求
不能由假想的化肥厂D来供给，因此相应的运
价定义为任意大正数M ；而另一部分20万吨满
足与否都是可以的，因此可以由假想化肥厂D
来供给，按前面讲的，令相应运价为“0”。
凡是需求分两种情况的地区，实际上可按
照两个地区来看待，这样可以将表4-39所示
的运输问题转换为表4-40所示的运输问题。
表4-40 （单位：万吨）
地区1 地区1 地区2 地区3 地区4 地区4 年产量
化肥厂A 16 16 13 22 17 17 50
化肥厂B 14 14 13 19 15 15 60
化肥厂C 19 19 20 23 M M 50
化肥厂D M 0 M 0 M 0 50
年需要量 30 20 70 30 10 50
用表上作业法计算，可以求得这个问题的最优方案
如表4-41所示。
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 13 22 17 17
B 14 14 13 19 15 15
C 19 19 20 23 M M
D M 0 M M 0
两最小元素差
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
19
0
30
2 14 0 2 15
3
1
0
0
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 13 22 17 17
B 14 14 13 19 15 15
C 19 19 20 23 M M
D M 0 M 0 M
两最小元素差 2 14 0 2 15
3
1
0
00
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
30 20
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 22 17 17
B 14 14 13 19 15 15
C 19 19 20 23 M M
D M 0 M 0 M
两最小元素差 2 2 0 2 2
3
1
0
00
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
30 20
13
50
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 22 17 17
B 14 14 13 19 15
C 19 19 20 23 M M
D M 0 M 0 M
两最小元素差 5 5 7 M M
3
1
0
00
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
30 20
13
50
15
10
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 22 17 17
B 14 14 13 19
C 19 19 20 23 M M
D M 0 M 0 M
两最小元素差 5 5 7 M M
3
1
0
00
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
30 20
13
50
15
10
15
30
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 22 17 17
B 14 19
C 19 19 20 23 M M
D M 0 M 0 M
两最小元素差 5 5 7 M M
3
0
0
00
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
30 20
13
50
15
10
15
30
13
20
14
地区1 地区1 地区2 地区3 地区4 地区4 两最小元素差
A 16 16 22 17 17
B 14 14 19
C 19 19 20 23 M M
D M 0 M 0 M
两最小元素差 5 5 7 M M
3
1
0
00
地区1 地区1 地区2 地区3 地区4 地区4 年产量
A 50
B 60
C 50
D 50
年需要量 30 20 70 30 10 50
30 20
13
50
15
10
15
30
13
20
030 20
[例4-6] 在A1、A2、A3、A4、A5和A6六个经济区
之间有砖、砂子、炉灰、块石、卵石、木材和
钢材七种物资需要运输。具体的运输需求如表
4-43所示，各地点间的路程（公里）见表4-44
，试确定一个最优的汽车调度方案。
表4-43
货物 起点 终点 车次 起点 终点 车次 起点 终点 车次
砖 A1 A3 11 A1 A5 2 A1 A6 6
砂子 A2 A1 14 A2 A3 3 A2 A6 3
炉灰 A3 A1 9 A4 A1 4
块石 A3 A4 7 A3 A6 5
卵石 A4 A2 8 A4 A5 3
木材 A5 A2 2
钢材 A6 A4 4
表4-44
到
从
A2 A3 A4 A5 A6
A1 2 11 9 13 15
A2 2 10 14 10
A3 4 5 9
A4 4 16
A5 6汽车的最优调度实质上就是空车行驶的
公里数最少。先构造如表4-45所示的各地
区汽车出入平衡表，表中“十”号表示该
点产生空车，“—”号表示该点需要调进
空车。
表4-44
A1 A2 A3 A4 A5 A6
出车数 19 20 21 15 2 4
来车数 27 10 14 11 5 14
平衡数 +8 -10 -7 -4 +3 +10
平衡结果A1、A5、A6除装运自己的货物外，可
多出空车21车次；A2、A3、A4缺21车次。按最
小空驶调度，可构造表4-46所示的运输问题
数据表，进而可得表4-47所示的最优调度方
案。
表4-45
A2 A3 A4 ai
A1 2 11 9 8
A5 14 5 4 3
A6 10 9 16 10
bj 10 7 4
表4-46
A2 A3 A4 ai
A1 8 8
A5 3 3
A6 2 7 1 10
bj 10 7 4
作 业
课本P62：6、7题
课本P63：8题
第62页习题
6.已知某厂每月可生产甲产品270吨，先运至
A1、A2、A3三个仓库，然后在分别供应B1、B2、
B3、B4、B5五个用户。已知仓库容量分别为50、
100、150吨，各用户的需要量分别为25、105、
60、30、70吨。已知从该厂经各仓库然后供应
各用户的运费如下表所示，试确定一个使总运
费最少的调运方案。
8/8/2022
仓库总容量：50+100+150=300（t）
各地区需求：25+105+60+30+70=290（t）
由于该厂每月最多生产甲产品270t，则仓库有30t
不满，各地区有20t不能满足需求
可假设存在仓库A4，它的存储量为20t，用户B6 的
需求量为30t。这样就转化为产销平衡问题。由于
A4 与B6都是假设的，不需要运输，故运价都为0，
但是由A4运到B6的运输无法发生，因两者皆为假设
的，运价为无穷大，设为M。
此题属于产销不平衡问题
第62页习题
8/8/2022
用伏格尔法求解初始基可行解得：
B1 B2 B3 B4 B5 B6 产量
A1 50 50
A2 25 45 30 100
A3 10 60 50 30 150
A4 20 20
销量 25 105 60 30 70 30
数字格内填入相应价格，用位势法检验是否为最优解，得：
B1 B2 B3 B4 B5 B6 ui
A1 15 0
A2 20 40 30 25
A3 35 40 25 0 20
A4 0 -5
vj -5 15 20 5 5 -20
用位势法检验是否为最优解，得：
B1 B2 B3 B4 B5 B6 ui
A1 σ11=15 15 σ13= 0 σ14= 15 σ15=35 σ16=20 0
A2 20 40 σ23=-30 30 σ25=0 σ26=-5 25
A3 σ31=15 35 40 σ34=30 25 0 20
A4 σ41= 10 σ42=-10 σ43=-15 σ44=0 0 σ46=M+25 -5
vj -5 15 20 5 5 -20
因检验数存在负数，故需用闭合回路法调整
B1 B2 B3 B4 B5 B6 产量
A1 σ11=15 50 σ13= 0 σ14= 15 σ15=35 σ16=20 50
A2 25 45 σ23=-30 30 σ25=0 σ26=-5 100
A3 σ31=15 10 60 σ34=30 50 30 150
A4 σ41= 10 σ42=-10 σ43=-15 σ44=0 20 σ46=M+25 20
销量 25 105 60 30 70 30
用闭合回路法调整得：
B1 B2 B3 B4 B5 B6 产量
A1 50 50
A2 25 60 15 100
A3 50 70 30 150
A4 5 15 20
销量 25 105 60 30 70 30
用位势法检验得：
B1 B2 B3 B4 B5 B6 ui
A1 （5
）
15 (20) (5) (35) (20) 0
A2 20 （10
）
15 30 (10) (5) 15
A3 (5) 35 （20
）
(20) 25 0 20
A4 (10) 0 (15) 0 (10) (M+35) -15
vj 5 15 0 15 5 -20
因检验数全为正，所以已得最优方案。
即A3差30t没有得到满足， B2缺5t，B4缺15t。
7、已知某运输问题的单位运价及最优调运方
案如表所示（括号中的数据代表运输数量），
由于产地A2至销地B2的道路关闭，故最优调运
方案将发生变化，试在原最优调运方案的基础
上，寻找新的最优调运方案。
表4-50
B1 B2 B3 B4 B5 ai
A1 10 20 5（4） 9（5
）
10 9
A2 2 10（4
）
10 30 6 4
A3 1（3） 20（1
）
7 10（1
）
4（3
）
8
bj 3 5 4 6 3
解：由于A2 到B2道路关闭，则其运价为M，应
令其出基，以实现最优调度。先将M反映进产
销平衡表，然后用位势法作检验，有：
B1 B2 B3 B4 B5
A1 （10） （1） 5 9 (7) 0
A2 （21-
M）
M (24-M) （40-
M）
(22-M) M-19
A3 1 20 （1） 10 4 1
0 19 5 9 3
要令A2 B2出基，即令其运输量为0，找出负检验数最小的来
进行调整，得：
B1 B2 B3 B4 B5 产量
A1 4 5 9
A2 3 1 4
A3 5 1 2 8
销量 3 5 4 6 3
用位势法作检验，有：
B1 B2 B3 B4 B5
A1 （11
）
（1） 5 9 (7) 0
A2 2 （M-
22）
(2) （18） 6 3
A3 （1） 20 （1） 10 4 1
-1 19 5 9 3
检验数已全为非负，故已得最优调度方案。
8、已知某运输问题的单位运价及最优调运方
案如表4所示，试回答下述问题：
(1)A1到B2、A3到B5、和A4到B1的单位运价，分
别在什么范围内变化时上表中给出的最优
方案不变；
(2)若A1到B2的单位运价由1变为3，最优方案
将发生怎样的变化；
(3)若A3到B5的单位运价由4变为2，最优方案
将发生怎样的变化；
表4-51
B1 B2 B3 B4 B5 B6 ai
A1 2（20
）
1（30
）
3 3 3 5 50
A2 4 2（20
）
2（20
）
4 4 4 40
A3 3（10
）
5 4 2（39
）
4 1（11
）
60
A4 4 2 2 1（1
）
2（30
）
2 31
bj 30 50 20 40 30 11
解：（1）设A1 到B2的单位运价为c12，因A1 到B2是
基变量，它的运价变化会引起非基变量检验系数的
变化，此时，只需对其再进行位势法分析即可。
8/8/2022
要令最优方案不变，则非基变量的检验数非负；
故有c12 ≥0；3- c12 ≥ 0；4- c12 ≥0；2- c12
≥ 0；2+ c12≥0；1+ c12 ≥ 0
解上述不等式得0≤ c12 ≤2。即A1 到B2的单位
运价在[0，2]内变化时，最有方案不变。
B1 B2 B3 B4 B5 B6
A1 2 c12 (3- c12) (2) (1) (5) 0
A2 （ c12
）
2 2 （20） (1+ c12) (2+ c12) 2- c12
A3 3 （4- c12
）
（3- c12
）
2 （1） 1 1
A4 (c12) (2- c12) (1) 1 2 (2) 0
2 c12 c12 1 2 0
(1)
A3 到B5的单位运价属于非基变量，它的变
化不会引起其它检验数变化，故只需保证其
检验数非负即可。
先用位势法算出原方案的检验数：
B1 B2 B3 B4 B5 B6 ui
A1 2 1 (2) (2) (1) (5) 0
A2 （1
）
2 2 （3） (1) (3) 1
A3 3 （3
）
（2） 2 （1） 1 1
A4 (2) (1) (1) 1 2 (2) 0
vj 2 1 1 1 2 0 设A3 到B5的单位运价为c35，则其检验数满足
c35 -（1+2）≥ 0，即c35 ≥ 3。也就是说A3 到B5的
单位运价大于等于3时，最有方案不变。
A4 到B1的单位运价属于非基变量，它的变化
不会引起其它检验数变化，故只需保证其检
验数非负即可。
设A4到B1的单位运价为c41，则其检验数
满足c41 -（0+2）≥ 0，即c35 ≥2。也就是说
A4到B1的单位运价大于等于2时，即A4 到B1的
单位运价变化范围是[2，+∞)最有方案不变。
先用位势法算出原方案的检验数：
B1 B2 B3 B4 B5 B6 ui
A1 2 1 (2) (2) (1) (5) 0
A2 （1
）
2 2 （3） (1) (3) 1
A3 3 （3
）
（2） 2 （1） 1 1
A4 (2) (1) (1) 1 2 (2) 0
vj 2 1 1 1 2 0
把变化直接反映到表中可得下表：
B1 B2 B3 B4 B5 B6
A1 2 3 (0) (2) (1) (5) 0
A2 （3
）
2 2 （20
）
(4) (5) -1
A3 3 （1
）
（0） 2 （1） 1 1
A4 (3) (-1) (1) 1 2 (2) 0
2 3 3 1 2 0
(2)若A1到B2的单位运价由1变为3，最优方案将发生
怎样的变化；
因存在检验数为负数，最优方案发生改变，用闭合回路法调整得：
B1 B2 B3 B4 B5 B6 ai
A1 21 29 50
A2 20 20 40
A3 9 40 11 60
A4 1 30 31
bj 30 50 20 40 30 11
表4-51
B1 B2 B3 B4 B5 B6 ai
A1 2（20
）
3（30
）
50
A2 2（20
）
2（20
）
40
A3 3（10
）
2（39
）
1（11
）
60
A4 1（1
）
2（30
）
31
bj 30 50 20 40 30 11
重新计算检验数，得：
B1 B2 B3 B4 B5 B6
A1 2 3 (0) (2) (0) (5) 0
A2 （3
）
2 2 （4） (2) (5) -1
A3 3 （1
）
（0） 2 （0） 1 1
A4 (3) 2 (0) （1） 2 (3) -1
2 3 3 1 3 0非基变量检验数均为非负，故为最优方案。
（3）把A3 到B5的单位运价改为2，然后求检验数得：
B1 B2 B3 B4 B5 B6
A1 2 1 (2) (2) (1) (5) 0
A2 （1
）
2 2 （3） (1) (3) 1
A3 3 （3
）
（2） 2 （-1） 1 1
A4 (2) (1) (1) 1 2 (2) 0
2 1 1 1 2 0
B1 B2 B3 B4 B5 B6 ai
A1 2（20
）
1（30
）
3 3 3 5 50
A2 4 2（20
）
2（20
）
4 4 4 40
A3 3（10
）
5 4 2（39
）
4 1（11
）
60
A4 4 2 2 1（1
）
2（30
）
2 31
bj 30 50 20 40 30 11
表4-51
由于存在负检验数，故最优方案发生变化，此时用闭合回路法调
整得：
B1 B2 B3 B4 B5 B6 ai
A1 20 30 50
A2 20 20 40
A3 10 9 30 11 60
A4 31 31
bj 30 50 20 40 30 11
重新计算检验数，得：
B1 B2 B3 B4 B5 B6
A1 2 1 (2) (2) (1) (5) 0
A2 （1
）
2 2 （2） (1) (3) 1
A3 3 （3
）
（2） 2 （1） 1 1
A4 (2) (1) (1) 1 2 (2) 0
2 1 1 1 2 0
检验数全为非负，故已得最优方案。
B1 B2 B3 B4 B5 B6 产量
A1 σ11=15 50 σ13= 0 σ14= 15 σ15=35 σ16=20 50
A2 25 45 σ23=-30 30 σ25=0 σ26=-5 100
A3 σ31=15 10 60 σ34=30 50 30 150
A4 σ41= 10 σ42=-10 σ43=-15 σ44=0 20 σ46=M+25 20
销量 25 105 60 30 70 30
B1 B2 B3 B4 B5 B6 产量
A1 σ11=15 50 σ13= 0 σ14= 15 σ15=35 σ16=20 50
A2 25 45 30 σ25=0 σ26=-5 100
A3 σ31=15 σ34=30 30 150
A4 σ41= 10 σ44=0 σ46=M+25 20
销量 25 105 60 30 70 30
6515 50
20σ43=-15 515
55
σ42=-105
50 70
