03运筹学-运输问题.ppt

1,3.1运输问题及其数学模型3.2运输问题的求解-表上作业法3.3产销不平衡的运输问题3.4运输问题应用,第三章运输问题,2,3.1、运输问题模型及其数学模型,问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,3,单位运价表,产销平衡表,运输表,调运方案,4,5,(1)(2),6,特征：1、平衡运输问题必有可行解，也必有最优解；2、运输问题的基本可行解中应包括m+n1个基变量。,7,例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问应如何调运，可使得总运输费最小?,8,解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3；j=1，2，3，4）,所以此运输问题的线性规划模型如下：Minf=3x11+11x12+3x13+10 x14+x21+9x22+2x23+8x24+7x31+4x32+10 x33+5x34,9,s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x24=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij0(i=1、2、3；j=1、2、3,10,其系数矩阵为：,共有m+n行，分别表示产地和销地；有mn列分别表示各变量；每列只有两个1，其余为0。,X11X12X13X14X21X22X23X24X31X32X33X34,11,一般运输问题的提法：假设A1、A2、Am表示某物资的m个产地；B1、B2、Bn表示某物资的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。如果a1+a2+am=b1+b2+bn，则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论产销平衡问题。,12,在实际问题建模时，还会出现如下一些变化：有时目标函数求最大，如求利润最大或营业额最大等；当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在产量约束条件中加上m个松弛变量；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在需求约束条件中减去n个松弛变量。,13,运输问题求解的有关概念,(1)基变量的特点：基变量共有m+n-1个，产销平衡问题总有可行解，也总有最优解。,得出运输问题的一个基可行解后，将基变量的值xij填入运输表相应的格内，称为基格（含0）；非基变量对应的格不填入数字，称为空格。,（2）产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路.,14,定义3.1决策变量格凡是能够排列成下列形式,xab,xac,xdc，xde,xst,xsb（3.1）或xab,xcb,xcd,xed,xst,xat(3.2),其中，a,d,s各不相同；b,c,t各不相同。我们称之为变量集合的一个闭回路，并将式（3.1）、（3.2）中的变量称为这个闭回路的顶点。,15,等都是闭回路，若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：,例如：,16,闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。,根据定义可以看出闭回路的一些明显特点:：,17,若变量组xab,xcd,xef,xst中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量pab,pcd,pef,pst线性相关,关于闭回路有如下的一些重要结论：,设xab,xac,xdc,xde,xst,xsb是一个闭回路，那么该闭回路中变量所对应的系数列向量pab,pac,pdc,pde,pst,psb线性相关；,18,定理3.1变量组xab,xcd,xef,xst所对应的系数列向量pab,pcd,pef,pst线性无关的充分必要条件是这个变量组中不包含闭回路。,推论产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是它不含闭回路。,19,运输问题的求解思路,20,计算步骤：,(1)找出初始调运方案。即在(mn)产销平衡表上给出m+n-1个数字格。(最小元素法、西北角法或伏格尔法）,(2)求检验数。（闭回路法、位势法或加减法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。,(3)对方案进行改善，找出新的调运方案。（表上闭回路法调整）,确定m+n-1个基变量,(4)重复（2）、（3），直到求得最优调运方案。,空格,3.2运输问题求解表上作业法,21,表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。,22,例3.2某运输资料如下表所示：,问：应如何调运可使总运输费用最小？,1、求初始方案：最小元素法、西北角法、伏格尔法,23,基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,3,11,3,10,1,9,2,7,4,10,5,8,总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元,方法1：最小元素法,3,4,1,6,3,3,24,练习,12,13,13,19,1,2,25,方法2：西北角法（或左上角法）,此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：,3656,749,3,449,0656,4,049,0256,2,029,0056,2,009,0036,36,0000,000,340002200036,26,在满足约束条件下尽可能的给最左上角的变量最大值.,8,8,6,4,8,14,所以，初始基可行解为：(8,8,4,8,14)目标函数值Z372,例3.3某运输资料如下表所示：,27,练习,8,13,13,14,6,6,28,最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。例如下面两种运输方案。,最小元素法：,总运费是z=108+52+151=105,另一种方法：,总运费z=105+152+51=85,29,方法3：Vogel法,1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,10-3=7,2-1=1,5-4=1,3-1=2,9-4=5,3-2=1,8-5=3,30,2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。,3,11,3,10,1,9,2,7,4,10,5,8,5,31,7,1,3,5,2,7,5,3,32,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费:(13)(46)(35)(210)(18)(35)85元,33,14,所以，初始基可行解为：目标函数值Z244,例3.4某运输资料如下表所示：,34,14,所以，初始基可行解为：目标函数值Z244,8,例3.4某运输资料如下表所示：,35,14,所以，初始基可行解为：目标函数值Z244,8,8,例3.4某运输资料如下表所示：,36,14,所以，初始基可行解为：目标函数值Z244,8,8,例3.4某运输资料如下表所示：,12,37,14,所以，初始基可行解为：目标函数值Z244,8,8,例3.4某运输资料如下表所示：,12,2,4,38,产销平衡表,运价表,2513,011,6,012,3,212,3,76,5,1,2,39,练习,1,2,13,12,13,19,40,2、最优解的判别（检验数的求法）,求检验数的方法有三种：闭回路法位势法加减法,（1）闭合回路法：ij0（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数ij0，非基变量的检验数ij0。,ij0表示运费增加。,41,方法1闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。,调运方案的任意空格存在唯一闭回路。,注：1.每一空格有且仅有一条闭回路；2.如果某数字格有闭回路，则此解不是可行解。,若令则,运费的增量,分析：,42,以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。则解的变化和目标函数的变化如何。,43,要保证产销平衡，则,称为闭回路,1,44,1,2,45,1,2,1,46,10,2,1,1,47,1,2,1,12,10,48,1,2,1,-1,12,10,检验数中有负数，说明原方案不是最优解。,49,练习,5,5,7,9,-3,-11,闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算都会产生困难。,50,ui,vj,m个,n个,方法2对偶变量法（位势法）,设其对偶变量为：,51,uivj无约束（i=1,2,m;j=1,2,n),标准型运输问题的对偶问题模型为：,则运输问题变量xij的检验数为：,52,用位势法对初始方案进行最优性检验的方法：,1）在给定初始解的表上增加一行和一列，在列中填入ui，在行中填入vj。,2）令u10，再按cij-(ui+vj)=0（基变量的cij求出其余的ui与vj。,3）由ij=Cij-（ui+vj），求出非基变量的检验数。,53,3,11,3,10,1,9,2,7,4,10,5,8,u1,u2,u3,v3,v4,v1,v2,注意：基变量的检验数ij=Cij-（ui+vj）=0,4,3,6,3,1,3,54,3,11,3,10,1,9,2,7,4,10,5,8,0,-1,-5,3,10,2,9,令u1=0,u1+v3=3,u1+v4=10,u2+v3=2,u2+v1=1,u3+v2=4,u3+v4=5,4,3,6,3,1,3,55,2,4,3,6,3,1,3,（1）,（2）,（1）,（-1）,（10）,（12）,当存在非基变量的检验数ij0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,注意：非基变量的检验数ij=cij-（ui+vj）,11=c11-（u1+v1）=3-(0+2)=1,31=c31-（u3+v1）=7-(2-5)=10,24=c24-（u2+v4）=8-(10-1)=-1,22=c22-（u2+v2）=9-(9-1)=1,12=c12-（u1+v2）=11-(0+9)=2,33=c33-（u3+v3）=10-(3-5)=12,3,11,3,10,1,9,2,7,4,10,5,8,56,u1+v4=c14=10u1+v3=c13=3u2+v1=c21=1u2+v3=c23=2u3+v2=c32=4u3+v4=c34=5,令u1=5则有v4=5,v3=-2,u2=4,u3=0,v2=4,v1=-3,再求检验数：,11=c11u1-v1=35(-3)=1,12=c12u1v2=1154=2,22=c22u2v2=944=1,24=c24u2v4=845=-1,31=c31u3-v1=70(-3)=10,33=c33u3v3=100(-2)=12,57,方法3加减法,在运价表中，每行或每列的元素加上或减去一个数，使基变量对应的运价变成零。所得各数即为检验数。,-3,-7,+2,-6,-2,+1,58,3、解的改进闭合回路调整法（原理同单纯形法一样）,当在表中空格处出现负检验数时，表明未得最优解。若有两个或两个以上的负检验数时，一般选用其中最小的负检验数，以它对应的空格为调入格，即以它对应的非基变量为换入变量。做一闭合回路。,(1)确定换入基的变量：当存在非基变量的检验数kl0且kl=minij时，以Xkl为换入变量，找出它在运输表中的闭合回路。,接上例：,解的改进的具体步骤：,59,2,4,3,6,3,1,3,3,11,3,10,1,9,2,7,4,10,5,8,（1）,（2）,（1）,（-1）,（10）,（12）,(2)顶点编号：以空格(Ak,Bl)(或进基变量xik）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。,1,3,2,4,60,2,4,3,6,3,1,3,3,11,3,10,1,9,2,7,4,10,5,8,（1）,（2）,（1）,（-1）,（10）,（12）,(2)顶点编号：以空格(Ak,Bl)(或进基变量xik）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。,1,3,2,4,换出变量X23,61,(3)确定换出基的变量：在该闭回路上，从所有偶数号格点的调运量中选出最小值的顶点（格子），以该格子中的变量为换出变量。,(4)确定新的运输方案：以换出变量的运输量为调整量，将该闭回路上所有奇数号格的调运量加上调整量，所有偶数号格的调运量减去，其余的不变，这样就得到一个新的调运方案。该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。,(5)然后，再对得到的新解进行最优性检验，加不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。,62,2,3,6,3,1,(1),(1),(1),(1),3,11,3,10,1,9,2,7,4,10,5,8,4,3,63,3,10,3,9,vj,-5,A3,-2,A2,0,A1,ui,B4,B3,B2,B1,5,3,6,3,1,2,3,11,3,10,1,9,2,7,4,10,5,8,重新求所有非基变量的检验数：,64,3,10,3,9,vj,-5,A3,-2,A2,0,A1,ui,B4,B3,B2,B1,5,3,6,3,1,2,（2）,（2）,（1）,（12）,（9）,（0）,当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：Z=(13)(46)(35)(210)(18)(35)85元,3,11,3,10,1,9,2,7,4,10,5,8,65,新的基本可行解求解回顾,(1)找闭回路：以最小的负检验数对应的非基变量为起始顶点寻找一个闭回路。,(2)求调整量：闭回路上偶数次顶点运量的最小值为调整量，记作：,(3)调整：闭回路上的偶数次顶点的调运量减去；闭回路上的奇数次顶点的调运量加上；非闭回路顶点的其他变量调运量不变；再去掉闭回路上的一个零运量。,66,24=-1，作x24的闭回路，,调整数=1，调整得,67,-3,-7,+2,-6,-1,求调整数得：,所有的检验数均为非负，因此得到最优解：,x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余的xij=0,上例中11检验数是0，经过调整，可得到另一个最优解。,68,69,-7,-6,所有的检验数均为非负，因此得到最优解：,x11=2,x13=5,x21=1,x24=3,x32=6,x34=3,其余的xij=0,最优解为,70,总运费为：f=32+35+11+83+46+53=85。,如果非基变量的检验数有等于零的时候，将出现多解的情况。上面的例题是多解情况。,71,4、表上作业法计算中的问题：,（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。（2）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。,如上例：11的检验数是0，经过调整，可得到另一个最优解。,72,退化解：表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在同时划去的行和列的任意空格处加一个0即可。利用入基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量，选择任意一个最小运量对应的基变量作为出基变量，并打上“”以示作为非基变量。,73,11,4,4,3,1,3,7,7,8,2,10,6,3,4,1,6,0,6,在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34,例3.5：用最小元素法求初始可行解,74,5、表上作业法小结,得最优方案算出运费,否,75,当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,当产大于销时，即：,数学模型为：,3.3、产销不平衡问题的处理,76,由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,77,当销大于产时，即：,数学模型为：,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：,78,销大于产化为平衡问题的数学模型为：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,79,例3.6求下列表中极小化运输问题的最优解。,因为有：,80,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。,注：按最小元素法求解初始解时，应最后考虑库存。为什么？,81,下表为计算结果。可看出：产地A4还有20个单位没有运出。,用前面的方法求运输方案：,82,例3.7某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。由各造纸厂到各用户的单位运价如表所示，请确定总运费最少的调运方案。,83,解：由于总产量22大于总销量18，故本问题是个产销不平衡运输问题。增加一假想销地B5，用表上作业法求解。,84,85,3.4运输问题的应用,由于在变量相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。,86,例3.8由n个地区需要某种物资，需要量分别不少于bj（j=1,n）。这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别不大于ai（i=1,m）,已知从第i个地区至第j个需求地区单位物资的运价为cij，又，试写出其对偶问题，并解释对偶变量的经济意义。,87,解：由题给出的条件，数学模型可写为:,对偶问题可写为：,88,对偶变量ui的经济意义为在i产地单位物资的价格，vj的经济意义为在第j销地单位物资的价格。对偶问题的经济意义为：如该公司欲自己将该种物资运至各地销售，其差价不能超过两地之间的运价（否则买主将在i地购买自己运至j地），在此条件下，希望获利为最大。,89,例3.9已知资料如下表所示，问如何供电能使总的输电费用为最小？,电力供需表,单位输电费用,90,初始方案,单位输电费用,电力供需表,91,ij,-(ui+vj),=,cij,(ui+vj),92,成本表,(ui+vj),调运方案,93,ij=cij-(ui+vj),成本表,调运方案,94,(ui+vj),C=5200,ij=cij-(ui+vj),95,例3.10有A1、A2、A3三个生产某种物资的产地，五个地区B1、B2、B3、B4、B5对这种物资有需求。现要将这种物资从三个产地运往五个需求地区，各产地的产量、各需求地区的需要量和各产地运往各地区每单位物资的运费如下表所示，其中B2地区的115个单位必须满足。问：应如何调运可使总运输费用最小？,96,运输费用及产量、需求量表,97,解：由于产量小于需求量，因此设一虚设产地A4,它的产量为需求量与产量的差20，与这一项有关的运输费用一般为零。因为B2地区的115个单位必须满足，即不能有物资从A4运往B2地区，于是取相应的费用为M（M是一个充分大的正数），以保证在求最小运输费用的前提下，该变量的值为零。,98,可以建立如下产销平衡的运输费用表,70,30,60,115,25,需求,20,0,0,0,M,0,A4,130,25,55,40,35,30,A3,100,30,30,15,40,20,A2,50,40,20,20,15,10,A1,产量,B5,B4,B3,B2,B1,销地产地,99,例3.11某研究院有B1、B2、B3三个区。每年取暖分别需要用煤3500吨、1100吨、2400吨，这些煤都要由A1、A2两处煤矿负责供应，价格、质量均相同。A1、A2煤矿的供应能力分别为1500吨、4000吨，运价（元/吨）如下表。由于需求大于供给，经院研究决定B1区供应量可减少0900吨，B2区必须满足需求量，B3区供应量不少于1600吨，试求总费用为最低的调运方案。,100,解：这是需求量大于生产量的运输问题，由于B1区供应量可减少0900吨，B2区必须满足需求量，B3区供应量不少于1600,101,吨，可以把B1区和B3区分别设为两个区：一个为必须满足需求量的区域，另一个为可以调整供应量的区域。这样，原问题化为五个需求区域B1、B1、B2、B3、B3的问题，同时增加一个虚设的产地A3。在运输费方面,必须满足需求量的相应变量，运费的取值为M，可调整需求量的相应变量，运费的取值为0，作出产销平衡的运价表,102,800,0,215,208,B3*,900,0,160,175,B1*,1600,1100,2600,需求量,1500,M,M,M,A3,4000,215,182,160,A2,1500,208,195,175,A1,产量,B3,B2,B1,销地产地,计算过程从略,103,例3.12某公司生产某种规格的设备，由于生产与季节有关系，生产能力与成本有差异，如下表所示。,某种规格设备各季节的生产能力与成本,104,该厂年初签订的合同规定：当年一、二、三、四每个季度末分别需要提供200、300、500、400台这种规格的设备。如果生产出来的设备当季不交货，每台每积压一个季度需储存、维护等费用为0.15万元。试求在完成合同的前提下，使该厂全年生产总费用为最小的决策方案。,105,解：设xij为第i季度生产的第j季度交货的设备数目，则问题的线性规划模型为：,cij=第i季度每台的生产成本+0.15(j-i)（储存、维护等费用）。计算可得：,c11=9.8,c12=9.95,c13=10.1,c14=10.25,c22=10.5,c23=10.65,c24=10.8,c33=10.3,c34=10.45,c44=10.6。,106,于是得到目标函数：,Minf=9.8x11+9.95x12+10.1x13+10.25x14+10.5x22+10.65x23+10.8x24+10.3x33+10.45x34+10.6x44,x11=200 x12+x22=300 x13+x23+x33=500 x14+x24+x34+x