第三章运输问题课件.ppt

运 筹 学,“运筹学”课题组,本章内容重点,第三章 运输问题,第三章 运输问题,前面讨论了一般线性规划问题的数学模型的建立和求解的方法，但在实际工作中，往往碰到有些线性规划问题，它们的约束条件的系数矩阵具有特殊的结构，这就使我们有可能找到比单纯形法更为简单的求解方法，从而节约大量的计算时间和费用。本章所讨论的运输问题就是属于这样一类特殊的线性规划问题，它在实践中具有重要的作用，具有广泛的应用。,3.1、运输问题的数学模型 在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：,运输问题：假设有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 的运量,则所求的数学模型为:,在该模型中，目标函数表示运输总费用，要求其极小化； 第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量； 第二个约束条件表示由某一产地运往销地的物品数量之和等于该产地的产量； 第三个约束条件表示变量的非负条件。,对于产销不平衡的情况，我们将另行处理。 这就是运输问题的数学模型，它包含mn个变量，m + n个约束条件，是一个线性规划问题。,如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量(以便求出初始基可行解)。 因此，即使是m =4，n = 5这样的简单问题, 变量个数就有29个之多，利用单纯形法进行计算是非常复杂的。 因此，我们有必要针对运输问题的某些特点，来寻求更为简单方便的求解方法。,3.2、表上作业法1、表上作业法的基本概念与重要结论： 针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下特点：（1）在该矩阵中，它的元素等于0或1（2）每列只有两个元素为1，其余都是0；,（3）对应于每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。根据这个特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题的方法，这种方法我们称为表上作业法。,根据运输问题的数学模型求出的运输问题的解，它代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。 由于运输问题也是一个线性规划问题，当用单纯形法进行求解时，我们首先应当知道它的基变量的个数； 其次，要知道这样一组基变量应当是由哪些变量来组成。,运输问题的解X必须要满足模型中的所有约束条件；基变量对应的约束方程组的系数列向量必须是线性无关的；解中基变量应由 m+n-1个变量组成(即基变量的个数 = 产地个数 + 销售地个数 1)，原因是在运输问题中虽然有m+n个约束条件，但由于总产量等于总销量，故只有m+n-1个约束条件是线性独立的。进一步我们想知道，怎样的 m+n-1个变量会构成一组基变量？,为此我们需要引入一些基本概念，通过对这些基本概念的分析和讨论，结合单纯形算法的基本结果，便可得出我们所需要的结论。,凡是能排成,互不相同，且,形成的变量的集合称之为一个闭回路。而把出现在闭回路中的变量称为这个闭回路的顶点。,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,从上面的例子中不难看出，如果把一个闭回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的。,定理3.1： m+n-1个变量 构成基变量的充分必要条件是它不包含有任何闭回路。,该定理给出了运输问题基的一个重要特征，这个结论是非常重要的，因为利用它可以判断 m+n-1个变量是否构成基变量，它比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。另外，在以后还将看到利用基的这个特征可以导出求运输问题的基本可行解的一种简便的方法。,2、 表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：（1）找出初始基可行解，即在 (mn) 产销平衡表上给出m+n-1个有数字的格，这些有数字的格不能构成闭回路，且行和等于产量，列和等于销售量；,(2）求各非基变量的检验数，即在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）、（3）步，直到求（得最优解为止。以下我们就具体给出求解运输问题表上作业法的计算步骤。,（1）、 确定初始基可行解确定初始基可行解即首先给出初始的调运方案，方法很多，我们只介绍其中的两种方法： 方法一：最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面由例题来说明最小元素法确定初始基可行解的具体步骤。,例3.2：某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。,表3.5,解：第一步：从单位运价表中找出最小运价为1，这表示先将 A2 的产品供应给 B1 。由于A2 每天生产4吨，B1 每天只需要 3吨，即 A2 除每日能满足B1 的需要外还余1吨。,因此在产销平衡表 (A2 , 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 每天生产7 吨，B3 尚缺 4 吨，因此在产销平衡表的(A1 , B3)交叉处填上 4，由于B3 的需求已满足，将单位运价表中的 B3 这一列运价划去。,如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为 86 元，如表3.7所示。,表3.7,应当注意的是，在用最小元素法确定初始基可行解的时候，有可能出现以下的两种特殊情况： 一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个作为基变量； 二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。,这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m + n 1）个，需要在同时划去的行或列的任一空格位置添上一个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。,例3.3,某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.8所示。利用最小元素法，求该公司的初始调运方案。,表3.8,解：第一步：从单位运价表中找出最小运价为1，这表示先将 A2 的产品供应 B1 。由于A2 每天生产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的产品已分配完毕，同时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, 方法二、伏格尔法： 最小元素法的缺点是，为了节省一处的费用，有时造成在其它地方要花多几倍的运费。伏格尔法考虑到，一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。 因此，对于差额最大处，就优先采用最小运费调运。 我们还是用例3.2 来说明伏格尔法的具体实施过程，步骤如下：,第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费之差，我们称之为列差额。如此可得表3.11：,表3.11,第二步：从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素。比较该元素所在的行和列的产量，取它们最小者填入产销平衡表相应的位置。 同时在单位运价表中划去一行或一列。由于B2 的列差额最大。B2 列中最小元素为 4（即 A3 行），可确定 A3 产品优先供应 B2 。比较它们的产量和销量，可知在单位运价表中划去 B2 列。在产销平衡表的( A3 , B2 ) 空格处填入 6。,第三步：对上述未划去的元素再比较出各行、各列的差额。重复第一、二步的工作，直到给出初始解为止。本问题利用伏格尔方法给出的初始调运方案如下表3.11所示。,表3.11,由以上可见：伏格尔方法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同，因而给出的初始调运方案也是基可行解。 且一般来说，用伏格尔方法比用最小元素法所求出的初始解更接近于最优解。本例用伏格尔方法给出的初始解的总运费为 85元。,（2）最优解的判别 得到运输问题的初始基可行解后就要判别这个解是否为最优解，判别的方法是计算非基变量即空格的检验数。因运输问题的目标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于 0 时为最优解。 下面介绍两种求空格检验数的方法。,、方法一：闭回路法在给出调运方案的计算表上，如表3.7，从每一空格出发，找一条闭回路。它是以空格为起点，用水平线或垂直线向前划，每碰到一数字格就转 90 度后继续前进。直到回到起始空格处为止。可以证明，每个空格都存在唯一的闭回路。(A1 , B1) 空格与(A1 , B4) 、 (A2 , B4) 和 (A2 , B1) 三个有数字的格构成一闭回路，如此等等。,闭回路计算检验数的经济解释为： 在已给出初始解的表3.7中，可以从任一空格出发，如从 (A1 , B1) 出发，若让 A1 的产品调 1 吨给B1，为了保持产销平衡，就要依次作调整：在 (A1 , B3) 处减少 1 吨，(A2 , B3) 处增加 1 吨，(A2 , B1) 处减少 1 吨，即构成了以(A1 , B1)空格为起点，其它为有数字的格的闭回路。如表3.12中的直线所示。,各顶点所在格的右上角的数字是单位运价。可见这一调整方案使运费增加了：(+1)3 + (-1) 3 + (+1)2 + (-1) 1 = 1 (元)这表明若这样调整运输方式将增加运费。将“1”这个数填入(A1 , B1) 格，这就是检验数。,表3.12,1,按以上所述，就可以找出 所有空格的检验数，见如下表3.13。,表3.13,这时检验数还存在负数，因为(A2 , B4) 空格的检验数为 1，这说明表3.7给出的方案还不是最优解，还需要进一步改进，改进方法见本节后面的基可行解的改进方法。,、 方法二：位势法用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点很多时，空格的数量很大，计算检验数将十分费时。下面介绍一种较为简便的方法位势法。,现在引进m+n 个未知量 u1 , , um , v1 , , vn，由上述基本可行解可构造如下一个方程组：,是一组基可行解，,其中cij为单位运价。方程组（3.1）共有m+n 个未知数和m+n-1个方程。(3.1)的解存在且恰有一个自由变量。称u1 , , um为行位势，v1 , , vn为列位势。,定理3.2 设已给了一组基本可行解，则对每一个非基变量xij 来说，它所对应的检验数为：ij = cij ( ui + vj ) 下面,我们就以例子来说明这种方法的具体实施过程。,仍以例3.2所给出的初始基可行解表3.7为例：第一步：在对应表3.7的数字格处填入单位运价如表3.14所示：,表3.14,第二步：在表3.14上增加一行和一列，列中填入行位势 ui ，行中填入列位势 vj 得表3.15。 先令u1= 0（行和列中基变量多的令为0），然后按ui + vj = cij ( i , j )基变量指标集 ，相继确定ui、vj 。由表3.15可见，u1= 0 时，由u1+ v3=c13=3可得v3 =3，由u1+v4 =c14= 10，可得v4 =10；在v4 =10时，由u3+v4 =c34= 5可得u3=-5。以此类推可确定所有的ui、vj的值。,表3.15,第三步：按ij = cij (ui + vj ) ,( i , j )非基变量指标集，计算所有的空格检验数。如： 11 = c11 (u1 + v1 ) =3 ( 0 + 2 ) = 1 12 = c12 (u1 + v2 ) = 11 - ( 0 + 9 ) = 2这些计算可直接在表3.15上进行。为了方便，特设计计算表，如表3.16。右上角框内的数为单位运价。在表3.16中还有负的检验数，说明还未得到最优解，还得进一步进行改进。,10,3,9,2,列位势vj,-5,-1,0,行位势ui,销地产地,B4,B3,B2,B1,A3,A2,A1,50,30,10,20,0,4,100,表3.16,31,112,91,8-1,710,1012,、 基可行解改进的方法闭回路调整法当计算所有的空格检验数时，出现了负检验数，这表明还未得到最优解。若有两个或两个以上的检验数为负时，一般选择其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表3.16可知 (A2 , B4)为调入格（即以它对应的变量 x24 为换入变量）。以此格为出发点，作一闭回路，如表3.17所示。,表3.17,(A2 , B4) 格的调入量 q 是选择闭回路上具有（-1）的数字格中的最小者。即 q = min1 , 3=1 (其原理与单纯形法中按q 规则来确定的换出变量是相同)，然后按闭回路上的正、负号，加入和减去此值，得到调整方案如表3.18所示。,表3.18 解的调整表,对表3.18给出的解，再用闭回路法或位势法求各空格的检验数，见表3.19，这时表中的所有检验数全都大于等于 0 ，所以表3.19所给出的解为最优解。这时得到的总运费的最小值是 85 元。,检验数都大于等于0，因此所得方案为最优方案。,表3.19 检验数表,应当指出的是，产销平衡的运输问题必定存在最优解。 那么有唯一最优解还是无穷多个最优解？,依据仍然是看非基变量（即空格处）的检验数是否有为0的。 若有，则存在无穷多个最优解；否则，只有唯一最优解。 由于表3.18可知，空格 (A1,B1)处的检验数为0，表明例3.2有无穷多个最优解。可在表3.18中以(A1,B1)为调入格,作闭回(A1,B1)+(A1,B4)-(A2 ,B4)+(A2 , B1)- (A1 , B1)+ 。,确定 = min2 , 3=2，经调整后得到另一个最优解，见表3.20。,表3.20,当然，我们的调入量可以是： 0 2 中的任一实数，这时的解仍为最优解，但不是基可行解（因为线性规划问题可以在顶点取到最优解，也可以是在非顶点即是边界点上取到最优解），本题如表3.21所示。,表3.21,3.3、产销不平衡的运输问题及其求解方法,前面讲的表上作业法，都是以产销平衡为前提的。但实际问题往往是不平衡的。这就需要把产销不平衡的问题转化为产销平衡的问题。,当产大于销时，即 时，运输问题的数学模型可以写成：,由于总的产量大于销售量，就要考虑多余的物资在那一个产地贮存的问题。设 xin+1 是产地 Ai 的贮存量，故有：,将其分别代入，得到：,这是一个产销平衡的运输问题。,类似地，当销大于产时，可以在产销平衡表中增加一个假想的产地 i = m + 1，该产地的产量为 ，在单位运价表中令从该产地到各个销售地的单位运价为：cm+1 j = 0，同样可以转化为产销平衡的运输问题。,例3.4,设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化肥的运价表如表3.22所示。试求出总的运费最省的化肥调拨方案。,单位运价：万元/万吨,表3.22,解：这是一个产销不平衡的运输问题，总产量为160万吨 ，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第IV个地区每年最多能分配得到60万吨， 这样最高需求就为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂 D，其年产量为 50 万吨。由于各地区的需求量包含两部分，如地区1，其中 30 万吨是最低需求，故不能由假想化肥厂 D 供给，,令相应的单位运价为 M（任意大的正数）；而另一部分 20 万吨满足或不满足均可以，因此可以由假想化肥厂 D 供给，按前述，可令相应的单位运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表（表3.23(a)）和单位运价表（表3.23(b)）并根据表上作业法，可以求得这个问题的最优解如表3.24所示。,3.23（a）产销平衡表,表3.23(b) 单位运价表,表3.24 最优调运方案,由于在变量个数相等的情况下，表上作业法的计算远比单纯形法的计算简单得多，所以在解决实际问题时，人们常常尽可能把某些线性规划问题化为运输问题的数学模型。下面介绍如何把线性规划问题转化为运输问题，以例3.5作为一个典型的实例进行介绍。,例3.5,某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3.25所示。又如果生产出来的柴油机当季不交货，每台每季度需存储费、维护费等共0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护等）费用最小的决策。,表3.25,解：由于每个季度生产出来的柴油机不一定当季交货，所以设 xij 表示为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足： x11 = 10 x12 + x22 = 15 x13 + x23 + x33 = 25 x14 + x24 + x34 + x44 = 20,又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有： x11 + x12 + x13 + x14 25 x22 + x23 + x24 35 x33 + x34 30 x44 10,第 i 季度生产的用于第 j 季度交货的每台柴油机的实际成本 cij 应该是该季度单位成本加上储存、维护等费用。cij 的具体数值见表3.26。,表3.26,设用 ai 表示该厂第 i 季度生产能力，bj 表示第 j 季度的合同供应量，则问题可写成：,显然这是一个产大于销的运输问题模型。注意到这个问题中当 i j 时，xij = 0，所以应该令对应的 cij = M，M 是充分大的正数，再加上一个假想的需求季份 ，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表（合二为一，见表3.27）。,表3.27 产销平衡表与单位运价表,经用表上作业法求解，可得多个最优方案，表3.28中列出最优方案之一。即第 I季度生产 25台，其中 10台当季交货，15台第 II季度交货；第 II季度生产 5台用于第III季度交货；第 III季度生产 30台，其中 20台当季交货，10台用于第 IV季度交货；第 IV季度生产 10台用于当季度交货。按此方案安排生产，可使该厂总的生产（包括储存、维护等）费用最省，即为 773万元。,表3.28 最优调运方案,Thank You !,