运输问题jssk运筹学.ppt

运 筹 学 教 程,制作单位:南京航空航天大学金城学院主讲人:朱雪春E-mail:,在经济建设中，经常会遇到大宗物资调拨中的运输问题，如煤炭、钢铁、木材、粮食等物资，在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,运输问题,例1.某公司从两个产地A1,A2将物品运往三个销地B1，B2，B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问应如何调运，使得总运输费最小？,运输问题,运输问题,解：我们知道A1、A2两个产地的总产量为：200+300=500（件）；B1，B2，B3三个销地的总销量为：150+150+200=500（件）,总产量等于总销量这是一个产销平衡的运输问题。把 A1，A2 的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。,运输问题,设xij表示从产地Ai调运到Bj的运输量（i=1,2;j=1,2,3），现将安排的运输量列表如下：,运输问题,从上表可写出此问题的数学模型。满足产地产量的约束条件为：x11+x12+x13=200，x21+x22+x23=300.满足销地销量的约束条件为：x11+x21=150，x12+x22=150，x13+x23=200.,运输问题,所以此运输问题的线性规划的模型如下：目标函数：min Z=6x11+4x12+6x13+6x21+5x22+5x23约束条件：x11+x12+x13=200，x21+x22+x23=300，x11+x21=150，x12+x22=150，x13+x23=200.xij0.(i=1,2;j=1,2,3),运输问题,运输问题,假设有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,运输问题,如果运输问题的总产量等于其总销量，即,则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。,产销平衡情况下的运输问题的数学模型：假设xij表示从Ai到Bj的运量，则所求的数学模型为,运输问题,该模型中，目标函数表示运输总费用，要求其极小化；第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第二个约束条件表示由某一产地运往各销地的物品数量之和等于该产地的产量；第三个约束条件表示决策变量的非负条件。,运输问题,约束条件展开：min Z=(c11x11+c12x12+c1nx1n)+(c21x21+c22x22+c2nx2n)+(cm1xm1+cm2xm2+cmnxmn),x11+x1n=a1 x21+x2n=a2 xm1+xmn=amx11+x21+xm1=b1 x12+x22+xm2=b2 x1n+x2n+xmn=bn,约束方程式共mn个变量，m+n个约束条件。,技术系数矩阵,系数矩阵的秩为m+n-1,基变量的个数是m+n-1（即基变量的个数产地个数销售地个数-1）,运输问题,求解平衡运输问题的表上作业法：,（1）确定一个初始的可行调运方案：西北角法，最小元素法，伏格尔法；（2）判断当前可行方案是否为最优：闭回路法和位势法；（3）方案调整直至找到最优方案。,运输问题,例3.2 某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价表如3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费最小。,运输问题,1）确定初始调运方案西北角法,西北角法使最简单而且能快速给出一个初始方案的方法，它从运输量的表格中的西北角即左上角开始确定运输量，并且取得尽可能大的运输量，从而获得一个初始调运方案。,运输问题,例3.2 某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价表如3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费最小。,运输问题,运输问题,检查全表，产销已平衡，得到初始调运方案：x11=3,x12=4,x22=2,x23=2,x33=3,x34=6,其余xij=0，总运费为135。方案中，调运量的个数正好是基变量应有的个数3+4-1=6。,运输问题,对于任何一个产销平衡问题，应用西北角法总可以给出一个初始调运方案，因此，平衡运输问题必有基本可行解，又因目标函数有下界（不能为负），因此，也必有最优解。并且，对于平衡运输问题，当产量和销量均为整数时，其可行解和最优解也必为整数解。,运输问题,西北角法的优点是简便易行，缺点是在制定调运方案时，没有考虑运输费用，即没有采用“就近供应”的原则，这样所得的初始方案往往离最优调运方案相差甚远。,运输问题,最小元素法：基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，以此类推，直到给出初始方案为止。,1）确定初始调运方案最小元素法,运输问题,检查全表，产销已平衡，得到初始调运方案：x13=4,x14=3,x21=3,x23=1,x32=6,x34=3,其余xij=0，总运费为86。对比西北角法和最小元素法，由于考虑了运价的影响，所以由最小元素法获得的调运方案要优于西北角法。,运输问题,1）确定初始调运方案伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处就应当采用最小运费调运。基此，伏格尔法的步骤：,运输问题,第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费之差，称为列差额。,运输问题,第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。如表中，B2列是最大差额所在列，B2列中最小元素为4，可确定A3的产品先供应B2的需要，同时将B2列数字划去，如图：,运输问题,第三步：对表中未划去的元素再分别计算出各行、各列的最小元素和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。如图：,运输问题,由以上可见，伏格尔法同最小元素法除在供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始解就是最优解。,运输问题,2）最优解的判别闭回路法,在用西北角法和最小元素法确定初始方案，产销平衡表中，我们称右上角没有填数字的格子为空格，而把右上角填有数字的个子称为基格。闭回路，就是从某一空格出发，沿水平或垂直方向前进，如遇基格可作垂直或水平方向转向（转向处称顶点）前进，也可穿越继续前进。如遇空格不能转向，必须穿越继续前进，但最后仍回到原来的空格，目的是围成一个矩形的，或各边顺次垂直的曲折多变形的闭合回路。,运输问题,2）最优解的判别闭回路法,闭回路的顶点除去起始和终了是同一个空格外，其他所有顶点均为基格。凡是可行的调运方案，每一个空格，也就是每一个非基变量，都可以画一个闭回路，而且是唯一的。,思考：最小元素法中，(A1,B1)，(A2,B2)的闭回路？,运输问题,运输问题,计算各空格的检验数，它等于其闭回路上奇数点运价与偶数点运价之负值的和。ij=(第一顶点的运价)-(第二顶点的运价)+(第三顶点的运价)-(第四顶点的运价)=(奇数顶点运价之和)-(偶数顶点运价之和),运输问题,运输问题,以x11检验数为例,运输问题,将检验数填入产销平衡表中，并用括号括起来。,运输问题,检验数的经济涵义是：在保证产销平衡的前提下，空格的调运量增加一个单位，相应在空格闭回路的偶数顶点均减少一个单位，奇数顶点均增加一个单位后，所引起的总运费的改变量。正的空格检验数意味着总运费将增加，负的空格检验数意味着总费用将减少。,最优解判别准则：若所有检验数都非负，则得到最优解，即相应的运输方案最优；若有检验数小于零，则方案还需要调整。,运输问题,2）最优解的判别位势法,用闭回路法求检验数时，需要给每一个空格找一条闭回路。当产销点很多时，空格的数量很大，计算检验数将十分费时。下面介绍一种较为简便的方法位势法。计算过程如下：,运输问题,2）最优解的判别位势法,（1）仅考虑基变量对应的运价（2）在表的下面和右边各增加一行和一列，分别称为位势行和位势列。在新增加的行、列中分别填上一些数字，表中的各个数恰好等于它所对应的位势行和位势列的两个所填数字之和；表中用ui(i=1,2,m)和vj(j=1,2,n)分别代表位势列和位势行上的各个数字，并分别称为ui和vj为第i行和第j列的位势。因它们之间相互关联，只要任选其中一个值，其余均能算出。,运输问题,令u10,运输问题,（3）计算各空格处的位势hij=ui+vj（4）计算各空格处的检验数ij=cij-hij,运输问题,3）调运方案的改进,调入变量的确定：取绝对值最大的那个负空格检验数所对应的非基变量作为调入变量；调出变量的确定：以调入变量为第一顶点，沿着闭回路某一前进方向，比较各偶数顶点的调运量，找出其最小值，这最小值所对应的变量为调出变量，而这个最小值就是调整量。调整调运方案：在调入变量所对应的闭回路中，所有奇数顶点的运量都加上调整量，所有偶数顶点的运量都减去调整量。而该闭回路顶点以外的地方，所有运量都不变。,运输问题,3）调运方案的改进,调整后的方案,运输问题,3）调运方案的改进,再计算各空格处的检验数,空格处的检验数都为非负，已得到最优解。此时，总运费最小为35+102+31+18+64+35=85元,运输问题,总运费最小为35+102+31+18+64+35=85元,最终方案是：,表上作业法计算中的问题,1、两个运价同时最小 当遇到两个运价同时是最小，比如都是1，则任意选择一个分配运量。,运输问题,表上作业法计算中的问题,2、无穷多最优解：产销平衡问题必有最优解，如何判断是唯一最优解还是无穷多最优解。原则：某个非基变量（空格）的检验数为0时，该问题有无穷多最优解。如例中空格（1，1）的检验数是0，表明例1有无穷多最优解。可在表中，以（1，1）为调入格，作闭回路(1,1)+-(1,4)-(2,4)+-(2,1)-(1,1)+。确定=min(2,3)=2。经调整后得到另一最优解。,运输问题,总运费最小为32+35+11+83+46+53=85元,最终方案是：,运输问题,3、退化,1）在用西北角法和最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列，这时就出现退化。出现退化时，在相应的格中一定要填入一个0，以表示此格为数字格。,举例：,运输问题,西北角法退化,需要划去A1行或B2列，然后在（2,2）或（1,3）格中添加1个0。,运输问题,最小元素法退化,需要划去B2列和A3行，然后在空格(1,2),(2,2),(3,3),(3,4)中任选一个添加一个0。,运输问题,3、退化,2）在用闭回路法调整时，在闭回路上出现两个和两个以上的具有（-1）标记的相等的最小值，这时只能选择其中一个作为调入量。而经调整后，得到退化解，这时另一个数字格必须填入一个0，表明它时基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记（-1）的取值为0的数字格，这是应取调整量=0,举例：,运输问题,3、退化,运输问题,3、退化,运输问题,练习：设某物资需要由产地A1,A2,A3调往销地B1,B2,B3,B4，各产地的产量和各销地的产量以及各产地到各销地的单位运价如表所示，请分别用最小元素法和伏格尔法确定最优方案。,运输问题,运输问题,该方案为最优调运方案，它对应的目标函数值即最小总运费为Z=143660361543=57,第3节 产销不平衡的运输问题及其求解方法,前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。当产大于销时,第3节 产销不平衡的运输问题及其求解方法,运输问题的数学模型可写成,第3节 产销不平衡的运输问题及其求解方法,由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。这时，只要增加一个假想的销地jm+1（实际上是储存），该销地的总需要量为：设xi,n+1是产地Ai的储存量，于是有：,第3节 产销不平衡的运输问题及其求解方法,可转化为产销平衡的运输问题,因为,在单位运价表中，从各产地到假想销地的单位运价为ci,n+1=0，就可转化成产销平衡的运输问题。,第3节 产销不平衡的运输问题及其求解方法,当产大于销时，只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为,而在单位运价表中从各产地到假想销地的单位运价为，就转化成一个产销平衡的运输问题。,第3节 产销不平衡的运输问题及其求解方法,在最优解中，虚设产地Am+1到销地Bj的运量实际上就是最后分配方案中销地Bj的缺货量。在产销不平衡问题中，如果某产地不允许将物资就地贮存或者不允许缺货，则要令相应运价Ci,n+1或Cm+1,j=M（M是充分大的正数）。,第3节 产销不平衡的运输问题及其求解方法,例2 设有三个化肥厂(A，B，C)供应四个地区(，)的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表3-25所示。试求出总的运费最节省的化肥调拨方案。,第3节 产销不平衡的运输问题及其求解方法,解：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分，如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表(表3-26)和单位运价表(表3-27)。,第3节 产销不平衡的运输问题及其求解方法,产销平衡表(表3-26),单位运价表(表3-27),第3节 产销不平衡的运输问题及其求解方法,根据表上作业法计算，可以求得这个问题的最优方案如表3-28所示),