一、典例
某食品公司经营糖果业务，公司下设三个工厂A1、A2、 A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产 量、销售量及调运时的单位运输费用情况。问：如何调运可 使总费用最小？
生产量：A1——7吨， A2 —— 4吨， A3 —— 9吨 销售量：B1 —— 3吨，B2 —— 6吨，B3 —— 5吨，B4 —— 6吨
最优否？
Y
STOP
N
新的基可行解
12
表上作业法步骤:
初始运输方案最优性检验改进运输方案
一、初始方案的确定
1.最小元素法 2.Vogel法 二、最优性检验 1.闭回路法 2.位势法 三、方案改进方法 在闭回路内改进。
13
最小元素法
产销平衡表 单位运价表
B1 B2
B3
B4 产量 3 3 6
A1 A2 A3
b2
┈
bn
aibj
32
2销产(bj>ai)
Min z= cij·xij
i=1j=1
m n
Min z= cij· xij +0xm+1,j
i=1 j=1 j=1
m
n
n
x a
j 1 ij
n
i
(i 1,2,...,m)
x a
j 1 ij
n
i
(i 1,2,...,m,m 1)
19
注: 只要求的基变量是正确的，并且数目为m+n-1个，那么 每个非基变量的闭回路存在且唯一，因此，检验数唯一。
20
位势法
位势表:
单位运价表
B1 B1
B3
B4 行位势ui
A1 A2 A3
列位势vj
(2) (9) 3 10 1 (8) 2 (9) (-3) 4 (-2) 5
1 0 -4
A1 A2 A3
销量
B1 B2 B3 B4 10 5 0 10 15 5 5 15 15 10
15 25 5
A1 A2 A3
B1 10 12 2 8 -
B2 1 7 14 6 6 6
B3 20 9 16 7 11 -
B4 11 9 10 10 20 2 2 13 18 12 - 7 9 9
28
表 上 作 业 法 步 骤
销量
3 3 6 6
4 1
5
7 4 9
A1 A2 A3
B1 3 1 7
B2 B3 11 3 9 2 4 10
B4 10 8 5
14
Vogel法
例 A1 A2 B1 B2 8 2 5 1 15
产量
10 20
销量 15
最小元素法：z=8×10+2×5+1×15=105
Vogel法：z=10×5+15×2+5×1=85
最小元素法
产销平衡表 单位运价表 产量
A1 A2 A3
销量
B1 B2 B3 B4 0 15 0 15 10 5 5 15 15 10
15 25 5
A1 A2 A3
B1 10 12 2
B2 1 7 14
B3 20 9 16
B4 11 20 18
27
Vogel法
产销平衡表 单位运价表 产量
A1 A2 A3
15
Vogel法
产销平衡表
B1 B2 B3 B4 产量 A1 A2 A3 销量 5 3 2 1 3 5 6 7 4 9 A1 A2 A3 列两 最小 元素 之差 B1 B2 B3 B4 行两最小元素之差 3 1 7 2 11 3 10 9 2 8 4 10 5 5 1 3 0 0 07 1 1 16 1 2 --
x
ij
0
(i 1, ..., m ; j 1,...,n)
x
ij
0
31
产＞销问题单位运价表
产地
销地
B1 C11 C21 ┆ Cm1
B2 C12 C22 ┊ Cm2
┈ ┈ ┈ ┈ ┈
Bn C1n C2n ┊ Cmn
Bn+1 ０ ０ ┆ ０
产量
A1 A2 ┊ Am
销量
a1 a2 ┊ am
b1
· · · · · · · · · · · · · ·
· · · · · ·0
· · · · · ·
j=n
0 0 · · · · · · 1
0 0 · · · · · ·1
· · · · · · · · · · · · 0 0 · · · · · · 1
17
例
产销平衡表 单位运价表
B3 B4 产量 0 A1 20 20 10 A2 10 A3 10 25 15 50 销量 30 25 10 15 B1 B2
A1 A2 A3
B1 2 8 4
B2 7 4 3
B3 3 6 10
B4 11 9 5
18
产销平衡表
单位运价表
闭 回 路 法
B1 B2 B3 B4 产量 A1 (1) (2) 4 3 7 A2 3 (1) 1 (-1) 4 A3 (10) 6 (12) 3 9 6 5 6 销量 3
产地
销地
B1 C11 C21 ┆ Cm1 0 b1
B2 C12 C22 ┊ Cm2 0 b2
┈ ┈ ┈ ┈ ┈ ┈ ┈
Bn C1n C2n ┊ Cmn 0 bn
B1 B2
B3 6 0
B4 产量 2 3 5
A1 A2 A3
销量
3 3 6 6
6 5 9
25
6
练习
产销平衡表 单位运价表
B1 B2
B3
B4 产量
A1 A2 A3
销量
15 25 5
5 15 15 10
A1 A2 A3
B1 10 12 2
B2 1 7 14
B3 20 9 16
B4 11 20 18
26
10
关于运输模型的几个结论：
(1)设有m个产地，n个销地且产销平衡的运输问题，则基变 量数是m+n-1； (2)若变量组B包含有闭回路，则B中变量对应的列向量线性 相关； (3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭 回路。
11
3.2 运输问题的求解方法：表上作业法
初始基可行解 单 纯 形 法 求 解 思 路
6
3 6
2 2
-
-
1 1
1
3 2
2
16
针对最小元素法和vogel法，需要说明的几点：
(1) 任何运输问题都有基可行解，且有最优解； (2) 如果供应量和需求量都是整数，那么一定可以得到整数 形式的最优解; (3) 用最小元素法和vogel法得到的是运输问题的一个基可行 解，数字格对应基变量； (4) 若在中途同时有行列要求得到满足，将同时划掉一行一 列，最后数字格个数将少于m+n-1个。为使数字格的个数恰 好等于m+n-1，在同时划去的行列中，任选（或选其价 格系数最小元素对应的）空格，填上数字0作为特殊的数字 格（即基变量）。
1 1 · · · · · ·1
· · · · · · · · · · · · 0 0 · · · · · · 0
· · · · · · · · · · · · · · · · · ·
i=m j=1 j=2
0 0
· · · · · · 0
0 0
· · · · · ·0
· · · · · · · · · · · · 1 1 · · · · · · 1
B1 3 1 7
B1 B3 11 3 9 2 4 10
B4 10 8 5
1
8
2
9
3.计算空格处位势； ij=ui+vj 4.计算空格处检验数： ij=cij- ij
21
1.数字格处上添上对应的运价；
2.计算行位势和列位势；
令v1=1，则依cij=ui+vj 计算各 ui和vj
检验数表 B1 B1 A1 A2 A3 销量 B3 B4 产量 7 4 9
· · · · · · · · · · · ·
i=1
i=2
1 1
· · · · · · · · · · · ·
· · · · · · 1
· · · · · ·
· · · · · ·0
· · · · · ·
· · · · · · · · · · · · 0 0 · · · · · · 0
0 0 · · · · · · 0
1 0 · · · · · · 0
0 1
· · · · · · · · · · · ·
1 0 · · · · · ·0
0 1
· · · · · · · · · · · ·
· · · · · · · · · · · · 1 0 · · · · · · 0
· · · · · · · · · · · · 0 1 · · · · · · 0
xij b j (j 1,2 ,..., n)
i 1
m
x
i 1
m 1
ij
b j (j 1,2 ,..., n) (i 1, ..., m,m 1 ; j 1,...,n)
x
ij
0
(i 1, ..., m ; j 1,...,n)
x
ij
0
33
销＞产问题单位运价表
23
例：
B3 A1 (0) (2) 5 A2 3 (2) (1) A3 (9) 6 (12) 销量 3 6 5
B1 B1
B4 2 1 3 6
产量 7 4 9
B1 B1 A1 A2 A3 销量 2 1 3