3.2 运输问题的表上作业法
一, 表上作业法的基本思想是,先设法给出
一个初始方案,然后根据确定的判别准则对初
始方案进行检查, 调整, 改进, 直至求出最
优方案, 如图 3-1所示 。
表上作业法和单纯形法的求解思想完全一致,
但是具体作法更加简捷 。
确定初始 方案
( 初 始
基本可行解 )
改进调整
( 换基迭代 )

判定是否
最 优?

结 束
最优方案
图 3-1 运输问题求解思路图
二, 初始方案的确定
1、作业表(产销平衡表)
初始方案就是初始基本可行解。
将运输问题的有关信息表和决策变量 —— 调
运量结合在一起构成,作业表,( 产销平衡
表 )。
表 3-3是两个产地、三个销地的运输问题作业表。
调 销地


产地
B1 B2 B3 产 量
A1
c11
X11
c12
X12
c13
X13 a1
A2
c21
X21
c22
X22
c23
X23 a2
销 量 b
1 b2 b3 ??
??
?
3
1
2
1 j
j
i
i ba
表 3-3 运输问题作业表(产销平衡表)
其中 xij是决策变量,表示待确定的从第 i个产
地到第 j个销地的调运量,cij为从第 i个产地到
第 j个销地的单位运价或运距。
2、确定初始方案的步骤:
( 1)选择一个 xij,令 xij= min{ai,bj}=
??
?
?
?
个销地需求满足第
个销地第个产地的产量全部运到第
j
j
b
ji
i
a
将具体数值填入 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有关信息表
450200150100
日销量
(需求量)
250756580乙
2001007090甲
日产量
(供应量)C BA
运距 城市
煤矿
例 3-2 的数学模型
?
?
?
?
?
?
?
?
?
?
?
???
??
??
??
???
???
??????;3,2,1;2,1,0
200
150
100
250
200
..
7565801007090m i n
2313
2212
2111
232221
131211
232221131211
jix
xx
xx
xx
xxx
xxx
ts
xxxxxxZ
ij
需求约束
日产量约束
总运输量
分别使用最小元素法和西北角法求出初
始方案。
& 最小元素法的基本思想是“就近供
应” ;
& 西北角法则不考虑运距(或运价),每
次都选剩余表格的左上角(即西北角)元
素作为基变量,其它过程与最小元素法相
同 ;
调 销地


产地
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
三, 最优性检验
检查当前调运方案是不是最优方案的过程
就是最优性检验。 检查的方法,计算非基变量
(未填上数值的格,即空格) 的检验数 (也称
为 空格的检验数 ),若全部大于等于零,则该
方案就是最优调运方案,否则就应进行调整。
1,闭回路法
以确定了初始调运方案的作业表为基础, 以
一个非基变量作为起始顶点, 寻求闭回路 。
该闭回路的特点是,除了起始顶点是非基变
量外, 其他顶点均为基变量 ( 对应着填上数值
的格 ) 。
可以证明, 如果对闭回路的方向不加区别, 对
于每一个非基变量而言, 以其为起点的闭回路
存在且唯一 。
约定作为起始顶点的非基变量为偶数次顶点,
其它顶点从 1开始顺次排列, 那麽, 该非基变
量 xij的检验数:
现在,在 用最小元素法确定例 3-2初始调运
方案的基础上,计算非基变量 X12的检验数,
ij?
=(闭回路上偶数次顶点运距或运价之和)
-(闭回路上奇数次顶点运距或运价之和)
( 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-2初始调运方案中以 X12(X21)为起点的闭回路
非基变量 X12的检验数:
非基变量 X21的检验数:
=( c12+c23) -( c13+c22)
=70+75-( 100+65) =-20,
12?
=( c21+c13) -( c11+c23)
=80+100-( 90+75) =15。
21?
经济含义,在保持产销平衡的条件下, 该非
基变量增加一个单位运量而成为基变量时 目
标函数值的变化量 。
2、位势法
以例 3-2初始调运方案为例,设置 位势变
量 和,在初始调运方案表的基础上
增加一行和一列(见下页表格)。
然后构造下面的方程组:
iu jv
?
?
?
?
?
?
?
???
???
???
???
75
65
1 0 0
90
2332
2222
1331
1111
cvu
cvu
cvu
cvu
( 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)
ij?
=(闭回路上偶数次顶点运距或运价之和)
-(闭回路上奇数次顶点运距或运价之和)
( 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
+
+-
-
继续上例,因 σ12=-20,画出以 x12为起始变量的闭回

?计算调整量,ε=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
20050
重复上面的步骤,直至求出最优调运方案:
调 销地


产地
B1 B2 B3 产 量
A1
90
X11
70
X12
100
X13
200
A2
80
X21
65
X22
75
X23
250
销 量 100 150 200 450
15050
20050
结 果
最优调运方案是:
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
000V(j)
+200+150+100Demands
0+250
+80
+200
+65+80
+50
S2
0+200
+100+70
+150
90
+50
S1
U(I)SuppliesD3D2D1SN\DN
4、求解结果报告
Summary of Results for TR2 Page,1
From To Shipment @cost Opp.ct,From To Shipment @cost Opp.ct
S1
S1
S1
D1
D2
D3
+50.000
+150.00
0
+90.00
+70.00
+100.0
0
0
+10.00
S2
S2
S2
D1
D2
D3
+50.000
0
+200.00
+80
+65
+80
0
5
0
Minimized OBJ = 35000 Iteration = 0 Elapsed CPU second = 53.3906
3.3运输问题的推广
一、产销不平衡的运输问题
供大于求
供不应求
增加虚拟销地
增加虚拟产地
产销平衡的运输问题
对应的运距(或运价)?
转化
二、转运问题
特点 是所调运的物资不是由产地直接运送
到销地, 而是经过若干中转站送达 。
求解思路, 转化成一个等价的产销平衡运
输问题, 再用表上作业法求出最优调运方
案 。 如何转化?
第一步, 将产地, 转运点, 销地重新编排,
转运点既作为产地又作为销地;
第二步, 各地之间的运距 ( 或运价 ) 在原
问题运距 ( 运价 ) 表基础上进行扩展:从
一地运往自身的单位运距 ( 运价 ) 记为零,
不存在运输线路的则记为 M( 一个足够大
的正数 ) ;
第三步, 由于经过转运点的物资量既
是该点作为销地的需求量, 又是该点
作为产地时的供应量, 但事先又无法
获取该数量的确切值, 因此通常 将调
运总量作为该数值的上界 。
对于产地和销地也作类似的处理 。
第六次作业
P123~P125:
3-1,3-2,3-4