线性规划在运输问题中的应用.doc

1、 2013届学士学位毕业论文线性规划在运输问题中的应用学 号:09404323姓 名：李勇班 级：信息0901指导教师：董建新专 业:信息与计算科学系 别:数 学 系完成时间：2013年6月学生诚信承诺书本人郑重声明：所呈交的论文线性规划在运输问题中的应用是我个人在导师董建新指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得长治学院或其他教育机构的学位或证书所使用过的材料.所有合作者对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名： 日期: 论文使用授权说明本人完全了解长治学院有关保留

2、、使用学位论文的规定，即:学校有权保留送交论文的复印件,允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。签名： 日期： 指导教师声明书本人声明:该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。 指导教师签名: 时间 摘 要随着我国市场经济的不断完善，同地区、不同地区、甚至跨国间的企业交易更加的频繁.因此,在运输中如何降低运输费用、减少运输路线等问题,已经成为交易活动的重点，而随着社会分工的细化，物流和运输业不断的发展，运输问题也就变的越来越复杂，运输量有时候非常巨大,

3、所以科学的组织运输显得十分重要.线性规划主要应用于解决最优化问题，而运输问题可以看作是一类特殊的线性规划问题。本文结合案例，分析了运输问题的基本特征及解决策略,并通过实例对运输问题进行了优化分析建立了线性规划的数学模型，并借助计算机进行求解，在本篇文章中主要应用的是excel求解，能快速准确的得到最优化方案,提高了实际运输工作中的经济效益。 关键词：线性规划;运输问题；excelLinear Programming In The Application Of The Transportation Problem 09404323 Li Yong Information and Computin

4、g ScienceFaculty adviser Dong Jian-xinAbstractAs the constant improvement of market economy in our country， trade become more frequently in the same areas， different regions and even multinational companies。 In transit, therefore， how to reduce the transportation cost， reduce transport routes and ot

5、her issues has become the focus of trading activities。 With the refinement of social division of labor, the development of logistics and transport， transportation problem also becomes more and more complex， traffic sometimes very large， so the science of organization transportation appears very impo

6、rtant. Linear programming is mainly applied to solve the optimization problem. Transportation problem can be regarded as a kind of special linear programming problem。 Combining with the case， analyzes the basic characteristics of the transportation problem and solving strategy, and through the insta

7、nce analysis of transportation problem is optimized， so that linear programming mathematical model is established。 The solution can be obtained with the aid of computer。 In this article， the problem is solved by the application of excel which can quickly and accurately get optimal solution. In addit

8、ion, it also improve the economic efficiency in the actual transportation work。个人收集整理，勿做商业用途文档为个人收集整理，来源于网络Key Word： Linear programming; transportation problem; excel目 录引言11. 线性规划的基本理论11.1 线性规划的基本概念11.2 线性规划的一般数学模型22线性规划在运输问题中的应用22.1 运输问题的基本特征22.2 运输问题的解决策略32.2。1 产销平衡运输问题的一般作法32。2.2 产销不平衡运输问题分两种情况33

9、.应用excel求解运输问题简介43。1 运输问题的形式43。2 在excel中的形式43.3 excel求解步骤54。运输问题实例55.结束语106。参考文献11致 谢12线性规划在运输问题中的应用09404323 李勇 信息与计算科学指导教师 董建新引言线性规划是决策系统的静态最优化数学规划方法之一。它经常作为经营管理决策中的数学手段,在现代决策中的应用是非常广泛的，它可以用来解决科学研究、工程设计、生产安排、军事指挥，经济规划、经营管理等各方面提出的大量问题。而最近几年，我国物流产业快速发展，形成了物流热。在物流产业的管理活动中,有着大量的规划问题,物资的合理调运就是其中一个比较重要的问

10、题。求物资调运的最优方案,就是要在满足各种资源限制的条件下，找到使运输总费用最小的调运方案，即运输问题。随着社会分工的细化，物流和运输业得到不断发展，“运输"变得越来越复杂，运输量有时非常巨大,科学组织运输显得十分重要。在本文中，运输问题只从供给量、需求量和单位运价方面考虑对总运费的影响，而对其他的一些经济因素或非经济因素，如价格折扣、交通限制、中转运输、政府政策等均未考虑.在求解最优方案时，采用了excel求解，能够快速准确的得到最优解。1。 线性规划的基本理论1。1 线性规划的基本概念 线性规划(LP）是运筹学的一个重要分支,是数学规划的一个重要组成部分。它所研究的问题可归纳为:

11、在一定的技术经济条件制约下，使某项指标取得最大成果(如利润最大或成本最低)，即为最优设计理论的一种。所谓最优设计理论,就是指在满足一定条件下,按某一种标准，从众多的方案中选择最好的方案.线性规划法是一种基本的数学规划方法,问题的主要特征是所有的约束和目标函数表示成变量的线性关系，约束既可以是等式的，也可以是不等式的,目标函数可取其极小值或极大值。它是管理定量分析的重要方法之一，广泛应用于经济学、管理科学等领域,在线性约束的条件下，使某个线性目标函数达到最优。例如：任务安排问题、配料问题、下料问题、布局问题、库存问题、运输问题和非生产性问题等.1.2 线性规划的一般数学模型 线性规划问题就是规定

12、某些变量的值，他们满足一些线性约束条件下，使某一线性函数的目标函数值达到最大或者最小.当然目标函数可能是极小值也可能是极大值;决策变量可能有非负的条件限制，也可能无非负条件限制；约束条件可能是方程式，也可能是不等方程式。线性规划问题得一般形式是：目标函数：约束条件： (I）其中为决策变量，均为常数，.并假设 0,否则可将方程两端同乘以(1）,将右端常数化为非负数,并简称（LP）问题。 如果原数学模型中第 i 个约束条件为“小于等于"或“大于等于”不等式；则在左边“加上”或“减去”一个非负的松驰变量,即可化为等式方程:，并令在目标函数中的系数为“零”。2线性规划在运输问题中的应用 在现

13、实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。 运输问题就是讨论有关物资调运的问题,即将数量和单位运价都给定的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输成本最低.运输问题是特殊的线性规划问题，根据问题的要求,建立数学模型,用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益.在运输问题中，确定的需求限制占据

14、着重要的地位,即必须确定需求以及相应地确定需求的约束条件。2。1 运输问题的基本特征运输问题解决的是已知产地的供应量、销地的需求量及运输单价，如何寻找总配送成本最低的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题;通常将产销不平衡问题转化为产销平衡问题来处理。运输问题的条件包括需求假设和成本假设。需求假设指每一个产地都有一个固定的供应量，所有的供应量都必须配送到目的地.与之类似,每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足；成本假设指从任何一个产地到任何一个销地的货物配送成本和所配送的数量成线性比例关系.2。2 运输问题的解决策略运输问题一般分为产销平衡问题和产销不平

15、衡问题。2.2.1 产销平衡运输问题的一般作法假设某物资有m个产地，各地的产量分别为;n个产地，各地的产量分别为;物资从产地运往销地的单位运价为，为第i个产地调运给第j个销地的物资的单位数量，满足:其数学模型为： (II)2。2.2 产销不平衡运输问题分两种情况（1）总产量大于总销量,即满足，此时只需要增加一个假象的销地j=n+1（实际上是库存），该销地的总需求量为（）,而单位运价表中冲个产地到假想销地的单位运价=0(=1,2）,就转化成了一个产销平衡问题,此时其数学模型与表达式（II）基本相同。(2)类总产量小于总销量，即满足，此时其数学模型与表达式(II)也基本相同，可以在产销平衡表中加一

16、个假想的产地i=n+1,该地产量为（），在单位运价表上令从该假想产地到各销地的运价=0（=1,2）同样可以转化成一个产销平衡的运输问题。现实生产的情况往往比较复杂,许多实际问题不一定完全符合运输问题的假设,可能一些特征近似但其中的一个或者几个特征却并不符合运输问题条件。一般来说，如果一个问题中涉及两大类对象之间的联系或往来，且该问题能提供运输问题所需要的三类数据：供应量、需求量、单位运价，那么这个问题（不管其中是否涉及运输）经适当约束条件的处理后,基本都可以应用运输问题模型来解决.例如追求的目标是效益最大而非成本最低，此时仅将表达式（II）中目标函数中Min的改为Max即可；部分(或全部)的供

17、应量（产量）代表的是从产地提供的最大数量(而不是一个固定的数值），此时只需将表达式(II）中的产地约束中部分(或全部）的“=”改成“”即可；部分(或全部）的需求量（销量）代表的是销地接收的最大数量（而不是一个固定的数值)，此时只需将表达式（II)中的销地约束中的“=”部分（或全部）改成“"即可；某些目的地同时存在最大需求最小需求，此时的解决办法是将表达式（II）中的相应的销地约束中的“”一个式子分解成“最大需求”和 “最小需求"的两个式子即可；某些配送中不能使用的出发地-目的地组合，此时的处理方法是添加一个新的约束条件=0。文档为个人收集整理,来源于网络个人收集整理,勿做商

18、业用途3。应用excel求解运输问题简介3.1 运输问题的形式销售地产地运价表产量销量3.2 在excel中的形式3。3 excel求解步骤1、 G1：G3填产量表，A5:E5填销量表,A7：E9填运价表.2、 F1填=SUM（A1:G1）并复制到F3；A4填=SUM（A1：A3),并复制到E4；A6填=SUMPRODUCT（A1：E3，A7：E9).3、 启动规划求解：设置目标单元格：$A$6等于：最小值可变单元格：A$1:$E$3约束：A4=A5，B4=B5，C4=C5，D4=D5，E4=E5,F1=G1,F2=G2，F3<=G3在“选项”中选中：采用线性模型，假定非负4、 求解此步

19、骤针对不同的变量个数都可以使用，在使用时只需录入相关的数据即可。4。运输问题实例例1。 某公司是一个拥有 3 个木材资源区和 5 个需要供应的市场的木材公司。木材资源区 1、2、3 每年所能够生产的木材量分别为 1500 万、2000 万和 1500 万米。每年市场 1、2、3、4、5 能够销售的木材量分别为 800 万、900 万、1000 万、1100 万和 1200 万米。过去，这个公司通过火车来运输木材。然而,由于使用火车的运输成本已经上升了，最近，该城市建立了一个新的港口，所以可以考虑使用水运的方式来运输其中的一部分木材。但是这种方式却需要公司要在水运方面进行投资。除了这些投资成本之

20、外，使用火车运输木材的成本（单位:万元每米)，沿着每一条路线使用轮船来运输木材（如果这个方式可行的话）的成本如下1表所示：表1 使用火车运输的单位成本(单位：万元）单位成本12345166455561722566049697834763615966表2 使用轮船运输的单位成本（单位：万元)单位成本1234513524313823128243643326363233沿着每一条路线用轮船每年运输每 100 万米，如下表3所示：表3 向市场运输木材的轮船的单位资金投入(单位：万元)单位资金投入123451285238-2753032265270250233183240275268283考虑到轮船的预

21、计使用期限和货币的时间价值,年成本大约就是表中所列数值的 1/10。公司的目标是要制定出一个全面运输计划,使年总成本最小（包括运输成本)。现在，公司管理科学小组的负责人分别制定出了三个能够使年成本最小的运输计划。方案 1：使用火车运输木材，并仅使用此方式.方案 2：仅使用轮船运输木材(只能使用火车的地方除外）。方案 3：根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材。求出能使运输成本最低的从各木材资源区到各个市场的运输数量及最低的运输成本。这是一个典型的运输问题,分别就三个不同的方案进行估计,看哪个方案的总运输成本最低，并且用excel可以很快得到一个最优解决方

22、案。首先，运用线性规划用代数的形式来建立它的数学模型。假设（i=1,2，3；j=1,2,3,4,5）为从每个木材资源区到每个市场的运输数量，目标是为了找出能使总运输成本最低的从每个木材资源区到每个市场的运输数量.方案 1:目标函数： 约束条件：运用excel进行线性规划求解可以很快得出使用火车到达各市场的木材公司最低的运输单位成本的最优值，如下表4所示：表4 火车运输的最低运输单位成本最优值运输量12345总产量1090006000150028000100020092000300030012001500总需求800900100011001200由此可知，继续使用火车来运输木材,最低的运输成本为

23、 28160 万元。资源区 1 到市场 2 的运输量为 900 万米，资源区 1 到市场 4 的运输量为 600 万米，资源区 2 到市场 1 的运输量为 800 万米,资源区 2 到市场 3 的运输量为 1000 万米,资源区 2 到市场 4 的运输量为 200 万米，资源区 3 到市场 4 的运输量为 300 万米资源区 3 到市场5 的运输量为 1200 万米。方案 2：由于考虑到轮船的预计使用期限和货币的时间价值，年成本大约就是表4中所列数值的 1/10。所以，对于向市场运输木材的轮船的单位资金投入如下表5：表5 向市场运输木材的轮船的单位资金投入（单位：万元)单位资金投入123451

24、28。523.827.530.3226。5272529。331。832427.526.828.3因此,对于向市场轮船运输木材的单位总成本（万元)如下表6：表6 向市场轮船运输木材的单位总成本（万元）单位总成本12345163.547。85558。568.3257.5554965.374。835063.558.85961.3目标函数： 约束条件为:运用excel进行线性规划求解可以很快得出使用轮船到达各市场的木材公司最低的运输单位成本的最优值,如下表7：表7 使用轮船运输最低的运输单位成本的最优值运输量12345总产量109000600015002500010005000200033000001

25、2001500总需求800900100011001200由此可知，仅使用轮船来运输木材（只能使用火车的地方除外），最低的运输成本为 27708 万元。资源区 1 到市场2 的运输量为 900 万米，资源区 1 到市场 4 的运输量为600 万米，资源区 2 到市场 1 的运输量为 500 万米,资源区 2 到市场 3 的运输量为 1000 万米,资源区 2 到市场4 的运输量为 500 万米，资源区 3 到市场 1 的运输量为300 万米，资源区 3 到市场 5 的运输量为 1200 万米。方案 3：因为要根据运输成本最低来确定使用火车或轮船，所以重新所选择的单位成本如表8：表8 重新所选择的

26、单位成本单位成本12345163.5455558。568.3256554965.374。83476358.85961。3目标函数： 约束条件：运用excel进行线性规划求解可以很快得出使用方案3最低的运输单位成本的最优值，如表9:表9 方案3最低的运输单位成本的最优值运输量12345总产量1090006000150025000100050002000330000012001500总需求800900100011001200由此可知，根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材，最低的运输成本为 27291 万元。资源区 1 到市场 2 的运输量为 900 万米，

27、资源区 1 到市场 4 的运输量为 600 万米，资源区 2到市场 1 的运输量为 500 万米，资源区 2 到市场 3 的运输量为 1000 万米,资源区 2 到市场 4 的运输量为 500 万米，资源区 3 到市场 1 的运输量为 300 万米，资源区 3 到市场 5 的运输量为 1200 万米。比较以上三种方案，方案 1 的继续使用火车来运输木材，最低的运输成本为 28160 万元。方案 2 的仅使用轮船来运输木材（只能使用火车的地方除外），最低的运输成本为27708 万元.方案 3 的根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材，最低的运输成本为 27291 万元。因此，该公司的最优调运方案为方案 3，即同样的运输量,总运输成本最低。5.结束语上面的案例具有很大启发性，它们揭示了运用线性规划模型解决运输问题的一般思路.在实际问题处理中，要求决策人员准确把握问题中的产销双方以及各自的产量与销量,在此基础上设置好约束条件，同时提炼出运输问题需要的所谓单位成本,建立运输问题的数学模型.运用线性规划法来指导一些投资决策具有一定的理论