毕业论文线性规划在垃圾运输问题的应用

学科分类号 110

黑龙江科技大学

本科学生毕业论文

题 目 线性规划在垃圾运输问题的应用 Linear programming is applied in waste transportation problem 姓 名 *** 学 号 2011*** 院 （系） 理学院 专业、年级 数学与应用数学 指导教师 **** 2015年6月12日

摘 要

我们知道,随着市场经济发展迅速，竞争也随之加快。为了能在这激烈的市场竞争中立足，企业都谋取最大的利润，最少的成本也就是最小的费用。企业通过不断的改进，利用各种方式企图使得费用最少。运输问题关心的是以最低的总配送成本把供应中心的任何产品运送到每 一个接收中心。每一个出发地都有一定供应量配送到目的地，每一个目的地都需要一定的需求量。 运输问题(Transportation Problem)是一个典型的线性规划问题。一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案的问题。

本论文运用线性规划的数学模型来解决此运输问题中总费用最小的问题。针对斯特兰运输公司南大西洋办公处的经理雷切尔对于垃圾处理的困惑，对其的三个处理方案进行优化求解，并运用excel电子表格的线性优化来计算各个方案的数学模型。

关键词 最优化 运输问题 线性规划

I

Abstract

As we know, with the market economy has developed rapidly, competition also will speed up. In order to establish oneself in the fierce market competition, enterprises seek maximum profit, the least cost is the minimum cost. Enterprise through continuous improvement, the use of a variety of ways in an attempt to make cost minimum. Transportation problem concerned in the lowest total distribution cost and the supply of any product shipped to each receiving center. Each source has certain supply and distribution to the destination, each destination needs certain demand. Transportation Problem, Transportation Problem) is a typical linear programming Problem. General transportation problem is to solve a product from a number of origin transportation to several Sales site , in each origin of supply and demand for each Sales site known, and know that all the transportation between the unit price under the premise of how to determine a scheme to make the total transportation cost minimum.

In this paper, using the mathematical model of linear programming to solve the transportation problem of minimum total cost. For strenger transport company of south Atlantic office manager Rachel for garbage disposal confusion, three of its treatment scheme optimization solution, and using the excel spreadsheets to calculate the linear optimization mathematical model of each scheme.

Keywords optimization Transportation problem Linear programming

II

目 录

摘 要.......................................................................................................................... I Abstract ...................................................................................................................... II 第1章 绪 论 ........................................................................................................ 1 1.1研究的目的和意义 ......................................................................................... 1 1.2 国内外研究状况 ........................................................................................... 1 1.3 本文的主要工作 ........................................................................................... 5 第2章Excel与线性规划的运输问题 ..................................................................... 6 2.1线性规划............................................................................................................. 6 2.1.1线性规划简介······································································· 6 2.1.2线性规划模型······································································· 6 2.2线性规划与运输问题 ..................................................................................... 7 2.2.1运输问题的基本特征 ····························································· 7 2.2.2运输问题的分类 ··································································· 7 2.3 Excel解决运输问题 .................................................................................... 11 2.3.1软件介绍 ··········································································· 11 2.3.2 运输问题形式 ····································································· 12 2.3.3在excel中的形式 ................................................................................. 12 2.3.4 excel求解步骤 ...................................................................................... 12 第3章 垃圾运输问题 .......................................................................................... 13 3.1问题的提出 ................................................................................................ 13 3.1.1 事例 ················································································· 13 3.1.2对上述问题的几种解决方案 ··················································· 14 3.2实例的分析 ................................................................................................ 15 3.2.1实例的数据分析 .................................................................................... 15 3.2.2对于几种方案的模型建立 ······················································ 15 3.2.3对于几种方案的模型的excel求解 ··········································· 18

待解决问题 ················································· 错误！未定义书签。

结 论 ....................................................................................................................... 25 致 谢 ....................................................................................................................... 26 参考文献................................................................................................................... 27

III

Contents

Abstract ................................................................................. 错误！未定义书签。 Abstract ................................................................................. 错误！未定义书签。 Chapter 1 Introduction ............................................................................................ 1 1.1Research purpose and meaning ...................................................................... 1 1.2 The research status at home and abroad .......................................................... 1 1.3 The main work of this article ........................................................................ 5 Chapter 2 Excel with linear programming transportation question ............................ 6 2.1 Linear programming ........................................................................................... 6 2.1.1 Introduction of linear programming·············································· 6 2.1.2 Linear programming model ······················································· 6 2.2 Linear programming and transportation problem ............................................ 7 2.2.1 The basic characteristics of transportation problem ·························· 7 2.2.2 The classification of the transportation problem ······························ 7 2.3 Excel solve the transportation problem ......................................................... 11 2.3.1 The software is introduced······················································· 11 2.3.2 Form of transportation problem ················································· 12 2.3.3 In the excel form .................................................................................... 12 2.3.4 excel solving steps ................................................................................. 12 Chapter 3 waste transportation problem .................................................................. 13 3.1 raise of problem .......................................................................................... 13 3.1.1 example ··············································································· 13 3.1.2 Several solutions to the problem ··············································· 14 3.2 The analysis of the instance ........................................................................ 15 3.2.1 Example analysis of the data ........................................................ 15 3.2.2 For several solution model is established in this paper ····················· 15 3.2.3 For several kinds of schemes of excel to solve the model ················· 18

待解决问题 ················································· 错误！未定义书签。

conclusions ................................................................................................................ 25 Acknowledgements .................................................................................................. 26 References ................................................................................................................. 27

IV

第1章 绪 论

1.1研究的目的和意义

当前，运输市场具有非常激烈的竞争，每一个企业都为了提高自己的竞争力，寻求一种使产销地之间的供应量以及需求量均达到最优搭配的运输方案，从而增加运输速度、减少运输成本、提高运输可靠性。所以，采用何种运输方式可以保证原材料和成产品的有效运送和及时供给，如何能够将一定数量的产品以最佳的运输方式运送给消费者对企业来说成为一种考验。由于经济和社会的发展的需要，定性定量地回答下列问题，在有关运输问题的决策过程中相当重要：在当前已有的运输条件下，如何分配各种运力和组织货物的合理流动使运输问题达到最佳化；为了使运输系统的整体性能最优，在各运输项目间考虑如何合理分配有限的投资或资源；未来年代，为解决运输需求和运输能力的矛盾，应该按照什么顺序新建、扩建或改建哪些运输项目，等等。运输和转运问题在理论和实际应用上都是非常有意义的一类问题，为了回答上述问题建立了一系列的运输系统的模型。所建立的模型应是科学地从运输活动中抽象出来的，它们可以被公式化应作为线性规划问题求解。

随着我国市场经济的不断完善，同地区、不同地区、甚至跨国间的企业交易活动更加频繁。因此，在运输中如何降低运输费用、减少运输路线等问题，已成为交易活动的重点，而线性规划主要应用于解决最优化问题。本文根据运输问题的基本特征，通过实例对运输问题进行了优化分析，建立了运输问题的线性规划数学模型，并借助于计算机进行求解，从而得到最优化的方案，提高了实际运输工作中的经济效益。日常生活中，人们经常需要将某些物品由一个空间位置移动到另一个空间位置，这就产生了运输，如何判定科学的运输方案，使运输所需的总费用最少，是本文要解决的问题。

1.2 国内外研究状况

运输问题是社会经济生活和军事活动中经常出现的优化问题,是特殊的线性规划问题,它是早期的线性网络最优化的一个例子。最早研究这类问题的Hitchcock以及后来的Koopmans独立地提出运输问题并详细地对该问题加以讨论;同时KaHTop0BH也围绕着运输问题作了大量的研究,因此运输问题义称为

1

Hitchcock问题或Kantorovich问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题.有些其他类型的问题经过适当变换后也可以归结为运输问题,如指派问题、最短路问题、最小费用流题可转化为运输问题或转运问题。 运输问题国外相关文献评述 。

由于运输问题的特殊数学结构，人们很早就意识到通过给出进基变量和离基变量的最优性条件，可以更有效地利用单纯形法对运输问题进行求解。Danzig（1951）提出的单纯形法作为求解运输问题的最初单纯形方法（Primal Simplex Transportation Method，PSTM）。随后Charnes和Cooper（1954）发展了逐级算法（Stepping-Stone Method，SSM），该算法提供了决定单纯形方法信息的可选择途径。除了PSTM与SSM，Adriano和Claudio（1974）给出了求解经典运输问题的一种搜索算法，该算法思想以Balas（1967）过滤算法为基础，最后给出了该运输问题在实际中的应用。Barr（1981）利用增加原有线路指标数据结构，对Kennington和Unger（1976）的算法进行了改进。Cabot and Erenguc （1984，1986）提出原问题的拉格郎日松弛问题，由此可获得条件惩罚函数，但由于缺少有效运输节点，使算法的计算结果并不理想。Dimitri和David（1989）给出求解运输问题的拍卖算法。拍卖算法是一种求解经典指派问题的平行松弛算法。他们将拍卖算法应用于线性运输问题的求解，该算法的思想是将运输问题转化为指派问题，然后修改拍卖算法，使其适用于运输问题的特殊结构。Vignaux和Michalewicz（1991）给出了求解线性运输问题的遗传算法（遗传算法是仿照自然选择的进化过程寻找问题的解），并举例说明了具有代表性的结构之间的关系，研究了遗传算法实现的程序，给出了多种不同结构的运输问题。Kleinschmidt和Schannath（1995）在改进网络流算法的基础上，给出了一般运输问题的网络流算法，算法使用了大量的检测迭代，是一种求解运输问题的强多项式算法。

国外学者从算法角度考虑，对于运输问题的求解提出了很多可行的解法，如表上作业法、图上求解法以及应用计算机实现的启发式多种算法等，其基本上可以总结如下：

表上作业法是解决一般运输问题最常用的解法，因其求解工作均在运输表上进行而得名。它是一种迭代算法，迭代步骤为：先按某种规则找出一个初始解；再对现行解作最优性判别；若该解不是最优解，就在运输表上对它进行调整改进，从而得出一个新解，再重复判别改进的过程，直至得到运输问题的最优解为止。

2

最短路线法。当已知某物资从出发地运往目的地，可有多条运输路线供选择，这时可构造费用网络图，用求最短路线的方法，选择最优的运输方案，需画出各种运输路线的线路图及图上每一条边（或弧）上的距离或费用（也可以用邻接矩阵表示），然后用Dijkstra标号法或邻接矩阵法求最优运输路线。 最小费用最大流是网络最大流问题加上对总费用最小这一约束条件后求最大流问题。其算法是从费用为0的最小费用出发，结合弧费用构造赋权有向图，再利用求最短路算法寻找最小费用增广链对原最小费用流进行调整，重复此过程直至最小费用增广链不存在为止。

随着智能搜索算法的发展，近年来有许多有关解决这类运输问题的人工智能方法的研究，如神经网络算法、禁忌搜索算法、遗传算法等。尤其是遗传算法在解决运输问题方面，已经得到了不错的效果。Michalewicz（1991）等人首先讨论了使用遗传算法来解决线性和非线性运输问题。 运输问题国内相关文献评述

国内学者对于运输问题的研究主要可以分为三个角度：一是在国外算法的基础上，对运输问题算法的改进研究；二是从目标函数的角度，在运输问题中有时要同时考虑运输成本最小、运输过程中货物损坏率最低以及单位运价变化的调整等多个目标；从约束函数的角度，有研究供给量和需求量在某个区间变化的不确定型运输问题、有时间窗口的运输问题等。 （一）算法角度的运输问题评述

臧运华（2002）将运输问题转化为图问题，通过构造赋权二分图G，应用图论理论，给出运输问题一种图上解法。郭强（2004）从基变量判断和寻找闭回路思想出发，提出不同于位势法和闭回路调整的运输问题迭代算法，但算法仍具有传统表上作业法的缺点，先求初始可行解再构造上述三个矩阵进行检测调整。刘徽（2005）讨论了两类运输问题的算法，传统运输问题的算法和受时间约束运输问题的方案及算法。该算法从运输问题可行域的内部出发，沿着中心路径的方向，通过反复迭代寻找运输问题的近似最优解。张美玉、黄翰等（2006）针对实数线性运输问题，提出了一种新型进化算法，在遗传算法的基础上引进了差异进化的思想，设计出具有全局搜索能力的重组算子，重组算子能够从理论上保证约束条件的满足，仿真实例显示了该算法的可行性和有效性。周先东等（2008）设计了基于遗传算法和粒子群优化算法的求解运输问题的GAPSO算法，为避开对非可行解的处理，该算法对迭代过程也进行了特殊设计，从而简化了运用随机搜索算法解决运输问题的过

3

程。

（二）目标函数角度的运输问题评述

自从建立了基本的运输问题模型以来，根据不同的物资调运实际状况建立的运输问题各种扩展模型也层出不穷。根据运输问题优化目标不同，基本上可以将运输问题分为三大类：即以费用最小为目标的费用优化运输问题、以时间最短为目标的时间优化运输问题和两类目标综合最优化的多目标优化运输问题。

费用最优化运输问题模型。此类运输问题模型将运输费用的最小化作为模型的优化目标，目前大多数运输问题模型都属于该类模型的扩展与引申。如变量有限制的运输问题，其在物资收发量约束的基础上还加入了对调运变量的约束；变约束的运输问题将物资收发量确定为某一个变化范围而不是一个确定的值。此外还有带中转点的运输问题、多运输方式综合运输模型等等。 时间最优化运输问题模型。此类运输问题以缩短调运时间为模型的优化目标，从而实现物资的快速运输。迄今为止，围绕解决这类问题已经进行了大量卓有成效的研究。较早的有运筹学的网络最短路模型、生产管理的调度理论和所谓的瓶颈运输问题。时间优化运输问题的特点即整体运输时间最短成为优化的第一目标，这时运用费用优化运输问题模型就难以给出满意的结果。前面所述的费用优化运输问题模型的优化目标为整体运输费用最小，运输费用具有线性叠加特性，或认为具有串联特性，即整体运输费用等于各分段费用的线性叠加；而运输时间则不具有线性叠加特性，因为各供应点的操作可同时或平行进行，整体完成时间并不是各分段时间的线性叠加，而是由各分段时间中的最大值控制，运输时间的这一特点使运输时间的优化具有明显的并联特性。

程桦、宋执环（2003）将物流运输中以时间为第一目标加入到一般运输问题中作为目标，将其分为先后发货即以总运输时间最小为目标和同时发货以各地运输时间最长为目标的两类运输问题，并重点对后者求解给出了算法。白国仲（2007）提出了该类问题的简算法。该算法实则是对传统算法—表上作业法稍作改进，以每次所求最优解中非零变量的单位运价为界，变换单位运价矩阵，重复进行表上作业法进行求解。 （三）约束函数角度的运输问题评述

高峰记等（2002）对于运输问题含有区间数不能完全确定情况，建立了其区间数模型，并引入λ水平将该模型转化为一般运输问题进行求解。谢凡

4

荣（2005）将需求区间型运输问题先转化为运输网络中求最小费用最大流问题，并利用计算机编程程序进行求解。但算法程序过于复杂，必须通过掌握其一系列算法为基础，不易理解，且编程及软件模块不具通用性。曾霁等（2008）针对运输问题中有些参数很难给出精确值的情况，考虑采用不确定型规划描述此类问题，提出运输问题的区间规划模型，采用区间不等式度的定义将不确定的运输问题区间模型转化为确定型运输问题模型，再用表上作业法求解，其实质为用表上作业法求解一般运输问题。

1.3 本文的主要工作

由于企业选择运输路线或运输工具不合理而导致物流运输成本不能最小化的问题普遍存在而管理运筹学却能很好的解决此问题。对运输问题进行优化分析，从而得到最优化的方案，提高实际运输工作中的经济效益。通过科学的方法对问题进行具体化，再建立数学模型并求解，就能找到运输成本最小的运输组合。运输问题依然属于线性规划问题的范畴，但是由于其约束方程组的系数矩阵具有特殊的结构，因而可以找到一种比单纯形表更简便的求解方法，正是基于此，运输问题从线性规划中单列出来进行讨论。本文重点介绍运用EXCEL电子表格模型解决运输问题。针对斯特兰运输公司南大西洋办公处的经理雷切尔对于垃圾处理的困惑，找到这一问题应用线性规划的约束条件并用EXCEL电子表格进行优化。

EXCEL 在管理科学领域的应用很多， 如线性规划、 运输问题、 指派问题、 网络最优化问题、 项目管理、 库存管理、 预测、 排队论和计算机仿真， 等等。 运用 EXCEL 建立模型， 求解模型， 能对管理者的决策提供很好支持。 配送路线的制定和优化问题在实际物流操作中有着广泛的应用， 也是非常困难的问题， 借助 EXCEL 工具来辅助制定和优化配送路线， 主要是对起点和终点相同的一类路径规划问题做出分析。

5

x31+x22+x23=26 x31+x32+x33=42 x41+x42+x43=53

x51+x52+x53=29

x61+x62+x63=38

x11+x21+x31 +x41+x51+x61<=65 x12+x22+x32 +x42+x52+x62<=80 x13+x23+x33 +x43+x53+x63<=105 xij>=0, for i=1,2,…6, j=1,2,3. xij为整数, for i=1,2,…6, j=1,2,3.

2从工厂运输到垃圾处理点，每箱废物至多可以经过工厂转运一次模型

设从工厂到工厂运量为向量y, 运量 金斯波特 丹维尔 美肯 塞尔玛 哥伦布 亚兰敦 金斯波特 \\ Y12 Y13 Y14 Y15 Y16 丹维尔 Y21 \\ Y23 Y24 Y25 Y26 美肯 Y31 Y32 \\ Y34 Y35 Y36 塞尔玛 Y41 Y42 Y43 \\ Y45 Y46 哥伦布 Y51 Y52 Y53 Y54 \\ Y56 亚兰敦 Y61 Y62 Y63 Y64 Y65 \\ 从工厂到处理场运量为向量x 运量 金斯波特 丹维尔 美肯 塞尔玛 哥伦布 亚兰敦 白水 X11 X12 X13 X14 X15 X16 罗斯堪洛 X21 杜拉斯 X31 X22 X32 X23 X33 美肯 4 11 \\ 3 7 15

16

X24 X34 塞尔玛 9 10 3 \\ 3 16

X25 X35 哥伦布 7 12 7 3 \\ 14

X26 X36 亚兰敦 8 7 15 16 14 \\

设工厂到工厂的运输成本为c1, 工厂\\工金斯波特 丹维尔 厂

金斯波特 \\ 6 丹维尔 6 \\ 美肯 5 11 塞尔玛 9 10 哥伦布 7 12 亚兰敦 8 7

从工厂到处理场的运输成本为c2

工厂\\处理厂 白水 罗斯堪洛 杜拉斯 金斯波特 12 15 17 丹维尔 14 9 10 美肯 13 20 11 塞尔玛 17 16 19 哥伦布 7 14 12 亚兰敦 22 16 18

则目标函数为 MinZ=c1y+c2x

第一组约束条件为对于任何的工厂来讲运出的量等于其产量

金斯波特、丹维尔、美肯、塞尔玛、哥伦布、亚兰敦每周产生的废物量分别为35桶、26桶、42桶、53桶、29桶、38桶。

第二组约束条件为对于任何作为转运工厂来讲，运出量等于运入量

Yi=Yj

第三组约束条件为对于任何垃圾处理场来讲，运入量小于或等于其处理能力。 白水、罗斯堪洛和杜拉斯的三个垃圾处理点每周最多可容纳的废物量分别为65桶、80桶和105桶。

3.可以从任何工厂和垃圾处理点转运，且每箱废物经过转运次数不限的模型

将工厂和处理场合并，都作为工厂和处理场看待，如果原本是工厂的，处理能力为0，如果原本是处理场的，产生的废物为0。

六家工厂金斯波特、丹维尔、美肯、塞尔玛、哥伦布、亚兰敦每周产生的废物量分别为35桶、26桶、42桶、53桶、29桶、38桶。

则另T =[35,26,42,53,29,38,0,0,0]T。 三家处理场白水、罗斯堪洛和杜拉斯的三个垃圾处理点每周最多可容纳的废物量分别为65桶、80桶和105桶。

则另S =[0,0,0,0,0,0,65,80,105]T 。 令工厂到处理场之间矩阵为C1, 工厂\\处理厂 白水 罗斯堪洛 杜拉斯 金斯波特 12 15 17 丹维尔 14 9 10 美肯 13 20 11 塞尔玛 17 16 19

17

哥伦布 7 14 12 亚兰敦 22 16 18

工厂到工厂之间矩阵为C2,

工厂\\工金斯波特 丹维尔 美肯 塞尔玛 哥伦布 亚兰敦 厂

金斯波特 \\ 6 4 9 7 8 丹维尔 6 \\ 11 10 12 7 美肯 5 11 \\ 3 7 15 塞尔玛 9 10 3 \\ 3 16 哥伦布 7 12 7 3 \\ 14 亚兰敦 8 7 15 16 14 \\ 处理场到处理场之间矩阵为C3, 处理点\\处理点 白水 罗斯堪洛 杜拉斯

白水 \\ 12 10 罗斯堪洛 12 \\ 15 杜拉斯 10 15 \\ ?C2C1?则令C??T。设决策变量为xij为i点产生的废物被运送到j处理场的?C3??C1量，i=1,2,?9, j=1,2,?9。令X=[xij] 则目标函数为?i?jci,jxi,j

约束(1)为，X[1,1,?.1]T=[35,26,42,53,29,38,0,0,0]T 约束(2)为，[1,1,?.1]X<=[0,0,0,0,0,0,65,80,105]T xij为整数for i=1,2,?9, j=1,2,?9.

3.2.3对于几种方案的模型的excel求解

1直接从工厂运输到垃圾处理点模型的数据计算

数据的输入

18

规划求解参数的设定

19

运算结果

这一方案的总运费为2822。

20

本文来源：https://www.bwwdw.com/article/n925.html