10
基在运输表中的表示
1 234
1 234
1
1
2
2
3
3
1 234
1 234
1
1
2
2
3
3
1 234
1 234
1
1
2
2
3
3
2019/12/27
浙江科技学院经济管理学院管工系
11
运输表中同行同列组成回路的变量
1 234 1 2 3
1 234 1 2 3
1 234 1 2 3
1 23 1 2 3
1 23 1 2 3
7
5
8
4
28
13
5
9
3 -13
-3
22
13
vj
6
2
3
5
5
4
3
7
ui 14 0
2
6
9
7 27 2
10
6
10
6
13
19
12
13
0
-4
2019/12/27
浙江科技学院经济管理学院管工系
27
三. 基变换－闭回路法
与单纯形法一样，如果所有非基变量检验数σij ≥0，则该基解 为最优解，否则不是最优解，需要进行基变换，换入变量的确 定方法一样，设换入变量xlk的检验数为σlk ，换出变量为xsf
求非基变量的检验数
闭回路法
对偶变量法
得到新的基础可行解
确定进基变量
沿闭回路调整运量
确定离基变量
2019/12/27
浙江科技学院经济管理学院管工系
32
单纯形法与表上作业法比较
单纯形法（Min）
表上作业法
确定初 始基变 量XB
检验数
调整
+松驰变量+（人工变量）
XB——系数矩阵为I，m个 其余XN
最小元素法、沃格尔法等
m
Σxij=bj j=1,…,n
i=1
xij≥0 i=1,…m,j=1,…,n
2019/12/27
浙江科技学院经济管理学院管工系
4
2.例如：三个产地四个销地，用网络表示
产量
产地
运价
销地 销量
a1=14 a2=27 a3=19
6
17
5 3
8
2
4 2
7
5
9
3 10
6
1
b1=22
2
b2=13
3
b3=12
2019/12/27
浙江科技学院经济管理学院管工系
33
例（P104，3.7）：
B1
B2
B3
B4
4
1
4
6
A1
8
1
2
5
0
A2
8
3
7
5
1
A3
4
6
5
6
3
该问题是一个产销平衡问题，也是求极小化问题， 可用表上作业法求解。
2019/12/27
浙江科技学院经济管理学院管工系
34
解： 1.用沃格尔法求初始基可行解
σij =Cij-CBB-1Pij＝ Cij-Y’Pij=Cij-(u1,u2,……,um,v1,v2,……,vn)Pij
= cij-(ui+vj) 对基变量而言： cij=(ui+vj) 由m+n-1个基变量对应m+n-1个线性方程
而LD的变量有m+n个，对偶问题有无穷多解，则可
设其中一个最优解为0，而推导出其他分量。从而求
B1
B2
…
A1
C11
C12
…
A2
C21
C22
…
Bn
产量
C1n
a1
C2n
a2
…
…
……
…
…
Am
Cm1
Cm2 …
Cmn
am
销量 b1
b2
…
bn
2019/12/27
浙江科技学院经济管理学院管工系
3
建模：设xij表示从Ai到Bj的运量，则所求的 数学模型为：
mn
min Ζn =ΣiΣ=1 cji=j1xij s.t. Σj=x1 ij=ai i=1,…m
总产量60吨
4
b4=13
产销平衡的运输问题
总销量60吨
2019/12/27
浙江科技学院经济管理学院管工系
5
运输问题线性规划模型
min z = 6x11 +7x12 +5x13 +3x14 +8x21 +4x22 +2x23 +7x24 +5x31 +9x32 +10x33 +6x34
s.t. x11 + x12 + x13 + x14
x21 + x22 + x23 + x24
x31 + x32 + x33 + x34
= 14 产
=
27
地 约
= 19 束
x11
+ x21
+ x31
x12
+ x22
+ x32
x13
+ x23
+ x33
x14
+ x24
+ x34
= 22
=
13
销 地
= 12 约
= 13 束
x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33
第三章 运输问题
3.1 运输问题及其数学模型 3.2 表上作业法 3.3 运输问题的进一步讨论
2019/12/27
浙江科技学院经济管理学院管工系
1
本章学习要求
掌握表上作业法及其在产销平衡运输问题求 解中的应用 掌握产销不平衡运输问题的求解方法
2019/12/27
浙江科技学院经济管理学院管工系
2
B1
B2
B3
B4
4
1
4
6
A1
5
3
1
2
5
0
A2
6
2
3 A3
7
5
1
3
1
6
列罚数 2
*
2019/12/27
5
6
3
1
1
1
1
5
*
浙江科技学院经济管理学院管工系
行罚数
8 3 *0 2 8 1 1 5* 4 2 24
35
解： 2.用位势法求非基变量检验数(求位势）
B1
B2
B3
4
1
4
A1
5
3
B4
ui
6 80
1 A2
lk min ij / ij 0
以xlk和基变量为顶点找一个闭回路，分别标号”+”,””,”+”,”_”；在标号为”-”的最小的运量为调整量，在 闭回路上进行调整，“＋”的加“-”的减，当存在xsf 为0时，为换出变量，得一新的基可行解，再求检验数。
2019/12/27
浙江科技学院经济管理学院管工系
3.1 运输问题及其数学模型
1.运输问题的一般提法：假设有m个生产地点，可以供应某
种物资（以后称为产地），用Ai来表示，i=1,…,m,有n个销地， 用Bj来表示，j=1,…,n，产地的产量和销地的销量分别为ai,bj， 从产地Ai到销地Bj运输一个单位物资的运价为Cij，这些数据可 汇总于下表，在假设产销平衡的条件下，即∑ai= ∑bj，问该如 何调运物品使总运费最小？
1
2
6 1
14
7
5
8
4
28
13
5
9
3
3
5
5
4
3
7
14
2
6
7 27
10
6
6
13
19
22
13
12
13
σ14 =(c14-c34+ c33 - c23 + c21 -c11)=3-6+10-2+8-6=7
2019/12/27
浙江科技学院经济管理学院管工系
21
1. 闭回路法(4)
1
2
6 1
14
7
5
8
4
28
1 23 1 2 3
2019/12/27
浙江科技学院经济管理学院管工系
4 4 4
12
一. 初始基可行解的确定
西北角法 最小元素法 沃格尔法
2019/12/27
浙江科技学院经济管理学院管工系
13
1.西北角法
方法：优先满足运输表中左上角空格的供销要求－
填一个数字只能划去一行或一列
1
2
3
4
6
7
5
2
2
8
4
2
13
12
7 272 3 4
5 3
19
9
10
6 1 14
19
22
13
12
13
列
1
3
3
3
罚
*
*
*
数
2019/12/27
浙江科技学院经济管理学院管工系
16
二. 最优性检验－求非基变量的检验数
闭回路法 位势法
2019/12/27
浙江科技学院经济管理学院管工系
17
1.闭回路法