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

第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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库毕业论文线性规划在垃圾运输问题的应用(2)在线全文阅读。