管理运筹学--运输问题.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理运筹学,华国伟,Email:huaguowei,北京交通大学经管学院物流管理系,第三章 运输问题,Transportation Problem,本节内容提要,3.1,运输问题的数学模,3.2,表上作业法,3.1,运输问题的数学模型,A,1,A,i,A,m,产地,产量,销地,B,1,B,j,B,n,销量,例：某运输问题的资料如下：,单位 销地,运价,产地,产量,2,9,10,2,9,1,3,4,2,5,8,4,2,5,7,销量,3,8,4,6,一、运输问题的数学模型,数学模型的一般形式,已知资料如下：,单 销,产 量,产地,产,量,销 量,运价,供需平衡,当产销平衡时，其模型如下：,A,i,的产品全部供应出去,B,j,的需求全部得到满足,产销平衡的运输问题必定存最优解,.,当产大于销时，其模型是：,当产小于销时，其模型是：,m,n,平衡表、运价表和二为一：,约束条件或解可用产销平衡表表示:,u,i,v,j,无约束,（,i=1,2,m;j=1,2,n),u,i,v,j,设,u,i,v,j,为对偶变量，对偶问题模型为,m,个,n,个,特征：,1,、平衡运输问题必有可行解，也必有最优解；,2,、运输问题的基本可行解中应包括,m,+,n,1,个基变量。,.,重复,.,，直到找到最优解为止。,步骤：,.,找出,初始基本可行解,（初始调运方案，一般,m+n-1,个数字格），用西北角法、最小元素法；,.,求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；,.,改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,二、表上作业法,确定,m+n-1,个基变量,空格,3.2,求解运输问题的算法,:,表上作业法,开 始,求各非基变,量的检验数,是否达到最优解,结束,确定换入变量,与换出变量,新的基可行解,求初始基可行解,N,Y,最小元素法，,伏格尔法,闭回路法，,位势法,闭回路调整法,例一、某运输资料如下表所示：,单位 销地,运价,产地,产量,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,1,、求初始方案：,3.2.1,初始基可行解的确定,西北角法,西北角发也就是从运价表的西北角位置开始,依次安排,m,个产地和,n,个销地之间的运输业务,从而得到一个初始调运方案的方法,.,西北角法应遵循“,优先安排运价表上编号最小的产地和销地之间,(,即运价表的西北角位置,),的运输业务,”的规则,.,.,西北角法,(,或左上角法,):,此法是纯粹的人为的规定,没有理论依据和实际背景,但它易操作,特别适合在计算机上编程计算,因而受欢迎,.,方法如下：,总的运费,(3,3),(4,11),(2,9),(2,2),(3,10),(6,5),135,元,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.,初始基可行解的确定,-,最小元素法：,基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,总的运输费用（,3,1,）（,6,4,）,（,4,3,）（,1,2,）（,3,10,）（,3,5,）,86,元,分别计算各行、各列次小、最小运价的差值,优先在最大差值处进行供需搭配,.,差值,=,次小,-,最小,步骤：,1,0,计算未划去行、列的差额,;,2,0,找出最大差额对应的最小元素,c,ij,进行供需分配,;,3,0,在未被划去的行、列重新计算差额,.,(3),初始基可行解的确定,-,最大差值法,(,伏格尔法,)Vogel,6,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,B,1,B,2,B,3,B,4,供量,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量,3,6,5,6,列差值,2,5,1,3,行差值,0,1,1,6,3,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,B,1,B,2,B,3,B,4,行差值,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,2,列差值,2,1,3,3,6,3,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,B,1,B,2,B,3,B,4,行差值,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,列差值,2,1,2,5,1,2,6,3,B,1,B,2,B,3,B,4,差值,A,1,3,11,3,10,7,A,2,1,9,2,8,6,A,3,7,4,10,5,差值,1,2,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,3,9,销量,3,6,5,6,以上方法得到的初始解为基可行解,每次行,(,需求,),或列,(,供应,),达到,饱和,每次必划掉一行或一列,得到的元素个数必为,m,+,n,-1,个,西北角法 最小元素法,最大差值法,练习,P97 3.1,3.2,ij,0,（因为目标函数要求最小化）,表格中有调运量的地方为基变量,空格处为非基变,量,.,基变量的检验数,ij,0,非基变量的检验数,ij,0.,ij,0,表示运费增加,.,2,、最优解的判别（检验数的求法）：,检验数,非基变量增加一个单位目标值的变化,（,1,）闭回路法,闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线,遇到填有运量的方格,可转,90,然后继续前进,直到到达出发的空格所形成的闭合回路,.,调运方案的任意空格存在唯一闭回路,.,销,产,B,1,B,2,B,3,B,4,供量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,差值法方案,一、最优调运方案的判定,3,1,4,6,3,3,最小元素法方案,+,-,+,-,x,11,为换入变量，,x,11,：,0,1,，运费的变化为3,-,1+2,-,3=1。这个变化就是,x,11,的检验数，故,11,=1,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,-1,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,12,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,12,10,4,检验数中有负数，说明原方案不是最优解。,空格,闭回路,检验数,(11),(12),(22),(24),(31),(33),(11)-(13)-(23)-(21)-(11),(12)-(14)-(34)-(32)-(22),(22)-(23)-(13)-(14)-(34)-(32)-(22),(24)-(23)-(13)-(14)-(24),(31)-(34)-(14)-(13)-(23)-(21)-(31),(33)-(34)-(14)-(13)-(33),1,2,1,-1,10,12,检验数还存在,负数,原方案不是最优方案,.,用闭回路求解检验数时,需要给每一个空格找一条闭回路,.,当产销点较多时,该方法较麻烦,.,u,i,v,j,自由变量,（,2,）位势法,标准型运输问题的对偶问题是：,X,B,X,N,X,S,0,C,N,-C,B,B,-1,N,-,C,B,B,-1,-,Y,S1,-,Y,S2,-,Y,检验数,对偶变量值等于原问题的检验数,松弛变量,基变量的检验数为零(,基变量,x,ij,)，,得,m+n,-,1,个方程,含,m+n,个未知数,令某个,u,i,(,或,v,j,)=0,可解出,m+n,个,u,i,和,v,j,;,由此得非基变量的检验数,.,1.,由基变量的检验数为,0,ij,=c,ij,-,(,u,i,+v,j,)=0,u,1,=0(,v,1,=0),得,u,i,v,j,2,.,利用,ij,=c,ij,-,(,u,i,+v,j,),求非基变量的检验数,可令任意的行或列的位势为,0(,任意值均可,为,0,出于计算简单考虑,),3,1,4,6,3,3,位势法,令,v,1,=0,由,c,21,=1=,u,2,+,v,1,，,得,u,2,=1,0,1,1,2,0,1,1,2,8,-3,7,位势表,2,9,8,9,-3,-2,检验数,0,1,1,2,8,-3,7,检验数表,1,2,1,-1,10,12,24,=-10，当前方案 不是最优方案。,1.,以,最小负检验数,为出发点寻找一条闭回路,.,2.,确定调整量,调出格中,最小,的运量,.,2.3,改进的方法,闭回路调整法,二、调运方案的调整,pq,ij,j,i,),(,min,=,b,j,产小于销：,a,i,产量,二、转运问题,出现下列问题：,产地与销地之间没有直达路线，货物由产地到销地必须通过中转站转运；,某些产地可以输入货物，销地也可以输出货物，,产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。,解法：,无转运问题。,根据问题求出最大可能周转量,Q,；,2.,纯转运点,产地：输出量,Q,；,销地：输入量,Q,；,输入,=,输出,3.,兼中转站的产地,A,i,=,销地：输入量,Q,；,产地：输出量,Q+,a,i,；,4.,兼中转站的销地,B,j,=,销地：输入量,b,j,+Q,；,产地：输出量,Q,；,列出各产地的输出量和各销地的输入量及各产销地之间的运价表,用表上作业法求解,.,输出：产地；中转站,(,纯,/,兼,),输入：销地；中转站,(,纯,/,兼,),例 某货物,其产地,A1,的产量为,10,单位,A2,的产量为,2,单位,销地,A3,、,A4,、,A5,的销量分别为,3,单位、,1,单位和,8,单位,其中产地,A2,、销,A4,又可作为中转站,.,同时,货物可通过纯中转站,A6,进行运输,.,各产地、销地及中转站之间的单位物资运价如表所示,试求一个使总运费最省的调运方案,.,销地,产地,A2,A3,A4,A5,A6,A1,2,6,3,1,2,A2,0,3,M,2,4,A4,M,2,0,3,1,A6,1,3,2,7,0,最大可能周转量,Q,=,a,1+,a,2=10+2=12,A1,纯产地,输出量,10;,A2,产地兼中转站,输出量,2+12=14,输入量,12;,A3,纯销地,输入量,3;,A4,销地兼中转站,输出量,12,输入量,1+12=13;,A5,纯销地,输入量,8;,A6,纯中转站,输出量、输入量均为,12.,根据以上情况列产销平衡表,.,销地,产地,A2,A3,A4,A5,A6,输出量,A1,2,6,3,1,2,10,A2,0,3,M,2,4,14,A4,M,2,0,3,1,12,A6,1,3,2,7,0,12,输入量,12,3,13,8,12,48,销地,产地,A2,A3,A4,A5,A6,输出量,A1,1,8,1,10,A2,12,2,14,A4,12,12,A6,1,11,12,输入量,12,3,13,8,12,48,不参加实际调运,3.4,应用举例,搞清“产地、销地”、“运价,”,“产量、需求”,写出,产销平衡表,运输问题的要素,:,未知数如何设,虚设,产地与销地,;,拆分,产地与销地,例,3.,某厂按合同规定须于每个季度末分别提供,10,15,25,20,台同一规格的柴油机,.,已知该厂各季度的生产能力及生产每台柴油机的成本如下表,.,如果生产出来的柴油机当季不交货,每台积压一个季度需储存、维护费用,0.15,万元,.,要求在完成合同的情况下,做出该厂全年费用最小的决策,.,季度,生产能力,单位成本,I,II,III,IV,25,35,30,10,10.8,11.1,11.0,11.3,搞清“产地、销地”、“运价,”,“产量、需求”,写出,产销平衡表,未知数如何设,设,x,ij,为第,i,季度生产的用于第,j,季度交货的柴油机数,.,合同要求：,产量约束：,第,i,季度生产的用于第,j,季度交货的柴油机的实际成本,c,ij,=,生产成本,+,储存维护费用,i,j,I,II,III,IV,I,II,III,IV,10.8,10.95,11.10,11.10,11.25,11.00,11.25,11.40,11.15,11.30,目标函数：,i,j,I,II,III,IV,产量,I,II,III,IV,10.8,M,M,M,10.95,11.10,M,M,11.10,11.25,11.00,M,11.25,11.40,11.15,11.30,25,35,30,10,销量,10,15,25,20,i,j,I,II,III,IV,D,产量,I,II,III,IV,10.8,M,M,M,10.95,11.10,M,M,11.10,11.25,11.00,M,11.25,11.40,11.15,11.30,0,0,0,0,25,35,30,10,销量,10,15,25,20,30,例,:,某玩具公司分别生产三种新型的玩具,每月可供应量分别为,1000,件,2000,件,2000,件，他们分别被送到甲乙丙三个百货商店销售,已知每月百货商店各类玩具预期销售量为,1500,件,由于经营原因,各百货商店销售不同玩具的盈利额不同,又知丙百货商店要求至少供应,C,玩具,1000,件,而拒绝进入,A,种玩具,求满足上述条件下使总盈利额为最大的供销分配方案,.,甲,乙,丙,可供量,A,B,C,5,16,12,4,8,10,-,9,11,1000,2000,2000,C,先满足丙,1000,件,甲,乙,丙,丁,可供量,A,B,C,5,16,12,4,8,10,-,9,11,0,0,0,1000,2000,1000,1500,1500,500,500,甲,乙,丙,丁,可供量,A,B,C,11,0,4,12,8,6,M,7,5,0,0,0,1000,2000,1000,1500,1500,500,500,已知某运输问题的产销平衡表,最优调运方案及单位运价表分别如表所示,由于从产地,2,至销地,B,的道路因故暂时封闭,故需对调运方案进行修正,试用尽可能简单的方法重新找出最优调运方案,.,A,B,C,D,E,产量,1,2,3,3,4,1,4,5,1,3,9,4,8,销量,3,5,4,6,3,A,B,C,D,E,1,2,3,10,2,1,20,10,20,5,10,7,9,30,10,10,6,4,10,变为,M,计算检验数进行调整,已知某运输问题的资料如下表所示,B,1,B,2,B,3,B,4,发量,A,1,2,6,5,3,15,A,2,1,3,2,1,12,A,3,3,2,7,4,13,收量,10,13,12,5,1,、表中的发量、收量单位为：吨，运价单位为：元,/,吨,试求出最优运输方案,.,练习：,2,、如将,A,2,的发量改为,17,，其它资料不变，试求最优调 运方案。,13,A,3,12,A,2,5,10,A,1,B,4,B,3,B,2,B,1,最终的运送方案,总的运费,85,元,/,吨,已知资料如下表所示，问如何供电能使总的输电费用为最小？,发电厂,发电量,A,1,700,A,2,200,A,3,100,城市,需电量,B,1,500,B,2,250,B,3,100,B,4,150,电力供需表,B,1,B,2,B,3,B,4,A,1,10,5,2,3,A,2,4,3,1,2,A,3,5,6,3,4,单位输电费用,作业：,B,1,B,2,B,3,B,4,u,i,A,1,10,5,2,3,0,A,2,4,-1,-4,-3,-6,A,3,5,0,-3,-2,-5,v,j,10,5,2,3,(u,i,+v,j,),B,1,B,2,B,3,B,4,u,i,A,1,0,0,0,0,A,2,0,4,5,5,A,3,0,6,6,6,v,j,ij,-(u,i,+v,j,),=,c,ij,B,1,B,2,B,3,B,4,A,1,200,250,100,150,A,2,200,A,3,100,C=5200,运输问题习题,二、如下所示的运输问题中,如果某一产地有一个单位物资未运出,就将发生存储费用,.,假定三个产地单位物资存储费用分别为,2,2,1,请用最小元素法求初始方案,用位势法调整出最优方案并计算出最优方案的总费用,.,销地,产地,I,II,III,IV,1,7,6,5,50,2,4,8,8,30,3,3,4,5,20,销量,30,20,40,三、某最小费用运输问题的调运方案如下,(,黑体字为运量,):,1.,上述方案是否可作为表上作业法求解时的初始解,?,说明理由,.,2.,如问题,1,的答案为是,请用用位势法进行检验并求出最优方案,.,单位运价,发点,收点,发量,B1,B2,B3,B4,A1,2,45,1,5,5,45,A2,2,2,4,30,1,30,A3,40,1,5,4,25,3,5,2,75,收量,40,50,25,35,四、某公司和供货商,A,、,B,、,C,签订了长期供货合同,按月为位于不同地区的三个下属工厂供应某种原料,三个供货商提供的原料品质基本相同,但由于所处的地理位置、人工成本等导致其实际供货成本有所不同,.,由于一次生产事故，导致最大的供货商,A,下个月的供货量无法全部满足,.,下个月供货商的供应量、工厂的需求量和供货商与工厂之间的供货成本如下表所示,.,公司经紧急协商,在工厂,1,所在地筹措到,100,吨的货源,供货成本为,23,百元,/,吨,;,工厂,2,所在地货源充足,供货成本为,25,百元,/,吨,.,但由于运力紧张两处货源均无法调运到外地,.,鉴于此种情况公司决定要优先保证工厂,1,的全部需求,工厂,3,的需求至少要满足,500,吨,.,该公司面临的问题是应如何协调各供货商和工厂之间的供货关系,才能使总的供货成本最小,.,请为本问题建立适合于应用于表上作业法的产销平衡表,.(,不必计算,),工厂,供货成本,（百元,/,吨）,供货商,1,2,3,供货量,（吨）,A,20,21,19,500,B,18,22,20,300,C,19,20,21,400,需求量（吨）,400,500,700,五、已知某极小化运输问题的有关数据如下表所示,:,表中黑体字为运量。,要求：用位势法计算表中方案的检验数并进行进一步调整。,教育部门认为：划分入学区域界限的适当目标是使学生到学校的平均路程最短。在这个初步计划中，他们要确定为了实现这一目标每一个区域内至少有多少学生要安排到哪一所学校，同时要满足表中最后两行规定的约束条件。,(1),建立该问题的运输问题约束条件,(2),按运输问题的最小元素法给出一个较好的初始分配方案。,