浅谈运筹学中的运输问题.doc11.doc

浅谈运筹学中的运输问题 摘 要：运筹学自二战以来开始打来那个应用在除战争以外的许多领域，尤其在企业管理中表现的尤为突出。运筹学的思想贯穿了企业管理的始终，在企业战略管理、生产计划、市场营销、运输问题、库存管理、人事管理、财务会计等各个方面都具有重要的作用，对企业管理的发展产生重要影响。这里我们主要对运输问题几种方法做一个简单的介绍。关键词：最下元素法；沃格尔法（Vogel）首先我们先来介绍运输问题的数学模型：设有m个产地（记作A1，A2，A3,Am），生产某种物资，其产量分别为a1,a2，am；有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即 。从第i个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设xij(i=1,2,，m；j=1,2,n)为第i个产地到第j个销地的运量，则数学模型为： （！）最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。下面举一个例子：求表37给出的运输问题的初始基本可行解。 B1B2B3B4aiA1311447A277384A3121069bj365620解：B1B2B3B4aiA1311（0）4（1）4（6）7A2773（4）84A31（3）2（6）1069bj365620 在x12、x22、x33、x34中任选一个变量作为基变量，例如选x12 初始基本可行解可用下列矩阵表示 表38中，标有符号 的变量恰好是3+41=6个且不包含闭回路，是一组基变量，其余标有符号的变量是非基变量， （2）运费差额法（Vogel）: 最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案， 15 15 15 15前一种按最小元素法求得，总运费是Z1=108+52+151=105，后一种方案考虑到C11与C21之间的差额是82=6，如果不先调运x21，到后来就有可能x110，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12这时总运费Z2=105+152+51=85Z1。 基于以上想法，运费差额法求初始基本可行解的步骤是： 第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n； 第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行或列的最小运价处优先调运； 第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。 用运费差额法求得的基本可行解更接近最优解，所以也称为近似方案。下面是一个例子：用运费差额法求表39运输问题的初始基本可行解。B1B2B3B4aiA1589115A2672425A311013820bj201052560 解：求行差额 ui, i=1,2,3及列差额vj,j=1,2,3,4.计算公式为 ui= i行次小运价i行最小运价 vj= j列次小运价j例最小运价销地产地B1B2B3B4aiuiA1589 12153A2172 （5）4251A361013 8202bj201052560vj41（7）4销地产地B1B2B3B4aiuiA15 （0）89 12153A21 （20）7 2 （5）4 253A36 1013 8202bj201052560vj（4）14销地产地B1B2B3B4aiuiA15 （0）8 （10）9 12 （5）154A21 （20）7 2 （5）4 25A36 10 13 8 （20）202bj201052560vj_2_(4)基本可行解： 总运费Z=108+201+52+208=270。求运输问题的初