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

2013届学士学位毕业论文线性规划在运输问题中的应用学号：名：班 级： 信息0901指导教师：专 业： 信息与计算科学系 别： 数学系完成时间：2013年6月学生诚信承诺书本人郑重声明：所呈交的论文《线性规划在运输问题中的应用》是我个人在导师童建新指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得长治学院或其他教育机构的学位或证书所使用过的材料。所有合作者对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：日期：论文使用授权说明本人完全了解长治学院有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。签名：日期：指导教师声明书本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。指导教师签名：时间摘要随着我国市场经济的不断完善，同地区、不同地区、甚至跨国间的企业交易更加的频繁。因此，在运输中如何降低运输费用、减少运输路线等问题，已经成为交易活动的重点，而随着社会分工的细化，物流和运输业不断的发展，运输问题也就变的越来越复杂，运输量有时候非常巨大，所以科学的组织运输显得十分重要。线性规划主要应用于解决最优化问题，而运输问题可以看作是一类特殊的线性规划问题。本文结合案例，分析了运输问题的基本特征及解决策略，并通过实例对运输问题进行了优化分析建立了线性规划的数学模型，并借助计算机进行求解，在本篇文章中主要应用的是excel求解，能快速准确的得到最优化方案，提高了实际运输工作中的经济效益。关键词：线性规划；运输问题；excelLinearProgrammingInTheApplicationOfThe

TransportationProblem09404323LiYongInformationandComputingScience

FacultyadviserDongJian-xinAbstractAstheconstantimprovementofmarketeconomyinourcountry,tradebecomemorefrequentlyinthesameareas,differentregionsandevenmultinationalcompanies.Intransit,therefore,howtoreducethetransportationcost,reducetransportroutesandotherissueshasbecomethefocusoftradingactivities.Withtherefinementofsocialdivisionoflabor,thedevelopmentoflogisticsandtransport,transportationproblemalsobecomesmoreandmorecomplex,trafficsometimesverylarge,sothescienceoforganizationtransportationappearsveryimportant.Linearprogrammingismainlyappliedtosolvetheoptimizationproblem.Transportationproblemcanberegardedasakindofspeciallinearprogrammingproblem.Combiningwiththecase,analyzesthebasiccharacteristicsofthetransportationproblemandsolvingstrategy,andthroughtheinstanceanalysisoftransportationproblemisoptimized,sothatlinearprogrammingmathematicalmodelisestablished.Thesolutioncanbeobtainedwiththeaidofcomputer.Inthisarticle,theproblemissolvedbytheapplicationofexcelwhichcanquicklyandaccuratelygetoptimalsolution.Inaddition,italsoimprovetheeconomicefficiencyintheactualtransportationwork.KeyWord:Linearprogramming;transportationproblem;excel目录TOC\o"1-5"\h\z\o"CurrentDocument"引言 2\o"CurrentDocument"1.线性规划的基本理论 2\o"CurrentDocument"1.1线性规划的基本概念 2\o"CurrentDocument"1.2线性规划的一般数学模型 3\o"CurrentDocument"2•线性规划在运输问题中的应用 3\o"CurrentDocument"2.1运输问题的基本特征 3\o"CurrentDocument"2.2运输问题的解决策略 4\o"CurrentDocument"2.2.1产销平衡运输问题的一般作法 4\o"CurrentDocument"2.2.2产销不平衡运输问题分两种情况 4应用excel求解运输问题简介 5\o"CurrentDocument"3.1运输问题的形式 5\o"CurrentDocument"在excel中的形式 5\o"CurrentDocument"excel求解步骤 6\o"CurrentDocument"运输问题实例 6\o"CurrentDocument"结束语 11\o"CurrentDocument"参考文献 12\o"CurrentDocument"致谢 13线性规划在运输问题中的应用09404323李勇信息与计算科学

指导教师董建新引言线性规划是决策系统的静态最优化数学规划方法之一。它经常作为经营管理决策中的数学手段，在现代决策中的应用是非常广泛的，它可以用来解决科学研究、工程设计、生产安排、军事指挥，经济规划、经营管理等各方面提出的大量问题。而最近几年，我国物流产业快速发展，形成了物流热。在物流产业的管理活动中，有着大量的规划问题，物资的合理调运就是其中一个比较重要的问题。求物资调运的最优方案，就是要在满足各种资源限制的条件下，找到使运输总费用最小的调运方案，即运输问题。随着社会分工的细化，物流和运输业得到不断发展，“运输”变得越来越复杂，运输量有时非常巨大，科学组织运输显得十分重要。在本文中，运输问题只从供给量、需求量和单位运价方面考虑对总运费的影响，而对其他的一些经济因素或非经济因素，如价格折扣、交通限制、中转运输、政府政策等均未考虑。在求解最优方案时，采用了excel求解，能够快速准确的得到最优解。线性规划的基本理论1.1线性规划的基本概念线性规划（LP）是运筹学的一个重要分支，是数学规划的一个重要组成部分。它所研究的问题可归纳为:在一定的技术经济条件制约下，使某项指标取得最大成果（如利润最大或成本最低），即为最优设计理论的一种。所谓最优设计理论，就是指在满足一定条件下，按某一种标准，从众多的方案中选择最好的方案。线性规划法是一种基本的数学规划方法，问题的主要特征是所有的约束和目标函数表示成变量的线性关系，约束既可以是等式的，也可以是不等式的，目标函数可取其极小值或极大值。它是管理定量分析的重要方法之一，广泛应用于经济学、管理科学等领域，在线性约束的条件下，使某个线性目标函数达到最优。例如：任务安排问题、配料问题、下料问题、布局问题、库存问题、运输问题和非生产性问题等。

1.2线性规划的一般数学模型线性规划问题就是规定某些变量的值，他们满足一些线性约束条件下，使某一线性函数的目标函数值达到最大或者最小。当然目标函数可能是极小值也可能是极大值；决策变量可能有非负的条件限制，也可能无非负条件限制；约束条件可能是方程式，也可能是不等方程式。线性规划问题得一般形式是：目标函数:Minz-cx+cx目标函数:Minz-cx+cx+ cx约束条件：a x +ax + a x111 122 1n]a x +ax + a x211 222 1n(或(或<)b1<)b（I）ax+axax+ax+ ax>(或<)bm11z.n22 叫x.>0(j-1,2 n)其中x为决策变量，c,a,b均为常数，i=1,2,3.・.m;j=1,2,3.・.n。并假设ij iijjb±0,否则可将方程两端同乘以（-1），将右端常数化为非负数，并简称（LP）问题。如果原数学模型中第i个约束条件为“小于等于”或“大于等于”不等式;则在左边“加上”或“减去”一个非负的松驰变量s>0,即可化为等式方程：ax+ax+……ax+s-b,并令s在目标函数中的系数为“零”。111 122 innii i线性规划在运输问题中的应用在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。运输问题就是讨论有关物资调运的问题,即将数量和单位运价都给定的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时,制定出流量与流向，使总运输成本最低。运输问题是特殊的线性规划问题，根据问题的要求,建立数学模型,用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益。在运输问题中，确定的需求限制占据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。2.1运输问题的基本特征运输问题解决的是已知产地的供应量、销地的需求量及运输单价，如何寻找总配送成本最低的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题；通常将产销不平衡问题转化为产销平衡问题来处理。运输问题的条件包括需求假设和成本假设。需求假设指每一个产地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足；成本假设指从任何一个产地到任何一个销地的货物配送成本和所配送的数量成线性比例关系。2.2运输问题的解决策略运输问题一般分为产销平衡问题和产销不平衡问题。2.2.1产销平衡运输问题的一般作法假设某物资有m个产地A、A A，各地的产量分别为a、a、a—a；nTOC\o"1-5"\h\z1 2 m 12 3m个产地B、B……B，各地的产量分别为b、b......b；物资从产地A.运往销地B.1 2 n 1 2 n i j的单位运价为%,x”为第i个产地调运给翁个销地的物资的单位数量，满足Ea=Eb:其数学模型为：iji=1 j=1Minz=EEex.i=1j=1Ex=a(i=1,2--m)产地约束i=1(II)Ex=b(j=1,2..・n)销地约束(II)TOC\o"1-5"\h\zJ=1 ,■x>0(i=1,2..・m;j=1,2--n)非负约束j2.2.2产销不平衡运输问题分两种情况（1）总产量大于总销量，即满足祠〉£b，此时只需要增加一个假象的销i=1 j=1地j=n+1（实际上是库存），该销地的总需求量为（祠-Eb），而单位运价表中i=1 j=1冲个产地到假想销地的单位运价匕丽=0（i=1，2……m），就转化成了一个产销平衡问题，此时其数学模型与表达式（II）基本相同。（2）类总产量小于总销量，即满足£气＜£b.，此时其数学模型与表达式（II）i=1 j=1也基本相同，可以在产销平衡表中加一个假想的产地i=n+1,该地产量为（&-£气），在单位运价表上令从该假想产地到各销地的运价c川.=0（.=1，j=1 i=1 ，2......乃）同样可以转化成一个产销平衡的运输问题。现实生产的情况往往比较复杂，许多实际问题不一定完全符合运输问题的假设，可能一些特征近似但其中的一个或者几个特征却并不符合运输问题条件。一般来说，如果一个问题中涉及两大类对象之间的联系或往来，且该问题能提供运输问题所需要的三类数据：供应量、需求量、单位运价，那么这个问题（不管其中是否涉及运输）经适当约束条件的处理后，基本都可以应用运输问题模型来解决。例如⑴追求的目标是效益最大而非成本最低，此时仅将表达式（II）中目标函数中Min的改为Max即可；⑵部分（或全部）的供应量（产量）代表的是从产地提供的最大数量（而不是一个固定的数值），此时只需将表达式（II）中的产地约束中部分（或全部）的“=”改成“M”即可；⑶部分（或全部）的需求量（销量）代表的是销地接收的最大数量（而不是一个固定的数值），此时只需将表达式（II）中的销地约束中的“=”部分（或全部）改成V唧可；⑷某些目的地同时存在最大需求最小需求，此时的解决办法是将表达式（II）中的相应的销地约束中的“Ex.=b（j=1,2,...〃）”一个式子分解成“最大需求”和“最小需求”的两个式子j=1即可；⑸某些配送中不能使用的出发地一日的地组合，此时的处理方法是添加一个新的约束条件x..=0.3.应用excel求解运输问题简介3.1运输问题的形式销售地产地运价表产量销量3.2在excel中的形式运价表2左侧和产量表上方和销售表目标函数运价表11 13.3excel求解步骤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、 求解此步骤针对不同的变量个数都可以使用，在使用时只需录入相关的数据即可。4.运输问题实例例1.某公司是一个拥有3个木材资源区和5个需要供应的市场的木材公司。木材资源区1、2、3每年所能够生产的木材量分别为1500万、2000万和1500万米。每年市场1、2、3、4、5能够销售的木材量分别为800万、900万、1000万、1100万和1200万米。过去，这个公司通过火车来运输木材。然而，由于使用火车的运输成本已经上升了，最近，该城市建立了一个新的港口，所以可以考虑使用水运的方式来运输其中的一部分木材。但是这种方式却需要公司要在水运方面进行投资。除了这些投资成本之外，使用火车运输木材的成本(单位：万元每米)，沿着每一条路线使用轮船来运输木材(如果这个方式可行的话)的成本如下1表所示：表1使用火车运输的单位成本(单位：万元)单位成本12345166455561722566049697834763615966表2使用轮船运输的单位成本（单位：万元）单位成本1234513524—3138231282436433263632—33沿着每一条路线用轮船每年运输每100万米，如下表3所示：表3向市场运输木材的轮船的单位资金投入（单位：万元）单位资金投入123451285238—2753032265270250233183240275268—283考虑到轮船的预计使用期限和货币的时间价值，年成本大约就是表中所列数值的1/10。公司的目标是要制定出一个全面运输计划，使年总成本最小（包括运输成本）。现在，公司管理科学小组的负责人分别制定出了三个能够使年成本最小的运输计划。方案1：使用火车运输木材，并仅使用此方式。方案2：仅使用轮船运输木材（只能使用火车的地方除外）。方案3：根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材。求出能使运输成本最低的从各木材资源区到各个市场的运输数量及最低的运输成本。这是一个典型的运输问题，分别就三个不同的方案进行估计，看哪个方案的总运输成本最低，并且用excel可以很快得到一个最优解决方案。首先，运用线性规划用代数的形式来建立它的数学模型。假设七（=1,2,3；j=1,2,3,4,5）为从每个木材资源区到每个市场的运输数量，目标是为了找出能使总运输成本最低的从每个木材资源区到每个市场的运输数量。方案1：目标函数：c=6(x+45c+55c+6X+72c+5&+6(X+49c+6贝+7&+47t+63c+6X+5贝+6&TOC\o"1-5"\h\z11 12 13 14 15 21 22 23 24 25 31 32 33 34 35'66x+45x+55x+61x+72x<150011 12 13 14 1556x +60x +49x +69x +78x <200021 22 23 24 2547x +63x +61x +59x +66x <150031 32 33 34 35x+x+x=800约束条件:<x+x+x=900约束条件:x+x+x=100013 23 33x+x+x=1100x+x+x=120015 25 35、x〔j>0(/=1,2,3;j=1,2,3,4,5)运用excel进行线性规划求解可以很快得出使用火车到达各市场的木材公司最低的运输单位成本的最优值，如下表4所示：表4火车运输的最低运输单位成本最优值运输量12345总产量1090006000150028000100020092000300030012001500总需求800900100011001200由此可知，继续使用火车来运输木材，最低的运输成本为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向市场运输木材的轮船的单位资金投入（单位：万元）单位资金投入12345128.523.827.530.3226.5272529.331.832427.526.828.3因此，对于向市场轮船运输木材的单位总成本（万元）如下表6：表6向市场轮船运输木材的单位总成本（万元）单位总成本12345163.547.85558.568.3257.5554965.374.835063.558.85961.3目标函数：c—63.5+47.8+55t+58.5+68.3+57.5+55t+4贝+65.3+74.X+5Ck+63.5+58.8+5贝+61.XTOC\o"1-5"\h\z11 12 13 14 15 21 22 23 24 25 31 32 33 34 35'63.5x+47.8x+55x+58.5x+68.3x<150011 12 13 14 1557.5x+55x+49x+65.3x+74.8x<200021 22 23 24 2550x+63.5x+58.8x+59x+61.3x<150031 32 33 34 35x+x+x=800约束条件为:<x+x+x=900约束条件为:x+x+x=100013 23 33x+x+x=1100x+x+x=120015 25 35、七>0(/=1,2,3;j=1,2,3,4,5)运用excel进行线性规划求解可以很快得出使用轮船到达各市场的木材公司最低的运输单位成本的最优值，如下表7：表7使用轮船运输最低的运输单位成本的最优值运输量12345总产量1090006000150025000100050002000330000012001500总需求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重新所选择的单位成本单位成本12345163.5455558.568.3256554965.374.83476358.85961.3目标函数:c=63.5+45c+55t+58.5+68.3+5&+55c+49c+65.3+74.8+47t+6X+58.8+5贝+61.XTOC\o"1-5"\h\z11 12 13 14 15 21 22 23 24 25 31 32 33 34 35'63.5x+45x+55x+58.5x+68.3x<150011 12 13 14 1556x+55x+49x+65.3x+74.8x<200021 22 23 24 2547x+63x+58.5x+59x+61.3x<150031 32 33 34 35x+x+x=800约束条件:<x+x+x=900约束条件:x+x+x=100013 23 33x+x+x=1100x+x+x=120015 25 35、气.>0(/=1,2,3;j=1,2,3,4,5)运用excel进行线性规划求解可以很快得出使用方案3最低的运输单位成本的最优值，如表9：表9方案3最低的运输单位成本的最优值运输量12345总产量1090006000150025000100050002000330000012001500总需求800900100011001200由此可知，根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材，最低的运输成本为27291万元。资源区1到市场2的运输量为900万米，资源区1到市场4的运输量为600万米，资源区2到市场1的运输量为500万米，资源区2到市场3的运输量为1000万米，资源区2到市场4的运输量为500万米，资源区3到市场1的运输量为300万米，资源区3到市场5的运输量为1200万米。比较以上三种方案，方案1的继续使用火车来运输木材，最低的运输成本为28160万元。方案2的仅使用轮船来运输木材（只能使用火车的地方除外），最低的运输成本为27708万元。方案3的根据在每一条特定地路线上哪种