运输问题的表上作业法(考)
运输问题的数学模型
*
一、初始解的求法
首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常 见的是左上角法（或西北角法）、最小元素法和Vogl近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法和左上角法加以介绍。
最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。
*
精品课程《运筹学》
精品课程《运筹学》
精品课程《运筹学》
例1：三煤矿A1，A2，A3运往B1，B2，B3，B4三个城市销售，各煤矿的供应量和需求量如下页表，各城市的需求量其间的距离(或单位运价)cij如表下页表方格中的数据所示，试建立使总运输量(或总运费)最小的运输问题数学模型。
*
*
单价cij
销售地Bj
供应量ai
B1
B2
B3
B4
供
应
地
Ai
A1
1
6
2
10
20
A2
7
3
5
8
20
A3
3
2
9
4
40
需求量bj
30
25
10
15
80
80
最小元素法分配的初始调运方案
*
单价cij
销售地Bj
供应
量 ai
B1
B2
B3
B4
供
应
地
Ai
A1
1
6
2
10
20
x11=20
A2
7
3
5
8
20
x23=10
x24=10
A3
3
2
9
4
40
x31=10
x32=25
x34=5
需求量bj
30
25
10
15
80
80
西北角法分配初始调运方案
*
单价cij
销售地Bj
供应
量 ai
B1
B2
B3
B4
供
应
地
Ai
A1
1
6
2
10
20
x11=20
A2
7
3
5
8
20
x21=10
x22=10
A3
3
2
9
4
40
x32=15
x33=15
x34=15
需求量bj
30
25
10
15
80
80
二、基本可行解的最优性检验
最优性检验就是检查所得到的方案是不是最优方案。当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍对偶变量法求检验数的方法。
*
位势计算结果
*
ui vi
v1=(0)
v2=–1
v3=–2
v4=1
供应量 ai
u1=1
1
6
2
10
20
x11=20
u2=7
7
3
5
8
20
x23=10
x24=10
u3=3
3
2
9
4
40
x31=10
x32=25
x34=5
需求量bj
30
25
10
15
位势法或闭回路法计算空格的检验数结果
*
vi
ui
v1=(0)
v2=–1
v3=–2
v4=1
供应
量 ai
u1=1
1
6
2
10
20
x11=20
σ12=6
σ13=3
σ14=8
u2=7
7
3
5
8
20
σ21=0
σ22= –3*
x23=10
x24=10
u3=3
3
2
9
4
40
x31=10
x32=25
σ33=8
x34=5
需求量bj
30
25
10
15
因σ22=–3<0，故知该解不是最优解，还有待调整改正。
解改进的具体步骤为:
(1)以xij为换入变量，找出它在运输表中的闭回路；
(2)以空格(Ai,Bj)为第一个奇数顶点．沿闭回路的顺(或逆)时针方向前进，对闭回路上的顶点依次编号；
(3)在闭回路上的所有偶数顶点中，找出运输量最小 的顶点(格子)，以该格中的变量为换出变量；
*
解的改进
(4)以 为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于 。
然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。
*
*
重新调整调运方案，现再用位势法或闭回路法求这个新解各非基变量的检验数，结果示于下页表中。由于所有非基变量的检验数全非负，故这个解为最优解。
位势法或闭回路法计算新检验数结果
*
vi
ui
v1=(0)
v2=–1
v3=–2
v4=1
供应量 ai
u1=1
1
6
2
10
20
x11=20
σ12=6
σ13=0
σ14=8
u2=4
7
3
5
8
20
σ21=3
x22=10
x23=10
σ24=3
u3=3
3
2
9
4
40
x31=10
x32=15
σ33=5
x34=15
需求量bj
30
25
10
15
步骤
*
（1）找出初始即可行解，即在产销平衡表上分配初始调运方案，保证xij≥0， ，并且xij>0的格（又称实格）必须有m+n-1个；
（2）求出各非基变量的检验数σij（空格检验数），σij≥0时停止计算；σij<0时在继续调整调运方案（换基迭代法）；
（3）确定进基变量（空格换入变量）和出基变量（实格调出变量），找出新的基可行解（用空格闭回路法调整）；
（4）重复第1-3步，直至获得σij≥0，输出xij*和minZ=Z*为止。
*
*
销地
产地
B1
B2
B3
B4
供应量
A1
10
12
2
6
80
A2
4
7
8
9
55
A3
3
8
4
13
45
需求量
30
65
15
70
180
销地
产地
B1
B2
B3
供应量
A1
50
40
80
20
A2
30
10
90
50
A3
60
30
20
80
需求量
50
40
60
150
*
某公司下属3个工厂（甲厂、乙厂、丙厂）生产同类产品，供应不同地区的3个城市（A城、B城、C城），工厂的供应量、城市的需求量及工厂到不同城市的单件运费如表
*
