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

管理运筹学,华国伟Email:huaguowei北京交通大学经管学院物流管理系,第三章运输问题TransportationProblem,本节内容提要,3.1运输问题的数学模3.2表上作业法,3.1运输问题的数学模型,A1,Ai,Am,产地,产量,销地,B1,Bj,Bn,销量,例：某运输问题的资料如下：,一、运输问题的数学模型,数学模型的一般形式已知资料如下：,供需平衡,当产销平衡时，其模型如下：,Ai的产品全部供应出去,Bj的需求全部得到满足,产销平衡的运输问题必定存最优解.,当产大于销时，其模型是：,当产小于销时，其模型是：,m,n,平衡表、运价表和二为一：,约束条件或解可用产销平衡表表示:,uivj无约束（i=1,2,m;j=1,2,n),ui,vj,设ui,vj为对偶变量，对偶问题模型为,m个,n个,特征：1、平衡运输问题必有可行解，也必有最优解；2、运输问题的基本可行解中应包括m+n1个基变量。,.重复.，直到找到最优解为止。,步骤：,.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；,.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；,.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,二、表上作业法,确定m+n-1个基变量,空格,3.2求解运输问题的算法:表上作业法,开始,求各非基变量的检验数,是否达到最优解,结束,确定换入变量与换出变量,新的基可行解,求初始基可行解,N,Y,最小元素法，伏格尔法,闭回路法，位势法,闭回路调整法,例一、某运输资料如下表所示：,1、求初始方案：,3.2.1初始基可行解的确定西北角法,西北角发也就是从运价表的西北角位置开始,依次安排m个产地和n个销地之间的运输业务,从而得到一个初始调运方案的方法.西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则.,.西北角法(或左上角法):此法是纯粹的人为的规定,没有理论依据和实际背景,但它易操作,特别适合在计算机上编程计算,因而受欢迎.方法如下：,总的运费(33)(411)(29)(22)(310)(65)135元,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.初始基可行解的确定-最小元素法：基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,总的运输费用（31）（64）（43）（12）（310）（35）86元,分别计算各行、各列次小、最小运价的差值,优先在最大差值处进行供需搭配.差值=次小-最小,步骤：,10计算未划去行、列的差额;,20找出最大差额对应的最小元素cij进行供需分配;,30在未被划去的行、列重新计算差额.,(3)初始基可行解的确定-最大差值法(伏格尔法)Vogel,6,行差值,0,1,1,6,3,3,6,3,5,1,2,6,3,以上方法得到的初始解为基可行解每次行(需求)或列(供应)达到饱和每次必划掉一行或一列得到的元素个数必为m+n-1个西北角法最小元素法最大差值法,练习,P973.13.2,ij0（因为目标函数要求最小化）表格中有调运量的地方为基变量,空格处为非基变量.基变量的检验数ij0,非基变量的检验数ij0.ij0表示运费增加.,2、最优解的判别（检验数的求法）：,非基变量增加一个单位目标值的变化,闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线,遇到填有运量的方格可转90,然后继续前进,直到到达出发的空格所形成的闭合回路.,调运方案的任意空格存在唯一闭回路.,差值法方案,一、最优调运方案的判定,最小元素法方案,+,-,+,-,x11为换入变量，x11：01，运费的变化为3-1+2-3=1。这个变化就是x11的检验数，故11=1,3,1,3,6,3,1,2,4,3,1,3,6,3,1,2,-1,4,3,1,3,6,3,1,2,1,-1,4,3,1,3,6,3,1,2,1,-1,12,4,3,1,3,6,3,1,2,1,-1,12,10,4,检验数中有负数，说明原方案不是最优解。,检验数还存在负数,原方案不是最优方案.,用闭回路求解检验数时,需要给每一个空格找一条闭回路.当产销点较多时,该方法较麻烦.,ui,vj自由变量,（2）位势法标准型运输问题的对偶问题是：,检验数,对偶变量值等于原问题的检验数,松弛变量,基变量的检验数为零(基变量xij)，,得m+n-1个方程,含m+n个未知数,令某个ui(或vj)=0,可解出m+n个ui和vj;由此得非基变量的检验数.,1.由基变量的检验数为0,ij=cij-(ui+vj)=0,u1=0(v1=0),得ui,vj2.利用ij=cij-(ui+vj),求非基变量的检验数可令任意的行或列的位势为0(任意值均可,为0出于计算简单考虑),位势法,令v1=0,由c21=1=u2+v1，得u2=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改进的方法闭回路调整法,从(p,q)空格开始画闭回路,其它转角点都是填有运量的方格,并从(p,q)空格开始给闭回路上的点按+1,-1,+1,-1编号，-1格的最小运量为调整量.,换出变量,运价,新的调运方案为：,或者直接算,7,1,3,4,9,11,10,2,3,10,8,5,运输问题的求解表上作业法步骤小结,第一步:确定初始基可行解（可行调运方案）方法：最小元素法与伏格尔法第二步:判别当前可行方案是否最优方法：闭回路法与位势法第三步:对现有方案进行调整方法：闭回路法,3.2.4表上作业法计算中的问题,无穷多最优解某非基变量(空格)的检验数为0.退化方案点数=产地数+销地数1;同时去掉一行和一列时应添加0方案;调整时出现两个或两个以上的最小值,新方案中也要添加0方案.,.无穷多最优解：产销平衡的运输问题必定存最优解.如果非基变量的ij0,则该问题有无穷多最优解.如上例:(1.1)中的检验数是0,经过调整,可得到另一个最优解.,4、表上作业法计算中的问题,.退化:表格中一般要有(m+n-1)个数字格.但有时,在分配运量时则需要同时划去一行和一列,这时需要补一个0,以保证有(m+n-1)个数字格.一般可在划去的行和列的任意空格处加一个0即可.,正常时一次只划掉同时划掉了一行和一列此时同时划掉一行和一列,不要补零,例1：,213552682176,例2：,0,0,0,4运输问题的扩展,本节重点,供需不平衡的运输问题,转运问题,运输问题的分类,产销平衡问题：ai=bj产销不平衡问题：,产大于销：aibj,产小于销：ai产量,二、转运问题,出现下列问题：产地与销地之间没有直达路线，货物由产地到销地必须通过中转站转运；某些产地可以输入货物，销地也可以输出货物，产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。,解法：,根据问题求出最大可能周转量Q；,3.兼中转站的产地Ai=,4.兼中转站的销地Bj=,列出各产地的输出量和各销地的输入量及各产销地之间的运价表,用表上作业法求解.,输出：产地；中转站(纯/兼)输入：销地；中转站(纯/兼),例某货物,其产地A1的产量为10单位,A2的产量为2单位,销地A3、A4、A5的销量分别为3单位、1单位和8单位,其中产地A2、销A4又可作为中转站.同时,货物可通过纯中转站A6进行运输.各产地、销地及中转站之间的单位物资运价如表所示,试求一个使总运费最省的调运方案.,最大可能周转量Q=a1+a2=10+2=12,A1纯产地,输出量10;A2产地兼中转站,输出量2+12=14,输入量12;A3纯销地,输入量3;A4销地兼中转站,输出量12,输入量1+12=13;A5纯销地,输入量8;A6纯中转站,输出量、输入量均为12.根据以上情况列产销平衡表.,不参加实际调运,3.4应用举例,搞清“产地、销地”、“运价”,“产量、需求”,写出产销平衡表,运输问题的要素:,未知数如何设,虚设产地与销地;拆分产地与销地,例3.某厂按合同规定须于每个季度末分别提供10,15,25,20台同一规格的柴油机.已知该厂各季度的生产能力及生产每台柴油机的成本如下表.如果生产出来的柴油机当季不交货,每台积压一个季度需储存、维护费用0.15万元.要求在完成合同的情况下,做出该厂全年费用最小的决策.,搞清“产地、销地”、“运价”,“产量、需求”,写出产销平衡表,未知数如何设,设xij为第i季度生产的用于第j季度交货的柴油机数.,合同要求：,产量约束：,第i季度生产的用于第j季度交货的柴油机的实际成本cij=生产成本+储存维护费用,目标函数：,例:某玩具公司分别生产三种新型的玩具,每月可供应量分别为1000件,2000件,2000件，他们分别被送到甲乙丙三个百货商店销售,已知每月百货商店各类玩具预期销售量为1500件,由于经营原因,各百货商店销售不同玩具的盈利额不同,又知丙百货商店要求至少供应C玩具1000件,而拒绝进入A种玩具,求满足上述条件下使总盈利额为最大的供销分配方案.,C先满足丙1000件,已知某运输问题的产销平衡表,最优调运方案及单位运价表分别如表所示,由于从产地2至销地B的道路因故暂时封闭,故需对调运方案进行修正,试用尽可能简单的方法重新找出最优调运方案.,10变为M,计算检验数进行调整,已知某运输问题的资料如下表所示,1、表中的发量、收量单位为：吨，运价单位为：元/吨试求出最优运输方案.,练习：,2、如将A2的发量改为17，其它资料不变，试求最优调运方案。,已知资料如下表所示，问如何供电能使总的输电费用为最小？,电力供需表,单位输电费用,作业：,(ui+vj),ij,-(ui+vj),=,cij,C=5200,运输问题习题,二、如下所示的运输问题中,如果某一产地有一个单位物资未运出,就将发生存储费用.假定三个产地单位物资存储费用分别为2,2,1,请用最小元素法求初始方案,用位势法调整出最优方案并计算出最优方案的总费用.,三、某最小费用运输问题的调运方案如下(黑体字为运量):1.上述方案是否可作为表上作业法求解时的初始解?说明理由.2.如问题1的答案为是,请用用位势法进行检验并求出最优方案.,单位运价,四、某公司和供货商A、B、C签订了长期供货合同,按月为位于不同地区的三个下属工厂供应某种原料,三个供货商提供的原料品质基本相同,但由于所处的地理位置、人工成本等导致其实际供货成本有所不同.由于一次生产事故，导致最大的供货商A下个月的供货量无法全部满足.下个月供货商的供应量、工厂的需求量和供货商与工厂之间的供货成本如下表所示.公司经紧急协商,在工厂1所在地筹措到100吨的货源,供货成本为23百元/吨;工厂2所在地货源充足,供货成本为25百元/吨.但由于运力紧张两处货源均无法调运到外地.鉴于此种情况公司决定要优先保证工厂1的全部需求,工厂3的需求至少要满足500吨.该公司面临的问题是应如何协调各供货商和工厂之间的供货关系,才能使