运筹学课程论文

利用表上作业法解供需相等问题

运筹学论文

—利用表上作业法解产销相等运输问题

摘要：运输问题是运筹学中的一个重要问题，也是物流系统优化的常见的问题，同时也是一种特殊的线性规划问题。怎么样尽可能的减少运输成本以及减少运输费用一直是各类物流系统密切关注的问题。本文通过科学的方法对问题具体化，再建立数学模型进行求解，以找到运输成本最小的组合。

关键词：运输问题 产销均衡 表上作业法

一、引言

运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问题：在大宗物资调运时，有若干个产地，根据已知的运输交通网，如何制定一个运输方案，将这些物资运到各个销售地，使得总运费最小。物流管理的本质要求就是求实效，即以最少的消耗，实现最优的服务，达到最佳的经济效益。搞好物流管理，可以通过合理的运输方案，使中间装卸搬运、储存费用降低、损失减少，在其他条件不变的情况下，降低物流成本就意味着扩大了企业的利润空间，提高了利润水平，所以一个合理的运输方案有着重要的意义。

运输问题提出后，人们对其求解方法进行了大量研究，并有了大量成果，尤其在近十几年，借由大量软件的开发，运输问题大多可以由电脑来解决，特别是对于那些数据异常多的运输问题，软件的应用就更加必要。但是，本文想重点探讨的是Danzig的表上作业法，这种方法是最简单和最常用的，对于数据较少的运输问题，非常适合。

二、运输问题研究现状：

运输问题是运筹学的一个分支，它研究的是如何在一个大宗物资调运中，制定出一个由若干个产地，将这些物资根据已知的运输交通网运到各个销售地的方案，使得总运费最小。运输问题是在1941年美国学者希奇柯克在研究生产组织和铁路运输方面的线性规划问题时提出的。 运输问题的提出，不仅可以求出物资的合理调运方案，其他类型的问题也都可以经过变换后转为运输问题来进行求解。运输问题自提出以来，人们对其解法进行了大量的研究： 从目标函数的角度，运输问题同时考虑运输总费用最小、运输过程中损坏率最低和单位运价变化的调整等多个目标，所以有宋叶新、陈绵云和吴晓平研究的具有模糊信息的目标运输问题求解、李珍萍研究的最短时限运输问题、带瓶颈限制的运输问题、运用禁忌搜索算法解决带固定费用的运输问题、调整单位运价使得运输计划最优的运输问题的逆问题等等。 从算法角度来看，人们对运输问题提出了大量算法，如表上作业法、图上求解法、遗传算法、神经网络算法、减运价算法、仿真优化法、内点法等等。 从计算机求解角度来看，目前已经有很多对运用计算机求解运输问题的研究，如运输问题的计算机求解 、Excel求解运输问题、Lingo求解 运输问题 、Matlab求解。此外，还有其他软件也可以求解运输问题， 比如运筹学CAI软件，不过功能比较少，Winqsb等等，现实中运用比较广泛的是Lingo和Matlab。 运输问题是社会经济生活中经常出现的优化问题，我们经常碰到物资调运如煤、粮食、钢材、木材等，这些都是大宗型的运输，在物流流通中通过合理的运输方案，使中间装卸搬运、储存费用降低、损失减少，以最少的消耗， 实现经济效益最大化， 所以一个合理的科学的运输方案有着重要的意义。 在众多的求解方法和求解工具中，总会有各自的优缺点，所以寻求一个好中更好的求解工具，提高求解效率和可扩展性将会有很重要的意义。 同时，在现实生活中，许多问题都可以转化成运输问题数学模型进行求解，所以研究运输问题也等于研究了很多相关的问题，其意义更明显。

利用表上作业法解供需相等问题

三、相关理论概述：

1.运输问题：

运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问题：在大宗物资调运时，有若干个产地，根据已知的运输交通网，如何制定一个运输方案，将这些物资运到各个销售地，使得总运费最小。物流管理的本质要求就是求实效，即以最少的消耗，实现最优的服务，达到最佳的经济效益。 2.线性规划：

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。 3、经典运输模型：

经典的运输问题是一个线性规划模型。假定某种物资有m个产地，n个销地ai 为第i产地的供应量， bj为第j个销地的需求量,cij 为从产地i到销地j的单位运费，xij为产地i到销地j的调运数量， xij≥0，其中i=1,2,…,m；j=1,2,…,n。 问如何组织调运才能使得总运费最省?

n

该问题为了寻找最佳调运方案， 即求解所有xij的值．使总的运输费用 mi=1 j=1cijxij达

n

到最少。其中当 mi=1ai= j=1bj时为平衡型运输问题：当其不相等的时候就位不平衡型运输问题。实际上步平衡型的运输问题通过转换可以变成平衡型的问题。当产量总量等于销售总量时，运输问题有可行解，且有最优解，且当产量和销售量均为整数时，必存在决策变量均为整数的最优解。

n

平衡型运输问题的数学模型如下：minZ= mi=1 j=1cijxij

n

S.t． mj=1xij=bj,j=1,2…m i=1xij=ai,i=1,2…n xij 0,对所有的i，j 运输问题的解法通常用表上作业法。 表上作业法是单纯形法在求解运输问题。 4、表上作业法

运输问题的解法通常用表上作业法。 表上作业法是单纯形法在求解运输问题。 表上作业通常有三种：西北角法、最小元素法、vogel（沃格尔）法。 （1）西北角法：

从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 （2）最小元素法：

从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 （3）vogel(沃格尔)法：

在运价表上写出每行和每列运价中最小元素和次小元素之差。从所有行差额和列差额中选取差额最大的一行或 一列进行分配，并对该行(或列)最小元素格填数。重新计算差额，重复上述手续。剩最后一行或一列按余额分配，只填数即可，确保有数字个数为m+n-1个。

利用表上作业法解供需相等问题

四、实例分析：

某公司下属四个储存某种物资的料库，供应五个工地的需要。四个料库的供应量和五个工地的需求量以及由各料库到各工地调运单位物资的运价见下表，试求运输费用最小的合理调运方案。

（1） 西北角法：

运费：5X250+2X100+4X200+1X300+7X50+2X400+2X200+8X300=6500

运费：5X250+4X300+1X300+7X50+2X400+3X100+2X400=6000

三种方法运费：6000<6800<<10100

五:结论：

利用表上作业法 …… 此处隐藏：2218字，全部文档内容请下载后查看。喜欢就下载吧 ……