论文题目：用数学方法来研究运输问题
指导老师：
学院：
院系：
学号：
姓名：
用数学方法来研究运输问题
【摘要】在成产活动和日常生活中，人们常常需要将某些物品（包括人们自身）由一个空间位置移动到另一个空间位置，这就产生了运输。随着社会和经济的发展，“运输”变得越来越复杂，运输量有时非常巨大，这就产生了成本，而如何缩小成本，降低耗费，就成了我们需要研究的问题了。
【关键词】数学模型 表上作业法 闭回路法
运输问题
单一品种多个产地供应一个销地的物资的运输调度问题
典型情况是：设某种物品有m个产地
，各产地的产量分别是
，运到销地B的运价分别为
；
多个产地供应多个销地的单品种物品的运输调度问题
典型情况是：设某种物品有m个产地
，各产地的产量分别是
，有n个销地
，各销地的销量分别为
，假定从产地
(i=1,2……,m)到销地
(j=1,2,……,n)运输单位物品的单价为
；
数学模型
（1） 单一品种物资的调度问题很简单，不需要讨论，现在要研究的是多个产地供应多个销地的运输问题。为了直观起见，可列出运输表。
变量说明：
（i=1，2……m，；j=1，2，……n）为由产地
运往销地
的物品数量；
为
到
的单位运价。
销地
产地
……
产量
……
销量
*（2）将单位运价单独列入另一个表中，并称其为运价表。
接收
发送
……
发送量
……
接受量
如果运输问题的总产量等于总销量，即有
则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。
产销平衡运输问题的数学模型可表示如下：
①
②
.
③
④
其中，约束条件右侧常数
满足①。
上述模型是一种线性规划模型，目标函数表示运输总费用，要求其极小化，约束条件的意义是由某一产地运往各个销地的物品数量之和等于该产地的产量，由各个产地运往某一销地的物品数量之和等于该销地的销量，同时，满足变量的非负性。
运输问题有优先最优解。
对于产销平衡的运输问题有，
，则
为运输问题的一个可行解，目标函数有下界，目标函数不必趋于
。由此可知，运输问题必存在有限最优解。
用表上作业法求解运输问题
（1）表上作业法：表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。是线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭合回路法、位势法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。最常用的表上作业法有最小元素法和西北角法。
（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。
（3）下面以最小元素法为例，来求解现实生活中的运输问题。
某部门有4个成产同类产品的工厂，生产的产品由4个销售点出售，各工厂的生产量以及各销售点的销售量(假定单位均为t)，各工厂到各个销售点的单位运价（元/t）均如以下运价表所示，为了节约经济成本，该部门应该如何进行运输调度？
接收
发送
发送量
4
12
4
11
11
2
10
3
9
9
8
5
11
6
7
6
9
8
7
21
接受量
10
12
11
15
48
解：由简单的计算可知，总产量=总销量=48，上述的运输问题为产销平衡的运输调度。
该问题的数学模型为：
.
销地
产地
产量
（1）4
12
(10) 4
11
11
(9) 2
10
3
9
9
8
(7) 5
11
6
7
6
（5）9
（1）8
(15) 7
21
销量
10
12
11
15
48
①因为
，则
，划去第二行；
②因为
，则
，划去第一列；
③因为
，则
，划去第三行；
④因为
，则
，划去第四列；
⑤因为
，则
，划去第三列；
⑥
，划去第四行，划去第二列；
这时，得到该运输问题的一个初始解：
其他变量均为0，总运费
这个解满足所有约束条件，其非零变量的个数为
*（4）当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间可能在某一格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时长发生的，为了使表上作业法的迭代工作能够顺利的进行下去，退化时应在同时划去的一行或一列的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中的基变量个数恰好为
个。
出现退化解的情况如下：
接收
发送
发送量
4
12
4
11
11
2
10
3
9
9
8
5
11
6
18
6
9
8
7
10
接受量
8
14
12
14
48
解的最优性检验
得到了运输问题的初始基可行解后，应对其进行最优性判别，看是不是最优解。常用的两种方法有闭回路法和对偶变量法。
（1）闭合回路法是借助图表作业方式，计算比较两种(或两种以上)变量值，以调整部分经济指标实现优化经营提高管理效益的管理统计方法。它最早用于运输经济部门管理，主要是在图表作业基础上调整运量，择优选取管理方案。
（2）闭合回路法步骤
其内容和步骤主要有三点：
①检验方案的数据指标，编排闭合回路。当某一运输方案有负检验数时，若使与负检验数相对应的非基变量不为零，可使目标函数值减少。它需要将绝对值最大的负检验数对应的非基变量作为换入变量，变成基变量。若有两个以上相等的绝对值最大的负检验数时，则选对应运费最小的一个非基变量为换入变量，其值从零增加到大于零的正值，即调整运量。反之，为满足约束条件换入变量增值后，则要从原来的某一基变量中减去相应数值，变成数值为零的换出变量，由此换入换出即运量的调整。
②调整方案(运量)数值，在满足约束条件下比较各可行解方案。按此法从换入变量出发作闭合回路运转，其四周顶点除换入变量外，其余将都是填有数字画圈的基变量。变(运)量的调整即在满足约束条件下，调整闭合回路中各顶点变量数值，从一运输方案(可行解)，找到另一接近最优化的新一组可行解方案。
③验证优化数据，择优选取最佳方案。新方案，再检验是否最优，直至得出最优解。
（3）下面以闭回路法为例对上述运输问题的初始解进行最优性检验。
检验数表：
销地
产地
产量
7
8
7
1
8
4
7
3
-2
销量
由于
，所以上述初始解不是最优解。应修正为：
重复上述检验，若
则为该运输问题的最优解；
则该运输问题不止一个最优解。
解的改进
对运输问题的一个解来说，若最优性检验时某非基变量
（空格）的检验数
为负，说明将这个非基变量变为基变量时运费会更小，因而这个解不是最优解，还可以进一步改进，如上步骤所示。
改进的方法是：在运输表中找到这个空格对应的闭回路
，在满足所有约束条件下，使
尽量增大并相应调整此闭回路上其他顶点的运输量，以得到另一个更好的基可行解。
运输问题的进一步讨论
前面研究的的运输问题都是以总产量等于总销量（产销平衡）为前提的，实际上，在很多运输问题中，总产量并不等于总销量。存在两种情况：
总产量大于总销量，即
这时的数学模型是
.
为借助产销平衡时的数学方法来求解运输问题，可增加一个假想的销地
，由于它实际上并不存在，因而由产地
调运到这个假想销地的物品数量
相当于松弛变量，实际上就是就地存贮在
的物品数量。就地存贮的物品不经运输，故令其单位运价
。
若令假想销地的产量为
，且
该运输模型变为
.
(2)总产量小于总销量，即
这时，只需增加一个假想的产地
即可，它的产量等于
由于这个假想的产地并不存在，由它发往各个销地的物品数量
实际上是各销地
所需物品的欠缺额，显然有
该运输模型为
.
（3）转运问题
除了上述产销不平衡的两种情况，还有一种更复杂的运输问题存在，即，前面讨论的共三种情况均是在产地直接运往销地的基础上，而现实生活中，这种运输方式并不处于主流地位，多情况下，我们需要先讲物品运到某个或某几个中间转运站，再辗转运到销售目的地。为了使运输费用最小化，我们在决定运输方案的时候有必要把转运给考虑进去。显然考虑转运将使运输问题复杂化。
假定
个产地
和
个销地
都可以作为中间转运站使用，从而发送物品的地点和接受物品的地点都有
个。
变量说明：
：第i个产地的产量
：第j个销地的销量
：由第i个发送地到第j个接收地的物品数量
：由第i个发送地到第j个接收地的单位运价
：第i个地点转运单位物品的费用
将产地和销地统一排号，且产地在前，销地在后，则有
假定为产销平衡问题，即有
当不考虑转运费时，可令
该运输模型为
.
参考文献
1：运筹学教程/胡运权主编，郭耀煌副主编.-3版-北京：清华大学出版社， 978-7-302-14738-1；
2：运筹学基础手册，徐光辉主编，北京：科学出版社，1999；
3：运筹学原理与方法，郭耀煌等，成都：西南交通大学出版社，1994；
4：运筹学基础及应用，胡运权，第四版，北京：高等教育出版社，2004；
5：数学建模在生活中的应用【J】，李苑辉，经济研究导刊；2011年18期；
6：运输问题表上作业法的解析【A】，杜子平，第六届中国青年运筹与管理学者大会论文集【C】，2004年；
7：运输问题的研究【D】，王田娥，吉林大学，2010年；
8：运输问题简便解法在生产计划中的应用【J】，贾春玉;甄玉敏;刘富成，长春大学学报，2006年07期；
9：实用管理方法手册周范林. [M].经济管理出版社,1997年2月第1版
