运输问题模型

《运输问题模型》由会员分享，可在线阅读，更多相关《运输问题模型（54页珍藏版）》请在金锄头文库上搜索。

1、 运输问题运输问题 摘要 运输问题是运筹学的一个分支，是线性规划的特殊形式。它研究的是如 何在一个大宗物资调运中，制定出一个由若干个产地将物资根据已知的运 输交通网运到各个销售地的方案，使得总运费最小。物流是整个物流活动 中核心，运输管理是物流活动的统筹规划和管理的一重要部分，对运输环 节进行规划和优化，对提高物流活动的运行效率有重要意义。 本文通过对运输问题模型和求解方法的研究，在产销平衡的条件下，运 用不同的软件 Excel、Lingo、和 Matlab 等对运输问题进行求解，同时对内 点法求解运输问题进行了研究，最终在计算机上得以实现。通过研究得出 结果如下： （1）三个软件 Excel

2、、Lingo 和 Matlab 在求解简单的运输问题，其结果 表上作业法求解的结果是一样的。 （2）在进行比较复杂的运输问题求解时，Excel 出现可变单元格过多而 无法进行继续求解，而 Lingo 和 Matlab 的求解结果相同，在时间耗费上差 异不大，在内存占用上 Matlab 比 Lingo 的大。 （3）根据内点法的原理和方法进行研究，编写出对运输问题进行求解 的代码，并实现求解。 关键词：运输问题 表上作业法 Excel Lingo Matlab 内点法 I Study on the Solution and Practice of the Model of Logistics T

3、ransportion Problem Abstract Transportion problem is a branch of Operations Research，it is a special form of linear programming. It researchs how to build a program that in a bulk material dispatching to delivered all these materials based on the known traffic network to all sales from a number of p

4、roducer, bringing the total freight minimum. Logistics is the core of the logistics activities, transportation management is an important part of overall planning and management in the logistics activities. Planning and management the transport link is very important for improving the efficiency of

5、logistics activities. Based on the study of the transportion model and its solution, under the conditions of production and marketing balance, used different software such as Excel, Lingo, Matlab and so on to solve the transportion problem, and also studied the solving of the transportion problem by

6、 using the internal point method, and eventually can be achieved in the computer. Through the results of the study are as follows: (1)Threesoftware, Excel, Lingo, and Matlab in solving a simple transportation problems, the result and result of suing Tabular method were the same. (2) When solved the

7、more complex transportation problem, Excel appears too much variable to solve, however the results of using Lingo and Matlab is the same, and little difference in time spenting and in the memory footprint Matlab is larger than the Lingo . (3) Based on the study of the principles and methods of inter

8、ior point method, to write a program to solve the transportion problem. II Keywords: The Transportation Problems Tabular Method Excel Lingo Matlab Interior Point Method 目录 第一章 绪 论.1 1.1 课题的来源.1 1.2 本课题的实现目标.1 1.3 运输问题的发展现状及研究意义.2 1.4 本课题的主要工作.3 第二章 线性规划与运输问题.4 2.1 线性规划.4 2.2 运输问题.5 第三章 运输问题求解实践.8 3.

9、1 单纯形法.8 3.2 表上作业法.8 3.3 工具求解实践.14 3.4 小结.21 第四章 大型运输问题案例求解与运输问题的应用.22 4.1 大型运输问题实例.22 4.2 运输问题的应用.27 第五章 内点法.31 5.1 运输问题的内点算法.31 5.2 牛顿法.32 5.3 中心路径和终止条件.33 5.4 运输问题的内点算法实现.34 第六章 总 结.40 6.1 结论.40 6.2 展望.40 参考文献.42 附 表.43 致 谢.49 0 第一章 绪论 1.1 课题的来源 运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问 题：在大宗物资调运时，有若干个产地，根据

10、已知的运输交通网，如何制 定一个运输方案，将这些物资运到各个销售地，使得总运费最小。物流管 理的本质要求就是求实效，即以最少的消耗，实现最优的服务，达到最佳 的经济效益。搞好物流管理，可以通过合理的运输方案，使中间装卸搬运、 储存费用降低、损失减少，在其他条件不变的情况下，降低物流成本就意 味着扩大了企业的利润空间，提高了利润水平，所以一个合理的运输方案 有着重要的意义。 运输问题模型提出后，人们对其求解的方法进行了大量的研究，并有 了重大成果，其中，Danzig 的表上作业法是最简单和最常用的，表上作业 法本质就是单纯形法，虽然表上作业法是最简单的，但是在求解的过程中 还是会耗费大量的时间，

11、在讲究高速高效的现代生活中显然是要被淘汰的， 随着计算机技术的发展和普及，人们把运输问题的求解依赖于计算机求解， 于是产生了大量求解运输问题的软件和工具，如 Excel、Lingo、和 Matlab 等。在众多的求解方法和求解工具中，总会有各自的优缺点，所以寻求一 个好中更好的求解工具，提高求解效率和可扩展性将会有很重要的意义。 1.2 本课题的实现目标 本课题通过研究运输问题在不同软件上的实现，首先进行小规模的运 输问题实践，对在不同的软件中求解的难易程度、耗时耗力，以及所求解 的结果的准确性进行比较分析，由于模型的规模较小，所以在求解过程中 其效果不是很明显，故为了提高说服力，对一个比较大

12、型的运输问题进行 求解，分析其差异性，寻找出各个软件的优异性，为在实践中提供一个依 据。最后把运输问题运用内点法在计算机上进行求解，将其结果与单纯形 法求解的效果进行比较分析。 1 1.3 运输问题的发展现状及研究意义 运输问题是运筹学的一个分支，它研究的是如何在一个大宗物资调运 中，制定出一个由若干个产地，将这些物资根据已知的运输交通网运到各 个销售地的方案，使得总运费最小。运输问题是在 1941 年美国学者希奇柯 克（Hitchcock）在研究生产组织和铁路运输方面的线性规划问题时提出的1。 运输问题的提出，不仅可以求出物资的合理调运方案，其他类型的问题也 都可以经过变换后转为运输问题来进

13、行求解。 运输问题自提出以来，人们对其解法进行了大量的研究： 从目标函数的角度，运输问题同时考虑运输总费用最小、运输过程中 损坏率最低和单位运价变化的调整等多个目标，所以有宋叶新、陈绵云和 吴晓平研究的具有模糊信息的目标运输问题求解2、李珍萍研究的最短时限 运输问题 3、带瓶颈限制的运输问题、运用禁忌搜索算法解决带固定费用 的运输问题、调整单位运价使得运输计划最优的运输问题的逆问题等等。 从算法角度来看，人们对运输问题提出了大量算法，如表上作业法、 图上求解法、遗传算法4,5、神经网络算法6、减运价算法、仿真优化法、 内点法等等。 从计算机求解角度来看，目前已经有很多对运用计算机求解运输问题

14、的研究，如运输问题的计算机求解7，8 、Excel 求解运输问题9 、Lingo 求 解运输问题10 、Matlab 求解11。此外，还有其他软件也可以求解运输问题， 比如运筹学 CAI 软件，不过功能比较少，Winqsb 等等，现实中运用比较广 泛的是 Lingo 和 Matlab。 运输问题是社会经济生活中经常出现的优化问题，我们经常碰到物资 调运如煤、粮食、钢材、木材等，这些都是大宗型的运输，在物流流通中 通过合理的运输方案，使中间装卸搬运、储存费用降低、损失减少，以最 少的消耗，实现经济效益最大化，所以一个合理的科学的运输方案有着重 要的意义。在众多的求解方法和求解工具中，总会有各自的

15、优缺点，所以 寻求一个好中更好的求解工具，提高求解效率和可扩展性将会有很重要的 意义。 同时，在现实生活中，许多问题都可以转化成运输问题数学模型进行 求解，所以研究运输问题也等于研究了很多相关的问题，其意义更明显。 2 1.4 本课题的主要工作 本课题通过对物流运输问题模型的分析，探讨其求解方法，并进行实 际操作，分析比较运输问题的手工求解和工具求解两类方法的具体求解过 程中的差异。并以广西某化肥厂的比较大型的物流运输问题作为对象，使 用工具对其进行求解，得出一个最佳方案。同时尝试采用内点法对运输问 题进行求解，同时总结了运输问题的应用方向。 论文的第二章主要是介绍了运输问题的一些基本情况，包

16、括 LP 模型， 运输问题的模型。第三章中分别讲述了运输问题的手工求解和工具求解的 方法步骤，并将其结果进行分析比较。第四章介绍了不同工具求解的方法 在比较大型的运输问题广西某化肥厂的运输问题案例的实现，对其结 果进行分析，并归纳总结了运输问题的应用方向。第五章介绍了内点法求 解运输问题的原理和算法，和对实例实现求解，最后对论文的工作进行了 总结。 3 第二章 线性规划与运输问题 2.1 线性规划 线性规划（LP）问题，就是求出在一个凸多面体上求出线性目标函数 的最小值。线性规划问题的标准形式为： 0, . . max 21 2211 22222121 11212111 2211 n mnmnmm nn nn nn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcz （2.1） 最早提出线性规划想法的是法国数学家 J.-B.-J.傅里叶和 C.瓦莱-普森， 分别于 1832 年和 1911 年独立提出的，但是那时并未引起