运筹学在运输问题中的应用.doc

1、毕 业 设 计（论 文）论文(设计)题目：运筹学在运输问题中的应用姓 名 ￥ 学 院 ￥学院 专 业 ￥ 年 级 ￥级 指导教师 ￥ 20XX 年 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

2、 产销平衡的运输问题 .82.23 产销不平衡的运输问题 .82.3 解决运输问题的几种方法 .92.31 最小元素法 .92.32 伏格尔方法（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本科毕业生论文 运筹学在运输问题中的应用 第 1 页 共 37 页摘要运筹

3、帷幄之中，决胜千里之外。运筹学作为一种科学决策的方法，早在孙子兵法中其思想和方法就被古人实施运用。在运输问题领域里，可以运用运筹学的知识，通过分析、计算得出最优的方案，以提高运输效率，节约运输成本，为运输企业和整个社会创造更高的经济效益。随着社会的发展和人们生活水平的提高，运输路线越来越复杂、运输企业也越来越多，在资源和人员有限的情况下，进行资源的优化配置和人员的合理分工,显得越来越重要。本文将从理论知识和实际应用这两大方面，对运输方案的优化进行全面、系统的解析，力求能让更多的人了解运筹学，应用运筹学，在提高企业效益的基础上，为运筹学的发展壮大尽一份力。关键词：运筹学 运输问题 方法 案例 最

4、优路径本科毕业生论文 运筹学在运输问题中的应用 第 2 页 共 37 页Abstract Devised strategies, winning the thousands of miles away.Operations research as a scientific decision-making methods, its ideas and methods have been used as early as in the “Art of War“ by the ancients. Operations Research has been widely applied in the f

5、ield of transport issues. In the field of transportation problems, using the knowledge of operations research , through the analysis, the calculation can be drawn optimal solution or a better solution than the previous program, so as to improve transport efficiency, saving transport costs, and creat

6、e 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 routes are becoming longer than before and more complex,.More and more enterprises enter the field of transport，and the competiti

7、on 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 staff reasonably are becoming more and more important.This article will analysis and optimize the transport program from the theor

8、y 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 research under the premise of improving enterprise efficiency. Keyword: Operations Research Transport Issues Method Case Optimal

9、 Path本科毕业生论文 运筹学在运输问题中的应用 第 3 页 共 37 页正文1、前言1.1 论文研究的背景与意义在当今社会，随着经济发展的逐步推进，居民的生活水平逐步提高，对物资的要求也越来越高，仅仅依靠当地的物资已经不能满足居民的生活要求。运输行业在此背景下逐步发展壮大，随着路途日趋增多、路径日趋复杂、运输领域竞争日趋激烈，如何进行人员分配和资源的优化配置日益重要。因此，在有限的资源和人员的情况下，如何进行资源的优化配置和人员的合理分配，以期获得更大利润、提高自己的竞争力得到越来越多的企业的重视。通过运用运筹学的知识和方法对运输问题进行资源的优化配置和人员的合理分配，不仅可以为企业节省成

10、本，提高效益和利润，还可以节约运输的时间，为广大的消费者带来优惠和便利。1.2 运筹学在运输问题中的现状虽然运筹学在实际生活中的作用被更多的人所认知，但是作为一门新兴的学科，运筹学在运输问题中的应用范围还很小。运输公司或因为对运筹学不了解或因为对运筹学能极大地优化资源配置节省成本不相信，许多的运输公司尚未对本公司的资源配置和人员分工进行最优化，我希望通过本论文让更多的运输行业的人认识到应用运筹学能给运输领域带来的经济效益和利益，让更多的运输行业的人能运用运筹学的思想来对资源优化配置和人员合理分工，为社会带来更大的利益和方便。1.3 本文的主要工作及结构安排一个好的运输线路必须具有总路线最短、总

11、的运输费用最少、人员的使用最少等特点。所以在本文中主要通过运筹学知识的综合应用，来对运输问题加本科毕业生论文 运筹学在运输问题中的应用 第 4 页 共 37 页以优化。本文的主要任务有：1、系统的介绍一下关于优化运输问题的运筹学理论知识，图与子图的介绍、动态规划的理论介绍、2、选取几个比较有代表性的运输问题，运用动态规划和多阶段决策的理论，用递推法、最小元素法、函数空间迭代法等方法，对运输的路线问题进行优化，从而节约成本，获得更大利益。3、总结和展望。说明本文的理论成果和应用成果，并对运筹学在运输问题中的应用的不足和今后的努力方向进行预计。2、预备知识2.1 运筹学的基本问题及概念2.11 运

12、筹学简介：运筹学的主要内容一般包含线性规划、非线性规划、整数规划、动态规划、多目标规划、网络分析、排队论、对策论、决策论、存储论、可靠性理论、模型论、投入产出分析等。其中，线性规划、非线性规划、整数规划、动态规划、多目标规划统称为规划论，它们主要解决两方面的问题：一个方面是对已给定的人力、物力和财力，怎样才能发挥他们的最大效益；另一个方面的问题是对于给定的任务，怎样才能用最少的人力、物力和财力去完成它。网络分析主要是研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小费用流问题、最优分派问题以及关键线路图等，特别是计划和安排大型的复杂工程时，网络技术是重要的工具。排队论主要用来解决

13、以下问题：在一些如机器等待修理，船舶等待装卸，顾客等待服务等日常生活中，它们有一个共同的特点，就是如果等待的时间长了，会影响生产任务的完成，或者顾客会自动离去而影响经济效益；如果增加修理工、装卸码头和服务台，固然能解决等待时间长的问题，但是又会蒙受修理工、码头和服务台空闲的损失，如何妥善的处理这些问题就需要用到排队论本科毕业生论文 运筹学在运输问题中的应用 第 5 页 共 37 页的理论和方法。对策论是研究具有厉害冲突的各方，如何制定出对自己有利从而战胜对手的斗争策略。例如：战国时代田忌赛马的故事便是对策论的一个经典例子。凡属“举棋不定”的事情都需要必须做出决策。人们之所以举棋不定，是因为人们

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

15、的效益最好。这样的问题常常可以化为或近似的化成所谓的“线性规划（Linear Programming，简记为 LP） ”问题。线性规划问题的一般形式为nxcxcz.min21nqjx mpibaaj iii ,.1,0,.1,.21其中 ，为待定的决策变量j已知的系数 组成的矩阵ijannnaaaA.212121本科毕业生论文 运筹学在运输问题中的应用 第 6 页 共 37 页称为约束矩阵；称 为目标函数，记为 ；nxcxcz.min21 njijxcz1称一个满足所有约束条件的向量 为线性规划问题的可行解或可行Tnx),.(1点，所有的可行点组成的集合称为线性规划问题的可行域，记为 D.任意

16、给定一个线性规划问题，下列三种情况必居其一：（1）可行域 D 为空集，则称该问题无解或者不可行；（2）可行域 D 不为空集，但目标函数在 D 上无界，此时称该问题无界；（3）可行域 D 不为空集，且目标函数有有限的最优值，此时称该问题有最优解。2.13 多阶段决策问题在实践中许多决策问题都与时间有关系，决策过程分成若干阶段，各阶段的决策相互关联，共同决定最终的目标。具体描述：有一个系统，可以分成若干个阶段，任意一阶段 k，系统的状态可以使用 表示（ 可以是数量、向量、集合等） 。在每一个阶段 k 的每一kxk个状态 都有一个决策集合 ，在 中选定一个决策 ，状kxQkxkqkxQ态 就转移到新

17、的状态 ，并且得到效益 。我们的目的kx1k),(qT),(xR就是在每一个阶段都在他的决策集合中选择一个决策，使所有的阶段的总效益到达最优。kkqR),(2.14 动态规划的最优化原理一个过程的最优策略具有这样的性质，即无论其初始状态以及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。通俗一点讲，就是任意给定一个决策序列（或称为策略） ，如果是最优的，那么从任何最后 k 阶段开始，对由这个策略形成的后面 k 阶段的初始状态组成的 k 阶段问题而言，这个策略的后面 k 个决策一定是这个 k 阶段问题本科毕业生论文 运筹学在运输问题中的应用 第 7 页

18、共 37 页的最优策略，与这 k 阶段之前的决策无关。2.2 几种常见的运输物流问题2.21 最短路问题从某地出发，途径若干中间点最后到达目的地，要求找出路程或费用最小的路线，根据途径中间点的情况最短路问题可分成两类：（1）每个路线包含的边数相等；（2）不同路线包含的边数不一定相等。2.22 产销平衡的运输问题一种产品有产地 它们分别的产量为 销售地有,.21iAia,.21，它们分别的销量为 ,其中 和 满lB,.21 jb.21 ia, jb,.21足关系 ，产品从 运送到 的费用为 ,根据约束条件，如何分配jibaijBjic运输才能使得运费最省。2.23 产销不平衡的运输问题所有能模式

19、化为产量与销量不相等的一类运输问题。具体可描述为有一种产品有产地 它们分别的产量为 ，销售地有,.21kAka,.21，它们分别的销量为 ,其中 和 满lB,.21 jb,.21 ., jb,.21足关系 ，产品从 运到 的单位费用为 ,根据约束条件，如何分jibaijBjic配运输才能使得运费最省。产销不平衡的问题可以分为两类：（1）对于“产量销量”的情形：产量盈余，可虚拟一个销售地（库存） ，让多余的产量均运到这个销售地，则该地的销售量=“产量-销量” ，同时令该虚拟的销售地的单位运价为 0；（虚拟的销地）本科毕业生论文 运筹学在运输问题中的应用 第 8 页 共 37 页（2）对于“销量产

20、量” ，可虚拟一个产地，让其产量=“销量-产量” ，同时令该虚拟的产地的单位运价为 0.解决这两类产销不平衡问题的核心方法：通过添加一个销售地或者产地，将产销不平衡转换为产销平衡的情形，然后由产销平衡问题中的表上作业法进行求解。解答运输问题的几种方法：2.3 解决运输问题的几种方法2.31 最小元素法最小元素法主要用来确定初始基可行解，主要步骤如下：步骤一：确定第一个基变量（1）从单位运价表中，找出最小运价；（2）对于最小运价处，用所在行的产量最大限度满足销售量（所在列）的需求。将满足之数填入产销平衡表中相应的位置处；（3）观察产和销的关系：1）如果产量用完，则划去所在行的单位运价信息；2）如果销量得到满足，则划去所在列的单位运价信息。步骤二：确定第二个基变量方法：在剩下的单位运价信息中，寻找最小值。并重复上述操作步骤三：按照上述步骤的方法进行操作，直到所有的运价都运算完。得到最优的方案。2.32 伏格尔方法（Vogel ）伏格尔法主要用于确定初始基可行解，主要步骤如下：步骤一：计算单位运价表中同行、同列的最小运费与次小运费之差，分别列在单位运价表的最右列和最下行（行差和列差） 。 步骤二：对行差和列差进行对比，找出最大差额。以与最大差额值同行（或同列）的最小运价为准，倾所在行的产量，最大限度地满足所在列的需求；一旦