运输问题的表上作业法
1、单纯形法（为什麽？）
2、表上作业法
由于问题的特殊形式而采用的更简洁、更方由于问题的特殊形式而采用的更简洁、更方
便的方法便的方法
一、表上作业法的基本思想
先设法给出一个初始方案,然后根据确定
的判别准则对初始方案进行检查、调整、改
进，直至求出最优方案，如图3-1所示。
表上作业法和单纯形法的求解思想完全一致，
但是具体作法更加简捷。
确定初始方案
( 初 始
基本可行解)
改进调整
（换基迭代）
否
判定是否
最 优？
是
结 束
最优方案
图1 运输问题求解思路图
二、 初始方案的确定
1、作业表（产销平衡表）
初始方案就是初始基本可行解。
将运输问题的有关信息表和决策变量——调
运量结合在一起构成“作业表”（产销平衡表）。
表2是两个产地、三个销地的运输问题作业表。
调 销地
运
量
产地
B1 B2 B3 产 量
A1
c11
X11
c12
X12
c13
X13 a1
A2
c21
X21
c22
X22
c23
X23 a2
销 量
b1 b2 b3
表2 运输问题作业表（产销平衡表）
其中xij是决策变量，表示待确定的从第i个产
地到第j个销地的调运量，cij为从第i个产地到
第j个销地的单位运价。
2、确定初始方案的步骤：
（1）选择一个xij，令xij= min{ai，bj}=
将具体数值填入xij在表中的位置；
（2）调整产销剩余数量：从ai和bj中分别减去xij
的值，若ai-xij=0，则划去产地Ai所在的行，即该
产地产量已全部运出无剩余，而销地Bj尚有需求
缺口bj-ai；若bj-xij =0，则划去销地Bj所在的列，
说明该销地需求已得到满足，而产地Ai尚有存余
量ai-bj；
（3）当作业表中所有的行或列均被划去，说明
所有的产量均已运到各个销地，需求全部满足，
xij的取值构成初始方案。否则，在作业表剩余的
格子中选择下一个决策变量，返回步骤（2）。
按照上述步骤产生的一组变量必定不构成
闭回路，其取值非负，且总数是m+n-1个，
因此构成运输问题的基本可行解。
对xij的选择采用不同的规则就形成各种不
同的方法，比如每次总是在作业表剩余的格
子中选择运价（或运距）最小者对应的xij，
则构成最小元素法，若每次都选择左上角格
子对应的xij就形成西北角法（也称左上角法）。
3、举例
例3-2 甲、乙两个煤矿供应A、B、C
三个城市用煤，各煤矿产量及各城
市需煤量、各煤矿到各城市的运输
距离见表3-4，求使总运输量最少的
调运方案。
表3-4 例3-2有关信息表
450 200 150 100
日销量
（需求量）
250 75 65 80 乙
200 100
70 90 甲
日产量
（供应量） C B A
运距 城市
煤矿
例3-2 的数学模型
分别使用最小元素法和西北角法求出初
始方案。
& 最小元素法的基本思想是“就近供应”
；
& 西北角法则不考虑运距（或运价），每
次都选剩余表格的左上角（即西北角）元
素作为基变量，其它过程与最小元素法相
同 ；
调 销地
运
量
产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
用最小元素法确定例3-2初始调运方案
150 100
100 100
100
100
100
得到初始调运方案为：
x11=100，x13=100，x22=150，x23=100
最小元素法实施步骤口诀
《运价表》上找最小，《平衡表》上定产销；
满足销量划去“列”，修改“行产”要记
牢；
（满足产量划去“行”，修改“列销”要记
牢）
划去列(行)对《运价》，
修改“行产(列销)”在《产销》；
余表再来找最小，方案很快就找到。
调 销地
运
量
产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
用西北角法确定例3-2初始调运方案
100 100100
50
50 200200
得到初始调运方案为：
x11=100，x12=100，x22=50，x23=200
三、最优性检验
检查当前调运方案是不是最优方案的过程
就是最优性检验。检查的方法：计算非基变量
（未填上数值的格，即空格）的检验数（也称
为空格的检验数），若全部大于等于零，则该
方案就是最优调运方案，否则就应进行调整。
定义 凡是能排成
(3-4)
或 (3-5)
形式的变量集合称为一个闭回路,并称式中变
量为该闭回路的顶点；其中 互不
相同, 互不相同。
1、闭回路法
X11
X
13
X21 X24
X
33
B1 B2 B3 B4
A1 X12 X14
A2 X22 X23
A3 X31 X32 X34
例 设m=3，n=4，决策变量xij表示从产地Ai
到销地Bj的调运量，列表如下，给出闭回路
在表中的表示法——
用折线连接起来的顶点变量。
练习 请给出闭回路 和
在表中的表示法。
X11
X
13
X21 X24
X
33
B1 B2 B3 B4
A1 X12 X14
A2 X22 X23
A3 X31 X32 X34
练习 下面的折线构成的封闭曲线连接的顶点
变量哪些不可能是闭回路？为什麽？
（a） （b） （c） （d） （e）
表中的折线构成一条封闭曲线，且所有的
边都是水平或垂直的；
表中的每一行和每一列由折线相连的闭回
路的顶点只有两个；
有关闭回路的一些重要结果
定理1 设 是一个闭
回路，则该闭回路中的变量所对应的系数列
向量 具有下面的
关系：
注意：列向量Pij =(0,…,0,1,0,…,0,1,0,…0)
T中两
个元素1分别处于第i行和第m+j行，直接计算
即可得到结果。
定理的证明可借助定理3-1和高等
代数中“向量组中，若部分向量线性
相关，则整个向量组就线性相关”的
定理得到。
定理 2 若变量组
中有一个部分组构成闭回路，则该变
量组对应的系数列向量线性相关。
约定作为起始顶点的非基变量为偶数次顶点，
其它顶点从1开始顺次排列，那么，该非基变
量xij的检验数：
现在，在用最小元素法确定例3-2初始调运
方案的基础上，计算非基变量X12的检验数
：
=（闭回路上偶数次顶点运距或运价之和）
-（闭回路上奇数次顶点运距或运价之和）
（3-6）
闭回路法以确定了初始调运方案的作业表为基础，
以一个非基变量作为起始顶点，寻求闭回路。
该闭回路的特点是：除了起始顶点是非基变量
外，其他顶点均为基变量（对应着填上数值的格）
。
可以证明，如果对闭回路的方向不加区别，对于
每一个非基变量而言，以其为起点的闭回路存在
且唯一。
调 销地
运
量
产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
100100
100150
例例3-23-2初始调运方案中以初始调运方案中以XX1212(X(X2121))为起点的闭回路为起点的闭回路
非基变量X12的检验数：
非基变量X21的检验数：
=（c12+c23）-（c13+c22）
=70+75-（100+65）=-20，
=（c21+c13）-（c11+c23）
=80+100-（90+75）=15。
经济含义：在保持产销平衡的条件下，该非
基变量增加一个单位运量而成为基变量时目
标函数值的变化量。
2、位势法
以例3-2初始调运方案为例，设置位势变
量 和 ，在初始调运方案表的基础上
增加一行和一列（见下页表格）。
然后构造下面的方程组：
（3-7）
例3-2初始调运方案位势变量对应表
调 销地
运
量
产地
B1 B2 B3 产
量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
位势变量vj v1 v2 v3
100100
100150
位势
变量
ui
u1
u2
方程组的特点：
方程个数是m+n-1=2+3-1=4个，位势变量共
有m+n=2+3=5个，通常称ui为第i行的位势，称
vj为第j列的位势；
初始方案的每一个基变量xij对应一个方程—
—-—所在行和列对应的位势变量之和等于该基
变量对应的运距（或运价）：ui+vj=cij；
方程组恰有一个自由变量，可以证明方程组
中任意一个变量均可取作自由变量。
给定自由变量一个值，解方程组式（3-7），
即可求得位势变量的一组值，根据式（3-6）结
合方程组（3-7），推出计算非基变量xij检验数
的公式 σij=cij-（ui+vj） （3-8）
在式（ 3-7）中，令 u1=0，则可解得 v1=90，
v3=100，u2=-25，v2=90，于是
σ12=c12-（u1+v2）=70-（0+90）=-20
σ21=c21-（u2+v1）=80-（-25+90）=15
与前面用闭回路法求得的结果相同。
位势法计算非基变量xij检验数的公式
σij=cij-（ui+vj） （3-8）
=（闭回路上偶数次顶点运距或运价之和）
-（闭回路上奇数次顶点运距或运价之和）
（3-
6）
闭回路法计算非基变量xij检验数的公式：
复习比较检验数计算的两种方法
思考：试解释位势变量的含义（提示：写出运输问思考：试解释位势变量的含义（提示：写出运输问
题的对偶问题）题的对偶问题）
四、方案调整
当至少有一个非基变量的检验数是负值时，
说明作业表上当前的调运方案不是最优的，应
进行调整。
若检验数σij小于零，则首先在作业表上以xij为
起始变量作出闭回路，并求出调整量ε：
ij
ε=min{该闭回路中奇数次顶点调运量xij}
调 销地
运
量
产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
100100
100150
+
+-
-
继续上例，因继续上例，因σσ1212=-20 =-20 ，画出以，画出以xx1212为起始变量的闭回路为起始变量的闭回路
计算调整量：ε=Min（100，150）=100。
按照下面的方法调整调运量：
闭回路上，奇数次顶点的调运量减去ε，偶数
次顶点（包括起始顶点）的调运量加上ε；闭
回路之外的变量调运量不变。
得到新的调运方案：
调 销地
运
量
产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
100100
200 50
重复上面的步骤，直至求出最优调运方案：
调 销地
运
量
产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量
100
150
200
450
150 50
200 50
结 果
最优调运方案是：
x11=50，x12=150，x21=50，x23=200
相应的最小总运输量为：
Zmin=90×50+70×150+80×50+75×200
=34000（吨公里）
运输问题的计算机求解
——表上作业法
1、适用软件
Transportation/Transshipment
Problem（TRP）
2、输入数据：
Maximize 1 minimize 2 <2>
Number of sources? <2>
Number of destinations? <3>
Number of transshipment point? <0>
Use the default names(S1 …Sn ,D1 …Dn
,T1…Tn) <Y>
Press the Space Bar to continue
if your entries are correct
Capacities of Sources
S1: 200 S2: 250
Demands of destinations
D1: 100 D2: 150 D3: 200
ENTER THE Cost/Profit
Coefficients of the TRP Model
-----Minimization------
From To
S1 D1: 90 D2: 70 D3: 100
S2 D1: 80 D2: 65 D3: 80
(注意：该例的输入数据与前例不同)
3、计算过程中的初始表
Initial solution by
0 0 0 V(j)
+200
+150
+100Demands
0 +250
+80
+200
+65
+80
+50
S2
0
+200
+100 +70
+150
90
+50
S1
U(I)Supplies D3 D2 D1SN\DN
4、求解结果报告
Summary of Results for TR2 Page :1
From To Shipment @cost . From To Shipment @cost .
S1
S1
S1
D1
D2
D3
+
+
0
+
+
+
0
0
+
S2
S2
S2
D1
D2
D3
+
0
+
+80
+65
+80
0
5
0
Minimized OBJ = 35000 Iteration = 0 Elapsed CPU second =
运输问题的推广
一、产销不平衡的运输问题
供大于求
供不应求
增加虚拟销地增加虚拟销地
增加虚拟产地增加虚拟产地
产销平衡的运输问题
对应的运距（或运价） ？
转化
二、转运问题
特点是所调运的物资不是由产地直接运送
到销地，而是经过若干中转站送达。
求解思路：转化成一个等价的产销平衡运
输问题，再用表上作业法求出最优调运方
案。
如何转化 ？
第一步，将产地、转运点、销地重新编排，
转运点既作为产地又作为销地；
第二步，各地之间的运距（或运价）在原
问题运距（运价）表基础上进行扩展：从
一地运往自身的单位运距（运价）记为零，
不存在运输线路的则记为M（一个足够大
的正数）；
第三步，由于经过转运点的物资量既
是该点作为销地的需求量，又是该点
作为产地时的供应量，但事先又无法
获取该数量的确切值，因此通常将调
运总量作为该数值的上界。
对于产地和销地也作类似的处理。
作业
