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

管理运筹学管理运筹学华国伟华国伟北京交通大学经管学院物流管理系北京交通大学经管学院物流管理系第三章第三章 运输问题运输问题 Transportation Problem本节内容提要本节内容提要3.1 运输问题的数学模运输问题的数学模 3.2 表上作业法表上作业法3.1 运输问题的数学模型运输问题的数学模型A1AiAm产地产量销地B1BjBn销量例：某运输问题的资料如下：例：某运输问题的资料如下：单位 销地 运价产地产量2910291342584257销量3846一、运输问题的数学模型一、运输问题的数学模型 数学模型的一般形式数学模型的一般形式 已知资料如下：已知资料如下：单 销 产 量产地产量销 量运运价价供需平衡供需平衡当产销平衡时，其模型如下：当产销平衡时，其模型如下：Ai的产品全部的产品全部供应出去供应出去Bj的需求全的需求全部得到满足部得到满足产销平衡的运输问题必定存最优解产销平衡的运输问题必定存最优解.当产大于销时，其模型是：当产大于销时，其模型是：当产小于销时，其模型是：当产小于销时，其模型是：mn平衡表、运价表和二为一：平衡表、运价表和二为一：约束条件或解可用产销平衡表表示约束条件或解可用产销平衡表表示:uivj无约束无约束（i=1,2,m;j=1,2,n)uivj设设u ui,v,vj为对偶变量，对偶问题模型为为对偶变量，对偶问题模型为m个个 n个个 特征：特征：1 1、平衡运输问题必有可行解，也、平衡运输问题必有可行解，也必有最优解；必有最优解；2 2、运输问题的基本可行解中应包、运输问题的基本可行解中应包括括 m+n1 个基变量。个基变量。.重复重复.，直到找到最优解为止。，直到找到最优解为止。步骤：步骤：.找出找出初始基本可行解初始基本可行解（初始调运方案，一（初始调运方案，一般般m+n-1m+n-1个数字格），用西北角法、最小元素法；个数字格），用西北角法、最小元素法；.求出各非基变量的检验数，判别是否达到求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用最优解。如果是停止计算，否则转入下一步，用位势法计算；位势法计算；.改进当前的基本可行解（确定换入、换改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；出变量），用闭合回路法调整；二、表上作业法二、表上作业法确定确定m+n-1个基变量个基变量空格空格3.2 求解运输问题的算法求解运输问题的算法:表上作业法表上作业法开开 始始求各非基变求各非基变量的检验数量的检验数是否达到最优解是否达到最优解结束结束确定换入变量确定换入变量与换出变量与换出变量新的基可行解新的基可行解求初始基可行解求初始基可行解NNY Y最小元素最小元素最小元素最小元素法，法，法，法，伏格尔法伏格尔法伏格尔法伏格尔法闭回路闭回路闭回路闭回路法，法，法，法，位势法位势法位势法位势法闭回路闭回路闭回路闭回路调整法调整法调整法调整法例一、某运输资料如下表所示：例一、某运输资料如下表所示：单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量36561 1、求初始方案：、求初始方案：初始基可行解的确定初始基可行解的确定西北角法西北角发也就是从运价表的西北角位置开始,依次安排m个产地和n个销地之间的运输业务,从而得到一个初始调运方案的方法.西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则.西北角法西北角法(或左上角法或左上角法):):此法是纯粹的人为的规定此法是纯粹的人为的规定,没有理论依据和实际背没有理论依据和实际背景景,但它易操作但它易操作,特别适合在计算机上编程计算特别适合在计算机上编程计算,因而受因而受欢迎欢迎.方法如下：方法如下：总的运费总的运费(33)(33)(411)(411)(29)(29)(22)(22)(310)(310)(65)(65)135135元元B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633 .初始基可行解的确定初始基可行解的确定-最小元素法：最小元素法：基本思想是就近供应，即从运价最小的地方开始供基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。应（调运），然后次小，直到最后供完为止。总的运输费用（总的运输费用（3131）（）（6464）（4343）（）（1212）（）（310310）（）（3535）8686元元分别计算各行、各列次小、最小运价的差值分别计算各行、各列次小、最小运价的差值,优先在优先在最大差值处进行供需搭配最大差值处进行供需搭配.差值差值=次小次小-最小最小 步骤：步骤：10 计算未划去行、列的差额计算未划去行、列的差额;20 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配进行供需分配;30 在未被划去的行、列重新计算差额在未被划去的行、列重新计算差额.(3)初始基可行解的确定初始基可行解的确定-最大差值法最大差值法(伏格尔法伏格尔法)Vogel 6 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656B1B2B3B4供量供量A13113107A219284A3741059销量销量3656列差值列差值2513行差值行差值 01 1 6 3 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3656B1B2B3B4行差值行差值A13113100A219281A3741052列差值列差值213 3 6 3 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3656B1B2B3B4行差值行差值A13113100A219281A374105列差值列差值212 5 1 2 6 3B1B2B3B4差值差值A13113107A219286A374105差值差值12 销销产产B1B2B3B4供量供量A17A24A3 39销量销量 3656以上方法得到的初始解为基可行解每次行(需求)或列(供应)达到饱和每次必划掉一行或一列得到的元素个数必为m+n-1个西北角法 最小元素法 最大差值法练习P97 3.1 3.2 ijij0 0（因为目标函数要求最小化）（因为目标函数要求最小化）表格中有调运量的地方为基变量表格中有调运量的地方为基变量,空格处为非基变空格处为非基变 量量.基变量的检验数基变量的检验数ijij0,非基变量的检验数非基变量的检验数ijij0.0.ij 0 表示运费增加表示运费增加.2 2、最优解的判别（检验数的求法）：、最优解的判别（检验数的求法）：检验数检验数非基变量增加一个非基变量增加一个单位目标值的变化单位目标值的变化（1）闭回路法）闭回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水平画水平(或垂直或垂直)直线直线,遇到填有运量的方格遇到填有运量的方格可转可转90,然后继续前进然后继续前进,直到到达出发直到到达出发的空格所形成的闭合回路的空格所形成的闭合回路.调运方案的任意空格存在唯一闭回路调运方案的任意空格存在唯一闭回路.销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656差差值值法法方方案案一、最优调运方案的判定一、最优调运方案的判定314 633最最小小元元素素法法方方案案+-+-x11为换入变量，为换入变量，x11：01，运费的变化为，运费的变化为3-1+2-3=1。这个变化就是。这个变化就是x11的检验数，故的检验数，故 11=1B1B2B3B4产量产量A17A24A39销量销量365631363124B1B2B3B4产量产量A17A24A39销量销量36563136312-14B1B2B3B4产量产量A17A24A39销量销量365631363121-14B1B2B3B4产量产量A17A24A39销量销量365631363121-1124B1B2B3B4产量产量A17A24A39销量销量365631363121-112104 检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。空格闭回路检验数(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)121-11012检验数还存在检验数还存在负数负数,原方案不是最优方案原方案不是最优方案.用闭回路求解检验数时,需要给每一个空格找一条闭回路.当产销点较多时,该方法较麻烦.ui,vj自由变量自由变量（2）位势法位势法标准型运输问题的对偶问题是：标准型运输问题的对偶问题是：XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数检验数对偶变量值等于对偶变量值等于原问题的检验数原问题的检验数松弛变量松弛变量基变量的检验数为零基变量的检验数为零(基变量基变量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出于计算简单考虑出于计算简单考虑)314 633位位势势法法 令令v1=0,由由c21=1=u2+v1，得得 u2=1 0 1 1 2 0 1 1 28-3 7位位势势表表2989-3-2检验数检验数 0 1 1 28-3 7检检验验数数表表121-11012 24=-10，当前方案，当前方案 不是最优方案。不是最优方案。1.以以最小负检验数最小负检验数为出发点寻找一条闭回路为出发点寻找一条闭回路.2.确定调整量确定调整量,调出格中调出格中最小最小的运量的运量.2.3 改进的方法改进的方法闭回路调整法闭回路调整法二、二、调运方案的调整调运方案的调整pqijj,i)(min =bj产小于销：产小于销：ai 产量产量二、转运问题二、转运问题出现下列问题：出现下列问题：1.产地与销地之间没有直达路线，货物由产地到销产地与销地之间没有直达路线，货物由产地到销地必须通过中转站转运；地必须通过中转站转运；2.某些产地可以输入货物，销地也可以输出货物，某些产地可以输入货物，销地也可以输出货物，3.产地与销地之间虽然有直达运输线，但直达运输产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。的费用（距离）比经过某些中转站的还要高。解法：解法：无转运问题。无转运问题。1.根据问题求出最大可能周转量根据问题求出最大可能周转量Q；2.纯转运点纯转运点产地：输出量产地：输出量Q；销地：输入量销地：输入量Q；输入输入=输出输出3.兼中转站的产地兼中转站的产地Ai=销地：输入量销地：输入量Q；产地：输出量产地：输出量Q+ai；4.兼中转站的销地兼中转站的销地Bj=销地：输入量销地：输入量bj+Q；产地：输出量产地：输出量Q；列出各产地的输出量和各销地的输入量及各产列出各产地的输出量和各销地的输入量及各产销地之间的运价表销地之间的运价表,用表上作业法求解用表上作业法求解.输出：产地；中转站输出：产地；中转站(纯纯/兼兼)输入：销地；中转站输入：销地；中转站(纯纯/兼兼)例例 某货物某货物,其产地其产地A1的产量为的产量为10单位单位,A2的产量为的产量为2单单位位,销地销地A3、A4、A5的销量分别为的销量分别为3单位、单位、1单位和单位和8单位单位,其中产地其中产地A2、销、销A4又可作为中转站又可作为中转站.同时同时,货物货物可通过纯中转站可通过纯中转站A6进行运输进行运输.各产地、销地及中转站各产地、销地及中转站之间的单位物资运价如表所示之间的单位物资运价如表所示,试求一个使总运费最试求一个使总运费最省的调运方案省的调运方案.销地销地产地产地A2A3A4A5A6A126312A2 03M24A4M2031A613270最大可能周转量最大可能周转量 Q=a1+a2=10+2=12A1 纯产地纯产地,输出量输出量10;A2产地兼中转站产地兼中转站,输出量输出量2+12=14,输入量输入量12;A3 纯销地纯销地,输入量输入量3;A4销地兼中转站销地兼中转站,输出量输出量12,输入量输入量1+12=13;A5纯销地纯销地,输入量输入量8;A6纯中转站纯中转站,输出量、输入量均为输出量、输入量均为12.根据以上情况列产销平衡表根据以上情况列产销平衡表.销地产地A2A3A4A5A6输出量A12631210A203M2414A4M203112A61327012输入量1231381248 销地产地A2A3A4A5A6输出量A118110A212214A41212A611112输入量1231381248不参加实际调运不参加实际调运3.4 应用举例应用举例搞清搞清“产地、销地产地、销地”、“运价运价”,“产量、需求产量、需求”,写出写出产销平衡产销平衡表表运输问题的要素运输问题的要素:未知数未知数如何设如何设虚设虚设产地与销地产地与销地;拆分拆分产地与销地产地与销地例例 3.某厂按合同规定须于每个季度末分别提供某厂按合同规定须于每个季度末分别提供10,15,25,20台同一规格的柴油机台同一规格的柴油机.已知该厂各季度已知该厂各季度的生产能力及生产每台柴油机的成本如下表的生产能力及生产每台柴油机的成本如下表.如果如果生产出来的柴油机当季不交货生产出来的柴油机当季不交货,每台积压一个季度每台积压一个季度需储存、维护费用需储存、维护费用0.15万元万元.要求在完成合同的情要求在完成合同的情况下况下,做出该厂全年费用最小的决策做出该厂全年费用最小的决策.季度季度生产能力生产能力单位成本单位成本IIIIIIIV2535301010.811.111.011.3搞清搞清“产地、销地产地、销地”、“运价运价”,“产量、需求产量、需求”,写出写出产销平产销平衡表衡表未知数未知数如何设如何设设设xij为第为第i季度生产的用于第季度生产的用于第j季度交货的柴油机数季度交货的柴油机数.合同要求：合同要求：产量约束：产量约束：第第i季度生产的用于第季度生产的用于第j季度交货的柴油机的实际成本季度交货的柴油机的实际成本cij=生产成本生产成本+储存维护费用储存维护费用ijIIIIIIIVIIIIIIIV10.810.9511.1011.1011.2511.0011.2511.4011.1511.30目标函数：目标函数：目标函数：目标函数：ijIIIIIIIV产量产量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.3025353010销量销量10152520ijIIIIIIIVD产量产量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.30000025353010销量销量1015252030 例:某玩具公司分别生产三种新型的玩具,每月可供应量分别为1000件,2000件,2000件，他们分别被送到甲乙丙三个百货商店销售,已知每月百货商店各类玩具预期销售量为1500件,由于经营原因,各百货商店销售不同玩具的盈利额不同,又知丙百货商店要求至少供应C玩具1000件,而拒绝进入A种玩具,求满足上述条件下使总盈利额为最大的供销分配方案.甲乙丙可供量ABC516124810-911100020002000C先满足丙1000件甲乙丙丁可供量ABC516124810-91100010002000100015001500500500甲乙丙丁可供量ABC11041286M7500010002000100015001500500500 已知某运输问题的产销平衡表,最优调运方案及单位运价表分别如表所示,由于从产地2至销地B的道路因故暂时封闭,故需对调运方案进行修正,试用尽可能简单的方法重新找出最优调运方案.ABCDE产量1233414513948销量35463ABCDE1231021201020510793010106410变为变为M,计算检验数进行调整计算检验数进行调整 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/吨吨 试求出最优运输方案试求出最优运输方案.练习：练习：2、如将、如将A2的发量改为的发量改为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。13A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费 85元元/吨吨 已知资料如下表所示，问如何供电能使总的输电费已知资料如下表所示，问如何供电能使总的输电费用为最小？用为最小？发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A110523A24312A35634单位输电费用单位输电费用作业：作业：B1B2B3B4ui A1105230A24-1-4-3-6A350-3-2-5vj 10523(ui+vj)B1B2B3B4ui A10000A20455A30666vj ij-(ui+vj)=cijB1B2B3B4A1200250100150A2200A3100C=5200运输问题习题二、如下所示的运输问题中二、如下所示的运输问题中,如果某一产地有一如果某一产地有一个单位物资未运出个单位物资未运出,就将发生存储费用就将发生存储费用.假定三个假定三个产地单位物资存储费用分别为产地单位物资存储费用分别为2,2,1,请用最小元请用最小元素法求初始方案素法求初始方案,用位势法调整出最优方案并计用位势法调整出最优方案并计算出最优方案的总费用算出最优方案的总费用.销销地地产产地地IIIIIIIV176550248830334520销销量量302040三、某最小费用运输问题的调运方案如下(黑体字为运量):1.上述方案是否可作为表上作业法求解时的初始解?说明理由.2.如问题1的答案为是,请用用位势法进行检验并求出最优方案.单单位位运价运价发发点点收点收点发发量量B1B2B3B4A124515545A222430130A3401542535275收收量量40502535四、某公司和供货商A、B、C签订了长期供货合同,按月为位于不同地区的三个下属工厂供应某种原料,三个供货商提供的原料品质基本相同,但由于所处的地理位置、人工成本等导致其实际供货成本有所不同.由于一次生产事故，导致最大的供货商A下个月的供货量无法全部满足.下个月供货商的供应量、工厂的需求量和供货商与工厂之间的供货成本如下表所示.公司经紧急协商,在工厂1所在地筹措到100吨的货源,供货成本为23百元/吨;工厂2所在地货源充足,供货成本为25百元/吨.但由于运力紧张两处货源均无法调运到外地.鉴于此种情况公司决定要优先保证工厂1的全部需求,工厂3的需求至少要满足500吨.该公司面临的问题是应如何协调各供货商和工厂之间的供货关系,才能使总的供货成本最小.请为本问题建立适合于应用于表上作业法的产销平衡表.(不必计算)工厂工厂供供货货成本成本（百元（百元/吨）吨）供供货货商商123供供货货量量（吨）（吨）A202119500B182220300C192021400需求量（吨）需求量（吨）400500700五、已知某极小化运输问题的有关数据如下表所示:表中黑体字为运量。要求：用位势法计算表中方案的检验数并进行进一步调整。教育部门认为：划分入学区域界限的适当目标是使学生到学校的平均路程最短。在这个初步计划中，他们要确定为了实现这一目标每一个区域内至少有多少学生要安排到哪一所学校，同时要满足表中最后两行规定的约束条件。(1)建立该问题的运输问题约束条件(2)按运输问题的最小元素法给出一个较好的初始分配方案。