第三章 运输问题 本章重点： 产销平衡运输问题的数学模型产销平衡

。
目标可以减少，说明当前
解不是最优解
闭回路法调整
选x22进基，找到闭回路
x12 5-
x14 1 +
x22 +
x24 5-
X22最多增加5
x12 5-5 x22 + 5
x14 1 +5 x24 5-5
X22进基，x12和x24经过调整同时变成 零。但是要注意只有一个变量出基。
例如：令x12出基
B1
B2
B3
B4
产量
A1 A2 A3 销量
× 2
3 1
× 8
3 ,0
×
9
10
×
3
4
4
4
2
8
4，0
79 2 5，2 5 7，3 6
B1
B2
B3
B4
产量
A1 A2 A3 销量
×
×
2
9
10
7
3
×
×
2
1
3
4
2
×
4
8
4
2
5
3 ,0
8
4，0 6,4
9 5,2,0 7，3
B1
B2
B3
B4
产量
A1 A2 A3 销量
7
-1
2
5
1
3
4
2
7
3
4
3
8
4
2
5
3 ,0
8,5 4，0 6,4,0
9,5 5,2,0 7,3,0
重新计算检验数
A1 u1=0
A2 u2=-5
A3 u3=-5 销量
B1

A1 A2 A3 销量
B1 B2 B3 B4 产量
3 11 3 10
7
1928
4
7 4 10 5
9
3
6
5
6
20
A1 A2 A3 A1 0 1 3 A2 1 0 M A3 3 M 0
B1
B2
B3
B4
B1
0142
B2
1021
B3
4203
B4
2130
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 T1 2 3 1 0 1 3 2 2 8 4 6 T2 1 5 M 1 0 1 1 4 5 2 7 T3 4 M 2 3 1 0 2 1 8 2 4 T4 3 2 3 2 1 2 0 1 M 2 6
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 1 3 10 27
1
A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 销量 20 20 20 20 20 20 20 23 2 25 26
– 产地和销地之间虽有直达路线，但直达运输的费用或 运输距离分别比经过某些中转站还要高或远。

7 4 9 3 6 5 6
2.1 确定初始基可行解
• 这与一般线性规划问题不同，产 销平衡的运输问题总是存在可行解。 因有
b a
i 1 j i 1
m
m
i
d
必存在 0≤ xij,i=1,…,m,j=1,…,n 是可行解。又因 0≤xij≤min(a1,bj) • 故运输问题的可行解和最优解必存在。 • 确定初始可行解的方法有很多，一般 希望的方法即简便又尽可能接近最优解。 下面介绍两种方法：最小元素法和伏格 尔（Vogel）法。（其它如西北角法等）
例1
• 某公司经销甲产品，它下设三个加工厂。每 日的产量分别为： • A1——7吨，A2——4吨，A3——9吨。该公 司把这些产品分别运往四个销售点。各销售 点每日的销量为：B1——3吨，B2——6吨， • B3——5吨，B4——6吨。已知从各工厂到各 销售点的单位产品的运价为表3-3所示，问该 公司应如何调运产品，在满足各销点的需要 量的前提下，使总运费为最少。
运价表与行差和 列差的计算
表3-10 伏格尔法
伏格尔法基可行解， 总运费为85，恰好得 到最优解
销地 B1 B2 B3 B4 行 产 差 量 产地
销地 B1 B2 B3 B4 产地 A1 A2
A1
A2 A3
3
1 7
11 3
9 4 5 6 2 1 5
10 0
8 3 6 1 1
7
4 9
10 5
列差 2 销量 3
A3
表3-13
B1 销地 加工厂 A1 A2 A3 销量 ห้องสมุดไป่ตู้2 B3 B4 产量
5 3 6 3 6 5
2 1 3 6
7 4 9

销地 产地 A1
A2
B1
B2
B3
B4
产量
6
5 3
3 1
4
4
2
A3
销量 2
4 7
1 3
4
4 6
3
7 5
3
5
6
8
4 3 13
σ11=-3, σ12=-2,σ23=-4, σ31=-1,σ33=1, σ34=-1
销地 产地 A1
A2
B1
B2
B3
B4
产量
6
5 0
3 4
4
4
2
A3
销量 2
4 7
4
4 6
3
4 3
5
3
4
3
4 7
1
5
4 6
A3 销量 2
7
0
4
6
3
5
3
4
8
3 13
x11检验数为 6-4+8-6+4-4=4
销地 产地 A1
A2
B1
B2
B3
B4
产量
6 4 2 4
5
3
4
3
4 7
1
5
4 6
A3 销量 2
7
0
4
6
3
5
3
4
8
3 13
x12检验数为 5-4+8-6=3
销地 产地 A1
A2
B1
B2
B3
B4
产量
2、位势法 当运输问题变量的格数较多时，用闭 回路法计算检验数比较麻烦，而位势法比 较简便。 对于运输问题 minf=CX AX=b X≥0 设B为其一个可行基，则xij的检验数为 σ ij=CBB-1Pij-Cij