第三章运输问题资料

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

1、运 筹 学,“运筹学”课题组,本章内容重点,第三章 运输问题,第三章 运输问题,前面讨论了一般线性规划问题的数学模型的建立和求解的方法，但在实际工作中，往往碰到有些线性规划问题，它们的约束条件的系数矩阵具有特殊的结构，这就使我们有可能找到比单纯形法更为简单的求解方法，从而节约大量的计算时间和费用。本章所讨论的运输问题就是属于这样一类特殊的线性规划问题，它在实践中具有重要的作用，具有广泛的应用。,3.1、运输问题的数学模型 在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总

2、运费最小。这类问题可用以下数学语言来描述：,运输问题：假设有m个生产地点，可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,m；有n个销售地，用Bj表示，j=1,2,n；产地的产量和销售地的销售量分别为ai ,i=1,2,m和bj，j=1,2,n，从Ai到Bj运输单位物资的运价为cij，这些数据可汇总于如表3.1。,表3.1,要求使总运费最小的调运方案。 如果运输问题的总产量等于其总销量，即,则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。 下面建立在产销平衡情况下的运输问题的数学模型。,解: 假设 xij 表示从Ai到 Bj 的运量,则所求的数学模型为:,在该模型中，

3、目标函数表示运输总费用，要求其极小化； 第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量； 第二个约束条件表示由某一产地运往销地的物品数量之和等于该产地的产量； 第三个约束条件表示变量的非负条件。,对于产销不平衡的情况，我们将另行处理。 这就是运输问题的数学模型，它包含mn个变量，m + n个约束条件，是一个线性规划问题。,如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量(以便求出初始基可行解)。 因此，即使是m =4，n = 5这样的简单问题, 变量个数就有29个之多，利用单纯形法进行计算是非常复杂的。 因此，我们有必要针对运输问题的某些特点，来寻求更为简单

4、方便的求解方法。,3.2、表上作业法 1、表上作业法的基本概念与重要结论： 针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下特点： （1）在该矩阵中，它的元素等于0或1 （2）每列只有两个元素为1，其余都是0；,（3）对应于每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。根据这个特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题的方法，这种方法我们称为表上作业法。,根据运输问题的数学模型求出的运输问题的解，它代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。 由于运输问题也是一个线性规划问题，当用单纯形法

5、进行求解时，我们首先应当知道它的基变量的个数； 其次，要知道这样一组基变量应当是由哪些变量来组成。,运输问题的解X必须要满足模型中的所有约束条件； 基变量对应的约束方程组的系数列向量必须是线性无关的； 解中基变量应由 m+n-1个变量组成(即基变量的个数 = 产地个数 + 销售地个数 1)，原因是在运输问题中虽然有m+n个约束条件，但由于总产量等于总销量，故只有m+n-1个约束条件是线性独立的。 进一步我们想知道，怎样的 m+n-1个变量会构成一组基变量？,为此我们需要引入一些基本概念，通过对这些基本概念的分析和讨论，结合单纯形算法的基本结果，便可得出我们所需要的结论。,凡是能排成,互不相同，

6、且,形成的变量的集合称之为一个闭回路。而把出现在闭回路中的变量称为这个闭回路的顶点。,x11、 x12、 x32、 x34、 x24、 x21 构成一个闭回路。这里有：i1= 1，i2 = 3，i3 = 2；j1 = 1，j2 = 2，j3 = 4。 若把闭回路的顶点在表中画出，并且把相邻两个变量用一条直线相连（今后就称这些直线为闭回路的边）。,例3.1 设 m = 3，n = 4，如表3.2所示,而表3.3，即顶点为 x12、x32、x34、x14 和表3.4，即顶点为 x11、x12、x22、x24、x34、x31 也分别构成两个闭回路。,表3.3,表3.4,从上面的例子中不难看出，如果把

7、一个闭回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的。,定理3.1： m+n-1个变量 构成基变量的充分必要条件是它不包含有任何闭回路。,该定理给出了运输问题基的一个重要特征，这个结论是非常重要的，因为利用它可以判断 m+n-1个变量是否构成基变量，它比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。另外，在以后还将看到利用基的这个特征可以导出求运输问题的基本可行解的一种简便的方法。,2、 表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所

8、不同，可归纳为： （1）找出初始基可行解，即在 (mn) 产销平衡表上给出m+n-1个有数字的格，这些有数字的格不能构成闭回路，且行和等于产量，列和等于销售量；,(2）求各非基变量的检验数，即在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步； （3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。 （4）重复（2）、（3）步，直到求（得最优解为止。以下我们就具体给出求解运输问题表上作业法的计算步骤。,（1）、 确定初始基可行解 确定初始基可行解即首先给出初始的调运方案，方法很多，我们只介绍其中的两种方法： 方法一：最小元素法： 最小元素

9、法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面由例题来说明最小元素法确定初始基可行解的具体步骤。,例3.2：某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。,表3.5,解：第一步：从单位运价表中找出最小运价为1，这表示先将 A2 的产品供应给 B1 。由于A2 每天生产4吨，B1 每天只需要 3吨，即 A2 除每日能满足B1 的需要外还余1吨。,因此在产销平衡表 (A2

10、 , B1) 交叉处填上3，表示 A2 调运3吨给B1，再在单位运价表中将B1 这一列运价划去，表示 B1 的需求已满足，不需要继续调运 (即x21 =3=min(a2,b1)=min(4 , 3)。,第二步: 从上述未划去的单位运价表的元素中找出最小的运价2 ，即A2 把剩余的产品供应给B3 ；B3 每天需要5 吨，A2 只剩余 1 吨，因此在上述产销平衡表的 (A2 , B3) 交叉处填上 1，划去上述运价表中A2 这一行运价，表示 A2的产品已分配完毕。,表3.6,第三步: 从上述第二步所得的单位运价表未划去的元素中找出最小元素为 3。这表示将 A1 的产品供应 B3 ， A1 每天生产

11、7 吨，B3 尚缺 4 吨，因此在产销平衡表的(A1 , B3)交叉处填上 4，由于B3 的需求已满足，将单位运价表中的 B3 这一列运价划去。,如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为 86 元，如表3.7所示。,表3.7,应当注意的是，在用最小元素法确定初始基可行解的时候，有可能出现以下的两种特殊情况： 一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个作为基变量； 二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于

12、该元素所在列的剩余销售量。,这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m + n 1）个，需要在同时划去的行或列的任一空格位置添上一个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。,例3.3,某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.8所示。利用最小元素法，求该公司的初始调运方案。,表3.8,解：第一步：从单位运价表中找出最小运价为1，这表示先将 A2 的产品供应 B1 。由于A2 每天生

13、产4吨，B1 每天只需要 3吨，因此在产销平衡表 (A2 , B1) 交叉处填上3，同时将单位运价表中的B1 这一列运价划去。,第二步: 从上述未划去的单位运价表的元素中找出最小的运价3 ，即A1的产品供应供应给B2 ；B2 每天需要5 吨，由于A1每天生产9吨，因此在上述产销平衡表的 (A1 , B2) 交叉处填上 5，划去上述运价表中B2这一列运价。,第三步: 从上述第二步所得的单位运价表未划去的元素中找出最小元素为 4。这表示将 A1 把剩余的产品供应给B4 ；B4 每天需要4吨，A1 正好剩余 4 吨，因此在上述产销平衡表的 (A1, B4) 交叉处填上 4，这时A1的产品已分配完毕，

14、同时B4 的需求已满足，因此划去上述运价表中A1 这一行和B4 这一列运价。,为了使有数字的格不减少，( 有数字的格的总数应为m + n 1个 )可以在空格( A1, B1 ) 、 ( A1, B3 ) 、 ( A2, B4 ) 、( A3, B4 )中任选一个格添加一个 “0”；同样，这个添加的“0”格当作基变量，取值为0。这里我们在 ( A1, B3 ) 处填0（即初始调运方案是一个退化的基可行解），表示为基变量。,如此，进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。如表3.9、表3.10所示。,表3.9,表3.9,表3.10, 方法二、伏格尔

15、法： 最小元素法的缺点是，为了节省一处的费用，有时造成在其它地方要花多几倍的运费。伏格尔法考虑到，一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。 因此，对于差额最大处，就优先采用最小运费调运。 我们还是用例3.2 来说明伏格尔法的具体实施过程，步骤如下：,第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费之差，我们称之为列差额。如此可得表3.11：,表3.11,第二步：从行差额和列差额中选出最大者，选择它所在的行或列中的

16、最小元素。比较该元素所在的行和列的产量，取它们最小者填入产销平衡表相应的位置。 同时在单位运价表中划去一行或一列。由于B2 的列差额最大。B2 列中最小元素为 4（即 A3 行），可确定 A3 产品优先供应 B2 。比较它们的产量和销量，可知在单位运价表中划去 B2 列。在产销平衡表的( A3 , B2 ) 空格处填入 6。,第三步：对上述未划去的元素再比较出各行、各列的差额。重复第一、二步的工作，直到给出初始解为止。 本问题利用伏格尔方法给出的初始调运方案如下表3.11所示。,表3.11,由以上可见：伏格尔方法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同，因而给出的初始调运方案也是基可行解。 且一般来说，用伏格尔方法比用最小元素法所求出的初始解更接近于最优解。本例用伏格尔方法给出的初始解的总运费为 85元。,（2）最优解的判别 得到运输问题的初始基可行解后就要判别这