运筹学论文
运筹学线性规划的运输问题
学号：12404318
姓名：刘文飞
班级：信息1201班
指导教师：钱淑英
专业：信息与计算科学
系别：数学系
运筹学线性规划的运输问题
12404318 刘文飞信息与计算科学
引言：
运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问题：在大宗物资调运时，有若干个产地，根据已知的运输交通网，如何制定一个运输方案，将这些物资运到各个销售地，使得总运费最小。
物流管理的本质要求就是求实效，即以最少的消耗，实现最优的服务，达到最佳的经济效益。
搞好物流管理，可以通过合理的运输方案，使中间装卸搬运、储存费用降低、损失减少，在其他条件不变的情况下，降低物流成本就意味着扩大了企业的利润空间，提高了利润水平，所以一个合理的运输方案有着重要的意义。
运筹学方法在物流工作中的应用运筹学研究的方法十分广泛，主要分支有：线性规划、非线性规划、目标规划、整数规划、几何规划，等等。
数学规划论主要研究计划管理工作中有关有限资源的分配的问题。
一般可以归纳为在满足既定的条件限制下，按某一衡量指标来寻求最优方案的问题，求解约束条件下目标函数的极值(极大值或极小值)的问题。
论文摘要：
运筹学是一门定量决策科学,它利用定量分析的方法(数学、管理科学、计算机科学)进行科学决策以实现最有效的管理来获得满意的经济效益,是现代管理的重要理论基础。
运筹学中的线性规划和线性规划问题一直分别采用修正单纯形法和单纯形法来求解。
运筹学研究的方法和模型已经非常成熟，随着物流学科的逐渐成熟，本文探讨了两个学科之间的关系，并根据实际案例研究如何利用运筹学中的线性规划模型，来解决现代物流企业中的实际应用问题。
[关键词]运筹学；线性规划；物流企业；运输问题。
正文
一：运筹学与物流学作为正式的学科都始于二战期间。
当时英美为了对付德国的空袭，在英国波得塞（Bawdsey）雷达站设立了专门的研究机构，从一开
始，两者就密切地联系在一起，运筹学应用的典型案例大都是物流作业或管理，它能根据实际的要求，通过数学的分析与运算，做出综合的合理安排，以达到较经济、有效地使用人力、物力、财力等资源。
二：运筹学方法在物流工作中的应用运筹学研究的方法十分广泛，主要分支有：线性规划、非线性规划、目标规划等。
在物流企业应用规划论的典型的例子如“运输问题”，即将某种物资从一个地点运送到另一个地点，要求在供销平衡的同时，定出流量与流向，使总运输成本最低。
运用规划论还可以解决“物资车辆调度”、“货物配装”、“物流资源(人员或设备)指派”、“最优路径”、“资源分配”等物流难题。
运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问题：在大宗物资调运时，有若干个产地，根据已知的运输交通网，如何制定一个运输方案，将这些物资运到各个销售地，使得总运费最小。
物流管理的本质要求就是求实效，即以最少的消耗，实现最优的服务，达到最佳的经济效益。
三：经典运输模型：
经典的运输问题是一个线性规划模型。
假定某种物资有m个产地，n个销地为第i产地的供应量，为第j个销地的需求量, 为从产地i到销地j的单位运费，为产地i到销地j的调运数量，≥0，其中i=1,2,…,m；j=1,2,…,n。
问如何组织调运才能使得总运费最省?
该问题为了寻找最佳调运方案，即求解所有的值．使总的运输费用达到最少。
其中当=时为平衡型运输问题：当其不相等的时候就位不平衡型运输问题。
实际上步平衡型的运输问题通过转换可以变成平衡型的问题。
当产量总量等于销售总量时，运输问题有可行解，且有最优解，且当产量和销售量均为整数时，必存在决策变量均为整数的最优解。
平衡型运输问题的数学模型如下：
S.t．=1,2…m =,i=1,2…n
,对所有的i，j
运输问题的解法通常用表上作业法。
表上作业法是单纯形法在求解运输问题。
四：表上作业法
运输问题的解法通常用表上作业法。
表上作业法是单纯形法在求解运输问题。
表上作业通常有三种：西北角法、最小元素法、vogel （沃格尔）法。
（1）西北角法：
从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。
然后按行（列）标下一格的数。
若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。
如此进行下去，直至得到一个基本可行解。
（2）最小元素法：
从运价最小的格开始，在格内的右下角标上允许取得的最大数。
然后按运价从小到大顺序填数。
若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。
如此进行下去，直至得到一个基本可行解。
（3）vogel(沃格尔)法：
在运价表上写出每行和每列运价中最小元素和次小元素之差。
从所有行差额和列差额中选取差额最大的一行或 一列进行分配，并对该行(或列)最小元素格填数。
重新计算差额，重复上述手续。
剩最后一行或一列按余额分配，只填数即可，确保有数字个数为m+n-1个。
五：产销不平衡的运输问题及其求解方法
前面讲的表上作业法，都是以产销平衡为前提的。
但实际问题往往是不平衡的。
这就需要把产销不平衡的问题转化为产销平衡的问题。
当产大于销时，即 ∑∑==≥n
j j m
i i b a 1
1
时，运输问题的数学模型可以写成：
⎪⎪⎪⎪⎩
⎪
⎪⎪⎪⎨⎧==≥===≤=∑∑∑∑====),1;,,1(0),,1(),,1(min 1
1m 11
n j m i x n j b x m i a x x c Z ij i m i ij i n
j ij i n
j ij
ij (1.21)
由于总的产量大于销售量，就要考虑多余的物资在那一个产地贮存的问题。
设 xin+1 是产地 Ai 的贮存量，故有：时。
当时；当：令：1,,,1:,0,,1,,,1,)
,,1()
,,1(''
1
1
1
1
111
1
11+=======-======++===+=+==+∑∑∑∑∑∑n j m i c n j m i c c b b a x n j b x
m i a x x x
ij ij ij n n
j j m
i i m i in j m
i ij
i n j ij n
j in ij
将其分别代入（1.21），得到：
⎪⎪⎪
⎪⎩
⎪⎪⎪⎪⎨⎧-=≥+======∑∑∑∑∑∑∑∑==+=+====+=m i n j j i n ij j m
i ij i n j ij ij
m i n
j ij m i n j ij ij
b a b x n n j b x m i a x x
c x c Z 1111
1
111
111
'
'
:0)1,,,1(),1(min (1.22)
这是一个产销平衡的运输问题。
类似地，当销大于产时，可以在产销平衡表中增加一个假想的产地1+=m i ,该产地的产量为∑∑==-m
i i n
j j a b 1
1
，在单位运价表中令从该产地到各个销售地的单位
运价为：01=+j m c ，同样可以转化为产销平衡的运输问题。
⎪⎪⎪
⎪⎩
⎪⎪⎪⎪⎨⎧-=≥==+====∑∑∑∑∑∑∑∑==++====+==n j m i i j m ij m i j ij n
j i ij ij
m i n
j ij ij m i n j ij
a b a x n j b x m m i a x x c x c Z 1111
1
111
111
'
;0),,1()1,,,1(min ‘
六：结论：
对于表上作业法的三种方法而言，西北角法虽然简单，但是，这种方
法只是单纯的解决了运输分配问题，没有考虑运费问题，因而导致了这种方法最后的运费较高，离最优运费相距甚远。
因而，在解决实际问题的时候，往往会放弃这种方法。
而最小元素法看起来十分合理，但是，有时按最小单位运价优先安排物品调运时，往往选择了价格较高的运点，从而使运输费用增加，因而最小元素法所得的运费多是较低的运费，但却不是最低的运费。
沃格尔法给出的解的函数值相对较小，往往可以作为最优解的近似解。
一般来说，如果要求方案不是非常精确，可以采用沃格尔法。
参考文献：
[1]王春晓.《求解运输问题的新算法》.《高校理科研究》.
[2]运筹学教材编写组．《运筹学(第三版)》.清华大学出版社.2005．
[3]胡运权．《运筹学教程》.清华大学出版社.2004．
[4]鄢玲.蔺赟.郭红霞运筹学在物流中的应用与发展[期刊论文]-沿海企业与科技2005(12)
[5]殷战稳.刘雷.安亚辉.YIN Zhan-wen.LIU Lei.AN Ya-hui 限期物资采购问题的运筹学模型[期刊论文]-平顶山工学院学报2005,14(5)。