《管理运筹学-运输问题.ppt》由会员分享，可在线阅读，更多相关《管理运筹学-运输问题.ppt（119页珍藏版）》请在三一办公上搜索。
1、管理运筹学,华国伟北京交通大学经管学院物流管理系,第三章 运输问题 Transportation Problem,本节内容提要,3.1 运输问题的数学模 3.2 表上作业法,3.1 运输问题的数学模型,A1,Ai,Am,产地,产量,销地,B1,Bj,Bn,销量,例：某运输问题的资料如下：,一、运输问题的数学模型,数学模型的一般形式 已知资料如下：,供需平衡,当产销平衡时，其模型如下：,Ai的产品全部供应出去,Bj的需求全部得到满足,产销平衡的运输问题必定存最优解.,当产大于销时，其模型是：,当产小于销时，其模型是：,m,n,平衡表、运价表和二为一：,约束条件或解可用产销平衡表表示:,uivj无
2、约束（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 求解运输问题的算法:表上作业法,开 始,求各非基变
3、量的检验数,是否达到最优解,结束,确定换入变量与换出变量,新的基可行解,求初始基可行解,N,Y,最小元素法，伏格尔法,闭回路法，位势法,闭回路调整法,例一、某运输资料如下表所示：,1、求初始方案：,初始基可行解的确定西北角法,西北角发也就是从运价表的西北角位置开始,依次安排m个产地和n个销地之间的运输业务,从而得到一个初始调运方案的方法.西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则.,.西北角法(或左上角法):此法是纯粹的人为的规定,没有理论依据和实际背景,但它易操作,特别适合在计算机上编程计算,因而受欢迎.方法如下：,总的运费(33)(4
4、11)(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,
5、6,行差值,0,1,1,6,3,3,6,3,5,1,2,6,3,以上方法得到的初始解为基可行解每次行(需求)或列(供应)达到饱和每次必划掉一行或一列得到的元素个数必为m+n-1个西北角法 最小元素法 最大差值法,练习,P97 3.1 3.2,ij0（因为目标函数要求最小化）表格中有调运量的地方为基变量,空格处为非基变 量.基变量的检验数ij0,非基变量的检验数ij0.ij 0 表示运费增加.,2、最优解的判别（检验数的求法）：,非基变量增加一个单位目标值的变化,闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线,遇到填有运量的方格可转90,然后继续前进,直到到达出发的空格所形成的闭合回路
6、.,调运方案的任意空格存在唯一闭回路.,差值法方案,一、最优调运方案的判定,最小元素法方案,+,-,+,-,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,v
7、j自由变量,（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
8、,-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,运输问题的求解表上作业法步骤小结,第一步:确定初始基可行解（可行调运方案）方法：最小元素法与伏格尔法第
9、二步:判别当前可行方案是否最优 方法：闭回路法与位势法第三步:对现有方案进行调整 方法：闭回路法,3.2.4 表上作业法计算中的问题,无穷多最优解 某非基变量(空格)的检验数为0.退化方案点数=产地数+销地数1;同时去掉一行和一列时应添加0方案;调整时出现两个或两个以上的最小值,新方案中也要添加0方案.,.无穷多最优解：产销平衡的运输问题必定存最优解.如果非基变量的ij0,则该问题有无穷多最优解.如上例:(1.1)中的检验数是 0,经过调整,可得到另一个最优解.,4、表上作业法计算中的问题,.退化:表格中一般要有(m+n-1)个数字格.但有时,在分配运量时则需要同时划去一行和一列,这时需要补一
10、个0,以保证有(m+n-1)个数字格.一般可在划去的行和列的任意空格处加一个 0 即可.,正常时一次只划掉同时划掉了一行和一列此时同时划掉一行和一列,不要补零,例1：,2 1 3 5 5 2 6 82 1 7 6,例2：,0,0,0,4 运输问题的扩展,本节重点,供需不平衡的运输问题,转运问题,运输问题的分类,产销平衡问题：ai=bj产销不平衡问题：,产大于销：ai bj,产小于销：ai bj,供需不平衡-虚设产地、销地,产大于销时增加一个虚拟的销售点,其销量为产销的差额,各产地到该销地的单位运价为0.销大于产时增加一个虚拟的产地,其产量为产销的差额,该产地到各销地的单位运价为0.,1.产大于
11、销：,模型：,运输表：,实际意义：虚设一个销地,运价为零,2.产小于销：,模型：,运输表：,实际意义：虚设一 个产地,运价为零,一、供需不平衡的运输问题,1、供不应求的运输问题,虚设一个供应地，其虚供应量为供不应求部分。,虚设一个供应地A3，其供应量=130-110=20,0 0 0,用最小元素法或差值法求初始方案。,例.甲、乙、丙三个城市今年冬季分别需要煤炭320、250、350万吨,由A、B两处煤矿负责供应.已知煤炭年供应量为A400万吨,B450万吨.由各煤矿至各城市的单位运价(万元/万吨)如下.,由于需大于供,经研究决定,甲城市供应量可减少030万吨,乙城市需要量应全部满足,丙城市供应
12、量不少于270万吨,试求将供应量分配完又使总运费最低的调运方案.,拆分需求刚需与弹性需求,甲：供应量可减少030万吨，乙城市全部满足，丙城市供应量不少于270万吨。,甲：供应量可减少030万吨，乙城市全部满足，丙城市供应量不少于270万吨。,1521,2216,M,M,M,0,0,最高需求产量,二、转运问题,出现下列问题：产地与销地之间没有直达路线，货物由产地到销地必须通过中转站转运；某些产地可以输入货物，销地也可以输出货物，产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。,解法：,根据问题求出最大可能周转量Q；,3.兼中转站的产地Ai=,4.兼中转站的销地B
13、j=,列出各产地的输出量和各销地的输入量及各产销地之间的运价表,用表上作业法求解.,输出：产地；中转站(纯/兼)输入：销地；中转站(纯/兼),例 某货物,其产地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,输入量
14、1+12=13;A5纯销地,输入量8;A6纯中转站,输出量、输入量均为12.根据以上情况列产销平衡表.,不参加实际调运,3.4 应用举例,搞清“产地、销地”、“运价”,“产量、需求”,写出产销平衡表,运输问题的要素:,未知数如何设,虚设产地与销地;拆分产地与销地,例 3.某厂按合同规定须于每个季度末分别提供10,15,25,20台同一规格的柴油机.已知该厂各季度的生产能力及生产每台柴油机的成本如下表.如果生产出来的柴油机当季不交货,每台积压一个季度需储存、维护费用0.15万元.要求在完成合同的情况下,做出该厂全年费用最小的决策.,搞清“产地、销地”、“运价”,“产量、需求”,写出产销平衡表,未
15、知数如何设,设xij为第i季度生产的用于第j季度交货的柴油机数.,合同要求：,产量约束：,第i季度生产的用于第j季度交货的柴油机的实际成本cij=生产成本+储存维护费用,目标函数：,例:某玩具公司分别生产三种新型的玩具,每月可供应量分别为1000件,2000件,2000件，他们分别被送到甲乙丙三个百货商店销售,已知每月百货商店各类玩具预期销售量为1500件,由于经营原因,各百货商店销售不同玩具的盈利额不同,又知丙百货商店要求至少供应C玩具1000件,而拒绝进入A种玩具,求满足上述条件下使总盈利额为最大的供销分配方案.,C先满足丙1000件,已知某运输问题的产销平衡表,最优调运方案及单位运价表分
16、别如表所示,由于从产地2至销地B的道路因故暂时封闭,故需对调运方案进行修正,试用尽可能简单的方法重新找出最优调运方案.,10变为M,计算检验数进行调整,已知某运输问题的资料如下表所示,1、表中的发量、收量单位为：吨，运价单位为：元/吨 试求出最优运输方案.,练习：,2、如将A2的发量改为17，其它资料不变，试求最优调 运方案。,已知资料如下表所示，问如何供电能使总的输电费用为最小？,电力供需表,单位输电费用,作业：,(ui+vj),ij,-(ui+vj),=,cij,C=5200,运输问题习题,二、如下所示的运输问题中,如果某一产地有一个单位物资未运出,就将发生存储费用.假定三个产地单位物资存
17、储费用分别为2,2,1,请用最小元素法求初始方案,用位势法调整出最优方案并计算出最优方案的总费用.,三、某最小费用运输问题的调运方案如下(黑体字为运量):1.上述方案是否可作为表上作业法求解时的初始解?说明理由.2.如问题1的答案为是,请用用位势法进行检验并求出最优方案.,单位运价,四、某公司和供货商A、B、C签订了长期供货合同,按月为位于不同地区的三个下属工厂供应某种原料,三个供货商提供的原料品质基本相同,但由于所处的地理位置、人工成本等导致其实际供货成本有所不同.由于一次生产事故，导致最大的供货商A下个月的供货量无法全部满足.下个月供货商的供应量、工厂的需求量和供货商与工厂之间的供货成本如
18、下表所示.公司经紧急协商,在工厂1所在地筹措到100吨的货源,供货成本为23百元/吨;工厂2所在地货源充足,供货成本为25百元/吨.但由于运力紧张两处货源均无法调运到外地.鉴于此种情况公司决定要优先保证工厂1的全部需求,工厂3的需求至少要满足500吨.该公司面临的问题是应如何协调各供货商和工厂之间的供货关系,才能使总的供货成本最小.请为本问题建立适合于应用于表上作业法的产销平衡表.(不必计算),五、已知某极小化运输问题的有关数据如下表所示:表中黑体字为运量。要求：用位势法计算表中方案的检验数并进行进一步调整。,教育部门认为：划分入学区域界限的适当目标是使学生到学校的平均路程最短。在这个初步计划中，他们要确定为了实现这一目标每一个区域内至少有多少学生要安排到哪一所学校，同时要满足表中最后两行规定的约束条件。(1)建立该问题的运输问题约束条件(2)按运输问题的最小元素法给出一个较好的初始分配方案。,
