闭回路：从空格出发顺时针(或逆时针)画水(或垂直)直线 ，遇到填有运量的方格可转90°，然后继续前进，直到到达出 发的空格所形成的闭合回路。
调运方案的任意空格存在唯一闭回路。
差
额 法
产
销
B1
B2
B3 B4 供量
方 案
A1 A2
3
52
7
1
4
A3
6
3
9
销量 3
6
56
① 闭回路法
闭回路：从空格出发顺时针(或逆时针)画水平(或 垂直)直线，遇到填有运量的方格可转90°，然后继续 前进，直到到达出发的空格所形成的闭合回路。
需
平
需方 供方
B1
B2
…
Bn 供应量
衡 表
A1
c11
c12
…
c1n
a1
A2
c21 c22 … c2n
a2
Am
cm1 cm2 … cmn
am
需求量
b1
b2
m
n
… bn ai b j
i 1
ji
如何建立供需搭配，使总的运输费用最小？
数学模型
设从Ai到Bj的物资运量为xij ，
nm
min z
cij x ij
4
10
12
5 -3
vj
0
7
1
8
24=-1＜0，当前方案 不是最优方案。
二、 调运方案的调整
min( i,j
ij
<
0
)
pq
xpq为换入变量
从(p,q)空格开始画闭回路，其它转角点都是
填有运量的方格，并从(p,q)空格开始给闭回路上
的点按+1，-1，+1，-1编号，-1格的最小运量为
调整量。
销地
产地
…
bn
mn
min z cij xij
i1 j1
ui
n
j1
xij
ai
( i 1,,m )
m个
vj
m
i1
xij
bj
( j 1,,n )
xij 0 ( i 1, ,m ; j 1, ,n )
n个
设ui,vj为对偶变量，对偶问题模型为
m
n
max w aiui b jv j
4
A3
7 4 10 5
9
需求量（T） 3 6 5 6
⑴最小元素法
销
产
B1
B2
B3
B4 产量
3
11
3
10
A1
7
43
1
9
2
8
A2 3
1
4
7
4
10
5
A3
6
9
3
销量 3
6
5
6
该方案总运费： Z=4×3+3×10+3×1+1×2+6×4+3×5=86
② 差额法
.
优产先地分在销别最地计大算差各额B1 行处、进各行B列供2 次需小搭、配B3最。小运价B4 的差行额差，额
第五章 货物运输方案的优化方法
本 章
产销平衡运输问题的数学模型
重
点
产销平衡运输问题的表上作业法
运输问题的数学模型
本
章 表上作业法
内
容
运输问题的扩展
§1 货物运输问题
需方 供方
B1
A1
A2
Am 需求量 b1
B2 … Bn 供应量
a1
运价
a2
am
m
n
b2
… bn ai b j
i 1
ji
供需平衡
供
B1
换出变量
B2
B3
B4
产量
A1
运价
A2
3
4(+1)… …3(-1) 7
┇
┇
1(-1)… …(+1)
4
A3
6
3
9
销量
3
6
5
6
=min{1，3}=1
新的调运方案为：
销地 产地 B1
B2
B3
B4 产量
A1
527
A2 3
14
A3
6
39
销量 3 6 5 6
z1 z0 24 86 11 85
B1 B2 B3 B4 产量
i 1
ji
ui v j cij
ui‚vj无约束 （i=1,2, …,m;j=1,2, …,n)
§2 初始调运方案的编制
计算步骤：
(1) 找出初始调运方案。即在(m×n)产销平衡表 上给出m+n-1个数字格。(最小元素法或差值法）
(2) 求检验数。（闭确回定路m法+n或-1位个势基法变）量判别是否
A1
3
A2
1
A3
7
列差额
2
11
3
10
0
9
2
8
1
4
10
5
1
5
1
3
步骤： 10 计算未划去行、列的差额；
20 找出最大差额对应的最小元素cij进行供需分配； 30 在未被划去的行、列重新计算差额。
B1
B2
B3
B4 行差额
A1
3
11
3 10
0
A2
1
9
2
8
1
A3
7
4 10 5
1
列差额 2
5
1
3
产 销 B1
B2
B3 B4 供量
A1
7
A2
4
A3
6
9
销量 3
6
56
B1
B2
B3 B4 行差额
A1
3 11 3 10
0
A2
1
9
28
1
A3
7
4 10 5
2
列差额 2
13
产 销 B1
B2
B3 B4 供量
A1
7
A2
4
A3
6
3
9
销量 3
6
56
B1
B2
B3 B4 行差额
A1
3 11 3 10
0
A2
1
9
28
1
A3
7
列差额 2
1 1
1
x22 x2n xm1 xm2 xmn
1 1 1
11
1 1
1
1 1
m×n 个变量，m+n 个约束，独立的约束方程 m+n-1 个，每个变量的系数是有 2 个 1、其它元 素均为 0 的向量。
平衡表、运价表和二为一：
销
产
B1
B2
…
c11
c12
A1
x11
x12
…
c21
c22
A2
得m+n-1个方程，令某个ui ( 或vj)=0，可解出 m+n个ui 和vj；由此得非基变量的检验数。
位 势 法
销
产
B1
B2
B3
B4 产量
3
11
3
10
A1
4
3
7
1
A2 3
9
2
1
8 4
7
4
10
5
A3
6
3
9
销量 3
6
5
6
令v1=0, 由c21=3= u2 +v1，得 u2=3
B1
B2
B3
B4
ui
3
4 10 5 12
销 产
B1
B2
B3 B4 供量
A1
7
A2
3
4
A3
6
3
9
销量 3
6
56
B1
B2
B3
B4
差额
A1
3 11 3 10
7
A2
1
9
2
8
6
A3
7
差额
4 10 5 12
产 销 B1
B2
B3 B4 供量
A1
52
7
A2
3
1
4
A3
6
3
9
销量 3
6
56
§3 调运方案的改进 一、最优调运方案的判定
① 闭回路法
11
3
10
A1
2
1
9
2
8
A2
1
7
4
10
5
A3
vj
0
1
位
势
B1
B2
B3
B4
ui
表
3
11
3
10
A1 2
9
2
1
9
2
8
A2
8
9
1
7 A3 -3
4
10
-2
5 -3
vj
0
7
1
8
检验数 ij cij (ui v j )
检 验 数 表
A1
B1
B2
B3
3
11
3
1
2
B4
ui
10 2
1
9
2
8
A2
1
-1
1
7
A3
10
调运方案的任意空格存在唯一闭回路。
销 产
B1