运筹学本科论文材料.doc

《运筹学本科论文材料.doc》由会员分享，可在线阅读，更多相关《运筹学本科论文材料.doc（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-/毕 业 设 计（论 文）论文(设计)题目：运筹学在运输问题中的应用 姓 名 ￥ 学 院 ￥学院 专 业 ￥ 年 级 ￥级 指导教师 ￥ 2013年 5 月 23 日-/目录摘要1正文31、前言31.1论文研究的背景与意义31.2运筹学在运输问题中的现状41.3本文的主要工作及结构安排42、预备知识52.1运筹学的基本问题及概念52.11运筹学简介：52.12 线性规划问题62.13多阶段决策问题72.14动态规划的最优化原理72.2几种常见的运输物流问题72.21最短路问题72.22产销平衡的运输问题82.23产销不平衡的运输问题82.3解决运输问题的几种方法92.31最小元素法92.32

2、伏格尔方法（Vogel）92.33表上作业法103、经典运输问题中运筹学的应用103.1最短路问题103.11提出问题103.12分析问题103.13解决问题113.2产销平衡的运输问题133.21提出问题133.22分析问题133.23解决问题143.24结果分析：234、总结与反思24参考文献：25附录26摘要 运筹帷幄之中，决胜千里之外。运筹学作为一种科学决策的方法，早在孙子兵法中其思想和方法就被古人实施运用。在运输问题领域里，可以运用运筹学的知识，通过分析、计算得出最优的方案，以提高运输效率，节约运输成本，为运输企业和整个社会创造更高的经济效益。随着社会的发展和人们生活水平的提高，运输

3、路线越来越复杂、运输企业也越来越多，在资源和人员有限的情况下，进行资源的优化配置和人员的合理分工,显得越来越重要。本文将从理论知识和实际应用这两大方面，对运输方案的优化进行全面、系统的解析，力求能让更多的人了解运筹学，应用运筹学，在提高企业效益的基础上，为运筹学的发展壮大尽一份力。关键词：运筹学 运输问题 方法 案例 最优路径 Abstract Devised strategies, winning the thousands of miles away.Operations research as a scientific decision-making methods, its ideas

4、 and methods have been used as early as in the Art of War by the ancients. Operations Research has been widely applied in the field of transport issues. In the field of transportation problems, using the knowledge of operations research , through the analysis, the calculation can be drawn optimal so

5、lution or a better solution than the previous program, so as to improve transport efficiency, saving transport costs, and create an economic benefits for both transport enterprises and the whole society. With the development of society and the improvement of peoples living standards, the transport r

6、outes are becoming longer than before and more complex,.More and more enterprises enter the field of transport，and the competition in the field of transport are becoming more and more fierce . In order to enhance the competitiveness ，how to optimize the allocation of limited resources and arrange st

7、aff reasonably are becoming more and more important.This article will analysis and optimize the transport program from the theory and practical application. I strive to make more people understand and apply operations research,and hope to do something for the development and expansion of operations

8、research under the premise of improving enterprise efficiency. Keyword: Operations Research Transport Issues Method Case Optimal Path正文1、前言1.1论文研究的背景与意义在当今社会，随着经济发展的逐步推进，居民的生活水平逐步提高，对物资的要求也越来越高，仅仅依靠当地的物资已经不能满足居民的生活要求。运输行业在此背景下逐步发展壮大，随着路途日趋增多、路径日趋复杂、运输领域竞争日趋激烈，如何进行人员分配和资源的优化配置日益重要。因此，在有限的资源和人员的情况下，如何

9、进行资源的优化配置和人员的合理分配，以期获得更大利润、提高自己的竞争力得到越来越多的企业的重视。通过运用运筹学的知识和方法对运输问题进行资源的优化配置和人员的合理分配，不仅可以为企业节省成本，提高效益和利润，还可以节约运输的时间，为广大的消费者带来优惠和便利。1.2运筹学在运输问题中的现状虽然运筹学在实际生活中的作用被更多的人所认知，但是作为一门新兴的学科，运筹学在运输问题中的应用范围还很小。运输公司或因为对运筹学不了解或因为对运筹学能极大地优化资源配置节省成本不相信，许多的运输公司尚未对本公司的资源配置和人员分工进行最优化，我希望通过本论文让更多的运输行业的人认识到应用运筹学能给运输领域带来

10、的经济效益和利益，让更多的运输行业的人能运用运筹学的思想来对资源优化配置和人员合理分工，为社会带来更大的利益和方便。1.3本文的主要工作及结构安排一个好的运输线路必须具有总路线最短、总的运输费用最少、人员的使用最少等特点。所以在本文中主要通过运筹学知识的综合应用，来对运输问题加以优化。本文的主要任务有：1、系统的介绍一下关于优化运输问题的运筹学理论知识，图与子图的介绍、动态规划的理论介绍、2、选取几个比较有代表性的运输问题，运用动态规划和多阶段决策的理论，用递推法、最小元素法、函数空间迭代法等方法，对运输的路线问题进行优化，从而节约成本，获得更大利益。3、总结和展望。说明本文的理论成果和应用成

11、果，并对运筹学在运输问题中的应用的不足和今后的努力方向进行预计。2、预备知识2.1运筹学的基本问题及概念2.11运筹学简介： 运筹学的主要内容一般包含线性规划、非线性规划、整数规划、动态规划、多目标规划、网络分析、排队论、对策论、决策论、存储论、可靠性理论、模型论、投入产出分析等。其中，线性规划、非线性规划、整数规划、动态规划、多目标规划统称为规划论，它们主要解决两方面的问题：一个方面是对已给定的人力、物力和财力，怎样才能发挥他们的最大效益；另一个方面的问题是对于给定的任务，怎样才能用最少的人力、物力和财力去完成它。网络分析主要是研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小

12、费用流问题、最优分派问题以及关键线路图等，特别是计划和安排大型的复杂工程时，网络技术是重要的工具。排队论主要用来解决以下问题：在一些如机器等待修理，船舶等待装卸，顾客等待服务等日常生活中，它们有一个共同的特点，就是如果等待的时间长了，会影响生产任务的完成，或者顾客会自动离去而影响经济效益；如果增加修理工、装卸码头和服务台，固然能解决等待时间长的问题，但是又会蒙受修理工、码头和服务台空闲的损失，如何妥善的处理这些问题就需要用到排队论的理论和方法。对策论是研究具有厉害冲突的各方，如何制定出对自己有利从而战胜对手的斗争策略。例如：战国时代田忌赛马的故事便是对策论的一个经典例子。凡属“举棋不定”的事情

13、都需要必须做出决策。人们之所以举棋不定，是因为人们在着手实现某个预期目标时，面前出现了多种情况，又有多种行动方案可供选择，决策者如何从中选择一个最优方案，才能达到最优目标，这便是决策论的任务。人们在生产和消费的过程中，都必须储备一定数量的原材料、半成品或商品，储存少了会因为停工待料或失去销售机会而遭受损失，存储多了又会造成资金积压，原材料及商品的损耗。因此，如何确定合理的存储量、购买批量和购货周期至关重要，这边是存储论需要解决的问题。2.12 线性规划问题 线性规划是运筹学的一个基本分支，其应用极其广泛。在各类经济生活中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组

14、织或计划，合理安排人力、物力资源，组织生产过程，使总的效益最好。这样的问题常常可以化为或近似的化成所谓的“线性规划（Linear Programming，简记为LP）”问题。线性规划问题的一般形式为 其中，为待定的决策变量 已知的系数组成的矩阵 称为约束矩阵；称为目标函数，记为；称一个满足所有约束条件的向量为线性规划问题的可行解或可行点，所有的可行点组成的集合称为线性规划问题的可行域，记为D.任意给定一个线性规划问题，下列三种情况必居其一：（1） 可行域D为空集，则称该问题无解或者不可行；（2） 可行域D不为空集，但目标函数在D上无界，此时称该问题无界；（3） 可行域D不为空集，且目标函数有有

15、限的最优值，此时称该问题有最优解。2.13多阶段决策问题 在实践中许多决策问题都与时间有关系，决策过程分成若干阶段，各阶段的决策相互关联，共同决定最终的目标。具体描述：有一个系统，可以分成若干个阶段，任意一阶段k，系统的状态可以使用表示（可以是数量、向量、集合等）。在每一个阶段k的每一个状态都有一个决策集合，在中选定一个决策，状态就转移到新的状态，并且得到效益。我们的目的就是在每一个阶段都在他的决策集合中选择一个决策，使所有的阶段的总效益到达最优。2.14动态规划的最优化原理一个过程的最优策略具有这样的性质，即无论其初始状态以及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态

16、而言，必须构成最优策略。通俗一点讲，就是任意给定一个决策序列（或称为策略），如果是最优的，那么从任何最后k阶段开始，对由这个策略形成的后面k阶段的初始状态组成的k阶段问题而言，这个策略的后面k个决策一定是这个k阶段问题的最优策略，与这k阶段之前的决策无关。2.2几种常见的运输物流问题2.21最短路问题 从某地出发，途径若干中间点最后到达目的地，要求找出路程或费用最小的路线，根据途径中间点的情况最短路问题可分成两类：（1）每个路线包含的边数相等；（2）不同路线包含的边数不一定相等。2.22产销平衡的运输问题 一种产品有产地它们分别的产量为销售地有，它们分别的销量为,其中和满足关系，产品从运送到的

17、费用为,根据约束条件，如何分配运输才能使得运费最省。2.23产销不平衡的运输问题 所有能模式化为产量与销量不相等的一类运输问题。具体可描述为有一种产品有产地它们分别的产量为，销售地有，它们分别的销量为,其中和满足关系，产品从运到的单位费用为,根据约束条件，如何分配运输才能使得运费最省。产销不平衡的问题可以分为两类：（1）对于“产量销量”的情形：产量盈余，可虚拟一个销售地（库存），让多余的产量均运到这个销售地，则该地的销售量=“产量-销量”，同时令该虚拟的销售地的单位运价为0；（虚拟的销地）（2）对于“销量产量”，可虚拟一个产地，让其产量=“销量-产量”，同时令该虚拟的产地的单位运价为0. 解决

18、这两类产销不平衡问题的核心方法：通过添加一个销售地或者产地，将产销不平衡转换为产销平衡的情形，然后由产销平衡问题中的表上作业法进行求解。解答运输问题的几种方法：2.3解决运输问题的几种方法2.31最小元素法 最小元素法主要用来确定初始基可行解，主要步骤如下：步骤一：确定第一个基变量（1） 从单位运价表中，找出最小运价；（2） 对于最小运价处，用所在行的产量最大限度满足销售量（所在列）的需求。将满足之数填入产销平衡表中相应的位置处；（3）观察产和销的关系：1）如果产量用完，则划去所在行的单位运价信息；2）如果销量得到满足，则划去所在列的单位运价信息。步骤二：确定第二个基变量方法：在剩下的单位运价

19、信息中，寻找最小值。并重复上述操作步骤三：按照上述步骤的方法进行操作，直到所有的运价都运算完。得到最优的方案。2.32伏格尔方法（Vogel） 伏格尔法主要用于确定初始基可行解，主要步骤如下：步骤一：计算单位运价表中同行、同列的最小运费与次小运费之差，分别列在单位运价表的最右列和最下行（行差和列差）。 步骤二：对行差和列差进行对比，找出最大差额。以与最大差额值同行（或同列）的最小运价为准，倾所在行的产量，最大限度地满足所在列的需求；一旦需求（或库存）被彻底满足（或库存调光），则随即划去该列（或行）的所有运价信息。（注意产量和销量的变化）步骤三：重新计算同行同列的最小运费与次小运费之差，并对其它

20、未被确定调拨值的行列，重复第二步的处理，直至构造出某初始调拨方案（初始解）。2.33表上作业法 表上作业法是求解运输问题的一种简便而有效的方法，求解过程在运输表上进行，这是一种迭代求解法，迭代步骤为：步骤一：按某种规则找出一个初始基可行解。步骤二：对进行解作最有判断，即求个非基变量的检验数，判别是否达到最优解。如果已经是最优解，则停止计算；如果不是最优解，则进行下一步骤。步骤三：在表上对初始方案进行改进，找出新的基可行解，再按照步骤二进行判别，直至找出最优解。3、经典运输问题中运筹学的应用3.1最短路问题3.11提出问题 在下图中，从A点铺设一条煤气管道到E点，求最短路线和最短路程 B1 4D

21、1 2 3 3 3 C1 5 A 2 1 1 2 B2 3 D2 E 1 1 4 3 C2 5 B3 5 2D33.12分析问题根据途径中间点的情况，这个问题是每个路线包含的边数相等的一类问题；从A到E需要经过三个中间站，第一站可以从,中选择，类似地，第二站、第三站分别可以在,和中选择。相连的两点间的距离已经给定，找一条从A到E的管道路线问题与确定三个中间站的位置本质上是一样的，当三个中间站的位置都确定了，一条从A到E的路线也就确定了。因此可以将此问题分成三个阶段，每个阶段确定一个中间站的位置，最终选择的路径由三个阶段的决策共同决定。3.13解决问题 用递推法解最短路径问题。由上图可知，求从A

22、到E的最短路径的第一步要么到，要么到，要么到，然后由（或或）到E，而且必沿着（或或）到E的最短路走。因而若知道、和到E的最短路，分别加上，就得到了三条从A到E的路，其中小的就是从A到E的最短路。从A到E有四条边，所以记从A到E的最短路长度为；从到E有三条边，所以记从到E的最短路长度为；从到E有三条边，所以记从到E的最短路长度为；从到E有三条边，所以记从到E的最短路长度为.由分析可知： ； 记从到E的最短路长度为； 记从到E的最短路长度为；因此同理以此类推；显然，从、到E的最短路如下其中表示从i点经过k条边到E的最短路长度。由于 和已知，所以即从到E的最短路程为5，最短路线为 E同理有 即从到E

23、的最短路程为4，最短路线为 E即从到E的最短路程为7，最短路线为 E即从到E的最短路程为6，最短路线为E即从到E的最短路程为9，最短路线 E即从A到E的最短路程为8，最短路线A E 3.2产销平衡的运输问题3.21提出问题 潍坊潍柴动力集团在分别在开发区、潍城区、坊子区三地设有生产点，它们的产量分别为40,20,40个单位产品，潍柴在奎文区、寿光、青州、安丘、临朐五地有零售商店， 它们需要的产品数量为25,10,20,30,15个单位产品，试建立运费最省的调运方案的数学模型。产品从产地运到销售地的每单位装运费表如下：表1-1奎文区寿光青州安丘临朐开发区7525405045潍城区35601008

24、070坊子区75669560303.22分析问题 如题目的描述，产量为40+20+40=100，销量为25+10+20+30+15=100，说明此题为产销平衡的运输问题，产销平衡的运输问题是运输问题中非常常见的一类问题。这个问题一方面要求满足奎文区、寿光、青州、安丘、临朐5个销售地的供货需求，而另一方面又要考虑开发区、潍城区、坊子区三个产地的运往销售地的运输费用，所以不但要求满足销售地分配需求，同时也要保证最大化的减少运输费用。这里选择何种分配方案，将涉及不同的运输费用，所以其是一个典型的线性规划问题，同时也是一个产销平衡运输问题。根据题目已知可以得出以下图论：奎文区寿光开发区青州潍城区坊子区

25、 安丘临朐3.23解决问题 建立模型：假设某物品有m个产地 ，各产地的产量是；有n个销地，各销售地销量分别为；假定从产地（i=1,2，m）向销售地（j=1，2，n）运价单位物品的运价是，问怎样调运这些物品才能使运费最少？ 设 为从产地运往销地的运输量，若各产地产量之和等于各销地销量之和，即有： 则得到下列产销平衡运输量问题的模型： 基本假设：针对题中的运输问题，为了方便计算，可以设开发区（），潍城区（）和坊子区（）分别销往奎文区（）、寿光（）、青州（）和安丘（）和临朐()五个城市销售量从运往的单位装运费如下表:表：1-27525405045356010080707565956030目标 最少费

26、用：约束条件： 1、供应限制 2、指标约束 定义符号说明：分别代表开发区、潍城区、坊子区三个生产点；分别代表奎文区、寿光、青州、安丘、临朐五个销售地。为从产地（i=1,2,3）向销售地（j=1,2,3,4,5）单位物品的装运价格， 为从产地（i=1,2,3）运往销售地（j=1,2,3,4,5）的运输量。Z即为整个运输过程中涉及的运输费用。min z则为整个运输问题中的最小运输费用。解题方法:最小元素法：是找出运价表中最小的元素，然后在运量表内对应的格填入允许取得的最大数值，若某行或者某列的产量或者销量已得到满足，则把运价表中该运价所在行或者列划去；找出未划去的运价中的最小数值，按此办法依次进行

27、下去，直至得到一个基本可行解的方法。表上作业法：是求解运输问题的一种简便而有效的方法，求解过程在运输表上进行，这是一种迭代求解法，迭代步骤为：步骤一：按某种规则找出一个初始基可行解。步骤二：对进行解作最有判断，即求个非基变量的检验数，判别是否达到最优解。如果已经是最优解，则停止计算；如果不是最优解，则进行下一步骤。步骤三：在表上对初始方案进行改进，找出新的基可行解，再按照步骤二进行判别，直至找出最优解。表上作业法具体求解如下：首先任意找出一个可行解，如下表：表：1-3：-3070产量2040 40451530201025销量56025950650751008051000600351510010

28、50040202575步骤一：从表1-2中找出最小装运价为25，位于（，）处。故优先考虑此项，由于产地的产量40大于销售地的销量10（4010），故在新建的运输量表1-4中的（，）位置应填10，表1-4产量10402040销量2510203015-而后销售地的销售量已经饱和，故在装运价格表1-2中划去列后，得新的装运费表格如下表表：1-57540504535100807075956030步骤二：从表1-5中找出最小运价为30，位于（，）处。故优先考虑此项。由于产地的产量40大于销售地的销量15（4015），故在运量表表1-4的（，）处填上15，得新的运输量的表格表1-6产量1040201540

29、销量2510203015-由于销售地的销量已经饱和，故划去装运价格表1-5中的列后，得新的装运价格表如下表1-7。7540503510080759560步骤三：从表1-7中找出最小运价为（，）处的35，所以优先考虑此项由于产地的产量20小于销售地的销量（2025），故在表运输量表1-6的（，）处填上20，得新的运输量表如下表1-8产量104020201540销量2510203015-由于产地的产量已经饱和，故划去表1-7中行，得新的装运价格表如下表1-9754050759560步骤四：从表1-9中找出最小装运价为40，位于（，）处，所以优先考虑此项，由于产地剩余产量30（40-10）大于销售地

30、的销售量20，故在表1-8的（，）位置应填上20，得新的运输量表如下表1-10产量10204020201540销量2510203015-由上表可以看出，由于销售地的销售量已经饱和，故从表1-9中划去行，得新的装运价格表如下表：1-1175507560步骤五：从表1-11中找出最小运价为50，位于（，）位置处，所以优先考虑此项。由于产地的剩余产量10（40-10-20）小于销售地的销售量30，故在运输量表1-10的（，）位置填上10，得新的运输量表格如下表1-12产量1020104020201540销量2510203015-由于产地的产量已经饱和，故从表1-11中划去行，得新的装运价格表如下表1

31、-137560步骤六：从表1-13中找出最小运价为60，位于（，）位置处。所以优先考虑此项，由于产地的剩余产量25（40-15）大于销售地的剩余销售量20（30-10），故在运输量表1-12中的（，）位置应填上20，得新的运输量表格如下表1-14产量102010402020201540销量2510203015-由于销售地的销售量已经饱和，所以从表1-13中划去列，得新的装运费表如下表1-1575步骤七：现在只剩下一个位置，且产地的剩余产量5（40-15-20）等于销售地的销售量5（25-20），所以在运输量表1-14中的（,）位置填上5，此时行和列均已饱和，在其余空格位置均填上0，得最终的运输

32、表格如下表1-16产量010201004020000020500201540销量2510203015-经以上步骤得到一个产销平衡且销量全部满足的调配方案。经过计算，空格的检验数均大于零，最优方案为：最小费用为：Lingo求解程序model:sets:origin/1.3/:a;sale/1.5/:b;routes(origin,sale):c,x;endsetsdata:a=40,20,40;b=25,10,20,30,15;c=75,25,40,50,45,35,60,100,80,70,75,65,95,60,30;enddataOBJmin=sum(routes:c*x);for(ori

33、gin(i):SUPsum(sale(j):x(i,j)=a(i);for(sale(j):DEMsum(origin(i):x(i,j)=b(j);EndLingo运行结果： Global optimal solution found. Objective value: 4275.000 Total solver iterations: 0 Variable Value Reduced Cost A( 1) 40.00000 0.000000 A( 2) 20.00000 0.000000 A( 3) 40.00000 0.000000 B( 1) 25.00000 0.000000 B(

34、2) 10.00000 0.000000 B( 3) 20.00000 0.000000 B( 4) 30.00000 0.000000 B( 5) 15.00000 0.000000 C( 1, 1) 75.00000 0.000000 C( 1, 2) 25.00000 0.000000 C( 1, 3) 40.00000 0.000000 C( 1, 4) 50.00000 0.000000 C( 1, 5) 45.00000 0.000000 C( 2, 1) 35.00000 0.000000 C( 2, 2) 60.00000 0.000000 C( 2, 3) 100.0000

35、0.000000 C( 2, 4) 80.00000 0.000000 C( 2, 5) 70.00000 0.000000 C( 3, 1) 75.00000 0.000000 C( 3, 2) 65.00000 0.000000 C( 3, 3) 95.00000 0.000000 C( 3, 4) 60.00000 0.000000 C( 3, 5) 30.00000 0.000000 X( 1, 1) 0.000000 10.00000 X( 1, 2) 10.00000 0.000000 X( 1, 3) 20.00000 0.000000 X( 1, 4) 10.00000 0.0

36、00000 X( 1, 5) 0.000000 25.00000 X( 2, 1) 20.00000 0.000000 X( 2, 2) 0.000000 65.00000 X( 2, 3) 0.000000 90.00000 X( 2, 4) 0.000000 60.00000 X( 2, 5) 0.000000 80.00000 X( 3, 1) 5.000000 0.000000 X( 3, 2) 0.000000 30.00000 X( 3, 3) 0.000000 45.00000 X( 3, 4) 20.00000 0.000000 X( 3, 5) 15.00000 0.000000 Row Slack or Surplus Dual Price OBJ 4275.000 -1.000000 SUP( 1) 0.000000 10.00000