运筹学ch运输问题.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运输问题的表示,网络图、线性规划模型、运输表,初始基础可行解,西北角法、最小元素法,非基变量的检验数,闭回路法、位势法,确定进基变量，调整运量，确定离基变量,第三章 运输问题TransportationProblem,一.运输问题的一般提法,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,典型范例,各工厂应分別运送多少数量至各配送中心，才能使总的运输成本最低？,供给及需求单位：1卡车的量,单位运输成本：千元,工厂,配送中心,供给,W1,W2,W3,W4,P1,6,7,5,3,14,P2,8,4,2,7,27,P3,5,9,10,6,19,需求,22,13,12,13,60,运价表,显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵,(3)产销平衡问题为等式约束.,【证】因为产销平衡，即 ，将前m个约束方程两边相加得,非基变量xij的检验数j位势法求检验(1),ui+vj+ij=cij,iii)在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n1个的需要。,求初始基本可行解的步骤是：,供过于求：即产量大于销量时有,得到这样的平衡表后，计算得到最优方案表5-29。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,初始基础可行解西北角法,设xij(i=1,2,3；,240，从A2 B4）出发其闭回路上=1，调整后得到一个新方案如下表），运量为=1的A2 B3变空格，得到新方案后再转 2。,各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。,ui=i行次小运价i行最小运价,以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。,2,3,2,1,3,4,1,运输问题网络图,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题线性规划模型,供应地约束,需求地约束,设xij(i=1,2,3；j=1,2,3,4)为i个工厂运往第j个配送中心的运量，这样得到下列运输问题的数学模型：,运输问题的表格表示,运输问题的一般提法是：,1.产销平衡问题,知：,m个产地记作A1，A2，A3,Am），其产量分别为a1,a2，am；,n个销地记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即 。,从第i个产地到j 个销地的单位运价为cij，,问：在满足各地需要的前提下，求总运输费用最小的调运方案。即AiBj 的运量xij 使,2.产销不平衡问题,此时分为两种情形来考虑：,供不应求：即产量小于销量时有,供过于求：即产量大于销量时有,二.运输问题的模型,产销平衡问题模型,将约束方程式展开可得,约束方程式中共mn个变量，m+n个约束。,上述模型是一个线性规划问题。但是其结构很特殊，特点如下：,1.变量多mn个），但结构简单。,技术系数矩阵,系数矩阵的特点:(1)约束条件的系数矩阵的元素只有两个:0,1.(2)元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j 个方程中)也出现一次.(3)产销平衡问题为等式约束.(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等.,2.m+n个约束中有一个是多余的因为其间含有一个平衡关系式 ）,所以R(A)=m+n-1，即解的mn个变量中基变量,为m+n-1个。,3.m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。一条回路中的顶点数一定是偶数。,【证】因为产销平衡，即 ，将前m个约束方程两边相加得,再将后n个约束相加得,显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵,【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,中任意m+n阶子式等于零，取第一行到m+n1行与,对应的列共m+n-1列组成的m+n1阶子式,m 行,n 行,故r(A)=m+n1所以运输问题有m+n1个基变量。,为了在mn个变量中找出m+n1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，通常引用闭回路的概念寻找这些基变量。,三.运输问题的解法,运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：,1.运输问题所涉及的变量多，造成单纯 形表太大；,2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。,以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。,运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：,第一步：求初始基行可行解初始调运方案）。常用的方法有最小元素法、元素差额法Vogel近似法）、左上角法。,第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。,第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。,表 上 作 业 法,左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打“”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n1,初始基础可行解西北角法,8,13,13,14,6,6,最小元素法的思想是优先满足单位运价最小的业务，即最小运价Cij 对应的变量xij优先赋值，,然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。,初始基础可行解最小元素法,初始基础可行解最小元素法1）,最小元素法2）,最小元素法3）,最小元素法4）,最小元素法5）,最小元素法6）,初始基础可行解元素差额法,（Vogel近似法）,求初始基本可行解的步骤是：,第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n；,第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行或列的最小运价处优先调运；,第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,12,15,A,2,1,7,2,4,25,A,3,6,10,13,8,20,b,j,20,10,5,25,60,【例】用元素差额法求下表运输问题的初始基本可行解。,【解】求行差额 ui,i=1,2,3及列差额vj,j=1,2,3,4.计算公式为,ui=i行次小运价i行最小运价,vj=j列次小运价j例最小运价,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,5,8,9,12,15,3,A,2,1,7,2,4,25,1,A,3,6,10,13,8,20,2,b,j,20,10,5,25,60,v,j,4,1,7,4,【】,5,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,5,8,9,12,15,3,A,2,1,7,2,4,25,3,5,A,3,6,10,13,8,20,2,b,j,20,10,5,25,60,v,j,4,1,4,20,【】,0,除去B3列，重新计算差额,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,5,8,9,12,15,4,A,2,1,7,2,4,25,5,A,3,6,10,13,8,20,2,b,j,20,10,5,25,60,v,j,2,4,20,0,【】,10,20,5,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优即为最优解）。,求检验数的方法有两种，闭回路法和位势法。,1闭回路法求检验数 求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,第二步，求检验数，判优,5,非基变量xij的检验数cij-zij闭回路法(1),12=c12-z12=c12-(c11-c21+c22)=7-6+8-4=5,5,闭回路法(2),13=c13-z13=c13-c11+c21-c23)=5-6+8-2=5,5,5,闭回路法(3),14=c14-z14=c14-(c11-c21+c21-c23+c33-c34)-=3-(6-8+2-10+6)=7,7,5,5,闭回路法(4),c24-z24=c24-(c23-c33+c34)=7-(2-10+6)=9,9,5,7,5,闭回路法(5),c31-z31=c31-(c21-c23+c33)=5-(8-2+10)=-11,-11,5,7,9,5,闭回路法(6),c32-z32=c32-(c22-c23+c33)=9-(4-2+10)=-3,-3,5,7,9,-11,这里31和 320,得到最优解。,Min z=61+3 13+8 2+4 13+2 12+5 19=142,11,5,5,4,8,2,小结：,运输问题的常用解法：,最小元素法确定初始方案）闭回路法检验当前方案）闭回路法方案调整）,例：某食品公司下设3个加工厂A1，A2，A3，和4个门市部B1，B2，B3，B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。,问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？,门市部加工厂,B,1,B,2,B,3,B,4,产 量,A,1,A,2,A,3,7,4,9,销 量,3 6 5 6,20,门市部加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,3 11 3 10,1 9 2 8,7 4 10 5,产销平衡表 单位：吨,单位运价表 单位：元/吨,解：1.确定初始方案:(最小元素法基本思想：就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，直到给出初始方案为止)从运价表上找出最小运价C21=1，A2 先保证供应B1，X21=3，划去运价表上B1 列；再从运价表上其余元素中找到最小的运价C23=2，加工厂A2 应供给B3，X23=1，划去A2行；再从运价表上其余元素中找到最小的运价C13=3，所以A1先保证供应B3，B3 尚缺4单位，因此X13=4，划去B3 列。,以此类推，得到一初始方案如下图）：,X21=3，X32=6，X13=4，X23=1，X14=3，X34=3有数格）,X11=X31=X12=X22=X33=X24=0空格）,B,1,B,2,B,3,B,4,A,1,4,3,A,2,3,1,A,3,6,3,注：,（）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；,（）如果填上一个运量之后能同时划去两条线一行与一列），就须在所划去的该行或该列填一个0，此0格当有数个对待。,初始方案运费Z0=31+64+43+12+310+35=86(元),2.检验闭回路法:计算空格的检验数）,找出任意空格的闭回路除此空格外，其余顶点均为有数格。如从a11出发可找,（A1 B1）（A1 B3）（A2 B3）（A2 B1）；计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的代数和。,如11c11-c13+c13-c21=3-3+2-1=1计算出此空格的检验数ij,若ij，则该方案为最优方案，否则转；,每一个空格的检验数=奇顶点运费之和 偶顶点运费之和。,B,1,B,2,B,3,B,4,A,1,1,2,4,3,A,2,3,1,1,-1,A,3,10,6,12,3,注：检验数的经济意义，以11为例，空格表示原方案中X11=0,即A1 B1 的运输量为0。若试着运1单位，则这样所引起的总费用的变化恰是11，可见检验数ij的意义是：Ai Bj增运单位所引起的总费用的增量。ij，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在 Ai Bj上增运。,(+1)*3+(-1)*3+(+1)*2+(-1)*1=1,空格检验数,3 11 3 10,1 9 2 8,7 4 10 5,B,1,B,2,B,3,B,4,A,1,1,2,4,3,A,2,3,1,1,-1,A,3,10,6,12,3,24=(+1)*8+(-1)*2+(+1)*3+(-1)*10=-1,表示原方案中X24=0,即A1 B1 的运输量为0。若试着运1单位，引起的总费用减少.,+,+,-,-,3 11 3 10,1 9 2 8,7 4 10 5,从ij 为最小负值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(这才能保证新的平衡)，其中为该空格闭回路中偶数顶点的最小值。240，从A2 B4）出发其闭回路上=1，调整后得到一个新方案如下表），运量为=1的A2 B3变空格，得到新方案后再转 2。,经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。,注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。（保证基变量个数不变）,3,6,1,3,2,5,3.调整:,1,2,9,2,1,12,4表上作业法须注意的问题：,i)在最终调运表中，若有某个空格非基变量的检验数为0时，则表明该运输问题有多重调运方案；,ii)在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列绝对不能同时把行、列划去，否则就不满足圈格=m+n1个的要求，即基变量的个数永远要保持为m+n1个）；,iii)在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n1个的需要。,iv)用最小元素法所得到的初始方案可以不唯一。,（）产销不平衡的运输问题,1.产大于销的情况：,添加松弛变量xin+1,xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即剩余量就地库存,产大于销的产销量表,A1,Am,a1,am,B1,Bn,b1,bn,Bn+1,A1,Am,B1,Bn,C11,0,0,C1n,Cm1,Cmn,产大于销的单位运价表,Bn+1,2.销大于产的情况：,添加松弛变量xm+1j,同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在，cm+1j为0。,销大于产的产销量表,A1,Am,a1,am,B1,Bn,b1,bn,Am+1,A1,Am,B1,Bn,C11,0,0,C1n,Cm1,Cmn,销大于产的单位运价表,Am+1,B1,B2,B3,B4,a,i,A1,5,9,2,3,60,A2,-,4,7,8,40,A3,3,6,4,2,30,A4,4,8,10,11,50,b,j,20,60,35,45,180,160,因为有：,【例】求下列表中极小化运输问题的最优解。,所以是一个产大于销的运输问题。,表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列,这样可得新的运价表：,B1,B2,B3,B4,B5,a,i,A1,5,9,2,3,0,60,A2,M,4,7,8,0,40,A3,3,6,4,2,0,30,A4,4,8,10,11,0,50,b,j,20,60,35,45,20,180,B1,B2,B3,B4,B5,Ai,A1,35,25,60,A2,40,40,A3,10,20,30,A4,20,10,20,50,Bj,20,60,35,45,20,180,下表为计算结果。可看出：产地A4还有20个单位没有运出。,上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,B1,B2,B3,B4,a,i,A1,5,9,2,3,60,A2,-,4,7,8,40,A3,3,6,4,2,30,A4,4,8,10,11,50,b,j,2060,5070,35,45,180,150210,需求量不确定的运输问题,（1总产量为180，B1，B4的最低需求量,20+50+35+45=150，这时属产大于销；,（2B1，B4的最高需求是60+70+35+45=210，这时属销大于产,（3虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,（4将B1与B2各分成两部分 的需求量是20，的需求量是40，的需求量分别是50与20，因此,必须由A1，A4供应，可由 A1、A5供应。,（5上述A5不能供应某需求地的运价用大M表示，A5到 、的运价为零。得到下表的产销平衡表。,先作如下分析：,B,3,B,4,a,i,A1,5,5,9,9,2,3,60,A2,M,M,4,4,7,8,40,A3,3,3,6,6,4,2,30,A4,4,4,8,8,10,11,50,A5,M,0,M,0,M,M,30,b,j,20,40,50,20,35,45,210,得到这样的平衡表后，计算得到最优方案表5-29。,产销平衡表,B3,B4,ai,A1,35,25,60,A2,40,40,A3,0,10,20,30,A4,20,30,50,A5,10,20,30,bj,20,40,50,20,35,45,210,表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型,看一个例子：,【例】有三台机床加工三种零件，计划第i台的生产任务为a i (i=1,2,3)个零件，第j 种零件的需要量为bj (j=1,2,3)，第i 台机床加工第j 种零件需要的时间为cij，如表32所示。问如何安排生产任务使总的加工时间最少？,零件,机床,B1,B2,B3,生产任务,A1,5,2,3,50,A2,6,4,1,60,A3,7,3,4,40,需要量,70,30,50,150,表32,5,2,3,50,6,4,1,60,7,3,4,40,70,30,50,150,50,30,20,10,40,确定初始基可行解,5,2,3,50,6,4,1,60,7,3,4,40,70,30,50,150,50,30,20,10,40,3,1,2,-1,计算空格的检验数,320,初始基可行解非优.,X32进基,min(30,40)=30,x12出基,5,2,3,50,6,4,1,60,7,3,4,40,70,30,50,150,50,30,50,10,10,3,2,2,1,调整量=30,调整x32,x31,x11,x12,计算新的可行解的空格检验数,全大于零,为最优,DF公司在接下来的三个月内每月都要按照销售合同生产出两种产品。表中给出了在正常时间Regular Time，缩写为RT和加班时间Over Time，缩写为OT内能够生产这两种产品的总数。,月,最大生产总量,产品1/产品2,销售,产品1/产品2,单位生产成本(1000元/件),单位储存成本（1000元/件）,RT,OT,RT,OT,1,2,3,10,8,10,3,2,3,5/3,3/5,4/4,15/16,17/15,19/17,18/20,20/18,22/22,1/2,2/1,（1对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解,（2建立总成本最小的数学模型并求出最优解,作 业,谢谢观看,