毕业设计表上作业法在货物运输组织中的应用分析课程设计.doc

运 输 工 程 课 程 设 计

题 目 表上作业法在货物运输组织中的应用分析

院 (部)

专 业

班 级

学生姓名

学 号

运 输 工 程 课 程 设 计 任 务 书

摘要
运输是人们借助于运输工具，在一定交通路线上实施运输对象空间位移的有目地的活动。现代化的运输不仅需要具备现代化的运输通路、港站和运载工具等设施设备，同时还必须用科学的方法和手段合理组织运输生产，充分发挥各种运输方式的运能和优势，提高运输效率，降低运输成本，以便更好的满足社会生产和人民生活的需要。企业的生产过程需要消耗一定的资源，而资源总是稀缺的，因此合理利用现有资源，并将其将行合理分配，是充分发挥企业资源效能、提高企业综合经济效益的必由之路。本文利用表上作业法求得了货物运输组织中的最小费原理，解决了物流公司在货物运输中所存在的问题，为物流公司的货物运输提供了一种行之有效的方法。通过建立物流配送模型，利用表上作业法解出最小运输成本，解决了降低运输成本问题，提升了物流公司的市场竞争力。

关键词：货物运输，表上作业发，应用实例分析。

目录
1 绪论 6
1.1 课题的提出 6
1.1.1 课题背景 6
1.1.2 课题意义 6
2 表上作业发 6
2.1 表上作业发的具体介绍 6
2.2 确定初始基本可行解 8
2.1.1 最小元素法 8
2.2.2 西北角法 11
2.2.3 伏格尔法（Vogel） 11
2.3 基本可行解的最优性检验 16
2.3.1 位势法 16
2.3.2 闭回路法 20
3 表上作业法在实际中的应用 22
3.1 产销平衡问题 22
3.1.1 平衡问题模型 23
3.2.3 数学模型的建立 23
3.2 产销不平衡问题 24
4 总结 24
参考文献 26

1 绪论
1.1 课题的提出
1.1.1 课题背景
运输问题是当今社会经济生活中经常出现的问题，在经济建设中，经常出现物资的调运问题，如何制定调运方案，将物资运往指定地点，而且实现运输费用最小，即为运输问题。运输问题是特殊的线性规划问题，它是现行网络最优化的一个例子。与一般线性规划问题不同的是它的约束方程组的系数矩阵具有特殊结构，这就需要采用不同甚至更为简约的方法来解决这种实际工作中遇到的问题。运输问题代表了物资合理调运、车辆合理调度等问题。其他类型问题经过一系列改变后也可归结为运输问题。
1.1.2 课题意义
物品运输问题在当今经济建设中是十分常见的问题，运输问题及运输成本的优化是运输企业制定调运方案时必须要考虑的内容，如何选择一个合理的运输方案使的运输费用最低是十分关键的。表上作业法可以较好的解决这类问题。本文主要目地便是系统全面的对表上作业法进行研究。
2 表上作业发
2.1 表上作业发的具体介绍
表上作业发的单纯形法在求解运输问题的一种简化方法，其实质是单纯形法，但具体计算和术语有所不同。从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 这个方法的基本思想是就近供应，即从运价表中最小运价开始确定调运量，然后次小，一直到给出初始调运方案为止.可归纳为：
（1）找出基本可行解。即在（m*n）产销平衡表上用西北角法或最小元素法，Vogel法给出m+n.1个数字，称为数字格。它就是初始基变量的取值。
（2）求各非基变量的检验数，即在表上记载空格的检验数，判断是否达到最优解。如以是最优解，则停止计算，否则转到下一步。
（3）确定换入变量和换出变量，找出新的基本可行解，在表上用闭环回路法调整。
（4）重复（2）（3）知道得到最优解为止。
以下通过实际原始材料研究表上作业发：
设有5个产地A1、A2、A3、A4、A5和4个销地B1、B2、B3、B4的运输问题，他们的供应量和需求量及单位运费如下表。
表2.1供应量和需求量及单位运费

B1
B2
B3
B4
供应量
A1
10
20
5
7
10
A2
13
9
12
8
20
A3
4
15
7
9
30
A4
14
7
1
0
40
A5
3
12
5
19
50
需求量
60
60
20
10
150
表2.2供应量和需求量

B1
B2
B3
B4
供应量
A1

10
A2

20
A3

30
A4

40
A5

50
需求量
60
60
20
10
150
2.2 确定初始基本可行解
确定初始基本可行解一般的方法是既简便，有尽可能接近最优解，下面介绍最小元素法和Vogel法。
2.1.1 最小元素法
最小元素法的基本思想就是就近供应，即从最小的运价开始确定供销关系，然后次小。一直到给出初始基本可行解，以上述材料为例进行讨论。
（1）从表2.1中找出最小运价为0，这表示先将A4的产品供应给B4，因为a4>b4
A4除满足B4的需求外，还可多余30的产品。在表2.2中的（A4,B4）的交叉处填上10，得表2.3。并将表2.1的B4列划去，得表2.4。
表2.3计算过程表（1）

B1
B2
B3
B4
供应量
A1

10
A2

20
A3

30
A4

10
40
A5

50
需求量
60
60
20
10
150
表2.4计算过程表（2）

B1
B2
B3
B4
供应量
A1
10
20
5
7
10
A2
13
9
12
8
20
A3
4
15
7
9
30
A4
14
7
1
0
40
A5
3
12
5
19
50
需求量
60
60
20
10
150

（2）在表2.4中在找出最小的运价1，确定A4中剩余30供应给B3，满足B3的需求量还多出10，并得出表2.5。并划去表2.1中的B3，得表2.6
表2.5计算过程表（3）

B1
B2
B3
B4
供应量
A1

10
A2

20
A3

30
A4

20
10
40
A5

50
需求量
60
60
20
10
150
表2.6计算过程表（4）

B1
B2
B3
B4
供应量
A1
10
20
5
7
10
A2
13
9
12
8
20
A3
4
15
7
9
30
A4
14
7
1
0
40
A5
3
12
5
19
50
需求量
60
60
20
10
150
（3）在表2.6中找出最小运价为3。a5<b1,所以A5里面的50全部供应给B1,还缺少10需求量，在从表中找出最小运价4，而B1只需求10，因此A3中止供应10给BI，还剩余20，由此的表2.7。在表2.6中划去B1列，由于A5里的均已供应完，均划去，得表2.8。

表2.7计算过程表（5）

B1
B2
B3
B4
供应量
A1

10
A2

20
A3
10

30
A4

20
10
40
A5
50

50
需求量
60
60
20
10
150
表2.8计算过程表（6）

B1
B2
B3
B4
供应量
A1
10
20
5
7
10
A2
13
9
12
8
20
A3
4
15
7
9
30
A4
14
7
1
0
40
A5
3
12
5
19
50
需求量
60
60
20
10
150
（4）现在只有B2的需求没有满足，所以A1,A2,A3,A4的全部供应给B2，刚好满足所有的供需量，由此的到表2.9。
表2.9调运方案表

B1
B2
B3
B4
供应量
A1

10

10
A2

20

20
A3
10
20

30
A4

10
20
10
40
A5
50

50
需求量
60
60
20
10
150
由表2.8可知，此方案的总费用为1O×20+20×9+10×4+20×15+10×7+20×1+0+50×3=960.
2.2.2 西北角法
从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 西北角法的基本思想是给产销平衡表左上角的变量分配运输量，以确定产销关系，依此类推，一直到给出初始可行方案为止。求解步骤如下：（1）先决定产销平衡表左上角变量 的值。令这个变量取尽可能大的值，即 ，在这个变量对应的数字格填上变量所取的值。（2）若，则在第L行空格处打“×”，这些空格不再赋值；若，则在第K列空格处打“×”，这些空格不再赋值；若=，则在行的空格处打“×”后，就不能在列的空格处打“×”，反之，若在列的空格处打“×”，就不在行空格处打“×”。（3）对表上没有打“×”的地方重复（1）， （2）步，直到所有格子都有标记止。
可以证明，用西北角法确定的初始方案是运输问题的一个初始基可行解，它也恰好包含m+n.1个数字格。
2.2.3 伏格尔法（Vogel）
最大差额法是一行或一列的整体出发考虑，会更加合理。一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小费用调运时，运输量就会加多从而运费增加越多。因而对差额最大处，要优先考虑，应当采用最小运费调运。最大差额法的具体步骤如下：
（1）在表2.1中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表2.10。

表2.10计算过程表（7）

B1
B2
B3
B4
行差额
A1
10
20
5
7
2
A2
13
9
12
8
1
A3
4
15
7
9
3
A4
14
7
1
0
1
A5
3
12
5
19
2
列差额
1
2
4
7

（2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表2.10中B4列是最大差额所在列。B4列最小元素为0，可确定A4产品先供应B4的需要。得表2.11。B4的需求量满足时，则在表2.11中划去B4，得表2.12。
表2.11计算过程表（8）

B1
B2
B3
B4
供应量
A1

10
A2

20
A3

30
A4

10
40
A5

50
需求量
60
60
20
10
150

表2.12计算过程表（9）

B1
B2
B3
B4
行差额
A1
10
20
5
7
2
A2
13
9
12
8
1
A3
4
15
7
9
3
A4
14
7
1
0
1
A5
3
12
5
19
2
列差额
1
2
4
7

（3）在表2.12中，未划去的行和列中再分别计算出行差额和列差额，得表2.13。
在表2.13中，A4为最大差额所在行，所对应的最小元素为B3列，则A4的成品供应给B3，A3里还有30个，B3需求30个，得表2.14。B3中的需求满足时，在表2.12中划去B3，得表2.15。
2.13计算过程表（10）

B1
B2
B3
行差额
A1
10
20
5
5
A2
13
9
12
3
A3
4
15
7
3
A4
14
7
1
6
A5
3
12
5
2
列差额
1
2
4

表2.14计算过程表（11）

B1
B2
B3
B4
供应量
A1

10
A2

20
A3

30
A4

20
10
40
A5

50
需求量
60
60
20
10
150
表2.15计算过程表（12）

B1
B2
B3
B4
行差额
A1
10
20
5
7
2
A2
13
9
12
8
1
A3
4
15
7
9
3
A4
14
7
1
0
1
A5
3
12
5
19
2
列差额
1
2
4
7

（4）在表2.15中，未划去的元素在进行计算出行差额和列差额，得表2.16.重复步骤（1），（2），可得表2.17。由于A1中的一全部供应完，则应划去，得表2.18。

表2.16计算过程表（13）

B1
B2
行差额
A1
10
20
10
A2
13
9
4
A3
4
15
1
A4
14
7
7
A5
3
12
9
列差额
1
2

表2.17计算过程表（14）

B1
B2
B3
B4
供应量
A1
10

10
A2

20
A3

30
A4

20
10
40
A5

50
需求量
60
60
20
10
150
表2.18计算过程表（15）

B1
B2
B3
B4
行差额
A1
10
20
5
7
2
A2
13
9
12
8
1
A3
4
15
7
9
3
A4
14
7
1
0
1
A5
3
12
5
19
2
列差额
1
2
4
7

一直重复步骤（1），（2），可得最终结果，如表2.19。

表2.19调运方案表

B1
B2
B3
B4
供应量
A1
10

10
A2

20

20
A3
30

30
A4

10
20
10
40
A5
20
30

50
需求量
60
60
20
10
150
由表2.17可知，此方案的最优解为：10×10+20×9+30×4+10×7+20×1+0+20×3+30×12=910。
由以上可见：最大差额法和最小元素法除在确定供求关系的原则上不同外，其余步骤基本相同。最大差额法给出的初始解比用最小元素法给出的初始解更接近最优解。本例题用最大差额法给出的初始解就是最优解继续判别。
2.3 基本可行解的最优性检验
最优解的检验的方法是查看空格（非基变量）的检验数是否有不符合最优性条件的。为此，介绍空格检验数的求法。基可行解是否最优的判别法有闭回路法、位势法。
2.3.1 位势法
位势法是一种检验数的简便方法，设是运输问题的m+n个约束条件对应的对偶变量，决策变量对应的列向量，对于一个基可行解，由单纯形法得知所有基变量（数字格）的检验数等于0，即,所以由m+n.1个数字格对应的及即可确定所有的值。 称分别为产销平衡表各行与各列的位势。 因为非基变量（空格）检验数，所以，只要计算出所有位势值，就能求出各空格的检验数。
首先根据最大差额法得到的初始方案并假设行位势为u，列位势为v得到表2.20。
表2.20位势计算表（1）

B1
B2
B3
B4
供应量
ui
A1
10【10】
【20】
【5】
【7】
10
　u1（0）
A2
【13】
20【9】
【12】
【8】
20
　u2（.10）
A3
30【4】
【15】
【7】
【9】
30
　u3（.6）
A4
【14】
10【7】
20【1】
10【0】
40
　u4（.12）
A5
20【3】
30【12】
【5】
【19】
50
　u5（.7）
需求量
60
60
20
10
150

vi
　v1（10）
　v2（19）
　v3（13）
　v4（12）

然后，计算位势。可先建立方程组，并据此计算出运输表各行和各列的位势，填入表2.21中。
u1+v1=10
u2+v2=9
u3+v1=4
u4+v2=7
u4+v3=1
u4+v4=0
u5+v1=3
u5+v2=12
由于方程数量为m+n.1个，而位势的数量为m+n个，所以无法直接求它们的值，但由于我们想得到的只是它们的相对关系，因此我们可以假设其中一个的数值，一般为了方便计算我们可以假设u1=0.解得：u1=0 u2=.10 u3=.6 u4=.12 u5=.7 v1 =10 v2=19 v3=13 v4=12。
最后计算检验数。有了位势之后，即可由公式计算出各空格的检验数，如表2.21所示。当所有的检验数都为非负时，方案即为最优的调整方案。否则为非最优，则需要调整。

表2.21检验数表（1）

B1
B2
B3
B4
供应量
ui
A1
0【10】
1【20】
.8【5】
.5【7】
10
　u1（0）
A2
13【13】
0【9】
9【12】
6【8】
20
　u2（.10）
A3
0【4】
2【15】
0【7】
3【9】
30
　U3（.6）
A4
16【14】
0【7】
0【1】
0【0】
40
　U4（.12）
A5
0【3】
0【12】
.1【5】
14【19】
50
　u5（.7）
需求量
60
60
20
10
150

vi
　v1（10）
　v2（19）
　v3（13）
　v4（12）

当表中空格处出现负检验数时，表明未得到最优解。若有两个或两个以上的负检验数，一般选择其中较小的负检验数，以它对应的空格为调入格，即以它对应的非基变量为换入变量。由表2.21得（1，3）为调入格。以此格作为出发点，作一个闭合回路，调整后的运输方案见表2.19。
表2.22计算过程表（16）

B1
B2
B3
B4
供应量
A1
2

8

10
A2

20

20
A3
30

30
A4

18
12
10
40
A5
28
22

50
需求量
60
60
20
10
150
再进行位势法判断：

表2.23位势计算表（2）

B1
B2
B3
B4
供应量
ui
A1
【10】
【20】
10【5】
【7】
10
　u1（0）
A2
【13】
20【9】
【12】
【8】
20
　u2（.2）
A3
30【4】
【15】
【7】
【9】
30
　u3（2）
A4
【14】
20【7】
10【1】
10【0】
40
　u4（.4）
A5
30【3】
20【12】
【5】
【19】
50
　u5（1）
需求量
60
60
20
10
150

vi
　v1（2）
　v2（11）
　v3（5）
　v4（4）

求出检验数见表2.23。
表2.24检验数表（1）

B1
B2
B3
B4
供应量
ui
A1
8【10】
9【20】
0【5】
3【7】
10
　u1（0）
A2
13【13】
0【9】
9【12】
6【8】
20
　u2（.2）
A3
0【4】
2【15】
0【7】
3【9】
30
　u3（2）
A4
16【14】
0【7】
0【1】
0【0】
40
　u4（.4）
A5
0【3】
0【12】
.1【5】
14【19】
50
　u5（1）
需求量
60
60
20
10
150

vi
　v1（2）
　v2（11）
　v3（5）
　v4（4）

当表中空格处出现负检验数时，表明未得到最优解。以此格作为出发点，作一个闭合回路，调整后的运输方案见表2.25，并算出位势数。

表2.25 位势计算表（3）

B1
B2
B3
B4
供应量
ui
A1
【10】
【20】
10【5】
【7】
10
　u1（0）
A2
【13】
20【9】
【12】
【8】
20
　u2（.3）
A3
30【4】
【15】
【7】
【9】
30
　u3（1）
A4
【14】
30【7】
【1】
10【0】
40
　u4（.5）
A5
30【3】
10【12】
10【5】
【19】
50
　u5（0）
需求量
60
60
20
10
150

vi
　v1（3）
　v2（12）
　v3（5）
　v4（5）

求出检验数，见表2.26
表2.26检验数表（3）

B1
B2
B3
B4
供应量
ui
A1
7【10】
8【20】
0【5】
2【7】
10
　u1（0）
A2
13【13】
0【9】
10【12】
6【8】
20
　u2（.3）
A3
0【4】
2【15】
1【7】
3【9】
30
　u3（1）
A4
16【14】
0【7】
1【1】
0【0】
40
　u4（.5）
A5
0【3】
0【12】
0【5】
14【19】
50
　u5（0）
需求量
60
60
20
10
150

vi
　v1（3）
　v2（12）
　v3（5）
　v4（5）

检验数均为非负数，所以此为最佳方案。得最小运费为：820。
2.3.2 闭回路法
为了确定空格（i,j）的检验数，可以先找出以该空格为一个顶点，其余顶点全是数字格的闭回路。所谓闭回路，就是从该空格出发，沿水平方向或垂直方向前进，遇到合适的数字格后转90°，继续前进，如果能够回到出发点，则称这个封闭折线为闭回路。该顶点通常记为第一个顶点，为奇数位，它的下一个顶点为偶数位，下面的顶点依次奇偶相同，奇数位取正值，偶数位取负值，各数累加的和就等于（i,j）格的检验数。 可以证明，在任何可行方案中，以空格（i,j）为一个顶点，其余顶点全是数字格的闭回路存在而且唯一。
下面以最大差额法的结果为例，对表2.19所有的非基变量的检验数计算过程如表2.27
表2.27闭合回路检验过程
非基变量
闭合回路
检验数
X12
X12→X52→X51→X11→X12
1
X21
X21→X22→X52→X51→X21
13
X32
X32→X52→X51→X31→X32
2
X41
X41→X42→X52→X51→X41
16
X13
X13→X11→X51→X52→X42→X43→X13
.8
X14
X14→X11→X51→X52→X42→X44→X14
.5
X23
X23→X22→X42→X43→X23
9
X24
X24→X22→X42→X44→X24
6
X33
X33→X31→X51→X52→X42→X43→X33
0
X34
X34→X31→X51→X52→X42→X44→X34
3
X53
X53→X43→X42→X52→X53
.1
X54
X54→X44→X42→X52→X54
14
按上述做法，可计算出表2.27中的所有非基变量的检验数，把它们填入相应位置的方括号内，如表2.28所示：

表2.28非基变量检验数

B1
B2
B3
B4
供应量
A1
10

20

5

7

10

10

[1]

[.8]

[.5]
A2
13

9

12

8

20

[13]

20

[9]

[6]
A3
4

15

7

9

30

30

[2]

[0]

[3]
A4
14

7

1

0

40

[16]

10

20

10
A5
3

12

5

19

50

20

30

[.1]

[14]
需求量
60
60
20
10
150
表格中所有的检验数不均为非负，这表明该方案不是最优，仍能调整，下面会介绍到。
3 表上作业法在实际中的应用
3.1 产销平衡问题
产销平衡是指生产量与销售量相同，即∑ai=∑bi。公路货运企业时常会遇到若干货源地向若干需求地的货物运输问题，供货量与需求量不尽相同，怎样合理组织运输，满足货主的运输要求，同时使完成运输计划的运输费用最低，这是运输业制定计划时优先考虑的问题。显然，调运方案可以有很多个，但最优方案只有一个，表上作业法可以找到这个最优方案。
表上作业法求解线性规划问题也是取迭代选优的办法，即给出一个初始可行方案，经过反复迭代，每次迭代使目标函数有所降低（以成本为目标函数），最后取得最优方案。
3.1.1 平衡问题模型
已知有M个供应地点，Ai，i=1，2，3，…,m。可供应某种物资，其供应量分别为ai，i=1，2，3…m,有N个销地Bj，j=1，2，3，…,n，其需求量分别为bj，j=1，2，3，…,n。从Ai到Bj运输单位物资的运价为cij这些问题可以汇总到产销平衡表（3.1）和单位运价表（3.2）中。
表3.1产销平衡表

1
2
3
…
n
产量
1

a1
2

a2
3

a3
…

…
m

am
销量
b1
b2
b3
…
bn

表3.2单位运价表

1
2
3
…
n
1
C11
C12
C13
…
C1n
2
C21
C22
C23
…
C2n
3
C31
C32
C33
…
C3n
…
…
…
…
…
…
m
Cm1
Cm2
Cm3
…
Cmn
3.2.3 数学模型的建立
若用xij表示从Ai到Bj的用量，那么供需平衡的条件下，要求得总费用最小的调运方案，可求解一下数学模型：

目标函数：

约束条件
这就是运输问题的数学模型，他有两个特点：
（1）它包括m×n个决策变量，m+n+1个约束方程。
（2）其系数矩阵的结构比较松散且特殊。
对于产销平衡的运输问题，由于一下关系式存在：、

所以模型最多只有m+n+1个独立的约束方程。即系数矩阵的秩< m+n+1。由于有以上特征所以求运输问题时，可用比较简单的计算方法，习惯上称表上作业法。
3.2 产销不平衡问题
对于产销平衡问题可以直接用表上作业法进行解决，但对于产销不平衡问题，要先将其划成产销平衡问题，才能使用表上作业法求解。

4 总结
经济迅速发展的今天，货物运输问题是十分常见的，市场竞争日益激烈，合理选择最优的调运方案是至关重要的。通过分析影响制造企业运输环节费用的主客观因素可知，短期内产品特点、运输方式、产量、运输距离和市场需求都不会发生太大变化，因此制造业只有在单位运费一定的情况下充分考虑市场需求和产地产量从而确定合理的运输量才能有效减少运输费用。运用表上作业发确定最佳调运方案既最大限度满足了市场需求使市场机会成本损失大大减少，同时又能保证合理库存不会因为产品积压产生更多地成本或造成损失。因此，表上作业发为制造业企业有效降低运输费用提供了可行的办法。一个最优的运输方案将给企业节省大量的资金，从未额降低货物成本，大大提高了企业的竞争力。表上作业发是物品运输问题中最常用的一种方法。虽然现在表上作业法仍然比较复杂，但是它不需要什么特殊工具，任何时候都能使用。相信在不久的将来，表上作业法将会一步一步的得到改进，更加便捷易于使用。
此次课程设计让我更加了解了表上作业法的实际应用，对计算机个别软件的操作技能也有提高。感谢老师和同学们的帮助，相信我会把收获运用到以后的学习、生活中。

参考文献
[1]杜子平.运输问题表上作业法的解析[C] .
[2]王有鸿,费威.运输问题国内外研究评述[J].东北财经.
[3]李彦臣，魏丽雅.产销平衡运输最低成本的表上作业法[J].交通科技与经济.
[4] 郭秀英.论运输问题表上作业法.[J]科技与管理
[5]刘华琼.物流优化技术.清华大学出版社.
[6]钱颂迪.运筹学[M].北京:清华大学出版社,2005,06.
[7]蒋宏锋.运输问题一种新的表上作业法[J]科学技术与工程2006.
.