浅谈运筹学中的运输问题
摘 要：运筹学自二战以来开始打来那个应用在除战争以外的许多领域，尤其在企业管理中表现的尤为突出。

运筹学的思想贯穿了企业管理的始终，在企业战略管理、生产计划、市场营销、运输问题、库存管理、人事管理、财务会计等各个方面都具有重要的作用，对企业管理的发展产生重要影响。

这里我们主要对运输问题几种方法做一个简单的介绍。

关键词：最下元素法；沃格尔法（V ogel ）
首先我们先来介绍运输问题的数学模型：设有m 个产地（记作A 1，A 2，A 3,…,Am ），生产某种物资，其产量分别为a 1,a 2，…，am ；有n 个销地（记作B 1，B 2，…，Bn ），其需要量分别为b 1,b 2，…，bn ；且产销平衡，即 。

从第i 个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。

设xij (i =1,2,…，m ；j =1,2,…,n )为第i 个产地到第j 个销地的运量，则数学模型为：
n
j m i x n j b x
m i a x
ij j
m
i ij
n
j i ij
,,1;,,1,
0,,1,,11
1 ==≥====∑∑==
∑∑
===n
j ij
ij m
i x
c z 1
1
min
（！）最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij 对应的变量xij 优先赋值
{}
j i ij b a x ,min =
然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。

下面举一个例子：求表3－7给出的运输问题的初始基本可行解。

解：
在x 12、x 22、x 33、x 34中任选一个变量作为基变量，例如选x 12 初始基本可行解可用下列矩阵表示
⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡634610
表3－8中，标有符号 的变量恰好是3+4－1=6个且不包含闭回路，
{}
323123141312,,,,,x x x x x x
是一组基变量，其余标有符号×的变量是非基变量，
（2）运费差额法（V ogel ）:最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。

有时为了节省某一处的运费，而在其它处可能运费很大。

运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。

例如下面两种运输方案，
20101258515
10⎥⎦⎤⎢⎣⎡=⨯C
2010125815510⎥
⎦⎤⎢⎣⎡=⨯C
15 15 15 15
前一种按最小元素法求得，总运费是Z 1=10×8+5×2+15×1=105，后一种方案考虑到C 11与C 21之间的差额是8－2=6，如果不先调运x 21，到后来就有可能x 11≠0，这样会使总运费增加较大，从而先调运x 21，再是x 22，其次是x 12这时总运费Z 2=10×5+15×2+5×1=85<Z 1。

基于以上想法，运费差额法求初始基本可行解的步骤是：
第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n；
第二步：找出所有行、列差额的最大值，即L=max{ui，vi}，差额L对应行或列的最小运价处优先调运；
第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。

用运费差额法求得的基本可行解更接近最优解，所以也称为近似方案。

下面是一个例子：
用运费差额法求表3—9运输问题的初始基本可行解。

ui= i行次小运价—i行最小运价
⎥⎥
⎥⎦⎤⎢⎢⎢⎣⎡=20520510
0X
基本可行解：
总运费Z =10×8+20×1+5×2+20×8=270。

求运输问题的初始方案还有很多方法，如左上角法、右上角法等。

常用的方法是Vogel 近似法、最小元素法。

以上就为我的简单介绍。

参考论文：运筹学
Operations Research
网络运筹学论文。